无向图中求两定点之间所有路径。图用二维数组存储。最好用c语言、给我解题思路也行。谢谢

Question

如题所述

Answer 1

/*
深度优先搜索算法。
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 图中最多的点数
#define MAX_NODES_NUM 10

// 图中两点最多的路径数
#define MAX_PATHS_BETWEEN_TWO_NODES_NUM (1<<(MAX_NODES_NUM-2))

// 标记无穷远的路径长度
#define INFINTITY (1<<30)

// 标记可以到达的路径长度
#define REACHABLE 1

#define TRUE 1
#define FALSE 0

struct Path
{
int size;
int nodes[MAX_NODES_NUM];
};
/*
获取地图 map 中 点 start 到 点 end 的所有路径

map : 地图
n : 地图的点数
start : 起点
end : 终点
paths : 保存找到的所有从 start 到 end 路径
paths : 保存找到的所有从 start 到 end 路径数目

*/
void getPaths(int map[][MAX_NODES_NUM],int n ,int start,int end,int isNodeUsed[],struct Path paths[],int * pathsNum)
{
int i,j;
struct Path tempPaths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];
int tempPathsNum ;

// 标记当前起点不可用
isNodeUsed[start] = TRUE;

for(i=0;i<n;i++)
{
// 节点不在路径中，且可以到达
if(isNodeUsed[i] == FALSE && map[start][i]== REACHABLE)
{
// 当前起点能直接到达终点
if(i == end)
{
paths[(*pathsNum)].size = 2;
paths[(*pathsNum)].nodes[0] = end;
paths[(*pathsNum)].nodes[1] = start;
(*pathsNum)++;
}
// 当前起点能不能直接到达终点，尝试当前节点通过其他节点达到终点
else
{
// 递归计算从当前起点到达终点的所有路径
tempPathsNum = 0;
getPaths(map,n,i,end,isNodeUsed,tempPaths,&tempPathsNum);

// 处理找到的，从当前起点到达终点的所有路径
for(j=0;j<tempPathsNum;j++)
{
// 在当前起点到达终点的所有路径中，添加当前起点
tempPaths[j].nodes[tempPaths[j].size] = start;
tempPaths[j].size ++;

// 合并到最终的路径中
paths[(*pathsNum)] = tempPaths[j];
(*pathsNum)++;
}
}
}
}
isNodeUsed[start] = FALSE;
}

int main(int argc, char *argv[])
{
int map[MAX_NODES_NUM][MAX_NODES_NUM];
int isNodeUsed[MAX_NODES_NUM];
struct Path paths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];
int pathsNum;

int i,j;
int start,end;
int a,b;
int n,m;

// 读取点数，路径数
while(scanf("%d%d",&n,&m)!=EOF)
{
// 初始化图
for(i=0;i<n;i++)
{
isNodeUsed[i] = FALSE;
for(j=0;j<n;j++)
{
map[i][j] = INFINTITY;
}
}

// 读入路径
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
// 标记 a b 间有路径，注意是无向图，标记两次
map[a][b] = REACHABLE;
map[b][a] = REACHABLE;
}

// 要连接的两个点
scanf("%d%d",&start,&end);

// 查找点 start 到点 end 的所有路径
pathsNum = 0;
getPaths(map,n,start,end,isNodeUsed,paths,&pathsNum);

// 打印点 start 到点 end 的所有路径
for(i=0;i<pathsNum;i++)
{
for(j=paths[i].size-1;j>=1;j--)
{
printf("%d -> ",paths[i].nodes[j]);
}
printf("%d\n",paths[i].nodes[j]);
}
}

return 0;
}

/*
测试用数据：
1）首先输入点数 n,路径条数 m，

2）接下来输入 m 对点的编号，每对点 a,b 表示点 a 和 点 b 之间有一条路
点的编号从 0 开始到 n-1.

3）最后输入要连接的两个点

输入：
6 14

0 1
0 2
1 0
1 3
2 0
2 4
2 5
3 1
3 5
4 2
4 5
5 2
5 3
5 4

0 5

输出：
0 -> 1 -> 3 -> 5
0 -> 2 -> 4 -> 5
0 -> 2 -> 5
*/追问

谢谢

本回答被提问者采纳