【算法】图的深度优先遍历

心已赠人 2022-06-13 02:53 247阅读 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 arr1[101], sum, n, arr2[101][101];
    void dfs(int cur)
    {
    	int i;
    	printf("%d ", cur);//打印出深度优先遍历图的每一个点
    	sum++;
    	if (sum == n)
    	{
    		return;
    	}
    	for (i = 1; i <= n; i++)
    	{
    		if (arr2[cur][i] == 1 && arr1[i] == 0)
    		{
    			arr1[i] = 1;
    			dfs(i);
    		}
    	}
    	return;
    }
    int main()
    {
    	int i, j, m, a, b;
    	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;
    			}
    		}
    	}
    	printf("请输入无向图的边界->\n");
    	for (i = 1; i <= n; i++)
    	{
    		scanf("%d %d", &a, &b);
    		arr2[a][b] = 1;
    		arr2[b][a] = 1;
    	}
    	arr1[1] = 1;
    	printf("深度优先遍历图的结果是：\n");
    	dfs(1);
    	printf("\n");
    	system("pause");
    	return 0;
    }

运行结果：

![Center 1][]

![Center 2][]

[Center]: /images/20220613/0c5ed823621c42de880cfb8362a6ad9e.png
[Center 1]: /images/20220613/0d9b5062675a4857b06d6cae04449b7f.png
[Center 2]: /images/20220613/9d7b26af699d4f04b66669d8ad1ed93d.png