【算法】图的广度优先算法

你的名字 2022-06-13 03:23 153阅读 0赞

图就是由一些小圆点（称为顶点）和连接这些小圆点的直线（称为变）组成的。

例如，下面的图：

![Center][]

上图就是由五个顶点（编号为1,2,3,4,5）和5条边（1-2,1-3,1-5,2-4,3-5）组成。

广度优先算法的主要思想是：首先以一个未被访问过的顶点，访问其所有相邻的顶点

然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。

代码的实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<stdio.h>
    #include<stdlib.h>
    
    int main()
    {
    	int i, j, n, m, a, b, cur, arr1[101] = { 0 }, arr2[101][101];
    	int que[10001], head;
    	int tail = 0;
    	printf("请输入矩阵的行和列->\n");
    	scanf("%d %d", &n, &m);
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= n; j++)
    		{
    			if (i == j)
    			{
    				arr2[i][j] = 0;
    			}
    			else
    			{
    				arr2[i][j] = 99999999;
    			}
    		}
    	}
    	for (i = 1; i <= m; i++)
    	{
    		scanf("%d %d", &a, &b);
    		arr2[a][b] = 1;
    		arr2[b][a] = 1;
    	}
    	head = 1;
    	tail = 1;
    
    	que[tail] = 1;
    	tail++;
    	arr1[1] = 1;
    
    	while (head < tail)
    	{
    		cur = que[head];
    		for (i = 1; i <= n; i++)
    		{
    			if (arr2[cur][i] == 1 && arr1[i] == 0)
    			{
    				que[tail] = i;
    				tail++;
    				arr1[i] = 1;
    			}
    			if (tail > n)
    			{
    				break;
    			}
    		}
    		head++;
    	}
    	printf("进行广度优先搜索遍历之后的结果为->\n");
    	for (i = 1; i < tail; i++)
    	{
    		printf("%d ", que[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

运行的结果：

![Center 1][]

![Center 2][]

[Center]: /images/20220613/4fa7ffd343a24f7897aba6d43d88762f.png
[Center 1]: /images/20220613/3d91801511b64d0c8c69b514d7e046ce.png
[Center 2]: /images/20220613/c68b42c3216740b48191a5d5dc860f02.png