10

考虑下图：

替代文字

我试图找到一种方法来枚举从源节点到目标节点的所有可能路径。例如，从 A 到 E，我们有以下可能的路径：

A B C D E
A B C E
A C D E
A C E

请注意，对于 ACDE，实际上有 2 条路径，因为其中一条使用边 F3，另一条使用边 F5。此外，由于 A 和 C 之间存在循环，因此您最终可能会得到无限数量的路径，但出于此目的，我只对在从源到目标的路径上没有重复节点的路径感兴趣。

我写了一个深度优先搜索（DFS）算法，但问题是当你在 2 个节点之间有多个边时（比如上面的边 F3 和 F5）我不知道如何处理它。我的算法只带回路径A C D E和A C E，而不带回其他路径。在 的情况下A B C E，我理解原因，因为它从 A 开始，然后到 C 并构建这些路径，但是当 DFS 回到节点 B 时，它然后尝试去 C，但是 C 已经被访问过所以它停止了。

无论如何，我只是想知道是否有办法做到这一点，或者这可能是 NP 完全的。

如果您想查看我的 DFS，代码如下（抱歉滥用宏，我在竞赛编程中使用这些，所以有点习惯）。

#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cmath>
#include <complex>
#include <stack>
#include "time.h"
using namespace std;
#define SZ(x) (int)x.size()
#define FOR(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define REP(i,n) FOR(i,0,n-1)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define ALL(a) (a).begin(),(a).end()
#define FORE(i,t) for(i=t.begin();i!=t.end();++i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef deque<int> DI;
typedef deque<string> DS;
typedef long long i64;
#define PI 3.14159265358979323
#define DEGTORAD(x) (double)x * 3.14159265358979323846264338327950288 / 180.0
#define RADTODEG(x) (double)x * 180 / 3.14159265358979323846264338327950288
#define prt if(1)printf
template <typename T> string tostr(const T& t) { ostringstream os; os<<t; return os.str(); } 

typedef pair< char, char > PCC;
map< PCC, int > adj;
map< char, bool > vis;

vector< char > path;

void dfs(char at) {
  if (at == 'E') {
    REP(i,SZ(path)) {
      if (i != 0)
        cout<<",";
      cout<<path[i];
    }
    cout<<",E"<<endl;
    return;
  }
  if (vis[at])
    return;
  vis[at] = true;
  map< PCC, int >::iterator it;
  FORE(it,adj) {
    if (it->first.first == at) {
      path.push_back(it->first.first);
      dfs(it->first.second);
      path.erase(path.end()-1);
    }
  }
}


int main() {
  adj[make_pair('A','B')] = 1;
  adj[make_pair('A','C')] = 1;
  adj[make_pair('C','D')] = 1;
  adj[make_pair('D','E')] = 1;
  adj[make_pair('E','I')] = 1;
  adj[make_pair('C','F')] = 1;
  adj[make_pair('F','G')] = 1;
  adj[make_pair('F','H')] = 1;
  adj[make_pair('C','E')] = 1;
  dfs('A');
  return 0;
}

输出：

---------- Capture Output ----------
A,C,D,E
A,C,E
4

3 回答 3

3

无论如何，我只是想知道是否有办法做到这一点，或者这可能是 NP 完全的。
我不相信您可以n!在多项式时间内输出可能的路径。如果每个节点都连接到其他节点，这就是你可能得到的结果。

但问题是，当您在 2 个节点之间有多个边时（如上面的边 F3 和 F5）
那么，您要考虑边F3并F5保持相同，对吗？那么，在调用之前删除重复的边缘可能是最简单的选择dfs。

因为它从 A 开始，然后到 C 并构建这些路径，但是当 DFS 返回节点 B 时，它会尝试转到 C，但 C 已经被访问过，所以它停止了。那么，让我们再次
标记为未访问过。C

void dfs(char at) {
    vis[at] = true;

    // do stuff with 'at'

    vis[at] = false;
}
于 2010-10-12T13:03:29.207 回答
1

以下是使用BFS的方法：以下 ( python) 函数（修改后的BFS在两个节点之间具有递归寻路函数）可用于在非循环图中查找两个节点之间的所有可能路径：

from collections import defaultdict

# modified BFS
def find_all_parents(G, s):
    Q = [s]
    parents = defaultdict(set)
    while len(Q) != 0:
        v = Q[0]
        Q.pop(0)
        for w in G.get(v, []):
            parents[w].add(v)
            Q.append(w) 
    return parents

# recursive path-finding function (assumes that there exists a path in G from a to b)   
def find_all_paths(parents, a, b): 
    return [a] if a == b else [y + b for x in list(parents[b]) for y in find_all_paths(parents, a, x)]

例如，对于下面的图 (DAG) G（通过从给定图中删除有向环和多边），由下式给出

G = {'A':['B','C'], 'B':['C'], 'C':['D', 'E', 'F'], 'D':['E'], 'E':['I'], 'F':['G', 'H']}

如果我们想找到节点之间的所有路径，'A'并且'E'（使用上面定义的函数 as find_all_paths(find_all_parents(G, 'A'), 'A', 'E'))，它将根据需要返回以下路径： 

# ACDE
# ABCDE
# ACE
# ABCE

在此处输入图像描述

于 2020-01-06T09:29:46.807 回答
0

我的猜测是，如果您说，重复路径问题也会出现

J->K->L->O->T
J->M->N->O->T

我认为你的“我们以前来过这里吗”测试不应该只看当前节点，而是看你到达那里的路径。所以不要检查“O”，检查“JMNO”和“JKLO”。

于 2010-10-12T13:15:25.657 回答