问题描述

假设图用邻接表表示，设计一个算法，输出从顶点 $i$ 到顶点 $j$ 的所有简单路径

输入格式

第一行包含三个整数 $n$ ， $m$ 和 $k$。

接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从点 $x$ 到点 $y$ 的有向边 ($x$, $y$)。

接下来 $k$ 行，每行包含两个整数 $s$ 和 $t$，表示要求输出顶点 $s$ 到顶点 $t$ 的所有简单路径。

输入

6 8 3
1 2
1 3
2 4 
3 4
4 5
5 3
2 7
7 4
1 4
2 5
1 5

输出

1 -> 4 的所有简单路径：
1 3 4 
1 2 7 4 
1 2 4 

2 -> 5 的所有简单路径：
2 7 4 5 
2 4 5 

1 -> 5 的所有简单路径：
1 3 4 5 
1 2 7 4 5 
1 2 4 5 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m, k;
bool st[N];
vector<int> path;

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int s, int t)
{
    if (s == t)
    {
        for (auto x : path) printf("%d ", x);
        puts("");
        return ;
    }

    for (auto p = head[s]; p; p = p->next)
    {
        int j = p->id;
        if (!st[j])
        {
            st[j] = true;
            path.push_back(j);
            dfs(j, t);
            path.pop_back();
            st[j] = false;
        }
    }
}


int main()
{
    cin >> n >> m >> k;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    while (k --)
    {
        int s, t;
        cin >> s >> t;
        printf("\n%d -> %d 的所有简单路径：\n", s, t);
        path.push_back(s);
        st[s] = true;
        dfs(s, t);  // 输出顶点s到顶点t的所有简单路径
        st[s] = false;
        path.pop_back();
    }

    return 0;
}

这个代码输出从顶点i到顶点j的所有简单路径的算法思想如下:

1. 用邻接表表示图,构建邻接表头head,每个节点存储下一个邻接节点指针。

2. 深度优先搜索dfs函数,递归搜索各条路径。

3. path向量存储当前路径,st数组标记每个节点是否访问过。

4. dfs函数入口是s节点,终止条件是找到t节点。

5. 对s节点的每一个邻接节点p递归搜索:

   • 将p加入path并标记为已访问

   • 继续递归dfs搜索下一个节点

   • 返回后删除p,恢复未访问状态

6. 每经过一个节点并回溯,输出当前path向量中的路径,即找到一条从s到t的路径。

7. 重复5-6步骤搜索s节点的所有可能路径,输出所有简单路径。

所以这个算法是使用深度优先搜索和回溯方法,结合path向量和st访问标记数组来记录和输出所有可能的路径,得到从初始节点到目标节点的所有简单路径。