多圖中的所有簡單路徑（深度優先遍歷）

Question

經過閱讀和搜索很長一段時間後，我仍然無法擺弄我的頭多圖的深度優先遍歷（或搜索）（兩個頂點可以有多個一個邊緣）。

我發現這個答案在另一個SO問題：

Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

這是一個很好的答案，但它僅適用於簡單圖。

因此，在短期，我需要從頂點A在多重圖所有簡單路徑（無重複頂點）到節點B，不僅是最短的。

我正在Java中使用JGraphT實現這一點，如果這有任何幫助。我不介意另一種語言的解決方案。如果這也有任何幫助，該圖被定向並加權。

P.S.我不關心算法的運行時間（我會緩存結果）。

我在尋找一個類似的鏈接的問題（我有連接到邊緣的一些更多的信息輸出，但是，這並不有很多事要做與跨越：

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

這是C. DFS搜索的實現可以修改與重圖工作海事組織。

如果這是你在找什麼，我可以修改它與「多重圖」的工作。 。

#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!!\n\n"); 
     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...\n\n"); 
    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!!\n\n"); 
       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++; 
       } 
      } 
     } 
    } 
} 

Answer 2

多圖和正常圖不應該實際上需要不同的代碼。在這兩種情況下，您都需要知道過去是否訪問了此特定路徑上的給定節點。無論有多少條邊可以連接兩個頂點，這都可以工作。

因此，您要做的是，對於每條路徑，保留已經訪問過的頂點列表，並且不要前往已訪問的頂點。因此，一些僞代碼：

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（即，如果多條邊連接兩條邊，僅在第一條邊上遞歸併忽略其餘條件）來調整以消除此行爲。