连通图与连通分量
- 连通图：无向图中，如果顶点$V_1$到$V_j$都有路径，则称$V_i$和$V_j$是连通的。如果图中任何两个顶点都是连通的，则称G为连通图。
- 连通分量：无向图G的极大连通子图称为G的连通分量。极大连通子图的意思是：该子图是G连通子图，如果再加一个顶点，该子图不连通。
- 对于连通图，则其连通分量就是它自己，对于非连通图，则有两个以上连通分量。
强连通图和强连通分量
- 强连通图：有向图中，如果任何两个顶点$V_1$到$V_j$都有路径，且$V_j$到$V_i$也有路径。则称G为强连通图。
- 强连通分量：有向图G的极大强连通子图称为G的强连通分量。极大连通子图的意思是：该子图是G的强连通子图，如果再加入一个顶点，该子图不再是强连通的。
(a)是强连通图，(b)不是强连通图，(c)是(b)的强连通分量
无向图的桥与割点
如图，去掉边$(5,8)$后图分裂成两个互不连通的子图，边$(5,8)$即为图G的桥。同样边$(5,7)$也为图的桥。
如果去掉无向连通图G中的一条边e，G分裂为两个不连通的子图，那么e为G的桥或割边。 如图5号节点即为图G的割点。
如果去掉无向图G中的一个点v以及v关联的所有边，G分裂成两个或两个以上不相连的子图，那么v为G的割点
注意：删除边时，只把该边删除，不删除边关联的点，而删除点时，要删除点以及相关联的所有边。
割点与桥的关系：
- 有割点不一定有桥，有桥一定存在割点
- 桥一定是割点依附的边
无向图的双连通分量
如果无向图中不存在桥，则称它为边双连通图，边连通图中，任意两个点，存在两条或以上路径，且路径上的边互不重复。
如果无向图中不存在割点，则称它为点双连通图，点连通图中，如果顶点数大于2,则任意两点间，存在两条或以上路径，且路径上的点互不重复。
无向图的极大边双连通子图成为边双连通分量，记为$e-DCC$。
无向图的极大边点连通子图成为边点连通分量，记为$v-DCC$。
双连通分量的缩点
把每一个边双连通分量$e-DCC$看作一个点，把桥看作两个缩点的无向边，得到一个树，这种方法称为$e-DCC$缩点。
如图，图中有两个桥，5-7,5-8,每个桥的边保留，桥两端的边连通分量缩成一个点，这样生成一个树。
注意：边连通分量就是删除桥之后留下的连通块，但点连通分量并不是删除割点后留下的连通块。
把每个点连通分量$v-DCC$看作一个点，把割点看成一个点，每个割点向包含它$v-DCC$连接一条边，得到一个树，这种方法称$v-DCC$缩点。
例如图G中有两个割点5、8，前三个点双连通粉来嗯都包含5,因此，5向他们引一条边，后2个点双连通分量都包含8，因此8向他们引一条边。
Tarjan算法
时间戳：dfn[n]表示u结点深度优先遍历的序号。
追溯点：low[u]表示u结点或u结点或u的子孙能通过非父子边追溯到dfn最小的结点序号。即回到最早的过去。
例如，在深度优先搜索中，每个点的时间戳和追溯点求解过程如下：
初始化时，dfn[u]=low[u]，如果该结点的邻接点未被访问，则一直深度优先遍历，1-2-3-5-6-4，此时4的邻接点1已被访问，且1不是被4的父节点，4的父节点是6（深度优先搜索树上的父节点）。那么4号结点能回到最早的过去是1号结点（dfn=1），因此low[4]=min(low[4],dfn[1])=1。返回时，更新路径上所有祖先结点的low值，因为子孙能回到追溯点，其祖先也能回到
无向图的桥
桥判定法则：
无向边$(x,y)$是桥，当且仅当搜索树上存在x的一个子节点y，满足：$low[y]>dfn[x]$
就是说，孩子的low值比自己的dfn值大，则该节点到这个孩子的边为桥。
如图，$(5,7)$，5的子节点7,满足$low[7]>dfn[5]$，则该边为桥。
无向图的割点
割点判定法则：
若x不是根节点，则x是割点，当且仅当搜索树上存在x的一个子节点y，满足$low[y]>=dfn[x]$
若x是根节点，则x是割点，当且仅当搜索树上存在两个子节点，满则上述条件。
就是说，如果不是根，孩子的low值大于等于自己的dfn值，该节点就是割点。如果是根，至少需要两个孩子满足条件。
如图，5的子节点7,满足$low[7]>dfn[5]$，则5为割点。
有向图的强连通分量
算法步骤：
深度优先遍历结点，第一次访问x时，将x入栈，且$dfn[x]=low[x]=++num$
遍历x所有的邻接点y
若y没有被访问，则递归访问y，返回时更新$low[x]=min(low[x], low[y])$
若y已经被访问，且在栈中，则令$low[x]=min(low[x], dfn[y])$
- x回溯之前，判断如果$low[x]=dfn(x)$，则栈中不断弹出结点，知道x出栈停止弹出的节点就是一个连通分量。
输入顺序不同，输出的强连通分量顺序也不同，但是分量中的结点是一样的
实现
Tarjan求桥
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <stdio.h>
#include <string.h>
#define MAXNUM 1000
int head[MAXNUM], cnt;
typedef struct Edge {
int to;
int next;
} Edge;
Edge e[MAXNUM << 1];
int low[MAXNUM], dfn[MAXNUM], num;
void init() {
memset(head, 0, sizeof(head));
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
cnt = num = 0;
}
void add(int u, int v) {
cnt ++;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
for (int i = 0; i < 10; ++i) {
printf("head:%d\n", head[i]);
}
printf("\n");
}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++num;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(v == fa) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = low[u] < low[v] ? low[u] : low[v];
if(low[v] > dfn[u]) printf("%d-%d是桥\n", u, v);
} else low[u] = low[u] < dfn[v] ? low[u] : dfn[v];
}
}
int main(int argc, char *argv[])
{
init();
add(1, 2);
add(2, 3);
add(3, 5);
add(5, 7);
add(5, 6);
add(6, 4);
add(4, 1);
for(int i = 1; i <= 7; i ++) {
if(!dfn[i]) tarjan(1, 0);
}
return 0;
}
|
Tarjan求割点
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <stdio.h>
#include <string.h>
#define MAXNUM 1000
int head[MAXNUM], cnt;
typedef struct Edge {
int to;
int next;
} Edge;
Edge e[MAXNUM << 1];
int low[MAXNUM], dfn[MAXNUM], num;
int root;
void init() {
memset(head, 0, sizeof(head));
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
num = cnt = 0;
}
void addEdge(int u, int v) {
cnt ++;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++num;
int chidCount = 0;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(v == fa) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = low[u] < low[v] ? low[u] : low[v];
if(dfn[u] < low[v]) {
chidCount ++;
if(u != root || chidCount > 1) printf("%d 是割点\n", u);
}
} else low[u] = low[u] > dfn[v] ? dfn[v] : low[u];
}
}
int main(int argc, char *argv[])
{
init();
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 5);
addEdge(5, 7);
addEdge(5, 6);
addEdge(6, 4);
addEdge(4, 1);
for(int i = 0; i <= 7; i ++) {
if(!dfn[i]) {
root = i;
tarjan(i, 0);
}
}
return 0;
}
|
Tarjan求强连通图
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNUM 1000
int head[MAXNUM], cnt;
typedef struct Edge {
int to;
int next;
} Edge;
int low[MAXNUM], dfn[MAXNUM], num;
typedef struct Stack {
int val;
struct Stack *next;
} *Stack;
Stack initialStack() {
Stack s = (Stack) malloc(sizeof(Stack));
if(!s) return NULL;
s->next = NULL;
return s;
}
int isEmpty(Stack s) {
return s->next == NULL;
}
void push(Stack s, int val) {
Stack elem = (Stack) malloc(sizeof(Stack));
elem->val = val;
elem->next = s->next;
s->next = elem;
}
void pop(Stack s) {
if(!isEmpty(s)) {
Stack temp = s->next;
s->next = temp->next;
free(temp);
}
}
int top(Stack s) {
if(!isEmpty(s)) {
return s->next->val;
}
printf("stack is empty.\n");
return -1;
}
Edge e[MAXNUM << 1];
Stack s;
int ins[MAXNUM];
void init() {
memset(head, 0, sizeof(head));
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
memset(ins, 0, sizeof(ins));
num = cnt = 0;
s = initialStack();
}
void addEdge(int u, int v) {
cnt ++;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
void tarjan(int u) {
low[u] = dfn[u] = ++num;
ins[u] = 1;
push(s, u);
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = low[u] < low[v] ? low[u] : low[v];
} else if(ins[v]) {
low[u] = low[u] < dfn[v] ? low[u] : dfn[v];
}
}
if(low[u] == dfn[u]) {
int v;
printf("连通分量:");
do {
v = top(s);
pop(s);
printf("%d ", v);
ins[v] = 0;
} while(v != u);
printf("\n");
}
}
int main(int argc, char *argv[])
{
init();
addEdge(1, 3);
addEdge(1, 2);
addEdge(3, 5);
addEdge(3, 4);
addEdge(3, 2);
addEdge(4, 5);
addEdge(4, 1);
addEdge(5, 1);
for(int i = 1; i <= 5; i ++) {
if(!dfn[i]) tarjan(i);
}
return 0;
}
|
