多图中的所有简单路径(深度优先遍历)

Question

阅读并搜索了很长一段时间后，我仍然无法理解多重图的深度优先遍历（或搜索）（两个顶点可以有多条边）。

我在另一个SO问题上找到了这个答案：

求两个任意顶点之间所有连接的图算法

这是一个很好的答案，但它只适用于简单图。

简而言之，我需要多图中从顶点A到顶点B的所有简单路径（没有重复顶点），而不仅仅是最短路径。

如果有任何帮助的话，我将使用JGraphT在Java中实现这一点。我不介意用另一种语言解决问题。如果这也有帮助的话，这个图是有向的和加权的。

附言：我不关心算法的运行时间（我会缓存结果）。

我正在寻找类似于链接问题中的输出（我在边缘附加了一些更多信息，但这与遍历没有太大关系：

All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

谢谢。

Answer 1

多图和普通图实际上不需要不同的代码。在这两种情况下，您都需要知道过去是否访问过该特定路径上的给定节点。无论有多少条边可以连接两个顶点，这都会起作用。

因此，您要做的是，对于每条路径，保留一个您已经访问过的顶点列表，并且永远不要移动到已经访问的顶点。因此，一些伪代码：

function DFSHelper(vertex v, array visited):
    for edge in v.edges:
        if edge.vertex_at_end not in visited:
            DFSHelper(edge.vertex_at_end, visited + [edge.vertex_at_end])
    for v in visited:
        print v + "->"
function DFS(vertex v):
    DFSHelper(v, [])

根据需要进行调整（例如，当前打印给定路径的所有子路径，如"a"、"a->B"、"a->B->C"等）。

还要注意，这将打印一些路径两次（如果同一对顶点之间有多条边）。通过在给定函数中仅从顶点B移动到顶点A一次，可以进行调整以消除这种行为（也就是说，如果多条边连接这两条边，则只在第一条边上递归，而忽略其余边）。

Answer 2

这是在C中实现DFS搜索。可以修改为使用MultiGraphs imo.

如果这是你想要的，我可以修改它以使用"MultiGraphs"。。

#include <stdio.h>
#include <malloc.h>
#include <conio.h>
typedef struct AdjacencyList
{
    char VertexID;
    int *IncidenceList;
}AdjList;
typedef struct Graph
{
    int VertexCount, Status;
    char VertexName;
    AdjList List;
    struct Graph *Next;
}Graph;
Graph* InitializeGraph();
Graph *InitGraphNode(int cnt);
void PerformDepthFirstSearch(Graph *graph);
int main()
{
    Graph *graph;
    graph = InitializeGraph();
    PerformDepthFirstSearch(graph);
    return 0;
}
Graph *InitGraphNode(int cnt)
{
    Graph *node = ((Graph*)malloc(sizeof(Graph)));
    node->List.IncidenceList = ((int*)malloc(sizeof(int)*cnt));
    node->Next = NULL;
    return node;
}
Graph* InitializeGraph()
{
    Graph *graphHead = NULL, *node, *tmp, *tmp2;
    char vname;
    int cnt, i, j, isIncident = 0;
    printf("Enter the number of vertices : ");
    scanf("%d", &cnt);
    if (cnt == 0)
    {
        printf("Number of vertices cannot be ZERO!!nn");
        return graphHead;
    }
    graphHead = InitGraphNode(1);
    graphHead->VertexCount = cnt;
    for(i = 0; i < cnt; i++)
    {
        printf("VertexName : ");
        vname = getche();
        printf("n");
        node = InitGraphNode(cnt);
        node->VertexName = vname;
        node->Next = NULL;
        node->Status = 1;
        if (graphHead->Next == NULL)
        {
            graphHead->Next = node;
        }
        else
        {
            tmp = graphHead;
            while (tmp->Next != NULL)
            {
                tmp = tmp->Next;
            }
            tmp->Next = node;
        }
    }
    tmp = graphHead->Next;
    printf("Prepare to input the adjacent elements of corresponding vertices...nn");
    for(i = 0; i < cnt; i++)
    {
        vname = tmp->VertexName;
        tmp2 = graphHead->Next;
        for(j = 0; j < cnt; j++)
        {
        here :
            printf("%c incident on %c :: (1 for YES)(0 for NO) ::-> ",vname, tmp2->VertexName);
            scanf("%d", &isIncident);
            if ((isIncident < 0)||(isIncident > 1))
            {
                printf("Wrong Input!! Try again!!nn");
                goto here;
            }
            tmp->List.IncidenceList[j] = isIncident;
            tmp2 = tmp2->Next;
        }
        tmp = tmp->Next;
    }
    return graphHead;
}
void PerformDepthFirstSearch(Graph *graph)
{
    Graph *Stack[100], *Copy = graph->Next, *node, *tmp = graph->Next;
    int top = 0, i, cnt = 0;
    Stack[top++] = Copy;
    Copy->Status++;
    while(top != 0)
    {
        node = Stack[--top];
        node->Status++;
        printf("%c, ", node->VertexName);
        for(i = 0; i < graph->VertexCount; i++)
        {
            if(node->List.IncidenceList[i] == 1)
            {
                while (cnt < i)
                {
                    tmp = tmp->Next;
                    cnt++;
                }
                if (tmp->Status == 1)
                {
                    Stack[top++] = tmp;
                    tmp->Status++;
                }
            }
        }
    }
}