算法设计题

sususususu

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

isdkz

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX_VERTICES 100
   
5. 
   
6. typedef struct Node {
   
7.     int vertex;
   
8.     struct Node* next;
   
9. } Node;
   
10. 
    
11. typedef struct {
    
12.     Node* head;
    
13. } AdjList[MAX_VERTICES];
    
14. 
    
15. void addEdge(AdjList adjList, int src, int dest) {
    
16.     Node* newNode = (Node*)malloc(sizeof(Node));
    
17.     newNode->vertex = dest;
    
18.     newNode->next = adjList[src].head;
    
19.     adjList[src].head = newNode;
    
20. }
    
21. 
    
22. void printAllPathsUtil(AdjList adjList, int u, int v, int visited[], int path[], int pathIndex) {
    
23.     visited[u] = 1;
    
24.     path[pathIndex] = u;
    
25.     pathIndex++;
    
26. 
    
27.     if (u == v) {
    
28.         for (int i = 0; i < pathIndex - 1; i++) {
    
29.             printf("%d -> ", path[ i]);
    
30.         }
    
31.         printf("%d\n", path[pathIndex - 1]);
    
32.     } else {
    
33.         Node* current = adjList[u].head;
    
34.         while (current != NULL) {
    
35.             if (!visited[current->vertex]) {
    
36.                 printAllPathsUtil(adjList, current->vertex, v, visited, path, pathIndex);
    
37.             }
    
38.             current = current->next;
    
39.         }
    
40.     }
    
41. 
    
42.     visited[u] = 0;
    
43.     pathIndex--;
    
44. }
    
45. 
    
46. void printAllPaths(AdjList adjList, int u, int v, int numVertices) {
    
47.     int visited[MAX_VERTICES] = {0};
    
48.     int path[MAX_VERTICES];
    
49.     int pathIndex = 0;
    
50. 
    
51.     printAllPathsUtil(adjList, u, v, visited, path, pathIndex);
    
52. }
    
53. 
    
54. int main() {
    
55.     int numVertices = 4;
    
56.     AdjList adjList;
    
57.     for (int i = 0; i < numVertices; i++) {
    
58.         adjList[ i].head = NULL;
    
59.     }
    
60. 
    
61.     addEdge(adjList, 0, 1);
    
62.     addEdge(adjList, 0, 2);
    
63.     addEdge(adjList, 1, 2);
    
64.     addEdge(adjList, 2, 0);
    
65.     addEdge(adjList, 2, 3);
    
66.     addEdge(adjList, 3, 3);
    
67. 
    
68.     int u = 2, v = 3;
    
69.     printf("从顶点%d到顶点%d的所有简单路径为：\n", u, v);
    
70.     printAllPaths(adjList, u, v, numVertices);
    
71. 
    
72.     return 0;
    
73. }
    

复制代码

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

sususususu

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]