[关闭]
@skyword 2017-06-03T02:59:46.000000Z 字数 7048 阅读 176

第十一次上机报告


问题描述

邻接表存图

  1. 实现基本函数和测试函数,以8-17为例
  2. 设计邻接表存图下的DFS,BFS函数
  3. 编写删除结点的函数

处理思路

邻接表存图:对于图中每个结点,维护一个链表,存储该点的各个邻接点
DFS:深度优先搜索,在每个结点,沿每条路径向内遍历并输出,没有后继结点时回溯
BFS:队列实现
删除点:首先对于要删除的点u,查找所有的邻接点v,调用删边函数delete_edge(u,v)。其次对于所有其他结点v,查找其邻接点中是否有u,若有,删除边(v,u),最后G->V--,即图中结点数目减一

代码设计

ADJD.h

main.cpp 测试主程序
没有额外函数

程序代码

ADJD.h

  1. #ifndef ADJD_H_INCLUDED
  2. #define ADJD_H_INCLUDED
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <queue>
  6. using namespace std;
  7. #define Max_V 20
  8. typedef struct node
  9. {
  10. int head;
  11. node* nxt;
  12. } edge; //for edge in adj_graph
  13. typedef struct
  14. {
  15. char val;
  16. int start;
  17. edge* adj;//head node of adj list for each node
  18. } Adj_List_Ele;
  19. typedef struct
  20. {
  21. int V;
  22. int E;
  23. Adj_List_Ele L[Max_V];
  24. void Adj_Graph_Init();
  25. void Adj_Destroy();
  26. void print();
  27. void print_vertex(int index, int type);
  28. void Adj_Delete_Vertex(int index);
  29. } Adj_Graph;
  30. void Adj_Graph::Adj_Graph_Init()
  31. {
  32. this->E = 0;
  33. this->V = 0;
  34. for(int i = 0; i < Max_V; i++)//that is, we number vertex from 0
  35. {
  36. this->L[i].adj = NULL;
  37. this->L[i].start = i;
  38. }
  39. }
  40. void Adj_Graph::Adj_Destroy()
  41. {
  42. edge* p,* q;
  43. for(int i = 0; i < this->V; i++)
  44. {
  45. p = this->L[i].adj;
  46. while(p != NULL)
  47. {
  48. q = p->nxt;
  49. free(p);
  50. p = q;
  51. }
  52. }
  53. }
  54. void Adj_Insert_Vertex(Adj_Graph* G, int index, char val)//add a vertex whose value = val, numbered index.
  55. {
  56. if(index >= 0 && index < Max_V)
  57. {
  58. G->L[index].val = val;
  59. G->V ++;
  60. }
  61. else printf("Add vertex failed. Its index should between 0 ~ %d.\n",Max_V-1);
  62. }
  63. void Adj_Insert_Edge(Adj_Graph* G, int s, int t)//add an edge from s to t
  64. {
  65. if(s < 0 || t < 0 || s >= G->V || t >= G->V)
  66. {
  67. printf("Add edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);
  68. return;
  69. }
  70. edge* p;
  71. p = (edge*)malloc(sizeof(edge));
  72. p->head = t;
  73. p->nxt = G->L[s].adj;
  74. G->L[s].adj = p;
  75. G->E ++;
  76. }
  77. void Adj_Delete_Edge(Adj_Graph* G, int s, int t, int type)//delete edge from s to t
  78. //Here, type is operation type; type = 0 means using this function manually, type = 1 means using this function by other functions
  79. {
  80. if(s < 0 || t < 0 || s >= G->V || t >= G->V)
  81. {
  82. printf("Delete edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);
  83. return;
  84. }
  85. edge* pre, *now;
  86. pre = NULL;
  87. now = G->L[s].adj;
  88. while(now != NULL && now->head != t)
  89. {
  90. pre = now;
  91. now = now->nxt;
  92. }
  93. if(now != NULL && pre == NULL && now->head == t)//pre is null means t is the first link-node of v1
  94. {
  95. G->L[s].adj = now->nxt;
  96. free(now);
  97. G->E --;
  98. }
  99. else if(now != NULL && now->head == t)//we find t, but t is not the first link-node of v1
  100. {
  101. pre->nxt = now->nxt;//jump off "now"
  102. free(now);
  103. G->E --;
  104. }
  105. else
  106. {
  107. if(type == 0)printf("There isn't an edge from %d to %d, though graph G has these two vertexes in it.\n",s,t);
  108. }
  109. }
  110. int Adj_GetFirst(Adj_Graph* G, int index)//get the first node of v
  111. {
  112. if(index < 0 || index >= G->V)printf("The index should between 0 and %d.\n",(G->V)-1);
  113. edge* p;
  114. p = G->L[index].adj;
  115. if(p == NULL)return -1;
  116. else return p->head;
  117. }
  118. int Adj_GetSecond(Adj_Graph* G, int index1, int index2)
  119. {
  120. if(index1 < 0 || index1 >= G->V || index2 < 0 || index2 >= G->V)
  121. {
  122. printf("The index should between 0 and %d.\n",(G->V)-1);
  123. return 0;
  124. }
  125. edge* p;
  126. p = G->L[index1].adj;
  127. while(p->head != NULL)
  128. {
  129. if(p->head != index2)
  130. {
  131. p = p->nxt;
  132. }
  133. else break;
  134. }
  135. p = p->nxt;
  136. if(p != NULL)return p->head;
  137. else return -1;
  138. }
  139. void Adj_Graph::Adj_Delete_Vertex(int index)//delete single vertex in graph
  140. {
  141. if(index < 0 || index >= this->V)
  142. {
  143. printf("The index should between 0 and %d.\n",(this->V)-1);
  144. return;
  145. }
  146. edge* e;
  147. e = this->L[index].adj;
  148. while(e != NULL)
  149. {
  150. Adj_Delete_Edge(this, index, e->head, 1);
  151. e = e->nxt;
  152. }
  153. //cout<<"****"<<endl;
  154. for(int i = 0; i < this->V; i++)
  155. {
  156. if(i == index)continue;
  157. e = this->L[i].adj;
  158. while(e != NULL)
  159. {
  160. if(e->head != index)
  161. e = e->nxt;
  162. else
  163. {
  164. Adj_Delete_Edge(this, i, e->head, 1);
  165. break;
  166. }
  167. }
  168. }
  169. this->L[index].val='#';
  170. /*
  171. for(int i = 0; i < this->V; i++)
  172. {
  173. if(i != index)continue;
  174. //now i == index
  175. else
  176. {
  177. for(int j = i+1; j < this->V; j++)
  178. {
  179. this->L[j-1] = this->L[j];
  180. //int now = this->L[j-1].adj->nxt->head;
  181. //printf("****%c ",this->L[now].val);
  182. }
  183. break;
  184. }
  185. }
  186. */
  187. //this->V--;
  188. }
  189. void Adj_Graph::print()
  190. //print graph by order following: print each link-node for each node ordered by index
  191. {
  192. for(int i = 0; i < this->V; i++)
  193. {
  194. if(this->L[i].val == '#')continue;
  195. printf("Vertex #%d : %c \n",i,this->L[i].val);
  196. printf("It's suffix vertex: ");
  197. edge* n;
  198. n = (edge*)malloc(sizeof(edge));
  199. n = this->L[i].adj;
  200. int cnt = 0;
  201. while(n != NULL)
  202. {
  203. cnt++;
  204. int now = n->head;
  205. n = n->nxt;
  206. printf("%c ",this->L[now].val);
  207. }
  208. if(cnt == 0)printf("empty.");
  209. printf("\n");
  210. }
  211. }
  212. void Adj_Graph::print_vertex(int index, int type)
  213. //print single vertex of graph, type = 0 means manually using, type = 1 means by other functions
  214. {
  215. char c = this->L[index].val;
  216. if(c == '#')return;
  217. else printf("%c",this->L[index].val);
  218. if(type == 0)printf("\n");
  219. else printf(" ");
  220. }
  221. //Search by DFS and BFS
  222. void Adj_DFS(Adj_Graph* G, int v, int vis[])
  223. {
  224. int nxt;
  225. vis[v] = 1;
  226. G->print_vertex(v, 1);
  227. nxt = Adj_GetFirst(G, v);
  228. while(nxt != -1)
  229. {
  230. if(vis[nxt] == 0) Adj_DFS(G, nxt, vis);
  231. nxt = Adj_GetSecond(G, v, nxt);
  232. }
  233. }
  234. void Adj_BFS(Adj_Graph* G, int v, int vis[])
  235. {
  236. int u,w;
  237. queue<int>q;
  238. vis[v] = 1;
  239. G->print_vertex(v, 1);
  240. q.push(v);
  241. while(!q.empty())
  242. {
  243. u = q.front();
  244. q.pop();
  245. w = Adj_GetFirst(G, u);
  246. while(w != -1)
  247. {
  248. if(vis[w] == 0)
  249. {
  250. vis[w] = 1;
  251. G->print_vertex(w, 1);
  252. q.push(w);
  253. }
  254. w = Adj_GetSecond(G, u, w);
  255. }
  256. }
  257. }
  258. #endif // ADJD_H_INCLUDED

main.cpp

  1. #include <malloc.h>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <cstring>
  5. #include "ADJD.h"
  6. using namespace std;
  7. int vis[20]={0};
  8. int main()
  9. {
  10. Adj_Graph* G;
  11. G = (Adj_Graph*)malloc(sizeof(Adj_Graph));
  12. G->Adj_Graph_Init();
  13. //Insert 6 vertexes as the graph described.
  14. for(int i = 0; i < 6; i++)
  15. {
  16. char c = 'A'+i;
  17. Adj_Insert_Vertex(G, i, c);
  18. }
  19. Adj_Insert_Edge(G, 5, 0); Adj_Insert_Edge(G, 4, 0); Adj_Insert_Edge(G, 0, 1);
  20. Adj_Insert_Edge(G, 2, 1); Adj_Insert_Edge(G, 3, 2); Adj_Insert_Edge(G, 1, 3);
  21. Adj_Insert_Edge(G, 3, 4); Adj_Insert_Edge(G, 5, 4); Adj_Insert_Edge(G, 1, 5);
  22. Adj_Insert_Edge(G, 2, 5); Adj_Insert_Edge(G, 3, 5);
  23. G->print();
  24. //Illegally adding vertex
  25. Adj_Insert_Vertex(G, 21, 'd');
  26. //Illegally adding edge
  27. Adj_Insert_Edge(G, 5, 9);
  28. //Delete an edge,legally and illegally
  29. //printf("Delete edge from 0 to 1.\n");
  30. //Adj_Delete_Edge(G, 0, 1, 0);
  31. //G->print();
  32. //Adj_Delete_Edge(G, 0, 1, 0);
  33. //Adj_Delete_Edge(G, 0, 9, 0);
  34. //printf("**%d",Adj_GetFirst(G, 0));
  35. printf("DFS-order of G: \n");
  36. Adj_DFS(G, 0, vis);
  37. printf("\n");
  38. memset(vis, 0 , sizeof(vis));
  39. printf("BFS-order of G: \n");
  40. Adj_BFS(G, 0, vis);
  41. printf("\n");
  42. G->Adj_Delete_Vertex(0);
  43. G->print();
  44. }

测试结果

基本函数

  1. Vertex #0 : A
  2. It's suffix vertex: B
  3. Vertex #1 : B
  4. It's suffix vertex: F D
  5. Vertex #2 : C
  6. It's suffix vertex: F B
  7. Vertex #3 : D
  8. It's suffix vertex: F E C
  9. Vertex #4 : E
  10. It's suffix vertex: A
  11. Vertex #5 : F
  12. It's suffix vertex: E A
  13. Add vertex failed. Its index should between 0 ~ 19.
  14. Add edge failed. The index of these two vertex should between 0 ~ 5.
  15. Delete edge from 0 to 1.
  16. Vertex #0 : A
  17. It's suffix vertex: empty.
  18. Vertex #1 : B
  19. It's suffix vertex: F D
  20. Vertex #2 : C
  21. It's suffix vertex: F B
  22. Vertex #3 : D
  23. It's suffix vertex: F E C
  24. Vertex #4 : E
  25. It's suffix vertex: A
  26. Vertex #5 : F
  27. It's suffix vertex: E A
  28. There isn't an edge from 0 to 1, though graph G has these two vertexes in it.
  29. Delete edge failed. The index of these two vertex should between 0 ~ 5.

搜索

  1. Vertex #0 : A
  2. It's suffix vertex: B
  3. Vertex #1 : B
  4. It's suffix vertex: F D
  5. Vertex #2 : C
  6. It's suffix vertex: F B
  7. Vertex #3 : D
  8. It's suffix vertex: F E C
  9. Vertex #4 : E
  10. It's suffix vertex: A
  11. Vertex #5 : F
  12. It's suffix vertex: E A
  13. DFS-order of G:
  14. A B F E D C
  15. BFS-order of G:
  16. A B F D E C
  17. Process returned 0 (0x0) execution time : 0.034 s
  18. Press any key to continue.

删点

  1. Delete vertex F
  2. Vertex #0 : A
  3. It's suffix vertex: B
  4. Vertex #1 : B
  5. It's suffix vertex: D
  6. Vertex #2 : C
  7. It's suffix vertex: B
  8. Vertex #3 : D
  9. It's suffix vertex: E C
  10. Vertex #4 : E
  11. It's suffix vertex: A
  12. Process returned 0 (0x0) execution time : 0.022 s
  13. Press any key to continue.
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注