[已解决]关于求最短路径法，哪位大侠能帮我翻转成C代码

wp231957

1. graph = {'A': ['B', 'C',"F"],
   
2.              'B': ['E'],
   
3.              'C': ['E',"F"],
   
4.              'D': ['E'],
   
5.              'E': ['G'],
   
6.              'F': ['H'],
   
7.              "G":["H"]}
   
8. 
   
9. def find_shortest_path(graph, start, end, path=[]):
   
10.         path = path + [start]
    
11.         if start == end:
    
12.             return path
    
13.         shortest = None
    
14.         for node in graph[start]:
    
15.             if node not in path:
    
16.                 newpath = find_shortest_path(graph, node, end, path)
    
17.                 if newpath!=None:
    
18.                     if not shortest or len(newpath) < len(shortest):
    
19.                         shortest = newpath
    
20.         return shortest
    
21.         
    
22. print(find_shortest_path(graph, 'A', 'H'))     

复制代码

最佳答案

月排行榜 / 总排行榜

人造人

2020-2-12 02:28:21

6个小时可还行，^_^

下面简单说一下

1.
C语言中没有函数默认参数，所以这里只能加上NULL

1. print(find_shortest_path(graph, 'A', 'H'))

复制代码

1. path_t path = graph_find_shortest_path(graph, 'A', 'H', NULL);

复制代码

2.
C语言中没办法像这样静态初始化（编译时初始化），所以只能运行时初始化了

1. graph = {'A': ['B', 'C',"F"],
   
2.              'B': ['E'],
   
3.              'C': ['E',"F"],
   
4.              'D': ['E'],
   
5.              'E': ['G'],
   
6.              'F': ['H'],
   
7.              "G":["H"]}

复制代码

1.         graph_t graph = graph_init();
   
2.         graph_insert(graph, 'A', "BCF");
   
3.         graph_insert(graph, 'B', "E");
   
4.         graph_insert(graph, 'C', "EF");
   
5.         graph_insert(graph, 'D', "E");
   
6.         graph_insert(graph, 'E', "G");
   
7.         graph_insert(graph, 'F', "H");
   
8.         graph_insert(graph, 'G', "H");

复制代码

还有，vs说我的代码有内存泄漏问题
我现在头有一点疼，^_^
明天再debug内存泄漏问题（明天指的是睡一觉起来）

下面贴代码
list.h

1. #ifndef _LIST_H_
   
2. #define _LIST_H_
   
3. 
   
4. #include <stddef.h>
   
5. #include <stdbool.h>
   
6. 
   
7. typedef char list_elem_t;
   
8. 
   
9. typedef struct list_node_tag
   
10. {
    
11.         list_elem_t e;
    
12.         struct list_node_tag *next;
    
13. } list_node_t;
    
14. 
    
15. typedef struct list_tag
    
16. {
    
17.         list_node_t *data;
    
18.         size_t length;
    
19. } *list_t;
    
20. 
    
21. list_t list_init(void);
    
22. void list_deinit(list_t list);
    
23. bool list_insert(list_t list, size_t index, list_elem_t e);
    
24. bool list_delete(list_t list, size_t index);
    
25. bool list_append(list_t list, list_elem_t e);
    
26. bool list_get(list_t list, size_t index, list_elem_t *e);
    
27. void list_clear(list_t list);
    
28. bool list_empty(list_t list);
    
29. size_t list_length(list_t list);
    
30. bool list_locate(list_t list, list_elem_t e);
    
31. list_t list_clone(list_t list);
    
32. 
    
33. #endif

复制代码

list.c

1. #include "list.h"
   
2. #include <stdlib.h>
   
3. 
   
4. list_t list_init(void)
   
5. {
   
6.         list_t list = malloc(sizeof(struct list_tag));
   
7.         list->length = 0;
   
8.         list->data = malloc(sizeof(list_node_t));
   
9.         list->data->e = 0;
   
10.         list->data->next = NULL;
    
11.         return list;
    
12. }
    
13. 
    
14. void list_deinit(list_t list)
    
15. {
    
16.         list_clear(list);
    
17.         free(list->data);
    
18.         free(list);
    
19. }
    
20. 
    
21. bool list_insert(list_t list, size_t index, list_elem_t e)
    
22. {
    
23.         if(list_length(list) < index)
    
24.                 return false;
    
25. 
    
26.         list_node_t *p = list->data;
    
27.         while(index--)
    
28.                 p = p->next;
    
29. 
    
30.         list_node_t *node = malloc(sizeof(list_node_t));
    
31.         node->e = e;
    
32.         node->next = p->next;
    
33.         p->next = node;
    
34.         ++list->length;
    
35.         return true;
    
36. }
    
37. 
    
38. bool list_delete(list_t list, size_t index)
    
39. {
    
40.         if(list_empty(list))
    
41.                 return false;
    
42.         if(list_length(list) <= index)
    
43.                 return false;
    
44. 
    
45.         list_node_t *p = list->data;
    
46.         while(index--)
    
47.                 p = p->next;
    
48. 
    
49.         list_node_t *temp = p->next;
    
50.         p->next = p->next->next;
    
51.         free(temp);
    
52.         --list->length;
    
53.         return true;
    
54. }
    
55. 
    
56. bool list_append(list_t list, list_elem_t e)
    
57. {
    
58.         return list_insert(list, list_length(list), e);
    
59. }
    
60. 
    
61. bool list_get(list_t list, size_t index, list_elem_t *e)
    
62. {
    
63.         if(list_empty(list))
    
64.                 return false;
    
65.         if(list_length(list) <= index)
    
66.                 return false;
    
67. 
    
68.         list_node_t *p = list->data->next;
    
69.         while(index--)
    
70.                 p = p->next;
    
71.         *e = p->e;
    
72.         return true;
    
73. }
    
74. 
    
75. void list_clear(list_t list)
    
76. {
    
77.         while(!list_empty(list))
    
78.                 list_delete(list, 0);
    
79. }
    
80. 
    
81. bool list_empty(list_t list)
    
82. {
    
83.         return !list_length(list);
    
84. }
    
85. 
    
86. size_t list_length(list_t list)
    
87. {
    
88.         return list->length;
    
89. }
    
90. 
    
91. bool list_locate(list_t list, list_elem_t e)
    
92. {
    
93.         for(size_t i = 0; i < list_length(list); ++i)
    
94.         {
    
95.                 list_elem_t elem;
    
96.                 list_get(list, i, &elem);
    
97.                 if(elem == e)
    
98.                         return true;
    
99.         }
    
100.         return false;
     
101. }
     
102. 
     
103. list_t list_clone(list_t list)
     
104. {
     
105.         list_t clone = list_init();
     
106.         for(size_t i = 0; i < list_length(list); ++i)
     
107.         {
     
108.                 list_elem_t e;
     
109.                 list_get(list, i, &e);
     
110.                 list_append(clone, e);
     
111.         }
     
112.         return clone;
     
113. }

复制代码

graph.h

1. #ifndef _GRAPH_H_
   
2. #define _GRAPH_H_
   
3. 
   
4. #include "list.h"
   
5. 
   
6. typedef char graph_elem_t;
   
7. 
   
8. typedef struct
   
9. {
   
10.         graph_elem_t v;
    
11.         list_t vs;
    
12. } graph_node_t;
    
13. 
    
14. typedef struct graph_tag
    
15. {
    
16.         graph_node_t *node;
    
17.         size_t length;
    
18. } *graph_t;
    
19. 
    
20. graph_t graph_init(void);
    
21. void graph_deinit(graph_t graph);
    
22. void graph_insert(graph_t graph, graph_elem_t v, const char *vs);
    
23. void graph_clear(graph_t graph);
    
24. 
    
25. typedef list_t path_t;
    
26. typedef list_elem_t graph_vertex_t;
    
27. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path);
    
28. void graph_print_path(path_t path);
    
29. void graph_free_path(path_t path);
    
30. 
    
31. #endif

复制代码

graph.c

1. #include "graph.h"
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. graph_t graph_init(void)
   
6. {
   
7.         graph_t graph = malloc(sizeof(struct graph_tag));
   
8.         graph->length = 0;
   
9.         graph->node = NULL;
   
10.         return graph;
    
11. }
    
12. 
    
13. void graph_deinit(graph_t graph)
    
14. {
    
15.         graph_clear(graph);
    
16.         free(graph);
    
17. }
    
18. 
    
19. void graph_insert(graph_t graph, graph_elem_t v, const char *vs)
    
20. {
    
21.         ++graph->length;
    
22.         graph->node = realloc(graph->node, sizeof(graph_node_t) * graph->length);
    
23.         graph->node[graph->length - 1].v = v;
    
24.         graph->node[graph->length - 1].vs = list_init();
    
25.         for(size_t i = 0; vs[i]; ++i)
    
26.                 list_append(graph->node[graph->length - 1].vs, vs[i]);
    
27. }
    
28. 
    
29. void graph_clear(graph_t graph)
    
30. {
    
31.         for(size_t i = 0; i < graph->length; ++i)
    
32.                 list_deinit(graph->node[i].vs);
    
33.         free(graph->node);
    
34.         graph->node = NULL;
    
35.         graph->length = 0;
    
36. }
    
37. 
    
38. static list_t get_vs(graph_t graph, graph_vertex_t v)
    
39. {
    
40.         for(size_t i = 0; i < graph->length; ++i)
    
41.         {
    
42.                 if(graph->node[i].v == v)
    
43.                         return graph->node[i].vs;
    
44.         }
    
45.         return NULL;
    
46. }
    
47. 
    
48. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path)
    
49. {
    
50.         if(!path)
    
51.                 path = list_init();
    
52. 
    
53.         list_append(path, start);
    
54.         if(start == end)
    
55.                 return path;
    
56. 
    
57.         list_t shortest = NULL;
    
58. 
    
59.         list_t vs = get_vs(graph, start);
    
60.         for(size_t i = 0; i < list_length(vs); ++i)
    
61.         {
    
62.                 graph_vertex_t node;
    
63.                 list_get(vs, i, &node);
    
64.                 if(!list_locate(path, node))
    
65.                 {
    
66.                         path_t newpath = graph_find_shortest_path(graph, node, end, list_clone(path));
    
67.                         if(!list_empty(newpath))
    
68.                         {
    
69.                                 if(!shortest || list_length(newpath) < list_length(shortest))
    
70.                                 {
    
71.                                         if(shortest)
    
72.                                                 list_deinit(shortest);
    
73.                                         shortest = list_clone(newpath);
    
74.                                 }
    
75.                                 list_deinit(newpath);
    
76.                         }
    
77.                 }
    
78.         }
    
79.         return shortest;
    
80. }
    
81. 
    
82. void graph_print_path(path_t path)
    
83. {
    
84.         for(size_t i = 0; i < path->length; ++i)
    
85.         {
    
86.                 list_elem_t e;
    
87.                 list_get(path, i, &e);
    
88.                 printf("%c ", e);
    
89.         }
    
90.         printf("\n");
    
91. }
    
92. 
    
93. void graph_free_path(path_t path)
    
94. {
    
95.         list_deinit(path);
    
96. }

复制代码

main.c

1. #include "graph.h"
   
2. 
   
3. int main(void)
   
4. {
   
5.         graph_t graph = graph_init();
   
6.         graph_insert(graph, 'A', "BCF");
   
7.         graph_insert(graph, 'B', "E");
   
8.         graph_insert(graph, 'C', "EF");
   
9.         graph_insert(graph, 'D', "E");
   
10.         graph_insert(graph, 'E', "G");
    
11.         graph_insert(graph, 'F', "H");
    
12.         graph_insert(graph, 'G', "H");
    
13.        
    
14.         path_t path = graph_find_shortest_path(graph, 'A', 'H', NULL);
    
15.         graph_print_path(path);
    
16.         graph_free_path(path);
    
17. 
    
18.         graph_deinit(graph);
    
19.         return 0;
    
20. }

复制代码

跳转到最佳答案楼层

wp231957

@zltzlt

zltzlt

wp231957 发表于 2020-2-11 17:13
@zltzlt

有点难不太会

wp231957

@人造人

人造人

wp231957 发表于 2020-2-11 19:05
@人造人

我研究研究

人造人

1. graph = {'A': ['B', 'C',"F"],
   
2.              'B': ['E'],
   
3.              'C': ['E',"F"],
   
4.              'D': ['E'],
   
5.              'E': ['G'],
   
6.              'F': ['H'],
   
7.              "G":["H"]}

复制代码

graph这个变量表示的图是这个样子吗？

wp231957

人造人 发表于 2020-2-11 19:47
graph这个变量表示的图是这个样子吗？

一点不差  

人造人

必须是 C 吗？不能用 C++ ？

wp231957

人造人 发表于 2020-2-11 20:08
必须是 C 吗？不能用 C++ ？

嗯，最好不用加加  因为加加有些特有的库   而c 都是原生态的

人造人

wp231957 发表于 2020-2-11 20:09
嗯，最好不用加加  因为加加有些特有的库   而c 都是原生态的

我试试吧

wp231957

人造人 发表于 2020-2-11 20:11
我试试吧

辛苦了

人造人

6个小时可还行，^_^

下面简单说一下

1.
C语言中没有函数默认参数，所以这里只能加上NULL

1. print(find_shortest_path(graph, 'A', 'H'))

复制代码

1. path_t path = graph_find_shortest_path(graph, 'A', 'H', NULL);

复制代码

2.
C语言中没办法像这样静态初始化（编译时初始化），所以只能运行时初始化了

1. graph = {'A': ['B', 'C',"F"],
   
2.              'B': ['E'],
   
3.              'C': ['E',"F"],
   
4.              'D': ['E'],
   
5.              'E': ['G'],
   
6.              'F': ['H'],
   
7.              "G":["H"]}

复制代码

1.         graph_t graph = graph_init();
   
2.         graph_insert(graph, 'A', "BCF");
   
3.         graph_insert(graph, 'B', "E");
   
4.         graph_insert(graph, 'C', "EF");
   
5.         graph_insert(graph, 'D', "E");
   
6.         graph_insert(graph, 'E', "G");
   
7.         graph_insert(graph, 'F', "H");
   
8.         graph_insert(graph, 'G', "H");

复制代码

还有，vs说我的代码有内存泄漏问题
我现在头有一点疼，^_^
明天再debug内存泄漏问题（明天指的是睡一觉起来）

下面贴代码
list.h

1. #ifndef _LIST_H_
   
2. #define _LIST_H_
   
3. 
   
4. #include <stddef.h>
   
5. #include <stdbool.h>
   
6. 
   
7. typedef char list_elem_t;
   
8. 
   
9. typedef struct list_node_tag
   
10. {
    
11.         list_elem_t e;
    
12.         struct list_node_tag *next;
    
13. } list_node_t;
    
14. 
    
15. typedef struct list_tag
    
16. {
    
17.         list_node_t *data;
    
18.         size_t length;
    
19. } *list_t;
    
20. 
    
21. list_t list_init(void);
    
22. void list_deinit(list_t list);
    
23. bool list_insert(list_t list, size_t index, list_elem_t e);
    
24. bool list_delete(list_t list, size_t index);
    
25. bool list_append(list_t list, list_elem_t e);
    
26. bool list_get(list_t list, size_t index, list_elem_t *e);
    
27. void list_clear(list_t list);
    
28. bool list_empty(list_t list);
    
29. size_t list_length(list_t list);
    
30. bool list_locate(list_t list, list_elem_t e);
    
31. list_t list_clone(list_t list);
    
32. 
    
33. #endif

复制代码

list.c

1. #include "list.h"
   
2. #include <stdlib.h>
   
3. 
   
4. list_t list_init(void)
   
5. {
   
6.         list_t list = malloc(sizeof(struct list_tag));
   
7.         list->length = 0;
   
8.         list->data = malloc(sizeof(list_node_t));
   
9.         list->data->e = 0;
   
10.         list->data->next = NULL;
    
11.         return list;
    
12. }
    
13. 
    
14. void list_deinit(list_t list)
    
15. {
    
16.         list_clear(list);
    
17.         free(list->data);
    
18.         free(list);
    
19. }
    
20. 
    
21. bool list_insert(list_t list, size_t index, list_elem_t e)
    
22. {
    
23.         if(list_length(list) < index)
    
24.                 return false;
    
25. 
    
26.         list_node_t *p = list->data;
    
27.         while(index--)
    
28.                 p = p->next;
    
29. 
    
30.         list_node_t *node = malloc(sizeof(list_node_t));
    
31.         node->e = e;
    
32.         node->next = p->next;
    
33.         p->next = node;
    
34.         ++list->length;
    
35.         return true;
    
36. }
    
37. 
    
38. bool list_delete(list_t list, size_t index)
    
39. {
    
40.         if(list_empty(list))
    
41.                 return false;
    
42.         if(list_length(list) <= index)
    
43.                 return false;
    
44. 
    
45.         list_node_t *p = list->data;
    
46.         while(index--)
    
47.                 p = p->next;
    
48. 
    
49.         list_node_t *temp = p->next;
    
50.         p->next = p->next->next;
    
51.         free(temp);
    
52.         --list->length;
    
53.         return true;
    
54. }
    
55. 
    
56. bool list_append(list_t list, list_elem_t e)
    
57. {
    
58.         return list_insert(list, list_length(list), e);
    
59. }
    
60. 
    
61. bool list_get(list_t list, size_t index, list_elem_t *e)
    
62. {
    
63.         if(list_empty(list))
    
64.                 return false;
    
65.         if(list_length(list) <= index)
    
66.                 return false;
    
67. 
    
68.         list_node_t *p = list->data->next;
    
69.         while(index--)
    
70.                 p = p->next;
    
71.         *e = p->e;
    
72.         return true;
    
73. }
    
74. 
    
75. void list_clear(list_t list)
    
76. {
    
77.         while(!list_empty(list))
    
78.                 list_delete(list, 0);
    
79. }
    
80. 
    
81. bool list_empty(list_t list)
    
82. {
    
83.         return !list_length(list);
    
84. }
    
85. 
    
86. size_t list_length(list_t list)
    
87. {
    
88.         return list->length;
    
89. }
    
90. 
    
91. bool list_locate(list_t list, list_elem_t e)
    
92. {
    
93.         for(size_t i = 0; i < list_length(list); ++i)
    
94.         {
    
95.                 list_elem_t elem;
    
96.                 list_get(list, i, &elem);
    
97.                 if(elem == e)
    
98.                         return true;
    
99.         }
    
100.         return false;
     
101. }
     
102. 
     
103. list_t list_clone(list_t list)
     
104. {
     
105.         list_t clone = list_init();
     
106.         for(size_t i = 0; i < list_length(list); ++i)
     
107.         {
     
108.                 list_elem_t e;
     
109.                 list_get(list, i, &e);
     
110.                 list_append(clone, e);
     
111.         }
     
112.         return clone;
     
113. }

复制代码

graph.h

1. #ifndef _GRAPH_H_
   
2. #define _GRAPH_H_
   
3. 
   
4. #include "list.h"
   
5. 
   
6. typedef char graph_elem_t;
   
7. 
   
8. typedef struct
   
9. {
   
10.         graph_elem_t v;
    
11.         list_t vs;
    
12. } graph_node_t;
    
13. 
    
14. typedef struct graph_tag
    
15. {
    
16.         graph_node_t *node;
    
17.         size_t length;
    
18. } *graph_t;
    
19. 
    
20. graph_t graph_init(void);
    
21. void graph_deinit(graph_t graph);
    
22. void graph_insert(graph_t graph, graph_elem_t v, const char *vs);
    
23. void graph_clear(graph_t graph);
    
24. 
    
25. typedef list_t path_t;
    
26. typedef list_elem_t graph_vertex_t;
    
27. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path);
    
28. void graph_print_path(path_t path);
    
29. void graph_free_path(path_t path);
    
30. 
    
31. #endif

复制代码

graph.c

1. #include "graph.h"
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. graph_t graph_init(void)
   
6. {
   
7.         graph_t graph = malloc(sizeof(struct graph_tag));
   
8.         graph->length = 0;
   
9.         graph->node = NULL;
   
10.         return graph;
    
11. }
    
12. 
    
13. void graph_deinit(graph_t graph)
    
14. {
    
15.         graph_clear(graph);
    
16.         free(graph);
    
17. }
    
18. 
    
19. void graph_insert(graph_t graph, graph_elem_t v, const char *vs)
    
20. {
    
21.         ++graph->length;
    
22.         graph->node = realloc(graph->node, sizeof(graph_node_t) * graph->length);
    
23.         graph->node[graph->length - 1].v = v;
    
24.         graph->node[graph->length - 1].vs = list_init();
    
25.         for(size_t i = 0; vs[i]; ++i)
    
26.                 list_append(graph->node[graph->length - 1].vs, vs[i]);
    
27. }
    
28. 
    
29. void graph_clear(graph_t graph)
    
30. {
    
31.         for(size_t i = 0; i < graph->length; ++i)
    
32.                 list_deinit(graph->node[i].vs);
    
33.         free(graph->node);
    
34.         graph->node = NULL;
    
35.         graph->length = 0;
    
36. }
    
37. 
    
38. static list_t get_vs(graph_t graph, graph_vertex_t v)
    
39. {
    
40.         for(size_t i = 0; i < graph->length; ++i)
    
41.         {
    
42.                 if(graph->node[i].v == v)
    
43.                         return graph->node[i].vs;
    
44.         }
    
45.         return NULL;
    
46. }
    
47. 
    
48. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path)
    
49. {
    
50.         if(!path)
    
51.                 path = list_init();
    
52. 
    
53.         list_append(path, start);
    
54.         if(start == end)
    
55.                 return path;
    
56. 
    
57.         list_t shortest = NULL;
    
58. 
    
59.         list_t vs = get_vs(graph, start);
    
60.         for(size_t i = 0; i < list_length(vs); ++i)
    
61.         {
    
62.                 graph_vertex_t node;
    
63.                 list_get(vs, i, &node);
    
64.                 if(!list_locate(path, node))
    
65.                 {
    
66.                         path_t newpath = graph_find_shortest_path(graph, node, end, list_clone(path));
    
67.                         if(!list_empty(newpath))
    
68.                         {
    
69.                                 if(!shortest || list_length(newpath) < list_length(shortest))
    
70.                                 {
    
71.                                         if(shortest)
    
72.                                                 list_deinit(shortest);
    
73.                                         shortest = list_clone(newpath);
    
74.                                 }
    
75.                                 list_deinit(newpath);
    
76.                         }
    
77.                 }
    
78.         }
    
79.         return shortest;
    
80. }
    
81. 
    
82. void graph_print_path(path_t path)
    
83. {
    
84.         for(size_t i = 0; i < path->length; ++i)
    
85.         {
    
86.                 list_elem_t e;
    
87.                 list_get(path, i, &e);
    
88.                 printf("%c ", e);
    
89.         }
    
90.         printf("\n");
    
91. }
    
92. 
    
93. void graph_free_path(path_t path)
    
94. {
    
95.         list_deinit(path);
    
96. }

复制代码

main.c

1. #include "graph.h"
   
2. 
   
3. int main(void)
   
4. {
   
5.         graph_t graph = graph_init();
   
6.         graph_insert(graph, 'A', "BCF");
   
7.         graph_insert(graph, 'B', "E");
   
8.         graph_insert(graph, 'C', "EF");
   
9.         graph_insert(graph, 'D', "E");
   
10.         graph_insert(graph, 'E', "G");
    
11.         graph_insert(graph, 'F', "H");
    
12.         graph_insert(graph, 'G', "H");
    
13.        
    
14.         path_t path = graph_find_shortest_path(graph, 'A', 'H', NULL);
    
15.         graph_print_path(path);
    
16.         graph_free_path(path);
    
17. 
    
18.         graph_deinit(graph);
    
19.         return 0;
    
20. }

复制代码

人造人

“2.
C语言中没办法像这样静态初始化（编译时初始化），所以只能运行时初始化了”

我后来想了想，用字符串的话也许可以做到静态初始化，但是在这之前我想了好久也想不到如何静态初始化（当然那时还没有引入字符串）
不管怎么说，反正代码已经写完了，就不改了
bug当然还要修复
^_^

wp231957

人造人 发表于 2020-2-12 02:43
“2.
C语言中没办法像这样静态初始化（编译时初始化），所以只能运行时初始化了”

十分感谢

人造人

只添加了一条语句

1. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path)
   
2. {
   
3.         if(!path)
   
4.                 path = list_init();
   
5. 
   
6.         list_append(path, start);
   
7.         if(start == end)
   
8.                 return path;
   
9. 
   
10.         list_t shortest = NULL;
    
11. 
    
12.         list_t vs = get_vs(graph, start);
    
13.         for(size_t i = 0; i < list_length(vs); ++i)
    
14.         {
    
15.                 graph_vertex_t node;
    
16.                 list_get(vs, i, &node);
    
17.                 if(!list_locate(path, node))
    
18.                 {
    
19.                         path_t newpath = graph_find_shortest_path(graph, node, end, list_clone(path));
    
20.                         if(!list_empty(newpath))
    
21.                         {
    
22.                                 if(!shortest || list_length(newpath) < list_length(shortest))
    
23.                                 {
    
24.                                         if(shortest)
    
25.                                                 list_deinit(shortest);
    
26.                                         shortest = list_clone(newpath);
    
27.                                 }
    
28.                                 list_deinit(newpath);
    
29.                         }
    
30.                 }
    
31.         }
    
32.         list_deinit(path);                // 这个path需要销毁
    
33.         return shortest;
    
34. }

复制代码

人造人

还有，你这个代码不能搜索 A 到 D  ?
我解决了我的代码的内存泄漏问题后，我就是好奇我的代码能不能搜索其他路径，然后发现报错，试了几个都报错，我又试了你的代码，也报错

wp231957

人造人 发表于 2020-2-12 12:51
还有，你这个代码不能搜索 A 到 D  ?
我解决了我的代码的内存泄漏问题后，我就是好奇我的代码能不能搜索其 ...

一样的，我不太懂  图这个数据结构  代码都是网上copy的

不知道这种情况下  这个d  属于什么状态   因为他和别人是不闭合的   所以 涉及到d的路径  都是报错的

如果d是可以走的   那么1楼代码就是问题代码

人造人

wp231957 发表于 2020-2-12 12:58
一样的，我不太懂  图这个数据结构  代码都是网上copy的

不知道这种情况下  这个d  属于什么状态    ...

嗯，一样的，图我学的也不好，这个问题就这样了
^_^

人造人

我还是忍不住又捡起了这个问题来研究，^_^

报错的原因我弄明白了

1. 
   
2. graph = {'A': ['B', 'C',"F"],
   
3.              'B': ['E'],
   
4.              'C': ['E',"F"],
   
5.              'D': ['E'],
   
6.              'E': ['G'],
   
7.              'F': ['H'],
   
8.              "G":["H"]}
   
9. 
   
10. def find_shortest_path(graph, start, end, path=[]):
    
11.         path = path + [start]
    
12.         if start == end:
    
13.             return path
    
14.         shortest = None
    
15.         for node in graph[start]:
    
16.             if node not in path:
    
17.                 newpath = find_shortest_path(graph, node, end, path)
    
18.                 print(newpath)
    
19.                 if newpath!=None:
    
20.                     if not shortest or len(newpath) < len(shortest):
    
21.                         shortest = newpath
    
22.         return shortest
    
23.         
    
24. print(find_shortest_path(graph, 'A', 'H'))
    

复制代码

1. 
   
2. ['A', 'B', 'E', 'G', 'H']
   
3. ['A', 'B', 'E', 'G', 'H']
   
4. ['A', 'B', 'E', 'G', 'H']
   
5. ['A', 'B', 'E', 'G', 'H']
   
6. ['A', 'C', 'E', 'G', 'H']
   
7. ['A', 'C', 'E', 'G', 'H']
   
8. ['A', 'C', 'E', 'G', 'H']
   
9. ['A', 'C', 'F', 'H']
   
10. ['A', 'C', 'F', 'H']
    
11. ['A', 'C', 'F', 'H']
    
12. ['A', 'F', 'H']
    
13. ['A', 'F', 'H']
    
14. ['A', 'F', 'H']
    

复制代码

这是这个算法对这个数据结构的所有搜索结果
可以看到，里面根本就没有 A - D 的路径

问题是 E 连着 D，但是graph这个数据结构中却没有说明
'E': ['G']
这个数据结构中只说明 E 连着 G，当然通过推导可以得到 E 连着 D，问题是这个算法中没有包含推导的代码


弄明白了问题所在，要得到解决方案也就简单了
只要把数据结构改成下面这样就可以了，把每一个顶点的对应关系都描述清楚就行了

1. 
   
2. graph = {
   
3.         'A': ['B', 'C', 'F'],
   
4.         'B': ['A', 'E'],
   
5.         'C': ['A', 'E', 'F'],
   
6.         'D': ['E'],
   
7.         'E': ['B', 'C', 'D', 'G'],
   
8.         'F': ['A', 'C', 'H'],
   
9.         'G': ['E', 'H'],
   
10.         'H': ['F', 'G']
    
11. }
    
12. 
    
13. 
    
14. def find_shortest_path(graph, start, end, path=[]):
    
15.         path = path + [start]
    
16.         if start == end:
    
17.             return path
    
18.         shortest = None
    
19.         for node in graph[start]:
    
20.             if node not in path:
    
21.                 newpath = find_shortest_path(graph, node, end, path)
    
22.                 if newpath!=None:
    
23.                     if not shortest or len(newpath) < len(shortest):
    
24.                         shortest = newpath
    
25.         return shortest
    
26.         
    
27. print(find_shortest_path(graph, 'A', 'D'))
    

复制代码

1. 
   
2. ['A', 'B', 'E', 'D']
   

复制代码

但是这样完整的说明对人类很不友好，这个问题也好解决
解决方案是
数据结构还是用简写，也就是下面这样

1. graph = {'A': ['B', 'C',"F"],
   
2.              'B': ['E'],
   
3.              'C': ['E',"F"],
   
4.              'D': ['E'],
   
5.              'E': ['G'],
   
6.              'F': ['H'],
   
7.              "G":["H"]}

复制代码

然后再写一个函数，用代码把这个简写的形式转换成完整的形式

我没有用python写转换函数，我还是在原来的C代码基础上写了转换函数，如果你愿意，你可以用python写一下转换函数，让我看看python中做这个转换有多么容易，^_^

这次修改了3个文件，main.c, graph.c, graph.h
list.c 和 list.h 没有改变，就不贴代码了

main.c

1. #include "graph.h"
   
2. 
   
3. int main(void)
   
4. {
   
5.         graph_t graph = graph_init();
   
6.         graph_insert(graph, 'A', "BCF");
   
7.         graph_insert(graph, 'B', "E");
   
8.         graph_insert(graph, 'C', "EF");
   
9.         graph_insert(graph, 'D', "E");
   
10.         graph_insert(graph, 'E', "G");
    
11.         graph_insert(graph, 'F', "H");
    
12.         graph_insert(graph, 'G', "H");
    
13.         graph_format(graph);
    
14.        
    
15.         path_t path = graph_find_shortest_path(graph, 'A', 'D', NULL);
    
16.         graph_print_path(path);
    
17.         graph_free_path(path);
    
18. 
    
19.         graph_deinit(graph);
    
20.         return 0;
    
21. }

复制代码

graph.h

1. #ifndef _GRAPH_H_
   
2. #define _GRAPH_H_
   
3. 
   
4. #include "list.h"
   
5. 
   
6. typedef char graph_elem_t;
   
7. 
   
8. typedef struct
   
9. {
   
10.         graph_elem_t v;
    
11.         list_t vs;
    
12. } graph_node_t;
    
13. 
    
14. typedef struct graph_tag
    
15. {
    
16.         graph_node_t *node;
    
17.         size_t length;
    
18. } *graph_t;
    
19. 
    
20. graph_t graph_init(void);
    
21. void graph_deinit(graph_t graph);
    
22. void graph_insert(graph_t graph, graph_elem_t v, const char *vs);
    
23. void graph_clear(graph_t graph);
    
24. size_t graph_length(graph_t graph);
    
25. bool graph_locate(graph_t graph, graph_elem_t v);
    
26. 
    
27. typedef list_t path_t;
    
28. typedef list_elem_t graph_vertex_t;
    
29. void graph_format(graph_t graph);
    
30. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path);
    
31. void graph_print_path(path_t path);
    
32. void graph_free_path(path_t path);
    
33. 
    
34. #endif

复制代码

graph.c

1. #include "graph.h"
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. graph_t graph_init(void)
   
6. {
   
7.         graph_t graph = malloc(sizeof(struct graph_tag));
   
8.         graph->length = 0;
   
9.         graph->node = NULL;
   
10.         return graph;
    
11. }
    
12. 
    
13. void graph_deinit(graph_t graph)
    
14. {
    
15.         graph_clear(graph);
    
16.         free(graph);
    
17. }
    
18. 
    
19. void graph_insert(graph_t graph, graph_elem_t v, const char *vs)
    
20. {
    
21.         ++graph->length;
    
22.         graph->node = realloc(graph->node, sizeof(graph_node_t) * graph->length);
    
23.         graph->node[graph->length - 1].v = v;
    
24.         graph->node[graph->length - 1].vs = list_init();
    
25.         for(size_t i = 0; vs[i]; ++i)
    
26.                 list_append(graph->node[graph->length - 1].vs, vs[i]);
    
27. }
    
28. 
    
29. void graph_clear(graph_t graph)
    
30. {
    
31.         for(size_t i = 0; i < graph_length(graph); ++i)
    
32.                 list_deinit(graph->node[i].vs);
    
33.         free(graph->node);
    
34.         graph->node = NULL;
    
35.         graph->length = 0;
    
36. }
    
37. 
    
38. size_t graph_length(graph_t graph)
    
39. {
    
40.         return graph->length;
    
41. }
    
42. 
    
43. bool graph_locate(graph_t graph, graph_elem_t v)
    
44. {
    
45.         for(size_t i = 0; i < graph_length(graph); ++i)
    
46.         {
    
47.                 if(graph->node[i].v == v)
    
48.                         return true;
    
49.         }
    
50.         return false;
    
51. }
    
52. 
    
53. static list_t get_vs(graph_t graph, graph_vertex_t v)
    
54. {
    
55.         for(size_t i = 0; i < graph_length(graph); ++i)
    
56.         {
    
57.                 if(graph->node[i].v == v)
    
58.                         return graph->node[i].vs;
    
59.         }
    
60.         return NULL;
    
61. }
    
62. 
    
63. void graph_format(graph_t graph)
    
64. {
    
65.         for(size_t i = 0; i < graph_length(graph); ++i)
    
66.         {
    
67.                 for(size_t j = 0; j < graph_length(graph); ++j)
    
68.                 {
    
69.                         if(i != j)
    
70.                         {
    
71.                                 for(size_t k = 0; k < list_length(graph->node[j].vs); ++k)
    
72.                                 {
    
73.                                         list_elem_t e;
    
74.                                         list_get(graph->node[j].vs, k, &e);
    
75.                                         if(graph->node[i].v == e)
    
76.                                         {
    
77.                                                 if(!list_locate(graph->node[i].vs, graph->node[j].v))
    
78.                                                         list_append(graph->node[i].vs, graph->node[j].v);
    
79.                                                 break;
    
80.                                         }
    
81.                                         if(!graph_locate(graph, e))
    
82.                                                 graph_insert(graph, e, "");
    
83.                                 }
    
84.                         }
    
85.                 }
    
86.         }
    
87. }
    
88. 
    
89. path_t graph_find_shortest_path(graph_t graph, graph_vertex_t start, graph_vertex_t end, path_t path)
    
90. {
    
91.         if(!path)
    
92.                 path = list_init();
    
93. 
    
94.         list_append(path, start);
    
95.         if(start == end)
    
96.                 return path;
    
97. 
    
98.         list_t shortest = NULL;
    
99. 
    
100.         list_t vs = get_vs(graph, start);
     
101.         for(size_t i = 0; i < list_length(vs); ++i)
     
102.         {
     
103.                 graph_vertex_t node;
     
104.                 list_get(vs, i, &node);
     
105.                 if(!list_locate(path, node))
     
106.                 {
     
107.                         path_t newpath = graph_find_shortest_path(graph, node, end, list_clone(path));
     
108.                         if(!list_empty(newpath))
     
109.                         {
     
110.                                 if(!shortest || list_length(newpath) < list_length(shortest))
     
111.                                 {
     
112.                                         if(shortest)
     
113.                                                 list_deinit(shortest);
     
114.                                         shortest = list_clone(newpath);
     
115.                                 }
     
116.                         }
     
117.                         list_deinit(newpath);
     
118.                 }
     
119.         }
     
120.         list_deinit(path);                // 这个path需要销毁
     
121.         if(!shortest)
     
122.                 shortest = list_init();
     
123.         return shortest;
     
124. }
     
125. 
     
126. void graph_print_path(path_t path)
     
127. {
     
128.         for(size_t i = 0; i < list_length(path); ++i)
     
129.         {
     
130.                 list_elem_t e;
     
131.                 list_get(path, i, &e);
     
132.                 printf("%c ", e);
     
133.         }
     
134.         printf("\n");
     
135. }
     
136. 
     
137. void graph_free_path(path_t path)
     
138. {
     
139.         list_deinit(path);
     
140. }

复制代码

wp231957

人造人 发表于 2020-2-12 15:44
我还是忍不住又捡起了这个问题来研究，^_^

报错的原因我弄明白了

谢谢我会一一测试的