发表于|更新于
|阅读量:
综合问题
1. 可达性问题。即判断从i到j是否存在一条路径。用BFS或DFS可解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| int vis[MaxSize] = {0};
bool Exist_Path_BFS(Graph G,int i,int j){ int k; int queue[MaxSize]; int front=0,rear=0; vis[i] = 1; queue[rear++] = i; while(front < rear){ k = queue[front++]; for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)){ if(vis[w] == 0){ if(w == j) return true; vis[w] = 1; queue[rear++] = w; } } } return false; }
|
2. 无向图连通分量个数
- 用DFS或BFS,时间复杂度为O(N2)
- 用并查集,时间复杂度为O(E)
并查集原理介绍
定义
1 2 3 4 5
| int S[MaxSize];
for(int i = 0;i < MaxSize;i++){ S[i] = i; }
|
查找:
1 2 3
| int Find(int x){ return S[x] == x?x:Find(S[x]); }
|
合并:
1 2 3 4 5 6 7
| void Union(int root1,int root2){ int a = Find(root1); int b = Find(root2); if(a == b) return ; S[a] = b; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| int GraphNums(ALGraph G){ int i,j; int num = 0; ArcNode * P; for(i = 1;i <= G.vexNum;i++){ P = G.vertices[i].first; while(P){ Union(i,P->adjVertex); P = p->NEXT; } }
for(j = 1;j <= G.vexNum;j++){ if(S[j] == j){ num++; } }
return num; }
|
3. 拓扑排序
- 用入度表进行拓扑(王道书上用的是这种方法)
- 用DFS进行拓扑(参考《算法导论》)
- 其他
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| int visited[MaxSize] = {0}; int d[MaxSize], f[MaxSize], topo[MaxSize], time = 0; int cnt = 0;
void MGDFSTraverse(Graph G){ for(int i=0;i < G.vexNum;i++){ if(!visited[i]){ DFS(G,i); } } }
void DFS(Graph G,int u){ visit(u); visited[u] = 1; time++; d[u] = time; for(w = FirstNeighbor(G,u);w >= 0;w = NextNeighbor(G,u,w)){ if(!visited[w]){ DFS(G,w); } } time++; f[u] = time; topo[cnt++] = u; }
void topological_sort(){ for(int i = cnt-1;i >= 0;i--){ printf("%d ",topo[i]); } }
|
4. Tarjan算法求割点、割边
tarjan算法不容易理解,一般来说,研究生入学考试中不会涉及该算法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| int timestamp = 0; int dfn[n], low[n], parent[n]; int visited[n] = {0};
void tarjan(int u){ int children = 0; dfn[u] = low[u] = timestamp++; visited[u] = 1; for(w = FirstNeighbor(u);w >= 0;w = NextNeighbor(w,u)){ if(!visited[w]){ children++; parent[w] = u; tarjan(w); low[u] = min(low[u],low[w]); if(parent[u] == -1 && children >= 2) else if(parent[u] != -1 && low[w] >= dfn[u]) }else if(u != parent[w]){ low[u] = min(low[u],dfn[w]); } } }
|
5. 图的离径、半径、直径、中心、边界
- 离径:顶点V与和它相距最远的顶点间的距离。
- 半径:所有顶点中最小的离径(可能不止一个点的最小离径都相同)
- 直径:所有顶点中最大的离径(可能不止一个点的最大离径都相同)
- 中心:具有最小离径的顶点组成的集合
- 边界:具有最大离径的顶点组成的集合
参考书籍
-
严蔚敏,吴伟民.数据结构:C语言版[M].北京:清华大学出版社.2007.
-
王道论坛.2019年数据结构考研复习指导[M].北京:电子工业出版社.2018.
-
李明哲,金俊,石端银. 图论及其算法[M]. 机械工业出版社.2010.
版权声明: 此文章版权归路双宁所有,转载请注明来源作者