图的广度优先搜索#

算法描述#

找到一个未被访问过的结点 $v_0$ ，并访问
依次访问 $v_0$ 每一个未被访问过的相邻节点，并对每个符合条件的相邻结点重复2，直到所有已被访问过的结点的所有相邻结点都被访问到
若还有未被访问过的结点，重复1直到所有结点都被访问

设计思维#

先给所有结点编号，再创建一个相应大小的数组来存储每个结点的访问信息，数组的索引就是对应结点的编号，当结点未被访问时对应的值为1，当访问结点时将对应值置为0
根据访问顺序，要当所有距离 $v_0$ 近的结点都被访问完时才访问更远的结点，所有可以用队列来获取下一个需要访问的结点。每当访问完当前结点，就把该节点所有未被访问过的相邻结点入队列，并获取队列访问队列中的下一个结点
图可以用邻接矩阵来存储，方便取相邻结点

算法实现#

1
// 图的广度优先遍历
2
/*
3
vers：结点数组
4
len：结点个数
5
*/
6
void graph_list_BFS_queue(VertexNode** vers, int len, char* pattern)
7
{
8
    int vs_find[len]; // 记录结点是否被访问过
9
    VertexNode** vs_queue = (VertexNode** )malloc(sizeof(VertexNode* ) * len); // 用来实现队列
10

11
    for(int i = 0; i < len; i ++)
12
    {
13
        vs_find[i] = 1;
14
        vs_queue[i] = NULL;
15
    }
16

17
    int f=0,r=0;// 循环队列的头和尾指针
18
    VertexNode* current = NULL;
19

20
    while(1)
21
    {
22
        if(current == NULL)
23
        {
24
            for(int i = 0; i < len; i ++)
25
            {
26
                if(vs_find[i]) // 找到一个未被访问的结点并访问
27
                {
28
                    current = vers[i];
29
                    printf(pattern, current->value); // 访问当前结点
30
                    vs_find[i] = 0;
31
                    break;
32
                }
33
            }
34

35
            if(current == NULL) return; // 没有未被访问过的结点
36
        }
37

38
        ArcNode* arc =NULL;
39
        while(current)
40
        {
41
            arc = current->firstarc;
42
            while(arc) // 访问所有未被访问的相邻结点，并入队列
43
            {
44
                if(vs_find[arc->adjvex])
45
                {
46
                    vs_queue[r] = vers[arc->adjvex];
47
                    r = (r+1)%len;
48
                    vs_find[arc->adjvex] = 0;
49
                    printf(pattern, vers[arc->adjvex]->value);
50

51
                }
52
                arc = arc->nextarc;
53
            }
54

55
            if(f==r) // 队列为空，所有当前连通分量的结点都访问完了
56
            {
57
                current = NULL;
58
            }
59
            else
60
            {
61
                // 取出下一个需要访问的结点
62
                current = vs_queue[f];
63
                f = (f+1)%len;
64
            }
65
        }
66
    }
67

68
}

运算结果#

测试代码

1
int main()
2
{
3
    int arr[18] = {0,1,1,0,2,1,0,3,1,1,2,1,2,3,1,2,4,1};
4
    VertexNode** vers = graph_list_VerArr(5);
5
    graph_list_createAdjacencyMatrixByArrWithWeight(vers, arr, 18, 0);
6
    printf("邻接矩阵如下:\n");
7
    graph_list_print(vers, 5, "%d号结点 :", "-> %d");
8

9
    printf("\n广度优先搜索如下:\n");
10
    graph_list_BFS_queue(vers, 5, "%d ");
11
    return 0;
12
}

运算结果

原文链接：CSDN