数据结构与算法 6. 图 2021-07-19 浏览量 1045 暂无评论 [TOC] ## 6.1 概述 邻接、关联、有向、无向、路径、环路 简单路径:路径中不含重复节点 欧拉环路(Eulerian tour):经过图中所有的边一次且恰好一次的路径构成的环路。 哈密尔顿环路(Hamiltonian tour):经过所有点一次且恰好一次的环路。 无向图的边数等于各定点度数之和的一半。 ## 6.2 邻接矩阵 adjacency matrix:点与点的关系,$R^{n×n}$ incidence matrix:点与边的关系,$R^{n×e}$ ### 节点实现 ```cpp typedef enum {UNDISCOVERED, DISCOVERED, VISITED} VStatus; // 这里用struct只是想省去严格的封装 template struct Vertex { Tv data; int inDegree, outDegree; VStatus status; int dTime, fTime; // 时间标签 int parent; // 在遍历树中的父节点 int priority; // 在遍历树中的优先级 Vertex(Tv const & d) : data(d), inDegree(0), outDegree(0), status(UNDISCOVERED), dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {} }; ``` ### 边实现 ```cpp typedef enum {UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD} EStatus; template struct Edge { Te data; int weight; EStatus status; Edge(Te const & d, int w) : data(d), weight(w), status(UNDETERMINED) {} }; ``` ### 邻接矩阵实现 ```cpp template class GraphMatrix : public Graph { private: Vector> V; Vector*>> E; public: GraphMatrix() {n = e = 0;} ~GraphMatrix() { for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) delete E[j][k]; } } ``` ### 顶点静态操作 ```cpp int nextNbr(int i, int j) { while ((-1 < j) && !exists(i, --j)); // 逆向顺序查找 return j; } int firstNbr(int i) { return nextNbr(i, n); } ``` ### 边操作 ```cpp bool exists(int i, int j) { return (0 <= i) && (i < n) && (0 <= j) && (j < n) && E[i][j] != NULL; } Te & edge(int i, int j) {return E[i][j]->data;} ``` 插入和删除只需要设置相应的邻接矩阵即可,并维护对应的信息。 ### 顶点动态操作 顶点的插入与删除,维护V[], E[], E[j] ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210718223938829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 综合评价 适合稠密图。 空间性能差。 平面图就稀疏,欧拉公式判断平面图$v-e+f-c=1$。0维:顶点数,1维:边数,2维:区域面片,+ 连通域 ## 6.3 广度优先搜索(BFS) 化繁为简,将图转化为支撑树(Spaning Tree)。等同于树的层次遍历。 遍历。 由指定节点出发,依次访问它的邻居,全部邻居访问完后再访问邻居的邻居。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210719104607637.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 单连通 ```cpp template void Graph::BFS(int v, int & clock) { Queue Q; status(v) = DISCOVERED; Q.enqueue(v); while (!Q.empty()) { int v = Q.dequeue(); dTime(v) = ++clock; for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) if (UNDISCOVERED == status(u)) { status(u) = DISCOVERED; Q.enqueue(u); status(v, u) = TREE; parent(u) = v; } else status(v, u) = CROSS; // 那(0, 1)和(1, 0)岂不是有两种状态了 status(v) = VISITED; } } ``` ### 多连通 ```cpp template void Graph::bfs(int s) { reset(); int clock = 0; int v = s; do if (UNDISCOVERED == status(v)) BFS(v, clock); while (s != (v = (++v % n))); } ``` ### 复杂度 本来是$O(n^2+e)$,但由于此处的for循环速度很快(一方面是特别基本的操作,另一方面是物理地址连续),所以第二个n可忽略,得到$O(n+e)$,也就是说至少要访问完每个节点和它的边。 ### 最短路径 BFS给出的顶点序列到起点s的距离,就是按照非降次单调排列的。 ## 6.4 深度优先搜索 过程: > 访问顶点s > 若s尚有未被访问的邻居,则任取其一u,递归执行DFS(u) > 否则,回溯 ### 单可达域 ```cpp template void Graph::DFS(int v, int & clock) { dTime = ++clock; status(v) = DISCOVERED; // 通过这个循环,可以实现回溯,访问祖先的下一个邻居 // 跳过父节点 for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) switch (status(u)) { case UNDISCOVERED: status(v, u) = TREE; parent(u) = v; DFS(u, clock); break; case DISCOVERED: status(v, u) = BACKWARD; break; default: // v < u,更早被发现,什么情况下会大于呢?回溯到祖先的邻居,且该邻居的邻居为visited status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS; break; status(v) = VISITED; fTime(v) = ++clock; } ``` ### 多可达域 有向图要更复杂一些。引入可达域的概念。 ```cpp template void Graph::dfs(int s) { reset(); int clock = 0; int v = s; do if (UNDISCOVERED == status(v)) DFS(v); while (s != (v = ++v % n))); } ``` 一个回边代表一个回路。 ### 嵌套引理 打的时间标签有何用呢? ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210719190103771.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 6.5 拓扑排序 任给有向图G,尝试将所有顶点拍成一个线性序列,使其次序与原图相容(每一个顶点都不会通过边指向前驱顶点)。 非有向无环图排不出。DAG:Directed Acyclic Graph ### 零入度算法 流程: > 先找零入度的点,找到了就去掉 > 再找下一个 挺麻烦,每次都要遍历得到零入度的点,且需要更新图,可能改变图的原结构。 ### 零出度算法 先知道最后要干嘛,再向前找干这个需要什么,抽象出来就是DFS,每次回溯时的点。 DGF各节点按fTime逆序排序 ## 6.6 双连通分量分解 无向图。 - 关节点:去除该点后,图中的连通域数量增加。 - 双连通图:无关节点的图 - 极大的双连通子图,称作双连通分量(Bi-Connected Components) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210719205439926.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) hca(v) = subtree(v)经后向边能抵达的最高祖先。 赞赏 微信支付 支付宝支付