c++ - 有向循环图中两个节点之间的路径数

Question

我想在有向图中找到顶点 1 和顶点 n 之间的路径数。该图包含循环。如果顶点 1 和顶点 n 之间的任何路径有循环，则结果应为“INFINITE PATHS”，否则为路径数。这是我尝试过的。

---

1)我修改了DFS算法，它从节点1开始，所有节点最初都是白色的。
2) 如果访问到一个灰色节点，则说明存在环路。
3)记录访问过的顶点的路径数组用于回溯循环中的节点。
4) 对于循环中的每个节点，未修改的 DFS 用于从该节点搜索第 n 个顶点。
5) 如果 DFS 从任何一个节点成功，则在顶点 1 和顶点 n 之间的路径中存在循环，因此它返回否则算法继续计算路径数。

C++实现

---

#include <stdio.h>
#include <malloc.h>
#include <vector>
#include <algorithm>

#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;
typedef struct vertexstruct{
   int color;
   vector<int> edgelist;
}vertex;

int ordinarydfs(int v,vertex *vertices,int numvertices){
    if(v == numvertices){
        return 1;       
    }

    if(vertices[v].color == WHITE){
         vertices[v].color = GRAY;
         for(int i=0;i<vertices[v].edgelist.size();i++){
             int x = ordinarydfs(vertices[v].edgelist[i],vertices,numvertices);
             if(x ==1) return 1;
         }
         vertices[v].color = BLACK; 
     }
     return 0;
}

int checkcycle(int v,vector<int>path,vertex *vertices,int numvertices){
    vector<int>::iterator it;
    vector<int>::iterator x;
    it = find (path.begin(), path.end(), v);
    for(x =it;x<path.end();x++)
        vertices[*x].color = WHITE;
    for(x =it;x<path.end();x++){
        if(ordinarydfs(*x,vertices,numvertices))
            return 1;   
    }
    for(x =it;x<path.end();x++)
        vertices[*x].color = GRAY;

    return 0;

}

long dfs(int v,vertex *vertices,int numvertices,vector<int> path){
    long paths = 0;
    if(v == numvertices){
            return 1;       
    }
    if(vertices[v].color == GRAY) {
         if(checkcycle(v,path,vertices,numvertices)) return -1;
    }   
    if(vertices[v].color == WHITE){
        vertices[v].color = GRAY;
        path.push_back(v);
        for(int i=0;i<vertices[v].edgelist.size();i++){     
            long x = dfs(vertices[v].edgelist[i],vertices,numvertices,path);
            vertices[vertices[v].edgelist[i]].color = WHITE;
            if(x == -1) return -1;
            paths += x;
        }
        vertices[v].color = BLACK;  
    }
    return paths % 1000000000;
}

void numpaths(int numvertices,int numedges,vertex *vertices){
    vector<int> path;
    long numpaths = 0;
    numpaths = dfs(1,vertices,numvertices,path);
    if(numpaths == -1)
        printf("INFINITE PATHS\n");
    else
        printf("%ld\n",numpaths);
}



int main(){
    int edgecount=0;
    int  numverts,numedges;
    fscanf(stdin,"%d %d",&numverts,&numedges);
   vertex verts[numverts+1];
   for(int i =1;i<=numverts;i++)
       verts[i].color = WHITE;
   edgecount = 0; 
   int a,b;
   while(edgecount < numedges){
       scanf("%d %d",&a,&b);
       verts[a].edgelist.push_back(b);
       edgecount++;
       }
   numpaths(numverts,numedges,verts);
}

---

该算法对于大图来说太慢了。这个问题有正确的方法吗？分享你的意见。谢谢。

Answer 1

一种完全不同的方法是将图形表示为邻接矩阵 A[i][j]=1 如果 (i,j) 是边，否则为 0。然后 A^i[s][t] 计算从 s 到 t 的长度为 i 的路径数(这可以通过归纳法证明。想想 A^2 代表什么)。求和 A[s][t] 的 1..|V| 次方，得到所有可能的长度不超过 |V| 的路径。要检查是否存在循环，请查看(通过再次乘以矩阵)是否有长度为 |V|+1,...,2|V| 的路径存在。

这有帮助吗？