第12讲 加权图及其应用1内容提要使用连接矩阵和优先队列来表示加权边设计加权图设计实现最小生成树Prim算法设计实现最小生成树Kruskal算法设计实现单源最短路径Dijkstra算法设计实现单源最短路径Floyd算法2加权图的表示3加权边的表示：边数组加权邻接矩阵优先邻接链表加权边的表示：边数组4int edges=0,1,2,0,3,8,1,0,2,1,2,7,1,3,3,2,1,7,2,3,4,2,4,5,3,0,8,3,1,3,3,2,4,3,4,6,4,2,5,4,3,6;带权图及其邻接矩阵带权图及其邻接矩阵 加权邻接矩阵6 优先邻接链表78GraphTestWeightedGraphAbstractGraphWeightedGraphTestWeightedGraph最小生成树最小生成树最小生成树的基本概念的基本概念 一个有一个有n个结点的连通图的个结点的连通图的生成树生成树是原图的极小连是原图的极小连通子图，它包含原图中的所有通子图，它包含原图中的所有n个结点，并且有保持图个结点，并且有保持图连通的最少的边。连通的最少的边。如果无向连通图是一个带权图，那么它的所有生如果无
