首页 文章

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

提问于
浏览 次
5

我想在有向图中找到顶点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);
}

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

c++ algorithm

4 回答

  • 1

    一种完全不同的方法是将图形表示为邻接矩阵A [i] [j] = 1 if if（i，j）是边，否则为0 . 然后A ^ i [s] [t]计算从s到t的路径数，长度为i（这可以通过归纳证明 . 想想A ^ 2代表什么） . 总和A [s] [t]为幂1 .. | V |，并且您拥有长度最大为| V |的所有可能路径 . 要检查是否存在循环，请参阅（通过再次乘以矩阵）长度为| V |的路径1，...，2 | V |存在 .

    这有帮助吗？

    回复于
  • 3

    您没有使用任何缓存，因此 dfs() 和 ordinarydfs() 将被多次调用 . 用于检查周期的 path 向量是多余的，因为您可以通过其颜色判断顶点是否在当前路径中 . 也没有必要进行特殊检查以查看循环是否连接到最后一个顶点，因为您已经计算了最后一个顶点有多少条路径 .

    我将整个BFS放在一个方法中并重写了大部分代码：

    #include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class Vertex;

const int WHITE = 0, GRAY = 1, BLACK = 2;
// WHITE: unseen, GRAY: in the current path, BLACK: finished (num paths known)
const int CYCLE = -1;

class Vertex
{
public:
    long long paths;
    int color;
    bool hasLoop;
    vector<Vertex *> nbrs;

    Vertex();
    long long countPaths();
};

int main()
{
    int numverts, numedges;
    Vertex** verts; // dynamically-allocated array of Vertex*
    scanf("%d %d", &numverts, &numedges);

    verts = new Vertex*[numverts+1];
    for (int i = 0; i < numverts + 1; i++) verts[i] = new Vertex();

    for (int i = 0; i < numedges; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        verts[a]->nbrs.push_back(verts[b]);
    }

    verts[numverts]->paths = 1; // the base case

    long long numPaths = verts[1]->countPaths();

    // free dynamic memory, set pointers to NULL to prevent accidents
    for (int i = 0; i < numverts; i++) { delete verts[i]; verts[i] = NULL; }
    delete[] verts; verts = NULL;

    if (numPaths == CYCLE) printf("INFINITE PATHS\n");
    else printf("%lld\n", numPaths);

    return 0;
}


Vertex::Vertex()
{
    paths = 0;
    color = WHITE;
    hasLoop = false;
}

long long Vertex::countPaths()
{
    // sets this->paths to the number of paths, or CYCLE (-1) for cycles
    // returns this->paths

    if (color == BLACK)
    {
        // paths already calculated, no need to do anything
    }
    else if (color == GRAY)
    {
        // detected a loop
        hasLoop = true;
    }
    else if (color == WHITE)
    {
        // recursively find all the paths from the neighbours
        color = GRAY;
        for (unsigned int i = 0; i < nbrs.size(); i++)
        {
            nbrs[i]->countPaths();
            if (nbrs[i]->paths == CYCLE)
            {
                // found cycle, no point continuing
                paths = CYCLE;
                break;
            }
            paths += nbrs[i]->paths;
        }
        color = BLACK;

        // check if some other node found a cycle to 'this'
        if (hasLoop && paths > 0) paths = CYCLE;
    }

    return paths;
}
    回复于
  • 2

    我们可以通过以下步骤解决这个问题：

    • 计算图形的强连通分量（SCC） .

    • 将SCC中的所有节点折叠为一个节点并标记它们 . 最终结果是我们有一个DAG，G ', of SCC' s . 一些SCC可能只包含一个节点 .

    • 对G'进行拓扑排序 .

    • 计算从目标节点到源节点的路径（使用建议的方法here . 使用该方法时将表示SCC的节点视为特殊情况并将其标记为具有无限路径 . （MAX_LONG）

    （如果仍然需要，我会尝试稍后发布一个实现）

    回复于
  • 0

    我试过这个，速度很快，但我不确定它是否正确 . 当您到达黑色节点时，这意味着您已经计算了该节点的路径，因此我将路径数存储在节点结构中并使用它 .

    #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;
    long paths;
}vertex;

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

return paths % 1000000000;
}

void numpaths(int numvertices,int numedges,vertex *vertices){
        long numpaths = 0;
        cyclenode = 0;
                throughend =0;
        numpaths = dfs(1,vertices,numvertices);
        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;
        verts[i].paths = 0;
    }
    edgecount = 0; 
        int a,b;
    while(edgecount < numedges){
                scanf("%d %d",&a,&b);
        verts[a].edgelist.push_back(b);
                edgecount++;
        }
    numpaths(numverts,numedges,verts);
}
    回复于

相关问题