sususususu 发表于 2023-11-12 00:30:15

算法设计题

算法设计题：假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。（用C语言解决）

isdkz 发表于 2023-11-12 00:30:25

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
} AdjList;

void addEdge(AdjList adjList, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = adjList.head;
    adjList.head = newNode;
}

void printAllPathsUtil(AdjList adjList, int u, int v, int visited[], int path[], int pathIndex) {
    visited = 1;
    path = u;
    pathIndex++;

    if (u == v) {
      for (int i = 0; i < pathIndex - 1; i++) {
            printf("%d -> ", path[ i]);
      }
      printf("%d\n", path);
    } else {
      Node* current = adjList.head;
      while (current != NULL) {
            if (!visited) {
                printAllPathsUtil(adjList, current->vertex, v, visited, path, pathIndex);
            }
            current = current->next;
      }
    }

    visited = 0;
    pathIndex--;
}

void printAllPaths(AdjList adjList, int u, int v, int numVertices) {
    int visited = {0};
    int path;
    int pathIndex = 0;

    printAllPathsUtil(adjList, u, v, visited, path, pathIndex);
}

int main() {
    int numVertices = 4;
    AdjList adjList;
    for (int i = 0; i < numVertices; i++) {
      adjList[ i].head = NULL;
    }

    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 2);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 2, 0);
    addEdge(adjList, 2, 3);
    addEdge(adjList, 3, 3);

    int u = 2, v = 3;
    printf("从顶点%d到顶点%d的所有简单路径为：\n", u, v);
    printAllPaths(adjList, u, v, numVertices);

    return 0;
}


这段代码实现了一个从顶点u到v的所有简单路径的算法。首先定义了一个邻接表结构，然后使用addEdge函数向邻接表中添加边。接着使用printAllPathsUtil函数递归地找到从顶点u到顶点v的所有路径，并将其打印出来。最后在main函数中构建了一个图，并调用printAllPaths函数进行测试。

sususususu 发表于 2023-11-12 00:40:22

本帖最后由 sususususu 于 2023-11-12 00:43 编辑

isdkz 发表于 2023-11-12 00:30
这段代码实现了一个从顶点u到v的所有简单路径的算法。首先定义了一个邻接表结构，然后使用addEdge函数 ...

为什么报错呢？
anonymous type with no linkage used to declare function 'void printAllPaths(<anonymous struct>*, int, int, int)' with linkage [-fpermissive]
页: [1]
查看完整版本: 算法设计题