C/C++ 使用邻接矩阵查找未加权和无向图中两个顶点之间的所有路径

Question

我正在尝试使用邻接矩阵查找起始顶点和结束顶点之间的所有路径。我的图表是未加权和无向的。

我试图遵循这个算法，但是，我在每个部分都卡住了。

算法：

procedure FindAllPaths(u, dest)
{
   push u to stack;
   if(u == dest)
   {
      print stack;
   }
   else
   {
      foreach v that is adjacent with u and not in stack now
      {
         FindAllPaths(v, dest);
      }
   }
   pop from stack;
}

我的代码：

void AdjacencyMatrix :: Find_All_Paths(int Origin, int Destination)
{
      /*
      MATRIX:
      0 1 0 1 1
      0 1 0 1 1
      0 0 0 1 0
      0 1 1 1 0
      1 1 0 1 1
      */
    //Push Origin to stack
    Push_Vertex.push(Origin);

    //Determine if Origin == Destination, if so, print the stack
    if(Origin == Destination)
    {
        while(!Push_Vertex.empty())
        {
            cout << Push_Vertex.top() << " ";
            Push_Vertex.pop();
        }//while
        cout << endl;
    }//if

    else

}//Find_All_Paths()

Answer 1

您需要遍历当前节点对应的行，找到与其相邻的节点。这在一定程度上取决于您的邻接矩阵是如何实现的，但它看起来像这样：

for(int v = 0; v < n; v++)
{
    if(adj[Origin][v] && !inStack[v])
    {
        Find_All_Paths(Origin, Destination);
    }
}

adj 是您的邻接矩阵，如果存在从 u 到 v 的边，则 adj[u][v] 为真。 inStack 是一个布尔数组，用于存储顶点是否在堆栈中以允许快速检查。初始化数组为false，并设置一个顶点对应的index，入栈时为true，出栈时为false

完整代码：

void AdjacencyMatrix :: Find_All_Paths(int Origin, int Destination)
{
    //Push Origin to stack
    Push_Vertex.push(Origin);
    inStack[Origin] = true;

    //Determine if Origin == Destination, if so, print the stack
    if(Origin == Destination)
    {
        while(!Push_Vertex.empty())
        {
            cout << Push_Vertex.top() << " ";
            Push_Vertex.pop();
        }//while
        cout << endl;
    }//if

    else
    {
        for(int v = 0; v < n; v++)
        {
            if(adj[Origin][v] && !inStack[v])
            {
                Find_All_Paths(Origin, Destination);
            }
        }
    }
    Push_vertex.pop();
    inStack[Origin] = false;

}//Find_All_Paths()

C/C++ 使用邻接矩阵查找未加权和无向图中两个顶点之间的所有路径

C/C++ Finding all paths between two vertex in unweighted & undirected graph using an adjacency matrix

c++

graph-theory

adjacency-matrix