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

/*

深度优先搜索算法。

*/

#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=0i<ni++)

{

// 节点不在路径中，且可以到达

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=0j<tempPathsNumj++)

{

// 在当前起点到达终点的所有路径中，添加当前起点

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=0i<ni++)

{

isNodeUsed[i] = FALSE

for(j=0j<nj++)

{

map[i][j] = INFINTITY

}

}

// 读入路径

for(i=0i<mi++)

{

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=0i<pathsNumi++)

{

for(j=paths[i].size-1j>=1j--)

{

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

*/

可以用邻接矩阵表示法：

#define max 100

typedef struct

{

int vex[max]//存储顶点值，类型可以变

int edge[max][max]//存储顶点之间的关系，以1或者0表示，1为有边，0为无

int e,v//vertex存储顶点数，edge存储边的条数，所以无向图1的个数是边的个数的两倍，谢谢。

}m

---