图的存储与Dijkstra算法求最短路径课件.ppt

《图的存储与Dijkstra算法求最短路径课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的存储与Dijkstra算法求最短路径什么是图图的分类有向图带权有向图无权有向图无向图带权无向图有权无向图图的表示方法邻接矩阵邻接表前向星图的邻接矩阵表示法对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。无向无权图的邻接矩阵表示1若(vi,vj)E，即vi,vj邻接0若(vi,vj)E，即vi,vj不邻接A[i][j]=(a)无向图abcd(b)顶点数组v

2、exsabcd0111101111011110(c)邻接矩阵无向带权图的邻接矩阵表示(a)带权无向图(b)顶点数组(c)邻接矩阵354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij若(vi,vj)E，即vi,vj邻接，权值为wij∞若(vi,vj)E，即vi,vj不邻接时A[i][j]=有向无权图的邻接矩阵(a)有向图acbde(b)顶点数组vexsabcde(c)邻接矩阵0110100000000111100000010有向带权图的邻接矩阵(b)顶点数组vexsabcde(c)邻接矩阵∞62∞∞∞∞∞∞3∞3

3、∞1∞∞4∞∞5∞∞∞∞∞(a)带权有向图354126abcde3图的邻接表表示法链表中的结点称为表结点，每个结点由三个域组成，如图7-9(a)所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，链域(nextarc)指向下一个与顶点Vi邻接的表结点，数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。每个链表设一个表头结点(称为顶点结点)，由两个域组成，如图7-9(b)所示。链域(firstarc)指向链表中的第一个结点，数据域(data)存储顶点名或其他信息。adjvexi

4、nfonextarc表结点：datafirstarc顶点结点：图7-9邻接链表结点结构无向无权图的邻接表表示法v1v2v3v4v501234MAX_VEX-1v1v2v3v4┇┇v5213⋀02⋀0314⋀204⋀23⋀⋀表示空指针前向星1243数组下标：12345678910110010302648213141424357910next：to：head：依次存储的边为：(1，2)、(2，1)、(1，3)、(3，1)、(1，4)、(4，1)(2，4)、(4，2)、(3，4)、(4，3)图的遍历深度优先遍历(DFS)广度优先遍历(BFS)图的最小生成树如果连通图

5、是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。最小生成树(MinimumSpanningTree)：带权连通图中代价最小的生成树称为最小生成树。求最小生成树的算法普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法v1v3v2v4v54857121136(a)带权无向图如图所示v2v45(b)选择与v2相邻的边最小的顶点(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45普里姆(Prim)算法求最小生成树的过程克鲁斯卡尔(Kruskal)算法求最小生成树的过程v1v3v2v4v54857121

6、136(a)(b)选择所有的边中权值最小的边3v5v4v36(e)v14v53v2v45(c)v143v5v4(d)v25v143v5v4求最短路径求单源最短路径：Dijkstra（迪杰斯特拉）算法，时间复杂度O(n2)求全局最短路径：Floyd算法，时间复杂度O(n3)使用者两种算法的条件：要求必须是无环图Dijkstra算法（求顶点A到其他顶点的最短距离）算法思想如下：初始化源点A到其他顶点的距离，若其他顶点与源点A无直接相连的边，则认为源点A到该顶点的距离为无穷大（程序中使用int或longlong的最大值表示无穷大）；选择当前距离源点A最近的顶点X（注

7、意：顶点X必须未被选择过）；以X点为参照，更新源点A到其他未被选择过的点M的距离若A->X->M小于A->M距离，则使用新距离替换原距离；若A->X->M大于等于A->M距离，则保持原距离不变；重复步骤2、3，直到选取完所有的点为止。求解过程：初始化源点A到B、C、D、E、F、G、H、I的路径长度从B、C、D、E、F、G、H、I中选择到源点A距离最小的顶点，该顶点为B以B为参照更新源点A到C、D、E、F、G、H、I的路径长度如果新路径长度小于原长度，则用新的长度作为A到该点的路径长度基于新的路径长度，重复步骤2、3。选择距离A点最近且未被选择过的点，直到选取完

8、所有点Dijkstra算法（求A到其他