数据结构、算法与应用-C++描述12.ppt

* * 若从顶点v 开始搜索(宽度或深度优先)且到达顶点w 时终止搜索，则可以找到一条从顶点v 到达顶点w 的路径。 要实际构造这条路径，需要记住从一个顶点到下一个顶点的边。 寻找路径 * * bool Network::FindPath (int v, int w, int length, int path[]) {// 寻找一条从v 到w的路径, 返回路径的长度，并将路径存入数组path[ 0 : l e n g t h ] / /如果不存在路径，则返回false / /路径中的第一个顶点总是v path[0] = v; length = 0; // 当前路径的长度 if (v == w) return true; / /为路径的递归搜索进行初始化 int n = Vertices( ) ; InitializePos(); // 遍历器 在图中寻找一个路径 * * int *reach = new int [n+1]; for (int i = 1; i = n; i++) reach[i] = 0; bool x = findPath(v, w, length, path, reach); DeactivatePos( ) ; delete [] reach; return x; } 在图中寻找一个路径 * * bool Network::findPath(int v, int w, int length, int path[], int reach[]) {// 实际搜索v到w的路径，其中v != w. // 按深度优先方式搜索一条到达w的路径 reach[v] = 1; int u = Begin(v); while (u) { if (!reach[u]) { length++; path[length] = u; // 将u 加入p a t h if (u == w) return true; if (findPath(u, w, length, path, reach)) return true; // 不存在从u 到w的路径 length--; //删除u } u = NextVertex(v) ; } return false; } 在图中寻找一个路径 * * 通过从任意顶点开始执行D F S或B F S，并且检验所有顶点是否被标记为已到达顶点，可以判断一个无向图G是否连通。 连通图及其构件 * * class Undirected : virtual public Network { public: bool Connected(); } ; 确定无向图是否连通 * * bool Undirected::Connected() {// 当且仅当图是连通的，则返回true int n = Ve r t i c e s ( ) ; // 置所有顶点为未到达顶点 int *reach = new int [n+1]; for (int i = 1; i = n; i++) reach[i] = 0; // 对从顶点1出发可到达的顶点进行标记 DFS(1, reach, 1); // 检查是否所有顶点都已经被标记 for (int i = 1; i = n; i++) if (!reach[i]) return false; return true; } 确定无向图是否连通 * * 从顶点i 可到达的顶点的集合C与连接C中顶点的边称为连通构件(connected component)。 在构件标识问题( component-labeling problem)中，对图中的顶点进行标识，当且仅当2个顶点属于同一构件时，分配给它们相同的标号。 构件 * * 可以通过反复调用D F S或B F S算法来标识构件。从每一个尚未标识的顶点开始进行搜索，并用新的标号标识新到达的顶点。 构件 * * 构件标识 * * 在一个n 顶点的连通无向图中，如果从任一个顶点开始进行BFS，所有顶点都将被加上标记。 由于所得到的边的集合中包含一条从v 到图中其他每个顶点的路径，因此它构成了一个连通子图，该子图即为G的生成树。 生成树 * * 宽度优先生成树:按B F S所得到的生成树 深度优先生成树:按D F S所得到的生成树 生成树 * * 宽度优先生成树 * * 深度优先生成树 {(1,3),(3,5),(5,2),(5,8),(8,7),(7,4),(4,6)} * * 图的基本概念 图的存储 图的遍历 路径、生成树 第十二章 总结 * * 加权有向图和无向图的链表节点中有一个权值域，而无权有向图和无向图中则没有。 分析 * * templateclass T class Adjacen