城市的地图如下图所示
图的深度遍历求最短路径
数据是这样给出的：
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个城市，8表示有8条公路。接下来的8行每行是一条类似“a b c”的数据：表示从城市a到城市b有c公里
已知有5个城市8条路径，可以用一个5*5的矩阵（二维数组e）来存储这些信息。
此外还需要一个book数组来记录哪些城市已经走过，以免出现死循环。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 999999
int book[101], e[101][101];
int n;
int min = 9999999;
int path[100]; /// 用来保存路径
void dfs(int cur, int dis)
{
int i;
if (n == cur) //判断是否到达了目标城市
{
for (i = 1; i <= n; i++) /// 输出所有可能的路径
{
if (path[i])
{
printf("%d ", path[i]); //输出路径
}
}
printf("\t\t该路径对应的长度是：%d\n", dis);//输出对应路径长度
if (min > dis) //更新最小路径
{
min = dis;
}
return;
}
for (i = 1; i <= n; ++i) //从1号城市到n号城市依次尝试
{
//判断当前城市cur到城市i是否有路，并判断城市i是否在已走过的路径中
if (e[cur][i] != INF && book[i] == 0)
{
book[i] = 1;//标记城市i已经在路径中
path[i] = i;//保存路劲到path数组中
dfs(i, dis + e[cur][i]);
book[i] = 0; /// 之前一部探索完毕后,取消对城市 i 的标记以便另一条路径选择顶点
path[i] = 0;
}
}
}
int main(/*int argc, char const *argv[]*/)
{
int i, j, a, b, c, m;
scanf_s("%d %d", &n, &m);
//初始化二维矩阵
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= n; ++j)
{
if (i == j)
{
e[i][j] = 0;
}
else
{
e[i][j] = INF;
}
}
}
//读入城市之间的道路
for (i = 1; i <= m; ++i)
{
scanf_s("%d %d %d", &a, &b, &c);
e[a][b] = c;
}
book[1] = 1; //标记1号城市已经在路径中
path[1] = 1;
dfs(1, 0);//1表示当前所在城市标号，0表示当前已经走过的路程
printf("最短路径的长度是：\n");
printf("%d\n", min);//打印最短路径
system("pause");
return 0;
}
上图对应的是有向图，如果是无向图怎么办呢？
其实，很简单：只需要在存储的时候加一句：e[b][a]=c ，并且修改一下for循环的参数防止重复for (i = cur; i <= n; ++i)
直接上代码和结果：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 999999
int book[101], e[101][101];
int n;
int min = 9999999;
int path[100]; /// 用来保存路径
void dfs(int cur, int dis)
{
int i;
if (n == cur) //判断是否到达了目标城市
{
for (i = 1; i <= n; i++) /// 输出所有可能的路径
{
if (path[i])
{
printf("%d ", path[i]); //输出路径
}
}
printf("\t\t该路径对应的长度是：%d\n", dis);//输出对应路径长度
if (min > dis) //更新最小路径
{
min = dis;
}
return;
}
for (i = cur; i <= n; ++i) //从1号城市到n号城市依次尝试
{
//判断当前城市cur到城市i是否有路，并判断城市i是否在已走过的路径中
if (e[cur][i] != INF && book[i] == 0)
{
book[i] = 1;//标记城市i已经在路径中
path[i] = i;//保存路劲到path数组中
dfs(i, dis + e[cur][i]);
book[i] = 0; /// 之前一部探索完毕后,取消对城市 i 的标记以便另一条路径选择顶点
path[i] = 0;
}
}
}
int main(/*int argc, char const *argv[]*/)
{
int i, j, a, b, c, m;
scanf_s("%d %d", &n, &m);
//初始化二维矩阵
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= n; ++j)
{
if (i == j)
{
e[i][j] = 0;
}
else
{
e[i][j] = INF;
}
}
}
//读入城市之间的道路
for (i = 1; i <= m; ++i)
{
scanf_s("%d %d %d", &a, &b, &c);
e[a][b] = c;
e[b][a] = c;
}
book[1] = 1; //标记1号城市已经在路径中
path[1] = 1;
dfs(1, 0);//1表示当前所在城市标号，0表示当前已经走过的路程
printf("最短路径的长度是：\n");
printf("%d\n", min);//打印最短路径
system("pause");
return 0;
}
网友评论