第十三章 图.pptVIP

第十三章 图 1、图的基本概念 2、图的存储结构 3、图的遍历与连通性 4、拓扑排序 5、最短路径 6、最小生成树 1、图的基本概念 图的定义与例 图、顶点、边、关联、邻接、顶点的度、有向图、无向图。 有向图与无向图 无向图与例 有向图与例 2、图的存储结构 集合表示 template int max_set struct Set { bool is_element[ max_set ]； }； 有向图的表示(邻接集合表示) template int max_size class Digraph { int count； Setmax_size neighbors[ max_size ]； }； // neighbors[ v ]表示顶点v的邻接点集合 有向图的表示(邻接矩阵表示) template int max_size class Digraph { int count； bool adjacency[ max_size ] [ max_size ]； }； 图的存储结构的实现 多重链表结构 Class Vertex{ Class Edge { Edge *first_edge; Vertex *end_point; Vertex *next_vertex; Edge *next_edge; }; }; 图的存储结构 邻接表结构 可以是连续存储结构，与邻接矩阵方法区别。 可以链表结构。具体地说是一维数组和一组单链表的组合。 3、图的遍历及其应用 图的遍历与树的遍历的区别： ⑴进行遍历时可能会遇到已遍历过的顶点；⑵因不连续有多个起点。 深度优先遍历（Depth-First traversal） DFS在访问图中某一个起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问的顶点w2；然后再从w2出发。进行类似的访问，如此进行下去，直到到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，即退到在u之前刚访问过的顶点，判断其是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从这个顶点出发进行与前述类似的访问；如果没有，就再退一步进行有哪些信誉好的足球投注网站。重复上述过程，直到图中所有顶点都被访问过为止。 template int max_size void Digraph max_size ∷depth_first(void(*visit)(Vertex )) const { bool visited [max_size]； Vertex v； for (all v in G ) visited[v] = false； // 访问数组初始化 for (all v in G ) if ( !visited[v] ) traverse (v, visited, visit )； } 深度优先遍历 template int max_size void Digraphmax_size ::traverse (Vertex v, bool visited [ ], void (*visit)(vertex )) const /* Pre: v is a vertex of the Digraph. Post: The depth-first traversal, using function *visit, has been completed for v and for all vertices that can be reached from v. Uses: traverse recursively. */ { Vertex w； visited [v] = true； // 对v加被访问的标记 (*visit)(v)； for (all w adjacent to v) //