图的深度优先搜索#

算法描述#

找一个未被访问过的结点 $v_0$ ，并访问它
找到该节点一个未被访问过的相邻结点 $v_1$ ，并访问 $v_1$ ，再找 $v_1$ 未被访问过的相邻结点。
重复2，直到某个结点 $v_x$ 没有未被访问过的相邻结点，这时退回上一个访问的结点再重复2，直到访问完 $v_0$ 的所有相邻结点
若此时仍有未被访问过的结点，重复1

设计思维#

可以给每个结点一个序号，然后创建一个相应长度的数组，初始化为全1数组，该数组索引代表结点序号，内容表示结点是否被访问过。若访问过则赋值为0。
为了方便找到上一个访问过的结点，可以使用栈来记录访问次序。
图可以用邻接表表示。邻接表可以比邻接矩阵更快速地找到相邻的结点。

算法实现——用栈#

1
// 邻接表深度优先搜索
2
/*
3
vers：结点数组
4
len：结点个数
5
*/
6
void graph_list_DFS_stack(VertexNode** vers, int len, char* pattern)
7
{
8
    int vs_find[len]; // 标记某个节点是否已经被访问
9
    VertexNode** vs_stack = (VertexNode** )malloc(sizeof(VertexNode*) * len); // 用来当栈使用
10

11
    // 初始化矩阵
12
    for(int i = 0; i < len; i++)
13
    {
14
        vs_find[i] = 1;
15
    }
16

17
    int index = -1;
18
    VertexNode* current = NULL;
19
    ArcNode* arc = NULL;
20

21
    while(1)
22
    {
23
        if(current == NULL) // 如果当前节点为空，说明已经访问完一个连通分量
24
        {
25
            for(int i = 0; i < len; i ++)
26
            {
27
                if(vs_find[i])
28
                {
29
                    current = vers[i];
30
                    vs_stack[++index] = current;
31
                    printf(pattern, i); // 访问当前节点
32
                    vs_find[i] = 0; // 标记为已访问
33
                    break;
34
                }
35
            }
36

37
            if(current == NULL) return; // 所有结点都被访问
38
        }
39

40
        arc = current->firstarc;
41
        while(arc)
42
        {
43
            if(vs_find[arc->adjvex]) // 有未被访问的邻接节点
44
            {
45
                current = vers[arc->adjvex];
46
                vs_stack[++index] = current;
47
                printf(pattern, arc->adjvex); // 访问第一个未被访问的相邻节点
48
                vs_find[arc->adjvex] = 0;
49
                break;
50
            }
51
            arc = arc->nextarc;
52
        }
53

54
        /*
55
        如果所有当前节点所有相邻点都被访问过，
56
        且栈中还有节点
57
        返回最近一次访问的节点
58
        */
59
        if(arc == NULL)
60
        {
61
            if(index >= 0)
62
            {
63
                current = vs_stack[index--];
64
            }
65
            else
66
                current=NULL;
67
        }
68
    }

运算结果#

测试代码

1
int main()
2
{
3
    int arr[15] = {0,2,1,0,3,1,0,4,1,3,1,1};
4
    VertexNode** vers = graph_list_VerArr(5);
5
    graph_list_createAdjacencyMatrixByArrWithWeight(vers, arr, 12, 1);
6
    printf("邻接矩阵如下:\n");
7
    graph_list_print(vers, 5, "%d号结点 :", "-> %d");
8
    printf("\n深度优先搜索如下:\n");
9
    graph_list_DFS_stack(vers, 5, "%d ");
10
    return 0;
11
}

运行结果

原文链接：CSDN