C语言用DFS实现找到图的所有路径（邻接矩阵实现）

链接：这里详细介绍了DFS遍历的过程，我主要是介绍实现

以下是例子，所有图的DFS遍历，只需要修改createGraphics()函数即可，即生成自己的map（邻接矩阵）,就可以找到两个点之间所有的路径。

1.问题如下：

输入一个矩阵的行数r（5-10）与列数c（5-10），生成一个无向图,该图每行有c个顶点每列有r个顶点，相邻顶点间有边连接，边的权值均为1，对该图的顶点进行编号，分别为1，2，...，r*c，用DFS找到某两个点之间的所有路径。

及类似如下的图：（只是简单的改变行和列）

2.代码如下

#include<stdio.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>

int map[100][100];
int row, column;

int i, j;
int pathOrder = 0;  //记录到当前找到的路径个数 
int startPoint, endPoint;
int path[100], visited[100] = { 0 };
int pathNumber = 0;

//
//初始化连接矩阵 
// 
void createGraphics()
{
	int tmp[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
	memset(map, 0, sizeof(map));
	for (i = 0; i < row*column; i++)
	{
		//找到该点上下左右4个点初始map 
		int r = i / column;
		int c = i % column;
		for (j = 0; j < 4; j++)
		{
			//（r,c)相邻的点为（r1,c1) 
			int r1 = r + tmp[j][0];
			int c1 = c + tmp[j][1];
			if (r1 >= 0 && r1 < row&&c1 >= 0 && c1 < column)
			{
				map[i][r1*column + c1] = 1;
			}
		}
	}
}


//
//返回第n个节点相连接序号最小的节点 
//
int first(int n)
{
	for (i = 0; i < row*column; i++)
	{
		if (map[n][i] == 1)
			return i;
	}
	printf("起点为故障点，请输入一个不为故障点的起点
");
	return 0;
}


//
//返回第n个节点相邻的点的个数
// 
int sumCount(int n)
{
	int count = 0;
	for (i = 0; i < row*column; i++)
	{
		if (map[n][i] == 1)
			count++;
	}
	return count;
}


//
//返回第n个节点相连的比now节点序号大的节点,
//
int next(int n, int now)
{
	for (i = now + 1; i < row*column; i++)
	{
		if (map[n][i] == 1)
			return i;
	}
	return 1000;  //当找不到节点n的下一个节点，返回1000
}


//
//DFS寻找所有路径 
//count为从起点到当前节点经过的节点数,pathNumber为寻找到的路径条数 
void DFS(int nowPoint, int count)
{
	visited[nowPoint] = 1;
	path[count++] = nowPoint;
	if (nowPoint == endPoint && (count) >= 1)
	{
		pathNumber++;
		printf("这两个城市间第%d条简单路径为: ", pathNumber);
		for (i = 0; i < (count)-1; i++)
		{
			printf("%d-->", path[i] + 1);
		}
		printf("%d
", path[(count)-1] + 1);
	}
	else
	{
		int k;
		for (k = first(nowPoint); k < row*column; k = next(nowPoint, k))
		{
			if (visited[k] == 0)
				DFS(k, count);
		}
	}
	visited[nowPoint] = 0;  //算法关键，回溯，将访问过状态变为未访问状态 
	(count)--;
	return;
}


int main()
{
	int count = 0, pathNumber = 0;
	printf("请输入要生成图的行和列：");
	scanf("%d%d", &row, &column);
	createGraphics();
	printf("请输入要找到路径的起点和终点:");
	scanf("%d%d", &startPoint, &endPoint);
	startPoint--;
	endPoint--;
	DFS(startPoint, count);
	system("pause");
	return 0;
}

3、结果如下：