综合问题

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;
}
//若是要求打印路径,新增个path数组用来存路径信息,新增变量d用来表示路径长度
//新增flag用来表示是否存在路径。最后判断flag,若存在,打印path即可。

2. 无向图连通分量个数

  1. 用DFS或BFS,时间复杂度为O(N2)O(N^2)
  2. 用并查集,时间复杂度为O(E)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. 拓扑排序

  1. 用入度表进行拓扑(王道书上用的是这种方法)
  2. 用DFS进行拓扑(参考《算法导论》)
  3. 其他
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
//用DFS进行拓扑
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)
//u为割点
else if(parent[u] != -1 && low[w] >= dfn[u])
//u为割点
}else if(u != parent[w]){
low[u] = min(low[u],dfn[w]);
}
}
}

5. 图的离径、半径、直径、中心、边界

  • 离径:顶点V与和它相距最远的顶点间的距离。
  • 半径:所有顶点中最小的离径(可能不止一个点的最小离径都相同)
  • 直径:所有顶点中最大的离径(可能不止一个点的最大离径都相同)
  • 中心:具有最小离径的顶点组成的集合
  • 边界:具有最大离径的顶点组成的集合

参考书籍


  1. 严蔚敏,吴伟民.数据结构:C语言版[M].北京:清华大学出版社.2007.

  2. 王道论坛.2019年数据结构考研复习指导[M].北京:电子工业出版社.2018.

  3. 李明哲,金俊,石端银. 图论及其算法[M]. 机械工业出版社.2010.