数据结构与算法( 六)图

没有最好的数据结构,只有最适合的数据结构,没有最快的算法,只有最适合的算法。

图是一种常见的非线性数据结构,探究图,其实就是将非线性数据线性化的尝试。

图的遍历部分发现一个博客写得挺好,直接修改转过来了

http://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html

一.图定义

1.有向图:边有方向的图。 无相图:边无方向。

2.无向完全图:任两个点之间都有边的图。

3.有向完全图:任两点之间都存在两个有向边的图。

4.路径:任两个顶点之间经过的顶点序列集,长度是顶点序列之间边的的数目。

5.简单路径:路径中没有重复的顶点。

6.连通图:任两个顶点之间都存在路径的图

7.连通分量(极大连通子图):image

8.连通图的生成树:包含图中全部的顶点,但只有n-1条边

9.图可以使用2维数组来表示他们之间的关系,(邻接矩阵单元值为0,表示没有边,1表示有边)。

image

二.图的遍历

图的遍历是树的遍历的推广,是按照某种规则(或次序)访问图中各顶点依次且仅一次的操作,亦是将网络结构按某种规则线性化的过程

由于图存在回路,为区别一顶点是否被访问过和避免顶点被多次访问,在遍历过程中,应记下每个访问过的顶点,即每个顶点对应有一个标志位,初始为False,一旦该顶点被访问,就将其置为True,以后若又碰到该顶点时,视其标志的状态,而决定是否对其访问。

对图的遍历通常有”深度优先搜索“和”广度优先搜索“方法,二者是人工智能的一个基础。

深度优先搜索(Depth First Search,简称DFS)

算法思路:

类似树的先根遍历。设初始化时,图中各顶点均未被访问,从图中某个顶点(设为V0)出发,访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问,则访问之,在 搜索Vi的一个邻接点(深度优先)…。若某顶点的邻接点全部访问完毕,则回溯(Backtracking)到它的上一顶点,然后再从此顶点又按深度优先的方法搜索下去,…,直到能访问的顶点都访问完毕为止。

设图G10如下图所示:

通过深度优先如下:

广度优先搜索(Breadth First Search),简称BFS

算法思路:

类似树的按层次遍历。初始时,图中各顶点均未被访问,从图中某顶点(V0)出发,访问V0,并依次访问V0的各邻接点(广度优先)。然后,分别从这些被访问过的顶点出发,扔仍按照广度优先的策略搜索其它顶点,….,直到能访问的顶点都访问完毕为止。

为控制广度优先的正确搜索,要用到队列技术,即访问完一个顶点后,让该顶点的序号进队。然后取相应队头(出队),考察访问过的顶点的各邻接点,将未访问过的邻接点访问 后再依次进队,…,直到队空为止。

通过广度优先如下:

下面看一下实现代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX 20
  5. //访问记录
  6. int visit[MAX];
  7. //图的结构设计
  8. typedef struct
  9. {
  10. int vex[MAX];//记录顶点
  11. int adjmatrix[MAX][MAX];//邻接矩阵
  12. int n;//顶点的个数
  13. }GRAPH;
  14. //初始化图
  15. int init_graph(GRAPH *pG)
  16. {
  17.     memset(pG,0,sizeof(GRAPH));
  18.     pG->n = -1;
  19.     printf(“input vex\n”);
  20. while(scanf(“%d”,&pG->vex[++pG->n]));
  21. while(getchar() != ‘\n’);
  22. #ifndef _DEBUG_
  23. int i = 0;
  24. for(i = 0;i < pG->n ;i ++)
  25. {
  26.         printf(“V%d “,pG->vex[i]);
  27. }
  28.     printf(“\n”);
  29. #endif
  30.     return 0;
  31. }
  32. //获取顶点的位置
  33. int locatevex(GRAPH *pG,int vex)
  34. {
  35. int i = 0;
  36. for(i = 0;i < pG->n;i ++)
  37. {
  38. if(pG->vex[i] == vex )
  39.             return i;
  40. }
  41.     return 0;
  42. }
  43. //输入图的顶点之间的边
  44. int input_edge(GRAPH *pG)
  45. {
  46. int vex1,vex2;
  47. int i,j;
  48.     printf(“input edge(i,j):\n”);
  49. //任意字母键结束
  50. while(scanf(“(%d,%d)”,&vex1,&vex2))
  51. {
  52.         getchar();
  53.         i = locatevex(pG,vex1);
  54.         j = locatevex(pG,vex2);
  55.         pG->adjmatrix[i][j] = pG->adjmatrix[j][i] = 1;
  56. }
  57. #ifndef _DEBUG_
  58. int m,n;
  59. for(m = 0;m < pG->n;m ++)
  60. {
  61. for(n = 0;n < pG->n; n ++)
  62. {
  63.             printf(“%d “,pG->adjmatrix[m][n]);
  64. }
  65.         printf(“\n”);
  66. }
  67. #endif
  68.     return 0;
  69. }
  70. //栈的设计
  71. typedef struct
  72. {
  73. int buf[MAX];
  74. int n;
  75. }Stack;
  76. //创建空栈
  77. Stack *create_empty_stack()
  78. {
  79.     Stack *stack;
  80.     stack = (Stack *)malloc(sizeof(Stack));
  81.     stack->n = -1;
  82.     return stack;
  83. }
  84. //出栈
  85. int pop_stack(Stack *stack)
  86. {
  87. int temp;
  88.     temp = stack->buf[stack->n];
  89.     stack->n –;
  90.     return temp;
  91. }
  92. //入栈
  93. int push_stack(Stack *stack,int data)
  94. {
  95.     stack->n ++;
  96.     stack->buf[stack->n] = data;
  97.     return 0;
  98. }
  99. //判断空栈
  100. int is_empty_stack(Stack *stack)
  101. {
  102. if(stack->n == -1)
  103.         return 1;
  104. else
  105.         return 0;
  106. }
  107. int visit_all(GRAPH *pG)
  108. {
  109. int i = 0;
  110. for(i = 0;i < pG->n; i ++)
  111. {
  112. if(visit[i] != 1)
  113.             break;
  114. }
  115. if(i == pG->n)
  116.         return 1;
  117. else
  118.         return 0;
  119. }
  120. //图的深度非递归遍历
  121. int DFS(GRAPH *pG,int v)
  122. {
  123.     Stack *stack;
  124. int i = 0;
  125.     stack = create_empty_stack();
  126.     push_stack(stack,pG->vex[v]);
  127.     visit[v] = 1;
  128.     printf(“V%d “,pG->vex[v]);
  129. while(!is_empty_stack(stack) || !visit_all(pG))
  130. {
  131. for(i = 0;i < pG->n;i ++)
  132. {
  133. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  134.                 break;
  135. }
  136. if(i == pG->n)
  137. {
  138.             v = pop_stack(stack);
  139. }else{
  140.             v = i;
  141.             push_stack(stack,pG->vex[v]);
  142.             visit[v] = 1;
  143.             printf(“V%d “,pG->vex[v]);
  144. }
  145. }
  146.     printf(“\n”);
  147.     return 0;
  148. }
  149. //队列的设计
  150. typedef struct node
  151. {
  152. int data;
  153.     struct node *next;
  154. }ListNode;
  155. typedef struct
  156. {
  157.     ListNode *front;
  158.     ListNode *rear;
  159. }Queue;
  160. //创建空队列
  161. Queue *create_empty_queue()
  162. {
  163.     Queue *queue;
  164.     ListNode *head;
  165.     queue = (Queue *)malloc(sizeof(Queue));
  166.     head = (ListNode *)malloc(sizeof(ListNode));
  167.     queue->front = queue->rear = head;
  168.     return queue;
  169. }
  170. //判断队列是否为空
  171. int is_empty_queue(Queue *queue)
  172. {
  173. if(queue->rear == queue->front)
  174.         return 1;
  175. else
  176.         return 0;
  177. }
  178. //入队
  179. int EnterQueue(Queue *queue,int data)
  180. {
  181.     ListNode *temp;
  182.     temp = (ListNode *)malloc(sizeof(ListNode));
  183.     temp->data = data;
  184.     temp->next = NULL;
  185.     queue->rear->next = temp;
  186.     queue->rear = temp;
  187.     return 0;
  188. }
  189. //出队
  190. int DelQueue(Queue *queue)
  191. {
  192.     ListNode *temp;
  193.     temp = queue->front;
  194.     queue->front = queue->front->next;
  195.     free(temp);
  196.     temp = NULL;
  197.     return queue->front->data;
  198. }
  199. //图的广度遍历
  200. int BFS(GRAPH *pG,int v)
  201. {
  202.     Queue *queue = create_empty_queue();
  203. int i = 0;
  204.     memset(&visit,0,sizeof(visit));
  205.     EnterQueue(queue,v);
  206.     visit[v] = 1;
  207. while(!is_empty_queue(queue))
  208. {
  209.         v = DelQueue(queue);
  210.         printf(“V%d “,pG->vex[v]);
  211. for(i = 0;i < pG->n;i ++)
  212. {
  213. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  214. {
  215.                 EnterQueue(queue,i);
  216.                 visit[i] = 1;
  217. }
  218. }
  219. }
  220.     printf(“\n”);
  221.     return 0;
  222. }
  223. int main()
  224. {
  225.     GRAPH G;
  226. int n;
  227. //输入顶点,初始化图
  228.     init_graph(&G);
  229. //初始化邻接矩阵
  230.     input_edge(&G);
  231. //图的深度遍历
  232.     DFS(&G, 0);
  233. //图的广度遍历
  234.     BFS(&G,0);
  235.     return 0;
  236. }

输出结果:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>