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

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代表什么）。对 1..|V| 的幂求和 A[s][t]，就得到了长度达到 |V| 的所有可能路径。要检查是否存在循环，请查看（通过再次乘以矩阵）长度为 |V|+1,...,2|V| 的路径是否存在 存在。

这有帮助吗？