无向图两个顶点之间的所有简单路径

[问题描述]

给定一个无向图的顶点个数, 再给出有关联的边的信息,请找出给定的两个顶点之间的所有简单路径。按照顶点编号的大小顺序依次输出。

[输入说明]

第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;
}

Leave a comment

Your email address will not be published. Required fields are marked *