[问题描述]
给定一个无向图的顶点个数, 再给出有关联的边的信息,请找出给定的两个顶点之间的所有简单路径。按照顶点编号的大小顺序依次输出。
[输入说明]
第1行是顶点个数, 第二行是关联的边的信息,以0 0作为输入的结束, 第三行是两个待求解的顶点
[输出说明]
待求解顶点之间的所有路径, 按照顶点编号的大小顺序依次输出
解题思路
- 根据输入生成无向图的邻接矩阵
- 由顶点编号按大小顺序输出可知
- 通过深度优先搜索确定路径
- 通过栈将生成的某条路径储存
- 在获得一条新的路径后打印结果,把栈顶元素(即终点)移除,继续遍历
- 当某顶点遍历所有弧后,将该顶点从栈顶移除
分解实现
建立邻接矩阵
将弧的信息用矩阵表示,当两个顶点间连接,置为1,否则初始为0。
#define MAXNUM 10
//存放无向图信息
int G[MAXNUM][MAXNUM] = {0};
void addArc(int oVex, int tVex)
{
G[oVex - 1][tVex - 1] = 1;
G[tVex - 1][oVex - 1] = 1;
}
void form()
{
int oVex, tVex;//弧的起点和终点
cin >> oVex;
cin >> tVex;
int i = 0;
while (oVex != 0 && tVex != 0)
{
cout << ++i << ": " << oVex << "\t" << tVex << endl;
addArc(oVex, tVex);//加入邻接表
cin >> oVex;
cin >> tVex;
}
}
深度优先搜索
通过递归实现,当搜索某个顶点no有一个弧连接尚未访问过的顶点i,则访问i并搜索i。
- 如果该顶点对应的弧所连接的顶点都已经访问过,则返回
- 若存在没有访问的顶点,则深度优先,递归调用该顶点进行搜索
//基础版的深度优先遍历
void DFS(int no)
{
//如果该顶点对应的弧所连接的顶点都已经访问过,则返回
//若存在没有访问的顶点,则深度优先,递归调用该顶点进行搜索
for (int i = 0; i < vexnum; i++)
{
//出现没有访问过的
if (G[no][i] == 1 && visited[i] == 0)
{
//访问
cout << "visit: " << i << endl;
visited[i] = 1;
DFS(i);
}
}
//返回
return;
}
栈
基本函数
栈存放顶点序号,数据类型为int类型
注:使栈的分配空间固定为MAXNUM,并不考虑添加元素的溢出问题。
#define MAXNUM 10
typedef int SElemType;
//栈
typedef struct {
SElemType* base;//构造栈和销毁之前,base值为null
SElemType* top;//栈顶指针
int stacksize;//已分配存储空间,以元素为单位
}SqStack;
SqStack S;
void initStack(SqStack& S)
{
//为栈分配内存
S.base = new SElemType[MAXNUM];
//C语言版
// S.base = (SElemType*)malloc(sizeof(SElemType) * MAXNUM);
//栈顶指针指向栈底
S.top = S.base;
S.stacksize = MAXNUM;
}
//入栈
void push(SqStack& S, SElemType data)
{
//不考虑溢出问题
//栈顶处写入数据,并上移
*S.top++ = data;
}
//出栈
//如果栈空,返回false,否则返回true
bool pop(SqStack& S, SElemType& data)
{
if (S.base == S.top)
return false;
else
{
data = *--S.top;
return true;
}
}
测试栈
void testStack()
{
SqStack S;
initStack(S);
push(S, 3);
push(S, 5);
push(S, 7);
push(S, 9);
push(S, 11);
cout << "stack: " << endl;
printStack(S);
int out;
while (pop(S, out))
{
cout << out << endl;
}
}
按[输出格式]顺序栈
//打印顺序栈内容(按照题目输出格式)
void printStack(SqStack S)
{
for (int i = 0; i < S.top - S.base; i++)
{
cout << *(S.base + i) + 1 << " ";
}
cout << endl;
}
核心函数
- 将路线存入栈中
- 如果到达目的地,则打印结果,并出栈
- 如果循环结束,则该地出栈
- 直至栈空退出
void DFS(int o, int t)
{
int foo;
//栈非空
if (S.base != S.top)
{
for (int i = 0; i < vexnum; i++)
{
//出现没有访问过的
if (G[o][i] == 1 && visited[i] == 0)
{
//访问
cout << "deo visit: " << i << endl;
visited[i] = 1;
//入栈
push(S, i);
//到达目的地顶点
if (i == t)
{
//打印当前路线
printStack(S);
//出栈
pop(S, t);
visited[t] = 0;
}
else
{
//继续深度优先遍历
DFS(i, t);
}
}
}
//返回
//出栈
pop(S, foo);
visited[foo] = 0;
}
return;
}
完整代码
#include <iostream>
#define MAXNUM 10
using namespace std;
//存放无向图信息
int G[MAXNUM][MAXNUM] = { 0 };
//存放搜索顶点结果
int visited[MAXNUM] = { 0 };
int vexnum;
typedef int SElemType;
//栈
typedef struct {
SElemType* base;//构造栈和销毁之前,base值为null
SElemType* top;//栈顶指针
int stacksize;//已分配存储空间,以元素为单位
}SqStack;
SqStack S;
void initStack(SqStack& S)
{
//为栈分配内存
S.base = new SElemType[MAXNUM];
//C语言版
// S.base = (SElemType*)malloc(sizeof(SElemType) * MAXNUM);
//栈顶指针指向栈底
S.top = S.base;
S.stacksize = MAXNUM;
}
//入栈
void push(SqStack& S, SElemType data)
{
//不考虑溢出问题
//栈顶处写入数据,并上移
*S.top++ = data;
}
//出栈
//如果栈空,返回false,否则返回true
bool pop(SqStack& S, SElemType &data)
{
if (S.base == S.top)
return false;
else
{
data= *--S.top;
return true;
}
}
//打印顺序栈内容(按照题目输出格式)
void printStack(SqStack S)
{
for (int i = 0; i < S.top-S.base; i++)
{
cout << *(S.base + i) + 1 << " ";
}
cout << endl;
}
void addArc(int oVex, int tVex)
{
G[oVex - 1][tVex - 1] = 1;
G[tVex - 1][oVex - 1] = 1;
}
void form()
{
int oVex, tVex;//弧的起点和终点
cin >> oVex;
cin >> tVex;
int i = 0;
while (oVex != 0 && tVex != 0)
{
//cout << i << ": " << oVex << "\t" << tVex << endl;
addArc(oVex, tVex);//加入邻接表
cin >> oVex;
cin >> tVex;
}
}
//此题目版的深度优先遍历
//将路线存入栈中
//如果到达目的地,则打印结果,并出栈
//如果循环结束,则该地出栈
//直至栈空
void DFS(int o,int t)
{
//如果该顶点对应的弧所连接的顶点都已经访问过,则返回
//若存在没有访问的顶点,则深度优先,递归调用该顶点进行搜索
int foo;
//栈非空
if (S.base!=S.top)
{
for (int i = 0; i < vexnum; i++)
{
//出现没有访问过的
if (G[o][i] == 1 && visited[i] == 0)
{
//访问
//cout << "deo visit: " << i << endl;
visited[i] = 1;
//入栈
push(S, i);
//到达目的地顶点
if (i == t)
{
//打印当前路线
printStack(S);
//出栈
pop(S, t);
visited[t] = 0;
}
else
{
//继续深度优先遍历
DFS(i,t);
}
}
}
//返回
//出栈
pop(S, foo);
visited[foo] = 0;
}
return;
}
void print()
{
for (int i = 0; i < vexnum; i++)
{
for (int j = 0; j < vexnum; j++)
{
cout << G[i][j] << " ";
}
cout << endl;
}
}
int main(void)
{
int start, end;//起点与终点
int choice;
cin >> vexnum;
form();
cout << "input the start and the target: " << endl;
cin >> start;
cin >> end;
//将起点入栈
initStack(S);
push(S, start - 1);
visited[start - 1] = 1;
DFS(start - 1, end - 1);
return 0;
}