数据结构D.S.期终复习幻灯片.ppt

第9章：图 1.无向图、有向图的有关概念 2.图的机内存储 邻接矩阵 邻接表 3.图的若干算法 1) 图的遍历----DFS BFS 2) 最小代价生成树---Prime算法 Kuscal算法 3) 最短路径-----Dijkstra算法 Floyed算法 4) 活动网络----AOV——拓扑排序 AOE——关键路径 4. 例1, 例2 第9章：图 2.图的机内存储 邻接矩阵 邻接表 Representation of graphs and digraphs 1.Adjacency Matrix G=(V,E), V={V1,V2,……,Vn} then the adjacency matrix of graph G: A(i,j)= 1 if i,j,j,i?E or (i,j)?E 0 otherwise Representation of graphs and digraphs For example: graph V1 V2 V3 V4 A(i,j)= 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1)Adjacency matrix of graph is a symmetric matrix 2) ?A(i,j)= ?A(j,i)=di (degree of vertex i) n j=1 n j=1 Representation of graphs and digraphs Digraph V1 V2 V5 V4 V3 A(i,j)= 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 ?A(i,j)= diout ?A(j,i)=diin j=1 n n j=1 Representation of graphs and digraphs Representation of networks, replace 1 with weights, others with ∞ W(i,j) if i!=j and i,j,j,i?E or(i,j)?E ∞ otherwise A(i,j)= Representation of graphs and digraphs For example: 除了邻接矩阵外,还要顶点信息表. 3 4 1 2 8 6 2 3 1 4 9 5 A(i,j)= ∞ 1 ∞ 4 ∞ ∞ 9 2 3 5 ∞ 8 ∞ ∞ 6 ∞ Representation of graphs and digraphs 2. Linked-adjacency Lists reduce the storage requirement if the number of edges in the graph is small. V1 V3 V2 V4 4 3 0 2 4 3 0 1 1 2 0 1 2 0 1 2 3 4 h dest link Representation of graphs and digraphs Digraph: V1 V2 V3 11 3 4 6 2 2 4 3 11 0 3 2 0 1 6 1 3 0 1 2 3 h dest cost link 2 6 3 3 0 2 2 0 1 4 0 1 11 1 2 3 h data adj Node Table: dest cost link 第9章：图 3.图的若干算法 1) 图的遍历----DFS BFS 以有向图为例: v1 v2 v6