c - 在图中找到所有可能的路线时无法摆脱死胡同

所以我有一个家庭作业，关于在图中找到用户指定的两个节点之间的所有路由代码可以工作，但有一个小问题。

所以我告诉程序告诉我节点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");
}

最佳答案

试试这个：

#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（）中声明helper数据结构，并在main（）中隐藏。

关于c - 在图中找到所有可能的路线时无法摆脱死胡同，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34166084/