在圖中找到所有可能的路由時無法擺脫死角

Question

因此，我做了一個關於在圖形中查找用戶指定的兩個節點之間的所有路由的作業。代碼有效，但存在一個小問題。

要得到什麼，我說什麼，見圖表連接什麼樣子：

（我知道，我應該是一個藝術家，而不是一個電腦工程師）

所以我告訴程序告訴我節點0和3之間的所有可能的路線，這是輸出（不是精確的輸出）：

0-3

0-1-2-3

0-2-1-3

所以問題在於最後一條路線。而不是0-2-3去0-2-1-3。因爲它不知道1是死路一條。所以要麼我不應該爲死衚衕節點做任何事情，要麼當我明白它們是死衚衕時不打印它們。

我試着做一些遞歸的東西，以檢查下一個節點是否是死衚衕，但他們竟然是無限循環。

那麼我該如何解決這個問題呢？

/* 
    Description: Finds all possible routes from a starting node to an end node 
       that is picked by the user. 

    NOTE: This code is working in devc++ but it has problems in visual studio 
      because of different functions. 

*/ 

#include <stdio.h> 
#include <string.h> 

find_routes2(int start, int finish, char route[9], char route_temp[9], 
      int mark[4], int graph[4][4]) 
{ 
    int i; 
    char route_temp2[9]; 

    for(i = 0; i < 4; i++) { 
     if (graph[start][i] != 0 && mark[i] != 0) { 
      sprintf(route_temp2, "-> %d", i); 
      strcat(route, route_temp2); 
      if (i == finish) { 
       printf("\nRoute: %s\n", route); 
       strcpy(route, route_temp); 
      } else { 
       mark[start] = 0; 
       find_routes2(i, finish, route, route_temp, mark, graph); 
      } 
     } 
    } 
} 

find_routes(int start, int finish, char route[9], char route_temp[9], 
      int mark[4], int graph[4][4]) 
{ 
    int i; 
    char route_temp2[9]; 

    for (i = 0; i < 4; i++) { 
     if (graph[start][i] != 0 && mark[i] != 0) { 
      sprintf(route_temp2, "-> %d ", i); 
      strcat(route, route_temp2); 

      if (i == finish) { 
       printf("\nRoute: %s\n\n", route); 
      } else { 
       mark[start] = 0; 
       find_routes2(i, finish, route, route_temp, mark, graph); 
      } 
      memset(mark, 1, 4*sizeof(int)); 
      strcpy(route, route_temp); 
     } 
    } 
} 

int main() 
{ 
    int graph[4][4] = { { 0, 1, 1, 1 }, { 1, 0, 1, 0 }, 
         { 1, 1, 0, 1 }, { 1, 0, 1, 0 } }; 
    int mark[4] = { 1, 1, 1, 1 }; 
    char route[9]; 
    char route_temp[9]; 
    int i, j; 

    printf("NOTE: This code is working in devc++ but it has problems \n" 
      "in visual studio because of different functions\n\n"); 
    printf("This is the graph(nodes are 0, 1, 2 ,3):\n\n0-1-2-3\n\n"); 
    for (i = 0; i < 4; i++) { 
     for (j = 0; j < 4; j++) { 
      printf("%d ", graph[i][j]); 
     } 
     printf("\n\n"); 
    } 

    printf("Select a starting node from \"0, 1, 2 ,3\": "); 
    scanf("%d", &i); 

    sprintf(route, "-> %d", i); 

    strcpy(route_temp, route); 

    printf("\nSelect a different ending node from \"0, 1, 2 ,3\"" 
      "(if you dont get any results it\n" 
      "means either you entered wrong numbers or there are no routes): "); 
    scanf("%d", &j); 
    if (i == j || i > 3 || j >3 || i < 0 || j < 0) { 
     printf("\nStart and finish nodes are same or wrong number(s) have" 
       " been entered. Please try \nagain.\n"); 
     exit(1); 
    } 
    find_routes(i, j, route, route_temp, mark, graph); 
    system("pause"); 
} 

Answer 1

嘗試這種情況：

#include <stdio.h> 
#include <stdlib.h> 

void display_route (int route[4], int n) 
{ 
    int i; 

    for (i = 0; i < n; i++) { 
     if (i > 0) { 
      printf (", "); 
     } 
    printf ("%d", route[i]); 
    } 
    printf ("\n"); 
} 

void find_routes_helper (const int graph[4][4], int finish, 
         int route[4], int n, int mark[4]) 
{ 
    // I is the last vertex of ROUTE 
    int i = route[n - 1]; 
    int j; 

    // if ROUTE ends at FINISH, the search is over 
    if (i == finish) { 
     display_route (route, n); 
     return; 
    } 

    // for each vertex J adjacent to I that is not already in ROUTE 
    for (j = 0; j < 4; j++) { 
     if (!mark[j] && graph[i][j]) { 
      // add J to ROUTE 
      route[n] = j; 
      n++; 
      mark[j] = 1; 
      // search routes that begin with ROUTE 
      find_routes_helper (graph, finish, route, n, mark); 
      // backtrack : remove J from ROUTE 
      n--; 
      mark[j] = 0; 
     } 
    } 
} 

void find_routes (const int graph[4][4], int start, int finish) 
{ 
    int i; 
    int route[4]; 
    int n; 
    int mark[4]; 

    // set things up so that ROUTE consists exactly of START 
    route[0] = start; 
    n = 1; 
    for (i = 0; i < 4; i++) { 
     mark[i] = 0; 
    } 
    mark[start] = 1; 

    find_routes_helper (graph, finish, route, n, mark); 
} 

int main() 
{ 
    int graph[4][4] = { 
     { 0, 1, 1, 1 }, 
     { 1, 0, 1, 0 }, 
     { 1, 1, 0, 1 }, 
     { 1, 0, 1, 0 } 
    }; 
    int i, j; 

    printf("This is the graph (nodes are 0, 1, 2 ,3):\n\n0-1-2-3\n\n"); 
    for (i = 0; i < 4; i++) { 
     for (j = 0; j < 4; j++) { 
      printf("%d ", graph[i][j]); 
     } 
     printf("\n"); 
    } 
    printf ("\n"); 

    printf("Select a starting node from \"0, 1, 2 ,3\": "); 
    scanf("%d", &i); 

    printf("\nSelect a different ending node from \"0, 1, 2 ,3\" (if" 
      " you don't get any results it means either you entered" 
      " wrong numbers or there are no routes): "); 
    scanf("%d", &j); 
    if (i == j || i > 3 || j > 3 || i < 0 || j < 0) { 
     printf("\nStart and finish nodes are same or wrong number(s) " 
       " have been entered. Please try again.\n"); 
     exit(1); 
    } 

    find_routes (graph, i, j); 
    return 0; 
} 

注搜索代碼如何表示作爲節點的數組，以及如何顯示邏輯是完全分開的路徑。還要注意如何在find_routes（）中聲明幫助程序數據結構並在main（）中隱藏該數據結構。

Answer 2

您可以在函數find_routes()中的遞歸堆棧頂部打印發現的路由，但如果這樣做，那麼您可以在該函數中每循環迭代一次只打印一個路由 - 也就是說，只有一個路線與每個初始邊緣的選擇。可以有多於一個，例如從節點1到節點0的兩條路徑都以0 - > 2開始。

此外，您沒有提供功能find_routes2()的機制來向其調用者指示其失敗，所以您將爲每個可能的初始曲線選擇打印一條路線。

後者實際上是較不嚴重的問題;它將通過修復第一個而變得毫無意義。爲此，請在每次到達目標頂點時打印完整發現的路線，而不是僅在完全返回到遞歸頂部之後。

還要注意，你需要小心你的頂點標記。當你訪問它們時，你要注意標記你的節點，但是當你完成訪問並且準備嘗試從當前任何節點的另一條路徑時，你不能標記它們。這會阻止您發現某些圖形中某些頂點對之間的所有可能路線，包括內置於程序中的路線。