图的深度优先遍历：城市地图

图的深度优先遍历：城市地图

从城市1到城市5，要求找出乘车时间最短的方案：

数据给出形式如下：

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

第一行的5表示有5个城市1，2，3，4，5；8表示有8条公路。

接下来8行是a b c形式的三组数据，表示：有一条路可以从城市a到城市b，乘车耗时c分钟。

若道路为单向车道（即有向图），求出从城市1到城市5的最短时间

若道路为双向车道（即无向图），求出从城市1到城市5的最短时间

解题代码

整体代码

//图的深度优先遍历——城市地图
#include<iostream>
using namespace std;

int city, road;//城市和公路
int minLeng=9999999;//记录最小值

void dfs(int** cityMap, bool* book, int now,int leng = 0,int target=5)//地图，标记数组，现在所处的城市，现在的路程长度，目标城市
{
	if (leng > minLeng) return;//如果当前路程已经大于最小路程，则不必找
	
	if (now == target)
	{
		if (leng < minLeng)
		{
			minLeng = leng;
		}
		return;
	}//如果找到更小的，则更新最短路程

	for (int i = 0; i < city + 1; i++)
	{
		if (cityMap[now][i] > 0 && book[i] == false)
		{
			book[i] = true;//标记已经走过
			dfs(cityMap, book, i, leng + cityMap[now][i], target);//下一步搜索
			book[i] = false;//出来后记得取消标记
		}
	}

	return;
}

int main()
{
	cin >> city >> road;//录入城市和公路的数量

	//创建城市矩阵
	int** cityMap = new int* [city + 1];
	for (int i = 0; i < city + 1; i++)
	{
		cityMap[i] = new int[city + 1];
		for (int j = 0; j < city + 1; j++)
		{
			cityMap[i][j] = -1;
		}//初始化一下
	}

	bool* book = new bool[city + 1];//创建标记数组
	for (int i = 0; i < city + 1; i++) book[i] = false;//初始化一下

	//录入城市公路数据
	int a, b, c;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b >> c;
		cityMap[a][b] = c;
		cityMap[b][a] = c;//无向图的话就要赋两次值
	}

	dfs(cityMap, book, 1);
	cout << minLeng;
	return 0;
}

数据的录入代码

int main()
{
	cin >> city >> road;//录入城市和公路的数量

	//创建城市矩阵
	int** cityMap = new int* [city + 1];
	for (int i = 0; i < city + 1; i++)
	{
		cityMap[i] = new int[city + 1];
		for (int j = 0; j < city + 1; j++)
		{
			cityMap[i][j] = -1;
		}//初始化一下
	}

	bool* book = new bool[city + 1];//创建标记数组
	for (int i = 0; i < city + 1; i++) book[i] = false;//初始化一下

	//录入城市公路数据
	int a, b, c;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b >> c;
		cityMap[a][b] = c;
		cityMap[b][a] = c;//无向图的话就要赋两次值
	}

	dfs(cityMap, book, 1);
	cout << minLeng;
	return 0;
}

注意给邻接矩阵赋值的时候，有向图赋值一次，无向图在与主对角线对称的位置还要再赋值一次

DFS代码

void dfs(int** cityMap, bool* book, int now,int leng = 0,int target=5)//地图，标记数组，现在所处的城市，现在的路程长度，目标城市
{
	if (leng > minLeng) return;//如果当前路程已经大于最小路程，则不必找
	
	if (now == target)
	{
		if (leng < minLeng)
		{
			minLeng = leng;
		}
		return;
	}//如果找到更小的，则更新最短路程

	for (int i = 0; i < city + 1; i++)
	{
		if (cityMap[now][i] > 0 && book[i] == false)
		{
			book[i] = true;//标记已经走过
			dfs(cityMap, book, i, leng + cityMap[now][i], target);//下一步搜索
			book[i] = false;//出来后记得取消标记
		}
	}

	return;
}

运行结果

单向道为9，双向道为7