无向图连通分量

边双连通分量

  • 定义：一个极大子图，去掉任意一条边，变成不连通分量
  • 缩点：树
    一条边只能属于一个边双连通分量

    点双连通分量

  • 定义：一个极大子图，去掉任意一个点，变成不连通分量
    缩点：

（区别）一个点可以属于多个点双连通分量

手动开栈模拟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
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
#include <stdlib.h>
#include <stdio.h>

#define N 4 //定义图中点个数

int a[N][N] = {{-1,1,1,-1},{1,-1,-1,1},{1,-1,-1,1},{-1,1,1,-1}}; //邻接矩阵，-1无边
int label[N] = {0}; //标记数组，0未标记

//定义栈及其方法
struct Stack
{
    int a[4]; //存入栈元素
    int top; //栈顶指针
};

void addStack(Stack *s, int data) //入栈
{
    s->top++;
    s->a[s->top] = data;
}

int delStack(Stack *s) //出栈
{
    return s->a[s->top--];
}

int getTop(Stack *s) //得到栈顶元素
{
    return s->a[s->top];
}

//使用栈的非递归DFS
void dfs(int start)
{
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->top = -1;
    printf("%d ", start);
    label[start] = 1;
    addStack(s, start);
    while(s->top != -1)
    {
        int tmp = getTop(s);
        int i;
        for(i=0; i<4; i++)
        {
            if(a[tmp][i] == 1 && label[i] == 0)
            {
                printf("%d ", i);
                label[i] = 1;
                addStack(s, i);
                break; //此处必须有break，否则构不成DFS
            }
        }
        if(i == 4)
            delStack(s);
    }
    free(s);
}

int main()
{
    dfs(0);
    return 0;
}