查找無向圖中兩個節點之間的所有可能路徑

Question

任何人都可以給我一個C代碼來查找兩個節點之間的所有可能路徑嗎？ 例如。 如果圖具有以下邊緣 1-2 1-3 2-3 2-4 3-4

1和4之間的所有路徑是：

1-2-3-4

1-2-4

1-3-4

1-3-2-4

Answer 1

深度優先搜索執行此任務。

Answer 2

（我假設你不想在你的路徑重複節點 - 否則可能路徑的數量是無限的。）

你可以做一個放鬆：

while (there is a change) { 
    for (v in nodes(G)) { 
    for (e in edges(v)) { 
     paths_to[v] = paths_to[v] union ((paths_to[e.to] not containing v) append v) 
    } 
    } 
} 

結果可以仍然是輸入圖的大小的指數。獲取所有路徑可能不是你想要做的。

Answer 3

這是一個簡單的問題算法。這不是一個最佳算法。

static struct { 
    int value1; 
    int value2; 
    int used; 
} data[] = { 
    { 1, 2 }, 
    { 1, 3 }, 
    { 2, 3 }, 
    { 2, 4 }, 
    { 3, 4 }, 
}; 

enum { DATA_SIZE = sizeof data/sizeof *data }; 

static int output[DATA_SIZE]; 

int traverse(int from, int to, int depth) { 
    output[depth++] = from; 

    int i; 
    if (from == to) { 
    for (i = 0; i < depth; i++) { 
     if (i) { 
     printf("-"); 
     } 
     printf("%d", output[i]); 
    } 
    printf("\n"); 
    } else { 
    for (i = 0; i < DATA_SIZE; i++) { 
     if (!data[i].used) { 
     data[i].used = 1; 

     if (from == data[i].value1) { 
      traverse(data[i].value2, to, depth); 
     } else if (from == data[i].value2) { 
      traverse(data[i].value1, to, depth); 
     } 

     data[i].used = 0; 
     } 
    } 
    } 
} 

int main() { 
    traverse(1, 4, 0); 
} 

Answer 4

遞歸方法：

findPaths(path = startNode, goal) 
    paths = [] 
    if the last node in path is goal: 
     return path 
    for each node n connected to the last node in path: 
     if n is not already on the path: 
      paths.append(findPaths(path.append(node), goal)) 
    return paths //may still be [] 

Answer 5

這是爲時已晚，而不是C代碼，但是可以幫助別人。這個算法展示了我如何在java中實現它。

findPath(start) 
    Childs = getDirectChildsOf(start) 
    foreach child in Childs 
     tempRoute; 
     tempRoute.add(start) 
     if (child == end) 
      return tempRoute.add(child) 
     else 
      tempRoute.add(findPath(child)) 
      if (tempRoute.last() == end) 
       return tempRoute; 

這裏tempRoute可能是一個Route類，維持節點列表。能夠添加單個node和其他route到tempRoute。 它也沒有找到所有可能的路徑。爲此你必須爲每個節點維護一個訪問標誌。