请教各位大神一个关于C语言中有向图的问题~~~

七夜未央

最近碰到一个比较复杂的数据结构问题，感觉和C里面的有向图的结构差不多的，自己写了一下，感觉很多地方都写得不是很合理，请教高人写一个创建此图的方法。

结构图大致如下：


// 节点struct定义如下：
struct Spoint
{
    int id;
    char name[10];
    Spoint *next;// 指向下一个节点
   Spoint *father;// 指向父节点
   Special *special;// 特殊节点，当一个节点有两个以上的父节点的时候则使用此链描述
};

结合上图以及上面的struct说明如下：
黑色的线代表的是next指针指向；蓝色的线代表的是father指针指向；红色的线是当一个节点有两个以上的前驱节点时使用的特殊节点special指针；

//特殊节点struct
struct Special
{
    Spoint *point;// point指针指向的是某个Spoint节点，如上图，类似g节点才会有Special的结构，而point指向e

    Spoint *next;// next指针指向的是下一个特殊节点，如上图，next指向的下一个特殊Special结构的point指针指向的是f的地址
};

数据源如下：
struct SourceData
{
    int id;
    char name[10];
    long pointId[100];// 这里记录的是每个节点的前驱节点的id号，最少有一个，最多100个，当只有一个的时候那么就表示该节点存在一个father节点，如果大于1，则表示该节点不存在 father节点了，而是特殊节点；
};

int main()
{
    vector<SourceData> vecData;// 假设数据源已经都放入到此vector中了

    for(int i = 0; i < vecData.size(); i++)
     {
          Create(vecData);
     }
}

// 那么我这里需要根据数据源生成一个类似上图中那样的结构,然后将链表头指针返回
Spoint * Create(vecData &data)
{
   
}

请大牛帮忙实现以下create函数，谢谢了~

yulihua49

七夜未央 发表于 2013-01-25 21:03
最近碰到一个比较复杂的数据结构问题，感觉和C里面的有向图的结构差不多的，自己写了一下，感觉很多地方都写 ...

father可以不要，问题更简单一些。
以vecData.size();尺寸分配一个spoint数组。
对于spoint数组的每个成员，用strtok分解priontId，填入special链表。
最后遍历数组，填写next。如果多重后继，next也应是链表。

folklore

1. struct gnote{
   
2. int id;
   
3. // void *pdata;
   
4. struct forwardlist{struct gnote *pgnext;struct forwardlist *next;} *next;
   
5. };

复制代码

七夜未央

回复 2# yulihua49
感谢回复，但是father链必须得要呢，如果没这条链的话那么就无法得知前驱节点的状态，需求就这么恶心{:3_188:}

   

yulihua49

七夜未央 发表于 2013-01-26 11:16
回复 2# yulihua49
感谢回复，但是father链必须得要呢，如果没这条链的话那么就无法得知前驱节点的状态， ...

father放在special里即可。
也可以用map，以id为key。
这样不必预先分配数组，随时加入新节点。
最后遍历next时，检索id也很方便。

captivated

要表示图，需要表示顶点和边。要么用矩阵，要么用邻接表，要么直接用内核链表那种节点做十字交叉链。
LZ用表示树的想法来表示图，感觉怪怪。。。

两个表示图的数据结构示例，首先是矩阵表示法。。。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #define VERTEX_NUM        8
   
6. 
   
7. // 矩阵记录每个顶点的连通状况.
   
8. // edge_cnt记录有多少条边.
   
9. typedef struct _graph graph_t;
   
10. 
    
11. struct _graph {
    
12.         int edge[VERTEX_NUM][VERTEX_NUM];  // 边
    
13.         int edge_cnt;                      // 边计数
    
14.         int visited[VERTEX_NUM];           // 顶点访问信息
    
15. };
    
16. 
    
17. // 创建图.
    
18. graph_t *graph_create(void)
    
19. {
    
20.         graph_t *thiz = malloc(sizeof(graph_t));
    
21.         if (NULL == thiz)
    
22.                 return NULL;
    
23. 
    
24.         int i, j;
    
25.         for (i = 0; i < VERTEX_NUM; i++)
    
26.                 for (j = 0; j < VERTEX_NUM; j++)
    
27.                 {
    
28.                         thiz->edge[i][j] = 0;       
    
29.                 }
    
30.         thiz->edge_cnt = 0;
    
31. 
    
32.         return thiz;
    
33. }
    
34. 
    
35. // 增加一条边, 也即将矩阵中沿反对角线对称的两个点位置1.
    
36. // 这个图是无向的.
    
37. void graph_add_edge(graph_t *thiz, int from, int to)
    
38. {
    
39.         thiz->edge[from][to] = 1;
    
40.         thiz->edge[to][from] = 1;
    
41.         thiz->edge_cnt++;
    
42. }
    
43. 
    
44. // 深度优先(depth first search/traverse)搜索/遍历
    
45. void __graph_dfs(graph_t *thiz, int start)
    
46. {
    
47.         // 访问的动作就是将该顶点值(其索引)打印.
    
48.         printf("%d ", start);
    
49. 
    
50.         // 已访问顶点要置位标记
    
51.         thiz->visited[start] = 1;
    
52. 
    
53.         // edge[start][i]为1则表示边存在(可访问)
    
54.         int i;
    
55.         for (i = 0; i < VERTEX_NUM; i++)
    
56.         {
    
57.                 if (thiz->edge[start][i] == 1 && thiz->visited[i] == 0)       
    
58.                         __graph_dfs(thiz, i);
    
59.         }
    
60. }
    
61. 
    
62. // dfs的外覆器
    
63. void graph_dfs(graph_t *thiz, int start)
    
64. {
    
65.         memset(thiz->visited, 0, sizeof(int) * VERTEX_NUM);
    
66.         printf("start => ");
    
67.         __graph_dfs(thiz, start);
    
68.         printf("end.\n");
    
69. }

复制代码

用邻接表表示的：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #define MAX 0xffffff
   
6. 
   
7. // edge infomation, 比如, 用一条边表示两顶点之间的交通状况,
   
8. // 则速度, 交通运输类型, 两顶点之间的距离, 票价如何,etc...
   
9. typedef struct _einfo einfo_t;
   
10. struct _einfo {
    
11.         int speed;
    
12.         char traffic_style[32];
    
13.         int distance;
    
14.         int price_per_km;
    
15. };
    
16. 
    
17. // edge，表示一条边
    
18. // w: weight, 权值, 该权值如何可以根据einfo来计算
    
19. // adj: adjacent / adjacency 邻接信息, 与什么顶点相连 -- 对应于vertex中的顶点标记.
    
20. // next: 链表不用说了
    
21. typedef struct _edge edge_t;
    
22. struct _edge {
    
23.         einfo_t einfo;
    
24.         int w;
    
25.         int adj;
    
26.         edge_t *next;
    
27. };
    
28. 
    
29. // vertex infomation
    
30. // data: 顶点的标记，标示该顶点，也就是顶点的id, 就像矩阵中用数组索引下标标示顶点一样,
    
31. // 只不过这种结构更灵活一些, id是可选的一个int数值.
    
32. typedef struct _vinfo vinfo_t;
    
33. struct _vinfo {
    
34.         char name[32];
    
35.         int data;
    
36. };
    
37. 
    
38. // vertex.
    
39. // nei_cnt: how many neighours this vertex hold.
    
40. // visited: has it been visited?
    
41. // head: head pointer of edge list.
    
42. // next: next vertex
    
43. typedef struct _vertex vertex_t;
    
44. struct _vertex {
    
45.         vinfo_t vinfo;
    
46.         int nei_cnt;
    
47.         int visited;
    
48.         edge_t *head;
    
49.         vertex_t *next;
    
50. };
    
51. 
    
52. // 图结构
    
53. // 总体结构是这样的, 就是链表链链表:
    
54. // holder  -> vertex1 -> vertex2 -> vertex3 -> vertex4 -> vertex5...
    
55. //                |
    
56. //             edge1[edge结构体对象中的adj表示该vertex1和哪一个顶点相连, ex, vertex3, 那么adj就是vertex3的information的data]
    
57. //                |
    
58. //             edge2[ex, 假如这个边节点表示vertex1和vertex5相连, 那么adj就是vertex5的data]
    
59. //                |
    
60. //            edge3...
    
61. 
    
62. typedef struct _graph graph_t;
    
63. struct _graph {
    
64.         vertex_t *holder;
    
65.         int v_cnt;
    
66.         int e_cnt;
    
67. };
    
68. 
    
69. // 初始化图, 只是创建一个容器的手柄,
    
70. // 让用户自行添加顶点和边, 图的最终形状通过添加确定
    
71. graph_t *graph_create(void)
    
72. {
    
73.         graph_t *thiz = NULL;
    
74.         thiz = malloc(sizeof(graph_t));
    
75.         if (!thiz)
    
76.                 return NULL;
    
77. 
    
78.         thiz->holder = NULL;
    
79.         thiz->v_cnt = 0;
    
80.         thiz->e_cnt = 0;
    
81. 
    
82.         return thiz;
    
83. }
    
84. 
    
85. void __graph_init_vertex(vertex_t *v, vinfo_t *vinfo)
    
86. {
    
87.         memcpy(&v->vinfo, vinfo, sizeof(vinfo_t));
    
88.         v->nei_cnt = 0;
    
89.         v->head = NULL;
    
90.         v->next = NULL;
    
91.         v->visited = 0;
    
92. }
    
93. 
    
94. void graph_add_vertex(graph_t *thiz, vinfo_t *vinfo)
    
95. {
    
96.         vertex_t **cur = &thiz->holder;
    
97. 
    
98.         vertex_t *v = malloc(sizeof(vertex_t));
    
99.         if (!v)
    
100.                 return;
     
101.        
     
102.         __graph_init_vertex(v, vinfo);
     
103. 
     
104.         while (*cur)
     
105.                 cur = &(*cur)->next;
     
106.        
     
107.         *cur = v;
     
108. 
     
109.         thiz->v_cnt++;
     
110. }
     
111. 
     
112. // key是顶点标记，根据顶点标记从图中[就是顶点链表]搜索到该顶点
     
113. vertex_t *graph_search_vertex(graph_t *thiz, int key)
     
114. {
     
115.         vertex_t *t = thiz->holder;
     
116. 
     
117.         while (t) {
     
118.                 if (t->vinfo.data == key)       
     
119.                         return t;
     
120.                 t = t->next;
     
121.         }
     
122. 
     
123.         return NULL;
     
124. }
     
125. 
     
126. // 无向图, 添加边, from, to 是顶点标记
     
127. // 如果是有向图就更简单, 只要给from顶点的邻接链表中增加一个边节点即可
     
128. void graph_add_edge(graph_t *thiz, int from, int to, einfo_t *einfo)
     
129. {
     
130.         // 首先得到需要增加边的两个顶点
     
131.         vertex_t *from_v = graph_search_vertex(thiz, from);
     
132.         vertex_t *to_v = graph_search_vertex(thiz, to);
     
133. 
     
134.         // 构建edge, 加到from_v的邻接链表中
     
135.         edge_t *ef = malloc(sizeof(edge_t));
     
136.         if (!ef)
     
137.                 return;
     
138.         ef->einfo = *einfo;
     
139.         ef->adj = to;
     
140.         ef->next = NULL;
     
141. 
     
142.         edge_t **cur = &from_v->head;
     
143.         while (*cur)
     
144.                 cur = &(*cur)->next;
     
145.         *cur = ef;
     
146. 
     
147.         // 加到to_v的邻接链表中
     
148.         edge_t *et = malloc(sizeof(edge_t));
     
149.         if (!et)
     
150.         {
     
151.                 free(ef);       
     
152.                 return;
     
153.         }
     
154.         et->einfo = *einfo;
     
155.         et->adj = from;
     
156.         et->next = NULL;
     
157. 
     
158.         cur = &to_v->head;
     
159.         while (*cur)
     
160.                 cur = &(*cur)->next;
     
161.         *cur = et;
     
162. 
     
163.         from_v->nei_cnt++;
     
164.         to_v->nei_cnt++;
     
165.         thiz->e_cnt++;
     
166. }
     
167. 
     
168. void __graph_dfs(graph_t *thiz, int start)
     
169. {
     
170.         vertex_t *v = graph_search_vertex(thiz, start);
     
171. 
     
172.         if (!v)
     
173.                 return;
     
174.        
     
175.         printf("%s ", v->vinfo.name);
     
176.         v->visited = 1;
     
177. 
     
178.         edge_t *e = v->head;
     
179.         while (e)
     
180.         {
     
181.                 v = graph_search_vertex(thiz, e->adj);
     
182.                 while (v->visited == 0)
     
183.                         __graph_dfs(thiz, v->vinfo.data);
     
184.                 e = e->next;
     
185.         }
     
186. }
     
187. 
     
188. void graph_dfs(graph_t *thiz, int start)
     
189. {
     
190.         vertex_t *v = thiz->holder;
     
191. 
     
192.         while (v)
     
193.         {
     
194.                 v->visited = 0;       
     
195.                 v = v->next;
     
196.         }
     
197. 
     
198.         __graph_dfs(thiz, start);
     
199.         printf("\n");
     
200. }

复制代码

PS：代码看上去有点长。耐心点读罢。。。

captivated

。。。见楼下。

captivated

另外：

图创建并不是生成图，因为每个图都不一样。
创建图只是创建一个容器的手柄。
然后给出添加/删除顶点和边的接口。

用户拿到这个容器的手柄，然后自行添加顶点和边，他想要什么形状，就是什么形状。

如果用户想要随机生成图，那么如何随机生成是用户自己的事情，他自己得想算法。当然也可以给一个随机生成图的接口。。。

captivated

1. // 例如:
   
2. int main(void)
   
3. {
   
4.         graph_t *g = NULL;
   
5. 
   
6.         g = graph_create();
   
7. 
   
8.         int i,j;
   
9. 
   
10.         vinfo_t vinfo_ary[] = {
    
11.                 { "深圳", 1 },
    
12.                 { "重庆", 2 },
    
13.                 { "成都", 3 },
    
14.                 { "西安", 4 },
    
15.                 { "上海", 5 },
    
16.                  // ...
    
17.         };
    
18. 
    
19.         // 用户加入顶点...
    
20.         for(i = 0; i < sizeof(vinfo_ary) / sizeof(vinfo_t); i++)
    
21.         {
    
22.                 graph_add_vertex(g, vinfo_ary + i);
    
23.         }
    
24. 
    
25.         einfo_t einfo_ary[] = {
    
26.                 { 120, "train", 2000, 2 },
    
27.                 { 150, "bus", 600, 5 },
    
28.                 { 130, "train", 1200, 3 },
    
29.                 // ...
    
30.         };
    
31. 
    
32.         // 用户自行增加边, 构建图的形状
    
33.         graph_add_edge(g, 1, 2, einfo_ary);
    
34.         graph_add_edge(g, 1, 3, einfo_ary + 1);
    
35.         graph_add_edge(g, 1, 4, einfo_ary + 2);
    
36.         // ...
    
37. 
    
38.         printf("\n从各个顶点开始的深度优先遍历:\n");
    
39.         int data[] = { 1, 2, 3, 4, 5 };
    
40.         for(i = 0; i < sizeof(data) / sizeof(int); i++)
    
41.                 graph_dfs(g, data[i]);
    
42. 
    
43.         graph_destroy(g);
    
44. 
    
45.         return 0;
    
46. }

复制代码

七夜未央

回复 9# captivated

多谢高人指教，可能是我之前对图的理解不正确，以至于和需求有点偏差，不过我的问题已经解决了，谢谢各位了，呵呵~