devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言数据结构与算法——深度、广度优先搜索（DFS、BFS）

作者：在线问答5 | 2024-08-18 15:51:57

赞

踩

C语言数据结构与算法——深度、广度优先搜索（DFS、BFS）

目录

一、深度优先搜索（Depth-First-Search 简称：DFS）

无向图的深度优先搜索

有向图的深度优先搜索

二、广度优先搜索（Breadth-First-Search 简称：BFS）

无向图的广度优先搜索

有向图的广度优先搜索

深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常见的图遍历算法，它们在C语言中被广泛应用于解决各种数据结构和算法问题。这两种搜索算法都用于遍历图或树中的节点，以便查找特定的目标或执行其他相关任务。

一、深度优先搜索（Depth-First-Search 简称：DFS）

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

无向图的深度优先搜索

1.1 遍历过程：

　　（1）从图中某个顶点v出发，访问v。

　　（2）找出刚才第一个被顶点访问的邻接点。访问该顶点。以这个顶点为新的顶点，重复此步骤，直到访问过的顶点没有未被访问过的顶点为止。

　　（3）返回到步骤（2）中的被顶点v访问的，且还没被访问的邻接点，找出该点的下一个未被访问的邻接点，访问该顶点。

　　（4）重复（2） （3） 直到每个点都被访问过，遍历结束。

例无权图：

第1步：访问A。

第2步：访问（A的邻接点）B。  在第1步访问A之后，接下来应该访问的是A的邻接点，即"B、F、E"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，B在"D、F和E"的前面，因此，先访问B。

第3步：访问（B的邻接点）C。在第2步访问B之后，接下来应该访问B的邻接点，即"F、D、C"中一个(A已经被访问过，就不算在内)。而由于C在D、F之前，先访问C。

第4步：访问（C的邻接点）D。在第3步访问C之后，接下来应该访问C的邻接点，即D。(B已经被访问过，就不算在内)。

第5步：访问（D的邻接点）E。

第6步：访问（E的邻接点）F。

故遍历结果为 A->B->C->D->E->F

有向图的深度优先搜索

第1步：访问A。

第2步：访问B。在访问A之后，接下来访问A的出边的另一个顶点，即顶点B。

第3步：访问C。 在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。

第4步：访问E。接下来访问C的出边的另一个顶点，即顶点E。

第5步：访问D。接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。

第6步：访问F。接下应该回溯"访问A的出边的另一个顶点F"。

第7步：访问G。

故遍历结果为A->b->c->E->D->F->G

二、广度优先搜索（Breadth-First-Search 简称：BFS）

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。

它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。

无向图的广度优先搜索

第1步：访问A。
第2步：依次访问B,E,F。
    在访问了A之后，接下来访问A的邻接点。顶点ABCDEFG按照顺序存储，B在"E和F"的前面，因此，先访问B。再访问完B之后，再依次访问E,F。
第3步：依次访问C,D。
    在第2步访问完B,E,F之后，再依次访问它们的邻接点。首先访问B的邻接点C，再访问E的邻接点D。

因此访问顺序是:A->B->E->F->C->D

有向图的广度优先搜索

第1步：访问A。
第2步：访问B。
第3步：依次访问C,E,F。
    在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。顶点ABCDEFG按照顺序存储，因此会先访问C，再依次访问E,F。
第4步：依次访问D,G。
    在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。

因此访问顺序是：A->B->C->E->F->D->G

邻接矩阵图表示的"无向图"

  1. /**
  2.  * C: 邻接矩阵图表示的"无向图(Matrix Undirected Graph)"
  3.  *
  4.  * @author skywang
  5.  * @date 2014/04/18
  6.  */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <malloc.h>
  11. #include <string.h>
  12.  
  13. #define MAX 100
  14. #define isLetter(a)  ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
  15. #define LENGTH(a)  (sizeof(a)/sizeof(a[0]))
  16.  
  17. // 邻接矩阵
  18. typedef struct _graph
  19. {
  20.     char vexs[MAX];       // 顶点集合
  21.     int vexnum;           // 顶点数
  22.     int edgnum;           // 边数
  23.     int matrix[MAX][MAX]; // 邻接矩阵
  24. }Graph, *PGraph;
  25.  
  26. /*
  27.  * 返回ch在matrix矩阵中的位置
  28.  */
  29. static int get_position(Graph g, char ch)
  30. {
  31.     int i;
  32.     for(i=0; i<g.vexnum; i++)
  33.         if(g.vexs[i]==ch)
  34.             return i;
  35.     return -1;
  36. }
  37.  
  38. /*
  39.  * 读取一个输入字符
  40.  */
  41. static char read_char()
  42. {
  43.     char ch;
  44.  
  45.     do {
  46.         ch = getchar();
  47.     } while(!isLetter(ch));
  48.  
  49.     return ch;
  50. }
  51.  
  52. /*
  53.  * 创建图(自己输入)
  54.  */
  55. Graph* create_graph()
  56. {
  57.     char c1, c2;
  58.     int v, e;
  59.     int i, p1, p2;
  60.     Graph* pG;
  61.     
  62.     // 输入"顶点数"和"边数"
  63.     printf("input vertex number: ");
  64.     scanf("%d", &v);
  65.     printf("input edge number: ");
  66.     scanf("%d", &e);
  67.     if ( v < 1 || e < 1 || (e > (v * (v-1))))
  68.     {
  69.         printf("input error: invalid parameters!\n");
  70.         return NULL;
  71.     }
  72.     
  73.     if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
  74.         return NULL;
  75.     memset(pG, 0, sizeof(Graph));
  76.  
  77.     // 初始化"顶点数"和"边数"
  78.     pG->vexnum = v;
  79.     pG->edgnum = e;
  80.     // 初始化"顶点"
  81.     for (i = 0; i < pG->vexnum; i++)
  82.     {
  83.         printf("vertex(%d): ", i);
  84.         pG->vexs[i] = read_char();
  85.     }
  86.  
  87.     // 初始化"边"
  88.     for (i = 0; i < pG->edgnum; i++)
  89.     {
  90.         // 读取边的起始顶点和结束顶点
  91.         printf("edge(%d):", i);
  92.         c1 = read_char();
  93.         c2 = read_char();
  94.  
  95.         p1 = get_position(*pG, c1);
  96.         p2 = get_position(*pG, c2);
  97.         if (p1==-1 || p2==-1)
  98.         {
  99.             printf("input error: invalid edge!\n");
  100.             free(pG);
  101.             return NULL;
  102.         }
  103.  
  104.         pG->matrix[p1][p2] = 1;
  105.         pG->matrix[p2][p1] = 1;
  106.     }
  107.  
  108.     return pG;
  109. }
  110.  
  111. /*
  112.  * 创建图(用已提供的矩阵)
  113.  */
  114. Graph* create_example_graph()
  115. {
  116.     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  117.     char edges[][2] = {
  118.         {'A', 'C'}, 
  119.         {'A', 'D'}, 
  120.         {'A', 'F'}, 
  121.         {'B', 'C'}, 
  122.         {'C', 'D'}, 
  123.         {'E', 'G'}, 
  124.         {'F', 'G'}}; 
  125.     int vlen = LENGTH(vexs);
  126.     int elen = LENGTH(edges);
  127.     int i, p1, p2;
  128.     Graph* pG;
  129.     
  130.     // 输入"顶点数"和"边数"
  131.     if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
  132.         return NULL;
  133.     memset(pG, 0, sizeof(Graph));
  134.  
  135.     // 初始化"顶点数"和"边数"
  136.     pG->vexnum = vlen;
  137.     pG->edgnum = elen;
  138.     // 初始化"顶点"
  139.     for (i = 0; i < pG->vexnum; i++)
  140.     {
  141.         pG->vexs[i] = vexs[i];
  142.     }
  143.  
  144.     // 初始化"边"
  145.     for (i = 0; i < pG->edgnum; i++)
  146.     {
  147.         // 读取边的起始顶点和结束顶点
  148.         p1 = get_position(*pG, edges[i][0]);
  149.         p2 = get_position(*pG, edges[i][1]);
  150.  
  151.         pG->matrix[p1][p2] = 1;
  152.         pG->matrix[p2][p1] = 1;
  153.     }
  154.  
  155.     return pG;
  156. }
  157.  
  158. /*
  159.  * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
  160.  */
  161. static int first_vertex(Graph G, int v)
  162. {
  163.     int i;
  164.  
  165.     if (v<0 || v>(G.vexnum-1))
  166.         return -1;
  167.  
  168.     for (i = 0; i < G.vexnum; i++)
  169.         if (G.matrix[v][i] == 1)
  170.             return i;
  171.  
  172.     return -1;
  173. }
  174.  
  175. /*
  176.  * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
  177.  */
  178. static int next_vertix(Graph G, int v, int w)
  179. {
  180.     int i;
  181.  
  182.     if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
  183.         return -1;
  184.  
  185.     for (i = w + 1; i < G.vexnum; i++)
  186.         if (G.matrix[v][i] == 1)
  187.             return i;
  188.  
  189.     return -1;
  190. }
  191.  
  192. /*
  193.  * 深度优先搜索遍历图的递归实现
  194.  */
  195. static void DFS(Graph G, int i, int *visited)
  196. {                                   
  197.     int w; 
  198.  
  199.     visited[i] = 1;
  200.     printf("%c ", G.vexs[i]);
  201.     // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
  202.     for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
  203.     {
  204.         if (!visited[w])
  205.             DFS(G, w, visited);
  206.     }
  207.        
  208. }
  209.  
  210. /*
  211.  * 深度优先搜索遍历图
  212.  */
  213. void DFSTraverse(Graph G)
  214. {
  215.     int i;
  216.     int visited[MAX];       // 顶点访问标记
  217.  
  218.     // 初始化所有顶点都没有被访问
  219.     for (i = 0; i < G.vexnum; i++)
  220.         visited[i] = 0;
  221.  
  222.     printf("DFS: ");
  223.     for (i = 0; i < G.vexnum; i++)
  224.     {
  225.         //printf("\n== LOOP(%d)\n", i);
  226.         if (!visited[i])
  227.             DFS(G, i, visited);
  228.     }
  229.     printf("\n");
  230. }
  231.  
  232. /*
  233.  * 广度优先搜索（类似于树的层次遍历）
  234.  */
  235. void BFS(Graph G)
  236. {
  237.     int head = 0;
  238.     int rear = 0;
  239.     int queue[MAX];     // 辅组队列
  240.     int visited[MAX];   // 顶点访问标记
  241.     int i, j, k;
  242.  
  243.     for (i = 0; i < G.vexnum; i++)
  244.         visited[i] = 0;
  245.  
  246.     printf("BFS: ");
  247.     for (i = 0; i < G.vexnum; i++)
  248.     {
  249.         if (!visited[i])
  250.         {
  251.             visited[i] = 1;
  252.             printf("%c ", G.vexs[i]);
  253.             queue[rear++] = i;  // 入队列
  254.         }
  255.         while (head != rear) 
  256.         {
  257.             j = queue[head++];  // 出队列
  258.             for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
  259.             {
  260.                 if (!visited[k])
  261.                 {
  262.                     visited[k] = 1;
  263.                     printf("%c ", G.vexs[k]);
  264.                     queue[rear++] = k;
  265.                 }
  266.             }
  267.         }
  268.     }
  269.     printf("\n");
  270. }
  271.  
  272. /*
  273.  * 打印矩阵队列图
  274.  */
  275. void print_graph(Graph G)
  276. {
  277.     int i,j;
  278.  
  279.     printf("Martix Graph:\n");
  280.     for (i = 0; i < G.vexnum; i++)
  281.     {
  282.         for (j = 0; j < G.vexnum; j++)
  283.             printf("%d ", G.matrix[i][j]);
  284.         printf("\n");
  285.     }
  286. }
  287.  
  288. void main()
  289. {
  290.     Graph* pG;
  291.  
  292.     // 自定义"图"(输入矩阵队列)
  293.     //pG = create_graph();
  294.     // 采用已有的"图"
  295.     pG = create_example_graph();
  296.  
  297.     print_graph(*pG);       // 打印图
  298.     DFSTraverse(*pG);       // 深度优先遍历
  299.     BFS(*pG);               // 广度优先遍历
  300. }

邻接表表示的"无向图"

  1. /**
  2.  * C: 邻接表表示的"无向图(List Undirected Graph)"
  3.  *
  4.  * @author skywang
  5.  * @date 2014/04/18
  6.  */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <malloc.h>
  11. #include <string.h>
  12.  
  13. #define MAX 100
  14. #define isLetter(a)  ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
  15. #define LENGTH(a)  (sizeof(a)/sizeof(a[0]))
  16.  
  17. // 邻接表中表对应的链表的顶点
  18. typedef struct _ENode
  19. {
  20.     int ivex;                   // 该边所指向的顶点的位置
  21.     struct _ENode *next_edge;   // 指向下一条弧的指针
  22. }ENode, *PENode;
  23.  
  24. // 邻接表中表的顶点
  25. typedef struct _VNode
  26. {
  27.     char data;              // 顶点信息
  28.     ENode *first_edge;      // 指向第一条依附该顶点的弧
  29. }VNode;
  30.  
  31. // 邻接表
  32. typedef struct _LGraph
  33. {
  34.     int vexnum;             // 图的顶点的数目
  35.     int edgnum;             // 图的边的数目
  36.     VNode vexs[MAX];
  37. }LGraph;
  38.  
  39. /*
  40.  * 返回ch在matrix矩阵中的位置
  41.  */
  42. static int get_position(LGraph g, char ch)
  43. {
  44.     int i;
  45.     for(i=0; i<g.vexnum; i++)
  46.         if(g.vexs[i].data==ch)
  47.             return i;
  48.     return -1;
  49. }
  50.  
  51. /*
  52.  * 读取一个输入字符
  53.  */
  54. static char read_char()
  55. {
  56.     char ch;
  57.  
  58.     do {
  59.         ch = getchar();
  60.     } while(!isLetter(ch));
  61.  
  62.     return ch;
  63. }
  64.  
  65. /*
  66.  * 将node链接到list的末尾
  67.  */
  68. static void link_last(ENode *list, ENode *node)
  69. {
  70.     ENode *p = list;
  71.  
  72.     while(p->next_edge)
  73.         p = p->next_edge;
  74.     p->next_edge = node;
  75. }
  76.  
  77. /*
  78.  * 创建邻接表对应的图(自己输入)
  79.  */
  80. LGraph* create_lgraph()
  81. {
  82.     char c1, c2;
  83.     int v, e;
  84.     int i, p1, p2;
  85.     ENode *node1, *node2;
  86.     LGraph* pG;
  87.  
  88.     // 输入"顶点数"和"边数"
  89.     printf("input vertex number: ");
  90.     scanf("%d", &v);
  91.     printf("input edge number: ");
  92.     scanf("%d", &e);
  93.     if ( v < 1 || e < 1 || (e > (v * (v-1))))
  94.     {
  95.         printf("input error: invalid parameters!\n");
  96.         return NULL;
  97.     }
  98.  
  99.     if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
  100.         return NULL;
  101.     memset(pG, 0, sizeof(LGraph));
  102.  
  103.     // 初始化"顶点数"和"边数"
  104.     pG->vexnum = v;
  105.     pG->edgnum = e;
  106.     // 初始化"邻接表"的顶点
  107.     for(i=0; i<pG->vexnum; i++)
  108.     {
  109.         printf("vertex(%d): ", i);
  110.         pG->vexs[i].data = read_char();
  111.         pG->vexs[i].first_edge = NULL;
  112.     }
  113.  
  114.     // 初始化"邻接表"的边
  115.     for(i=0; i<pG->edgnum; i++)
  116.     {
  117.         // 读取边的起始顶点和结束顶点
  118.         printf("edge(%d): ", i);
  119.         c1 = read_char();
  120.         c2 = read_char();
  121.  
  122.         p1 = get_position(*pG, c1);
  123.         p2 = get_position(*pG, c2);
  124.  
  125.         // 初始化node1
  126.         node1 = (ENode*)malloc(sizeof(ENode));
  127.         node1->ivex = p2;
  128.         // 将node1链接到"p1所在链表的末尾"
  129.         if(pG->vexs[p1].first_edge == NULL)
  130.           pG->vexs[p1].first_edge = node1;
  131.         else
  132.             link_last(pG->vexs[p1].first_edge, node1);
  133.         // 初始化node2
  134.         node2 = (ENode*)malloc(sizeof(ENode));
  135.         node2->ivex = p1;
  136.         // 将node2链接到"p2所在链表的末尾"
  137.         if(pG->vexs[p2].first_edge == NULL)
  138.           pG->vexs[p2].first_edge = node2;
  139.         else
  140.             link_last(pG->vexs[p2].first_edge, node2);
  141.     }
  142.  
  143.     return pG;
  144. }
  145.  
  146. /*
  147.  * 创建邻接表对应的图(用已提供的数据)
  148.  */
  149. LGraph* create_example_lgraph()
  150. {
  151.     char c1, c2;
  152.     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  153.     char edges[][2] = {
  154.         {'A', 'C'}, 
  155.         {'A', 'D'}, 
  156.         {'A', 'F'}, 
  157.         {'B', 'C'}, 
  158.         {'C', 'D'}, 
  159.         {'E', 'G'}, 
  160.         {'F', 'G'}}; 
  161.     int vlen = LENGTH(vexs);
  162.     int elen = LENGTH(edges);
  163.     int i, p1, p2;
  164.     ENode *node1, *node2;
  165.     LGraph* pG;
  166.  
  167.  
  168.     if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
  169.         return NULL;
  170.     memset(pG, 0, sizeof(LGraph));
  171.  
  172.     // 初始化"顶点数"和"边数"
  173.     pG->vexnum = vlen;
  174.     pG->edgnum = elen;
  175.     // 初始化"邻接表"的顶点
  176.     for(i=0; i<pG->vexnum; i++)
  177.     {
  178.         pG->vexs[i].data = vexs[i];
  179.         pG->vexs[i].first_edge = NULL;
  180.     }
  181.  
  182.     // 初始化"邻接表"的边
  183.     for(i=0; i<pG->edgnum; i++)
  184.     {
  185.         // 读取边的起始顶点和结束顶点
  186.         c1 = edges[i][0];
  187.         c2 = edges[i][1];
  188.  
  189.         p1 = get_position(*pG, c1);
  190.         p2 = get_position(*pG, c2);
  191.  
  192.         // 初始化node1
  193.         node1 = (ENode*)malloc(sizeof(ENode));
  194.         node1->ivex = p2;
  195.         // 将node1链接到"p1所在链表的末尾"
  196.         if(pG->vexs[p1].first_edge == NULL)
  197.           pG->vexs[p1].first_edge = node1;
  198.         else
  199.             link_last(pG->vexs[p1].first_edge, node1);
  200.         // 初始化node2
  201.         node2 = (ENode*)malloc(sizeof(ENode));
  202.         node2->ivex = p1;
  203.         // 将node2链接到"p2所在链表的末尾"
  204.         if(pG->vexs[p2].first_edge == NULL)
  205.           pG->vexs[p2].first_edge = node2;
  206.         else
  207.             link_last(pG->vexs[p2].first_edge, node2);
  208.     }
  209.  
  210.     return pG;
  211. }
  212.  
  213. /*
  214.  * 深度优先搜索遍历图的递归实现
  215.  */
  216. static void DFS(LGraph G, int i, int *visited)
  217. {
  218.     int w;
  219.     ENode *node;
  220.  
  221.     visited[i] = 1;
  222.     printf("%c ", G.vexs[i].data);
  223.     node = G.vexs[i].first_edge;
  224.     while (node != NULL)
  225.     {
  226.         if (!visited[node->ivex])
  227.             DFS(G, node->ivex, visited);
  228.         node = node->next_edge;
  229.     }
  230. }
  231.  
  232. /*
  233.  * 深度优先搜索遍历图
  234.  */
  235. void DFSTraverse(LGraph G)
  236. {
  237.     int i;
  238.     int visited[MAX];       // 顶点访问标记
  239.  
  240.     // 初始化所有顶点都没有被访问
  241.     for (i = 0; i < G.vexnum; i++)
  242.         visited[i] = 0;
  243.  
  244.     printf("DFS: ");
  245.     for (i = 0; i < G.vexnum; i++)
  246.     {
  247.         if (!visited[i])
  248.             DFS(G, i, visited);
  249.     }
  250.     printf("\n");
  251. }
  252.  
  253. /*
  254.  * 广度优先搜索（类似于树的层次遍历）
  255.  */
  256. void BFS(LGraph G)
  257. {
  258.     int head = 0;
  259.     int rear = 0;
  260.     int queue[MAX];     // 辅组队列
  261.     int visited[MAX];   // 顶点访问标记
  262.     int i, j, k;
  263.     ENode *node;
  264.  
  265.     for (i = 0; i < G.vexnum; i++)
  266.         visited[i] = 0;
  267.  
  268.     printf("BFS: ");
  269.     for (i = 0; i < G.vexnum; i++)
  270.     {
  271.         if (!visited[i])
  272.         {
  273.             visited[i] = 1;
  274.             printf("%c ", G.vexs[i].data);
  275.             queue[rear++] = i;  // 入队列
  276.         }
  277.         while (head != rear) 
  278.         {
  279.             j = queue[head++];  // 出队列
  280.             node = G.vexs[j].first_edge;
  281.             while (node != NULL)
  282.             {
  283.                 k = node->ivex;
  284.                 if (!visited[k])
  285.                 {
  286.                     visited[k] = 1;
  287.                     printf("%c ", G.vexs[k].data);
  288.                     queue[rear++] = k;
  289.                 }
  290.                 node = node->next_edge;
  291.             }
  292.         }
  293.     }
  294.     printf("\n");
  295. }
  296.  
  297. /*
  298.  * 打印邻接表图
  299.  */
  300. void print_lgraph(LGraph G)
  301. {
  302.     int i,j;
  303.     ENode *node;
  304.  
  305.     printf("List Graph:\n");
  306.     for (i = 0; i < G.vexnum; i++)
  307.     {
  308.         printf("%d(%c): ", i, G.vexs[i].data);
  309.         node = G.vexs[i].first_edge;
  310.         while (node != NULL)
  311.         {
  312.             printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data);
  313.             node = node->next_edge;
  314.         }
  315.         printf("\n");
  316.     }
  317. }
  318.  
  319. void main()
  320. {
  321.     LGraph* pG;
  322.  
  323.     // 自定义"图"(自己输入数据)
  324.     //pG = create_lgraph();
  325.     // 采用已有的"图"
  326.     pG = create_example_lgraph();
  327.  
  328.     // 打印图
  329.     print_lgraph(*pG);
  330.     DFSTraverse(*pG);
  331.     BFS(*pG);
  332. }

邻接矩阵表示的"有向图"

  1. /**
  2.  * C: 邻接矩阵表示的"有向图(Matrix Directed Graph)"
  3.  *
  4.  * @author skywang
  5.  * @date 2014/04/18
  6.  */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <malloc.h>
  11. #include <string.h>
  12.  
  13. #define MAX 100
  14. #define isLetter(a)  ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
  15. #define LENGTH(a)  (sizeof(a)/sizeof(a[0]))
  16.  
  17. // 邻接矩阵
  18. typedef struct _graph
  19. {
  20.     char vexs[MAX];       // 顶点集合
  21.     int vexnum;           // 顶点数
  22.     int edgnum;           // 边数
  23.     int matrix[MAX][MAX]; // 邻接矩阵
  24. }Graph, *PGraph;
  25.  
  26. /*
  27.  * 返回ch在matrix矩阵中的位置
  28.  */
  29. static int get_position(Graph g, char ch)
  30. {
  31.     int i;
  32.     for(i=0; i<g.vexnum; i++)
  33.         if(g.vexs[i]==ch)
  34.             return i;
  35.     return -1;
  36. }
  37.  
  38. /*
  39.  * 读取一个输入字符
  40.  */
  41. static char read_char()
  42. {
  43.     char ch;
  44.  
  45.     do {
  46.         ch = getchar();
  47.     } while(!isLetter(ch));
  48.  
  49.     return ch;
  50. }
  51.  
  52. /*
  53.  * 创建图(自己输入)
  54.  */
  55. Graph* create_graph()
  56. {
  57.     char c1, c2;
  58.     int v, e;
  59.     int i, p1, p2;
  60.     Graph* pG;
  61.     
  62.     // 输入"顶点数"和"边数"
  63.     printf("input vertex number: ");
  64.     scanf("%d", &v);
  65.     printf("input edge number: ");
  66.     scanf("%d", &e);
  67.     if ( v < 1 || e < 1 || (e > (v * (v-1))))
  68.     {
  69.         printf("input error: invalid parameters!\n");
  70.         return NULL;
  71.     }
  72.     
  73.     if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
  74.         return NULL;
  75.     memset(pG, 0, sizeof(Graph));
  76.  
  77.     // 初始化"顶点数"和"边数"
  78.     pG->vexnum = v;
  79.     pG->edgnum = e;
  80.     // 初始化"顶点"
  81.     for (i = 0; i < pG->vexnum; i++)
  82.     {
  83.         printf("vertex(%d): ", i);
  84.         pG->vexs[i] = read_char();
  85.     }
  86.  
  87.     // 初始化"边"
  88.     for (i = 0; i < pG->edgnum; i++)
  89.     {
  90.         // 读取边的起始顶点和结束顶点
  91.         printf("edge(%d):", i);
  92.         c1 = read_char();
  93.         c2 = read_char();
  94.  
  95.         p1 = get_position(*pG, c1);
  96.         p2 = get_position(*pG, c2);
  97.         if (p1==-1 || p2==-1)
  98.         {
  99.             printf("input error: invalid edge!\n");
  100.             free(pG);
  101.             return NULL;
  102.         }
  103.  
  104.         pG->matrix[p1][p2] = 1;
  105.     }
  106.  
  107.     return pG;
  108. }
  109.  
  110. /*
  111.  * 创建图(用已提供的矩阵)
  112.  */
  113. Graph* create_example_graph()
  114. {
  115.     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  116.     char edges[][2] = {
  117.         {'A', 'B'}, 
  118.         {'B', 'C'}, 
  119.         {'B', 'E'}, 
  120.         {'B', 'F'}, 
  121.         {'C', 'E'}, 
  122.         {'D', 'C'}, 
  123.         {'E', 'B'}, 
  124.         {'E', 'D'}, 
  125.         {'F', 'G'}}; 
  126.     int vlen = LENGTH(vexs);
  127.     int elen = LENGTH(edges);
  128.     int i, p1, p2;
  129.     Graph* pG;
  130.     
  131.     // 输入"顶点数"和"边数"
  132.     if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
  133.         return NULL;
  134.     memset(pG, 0, sizeof(Graph));
  135.  
  136.     // 初始化"顶点数"和"边数"
  137.     pG->vexnum = vlen;
  138.     pG->edgnum = elen;
  139.     // 初始化"顶点"
  140.     for (i = 0; i < pG->vexnum; i++)
  141.     {
  142.         pG->vexs[i] = vexs[i];
  143.     }
  144.  
  145.     // 初始化"边"
  146.     for (i = 0; i < pG->edgnum; i++)
  147.     {
  148.         // 读取边的起始顶点和结束顶点
  149.         p1 = get_position(*pG, edges[i][0]);
  150.         p2 = get_position(*pG, edges[i][1]);
  151.  
  152.         pG->matrix[p1][p2] = 1;
  153.     }
  154.  
  155.     return pG;
  156. }
  157.  
  158. /*
  159.  * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
  160.  */
  161. static int first_vertex(Graph G, int v)
  162. {
  163.     int i;
  164.  
  165.     if (v<0 || v>(G.vexnum-1))
  166.         return -1;
  167.  
  168.     for (i = 0; i < G.vexnum; i++)
  169.         if (G.matrix[v][i] == 1)
  170.             return i;
  171.  
  172.     return -1;
  173. }
  174.  
  175. /*
  176.  * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
  177.  */
  178. static int next_vertix(Graph G, int v, int w)
  179. {
  180.     int i;
  181.  
  182.     if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
  183.         return -1;
  184.  
  185.     for (i = w + 1; i < G.vexnum; i++)
  186.         if (G.matrix[v][i] == 1)
  187.             return i;
  188.  
  189.     return -1;
  190. }
  191.  
  192. /*
  193.  * 深度优先搜索遍历图的递归实现
  194.  */
  195. static void DFS(Graph G, int i, int *visited)
  196. {                                   
  197.     int w; 
  198.  
  199.     visited[i] = 1;
  200.     printf("%c ", G.vexs[i]);
  201.     // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
  202.     for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
  203.     {
  204.         if (!visited[w])
  205.             DFS(G, w, visited);
  206.     }
  207.        
  208. }
  209.  
  210. /*
  211.  * 深度优先搜索遍历图
  212.  */
  213. void DFSTraverse(Graph G)
  214. {
  215.     int i;
  216.     int visited[MAX];       // 顶点访问标记
  217.  
  218.     // 初始化所有顶点都没有被访问
  219.     for (i = 0; i < G.vexnum; i++)
  220.         visited[i] = 0;
  221.  
  222.     printf("DFS: ");
  223.     for (i = 0; i < G.vexnum; i++)
  224.     {
  225.         //printf("\n== LOOP(%d)\n", i);
  226.         if (!visited[i])
  227.             DFS(G, i, visited);
  228.     }
  229.     printf("\n");
  230. }
  231.  
  232. /*
  233.  * 广度优先搜索（类似于树的层次遍历）
  234.  */
  235. void BFS(Graph G)
  236. {
  237.     int head = 0;
  238.     int rear = 0;
  239.     int queue[MAX];     // 辅组队列
  240.     int visited[MAX];   // 顶点访问标记
  241.     int i, j, k;
  242.  
  243.     for (i = 0; i < G.vexnum; i++)
  244.         visited[i] = 0;
  245.  
  246.     printf("BFS: ");
  247.     for (i = 0; i < G.vexnum; i++)
  248.     {
  249.         if (!visited[i])
  250.         {
  251.             visited[i] = 1;
  252.             printf("%c ", G.vexs[i]);
  253.             queue[rear++] = i;  // 入队列
  254.         }
  255.         while (head != rear) 
  256.         {
  257.             j = queue[head++];  // 出队列
  258.             for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
  259.             {
  260.                 if (!visited[k])
  261.                 {
  262.                     visited[k] = 1;
  263.                     printf("%c ", G.vexs[k]);
  264.                     queue[rear++] = k;
  265.                 }
  266.             }
  267.         }
  268.     }
  269.     printf("\n");
  270. }
  271.  
  272. /*
  273.  * 打印矩阵队列图
  274.  */
  275. void print_graph(Graph G)
  276. {
  277.     int i,j;
  278.  
  279.     printf("Martix Graph:\n");
  280.     for (i = 0; i < G.vexnum; i++)
  281.     {
  282.         for (j = 0; j < G.vexnum; j++)
  283.             printf("%d ", G.matrix[i][j]);
  284.         printf("\n");
  285.     }
  286. }
  287.  
  288. void main()
  289. {
  290.     Graph* pG;
  291.  
  292.     // 自定义"图"(输入矩阵队列)
  293.     //pG = create_graph();
  294.     // 采用已有的"图"
  295.     pG = create_example_graph();
  296.  
  297.     print_graph(*pG);       // 打印图
  298.     DFSTraverse(*pG);       // 深度优先遍历
  299.     BFS(*pG);               // 广度优先遍历
  300. }

邻接表表示的"有向图"

  1. /**
  2.  * C: 邻接表表示的"有向图(List Directed Graph)"
  3.  *
  4.  * @author skywang
  5.  * @date 2014/04/18
  6.  */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <malloc.h>
  11. #include <string.h>
  12.  
  13. #define MAX 100
  14. #define isLetter(a)  ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
  15. #define LENGTH(a)  (sizeof(a)/sizeof(a[0]))
  16.  
  17. // 邻接表中表对应的链表的顶点
  18. typedef struct _ENode
  19. {
  20.     int ivex;                   // 该边所指向的顶点的位置
  21.     struct _ENode *next_edge;   // 指向下一条弧的指针
  22. }ENode, *PENode;
  23.  
  24. // 邻接表中表的顶点
  25. typedef struct _VNode
  26. {
  27.     char data;              // 顶点信息
  28.     ENode *first_edge;      // 指向第一条依附该顶点的弧
  29. }VNode;
  30.  
  31. // 邻接表
  32. typedef struct _LGraph
  33. {
  34.     int vexnum;             // 图的顶点的数目
  35.     int edgnum;             // 图的边的数目
  36.     VNode vexs[MAX];
  37. }LGraph;
  38.  
  39. /*
  40.  * 返回ch在matrix矩阵中的位置
  41.  */
  42. static int get_position(LGraph g, char ch)
  43. {
  44.     int i;
  45.     for(i=0; i<g.vexnum; i++)
  46.         if(g.vexs[i].data==ch)
  47.             return i;
  48.     return -1;
  49. }
  50.  
  51. /*
  52.  * 读取一个输入字符
  53.  */
  54. static char read_char()
  55. {
  56.     char ch;
  57.  
  58.     do {
  59.         ch = getchar();
  60.     } while(!isLetter(ch));
  61.  
  62.     return ch;
  63. }
  64.  
  65. /*
  66.  * 将node链接到list的末尾
  67.  */
  68. static void link_last(ENode *list, ENode *node)
  69. {
  70.     ENode *p = list;
  71.  
  72.     while(p->next_edge)
  73.         p = p->next_edge;
  74.     p->next_edge = node;
  75. }
  76.  
  77. /*
  78.  * 创建邻接表对应的图(自己输入)
  79.  */
  80. LGraph* create_lgraph()
  81. {
  82.     char c1, c2;
  83.     int v, e;
  84.     int i, p1, p2;
  85.     ENode *node1, *node2;
  86.     LGraph* pG;
  87.  
  88.     // 输入"顶点数"和"边数"
  89.     printf("input vertex number: ");
  90.     scanf("%d", &v);
  91.     printf("input edge number: ");
  92.     scanf("%d", &e);
  93.     if ( v < 1 || e < 1 || (e > (v * (v-1))))
  94.     {
  95.         printf("input error: invalid parameters!\n");
  96.         return NULL;
  97.     }
  98.  
  99.     if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
  100.         return NULL;
  101.     memset(pG, 0, sizeof(LGraph));
  102.  
  103.     // 初始化"顶点数"和"边数"
  104.     pG->vexnum = v;
  105.     pG->edgnum = e;
  106.     // 初始化"邻接表"的顶点
  107.     for(i=0; i<pG->vexnum; i++)
  108.     {
  109.         printf("vertex(%d): ", i);
  110.         pG->vexs[i].data = read_char();
  111.         pG->vexs[i].first_edge = NULL;
  112.     }
  113.  
  114.     // 初始化"邻接表"的边
  115.     for(i=0; i<pG->edgnum; i++)
  116.     {
  117.         // 读取边的起始顶点和结束顶点
  118.         printf("edge(%d): ", i);
  119.         c1 = read_char();
  120.         c2 = read_char();
  121.  
  122.         p1 = get_position(*pG, c1);
  123.         p2 = get_position(*pG, c2);
  124.         // 初始化node1
  125.         node1 = (ENode*)malloc(sizeof(ENode));
  126.         node1->ivex             = p2;
  127.         // 将node1链接到"p1所在链表的末尾"
  128.         if(pG->vexs[p1].first_edge == NULL)
  129.           pG->vexs[p1].first_edge = node1;
  130.         else
  131.             link_last(pG->vexs[p1].first_edge, node1);
  132.     }
  133.  
  134.     return pG;
  135. }
  136.  
  137. /*
  138.  * 创建邻接表对应的图(用已提供的数据)
  139.  */
  140. LGraph* create_example_lgraph()
  141. {
  142.     char c1, c2;
  143.     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  144.     char edges[][2] = {
  145.         {'A', 'B'}, 
  146.         {'B', 'C'}, 
  147.         {'B', 'E'}, 
  148.         {'B', 'F'}, 
  149.         {'C', 'E'}, 
  150.         {'D', 'C'}, 
  151.         {'E', 'B'}, 
  152.         {'E', 'D'}, 
  153.         {'F', 'G'}}; 
  154.     int vlen = LENGTH(vexs);
  155.     int elen = LENGTH(edges);
  156.     int i, p1, p2;
  157.     ENode *node1, *node2;
  158.     LGraph* pG;
  159.  
  160.  
  161.     if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
  162.         return NULL;
  163.     memset(pG, 0, sizeof(LGraph));
  164.  
  165.     // 初始化"顶点数"和"边数"
  166.     pG->vexnum = vlen;
  167.     pG->edgnum = elen;
  168.     // 初始化"邻接表"的顶点
  169.     for(i=0; i<pG->vexnum; i++)
  170.     {
  171.         pG->vexs[i].data = vexs[i];
  172.         pG->vexs[i].first_edge = NULL;
  173.     }
  174.  
  175.     // 初始化"邻接表"的边
  176.     for(i=0; i<pG->edgnum; i++)
  177.     {
  178.         // 读取边的起始顶点和结束顶点
  179.         c1 = edges[i][0];
  180.         c2 = edges[i][1];
  181.  
  182.         p1 = get_position(*pG, c1);
  183.         p2 = get_position(*pG, c2);
  184.         // 初始化node1
  185.         node1 = (ENode*)malloc(sizeof(ENode));
  186.         node1->ivex = p2;
  187.         // 将node1链接到"p1所在链表的末尾"
  188.         if(pG->vexs[p1].first_edge == NULL)
  189.           pG->vexs[p1].first_edge = node1;
  190.         else
  191.             link_last(pG->vexs[p1].first_edge, node1);
  192.     }
  193.  
  194.     return pG;
  195. }
  196.  
  197. /*
  198.  * 深度优先搜索遍历图的递归实现
  199.  */
  200. static void DFS(LGraph G, int i, int *visited)
  201. {
  202.     int w;
  203.     ENode *node;
  204.  
  205.     visited[i] = 1;
  206.     printf("%c ", G.vexs[i].data);
  207.     node = G.vexs[i].first_edge;
  208.     while (node != NULL)
  209.     {
  210.         if (!visited[node->ivex])
  211.             DFS(G, node->ivex, visited);
  212.         node = node->next_edge;
  213.     }
  214. }
  215.  
  216. /*
  217.  * 深度优先搜索遍历图
  218.  */
  219. void DFSTraverse(LGraph G)
  220. {
  221.     int i;
  222.     int visited[MAX];       // 顶点访问标记
  223.  
  224.     // 初始化所有顶点都没有被访问
  225.     for (i = 0; i < G.vexnum; i++)
  226.         visited[i] = 0;
  227.  
  228.     printf("DFS: ");
  229.     for (i = 0; i < G.vexnum; i++)
  230.     {
  231.         if (!visited[i])
  232.             DFS(G, i, visited);
  233.     }
  234.     printf("\n");
  235. }
  236.  
  237. /*
  238.  * 广度优先搜索（类似于树的层次遍历）
  239.  */
  240. void BFS(LGraph G)
  241. {
  242.     int head = 0;
  243.     int rear = 0;
  244.     int queue[MAX];     // 辅组队列
  245.     int visited[MAX];   // 顶点访问标记
  246.     int i, j, k;
  247.     ENode *node;
  248.  
  249.     for (i = 0; i < G.vexnum; i++)
  250.         visited[i] = 0;
  251.  
  252.     printf("BFS: ");
  253.     for (i = 0; i < G.vexnum; i++)
  254.     {
  255.         if (!visited[i])
  256.         {
  257.             visited[i] = 1;
  258.             printf("%c ", G.vexs[i].data);
  259.             queue[rear++] = i;  // 入队列
  260.         }
  261.         while (head != rear) 
  262.         {
  263.             j = queue[head++];  // 出队列
  264.             node = G.vexs[j].first_edge;
  265.             while (node != NULL)
  266.             {
  267.                 k = node->ivex;
  268.                 if (!visited[k])
  269.                 {
  270.                     visited[k] = 1;
  271.                     printf("%c ", G.vexs[k].data);
  272.                     queue[rear++] = k;
  273.                 }
  274.                 node = node->next_edge;
  275.             }
  276.         }
  277.     }
  278.     printf("\n");
  279. }
  280.  
  281. /*
  282.  * 打印邻接表图
  283.  */
  284. void print_lgraph(LGraph G)
  285. {
  286.     int i,j;
  287.     ENode *node;
  288.  
  289.     printf("List Graph:\n");
  290.     for (i = 0; i < G.vexnum; i++)
  291.     {
  292.         printf("%d(%c): ", i, G.vexs[i].data);
  293.         node = G.vexs[i].first_edge;
  294.         while (node != NULL)
  295.         {
  296.             printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data);
  297.             node = node->next_edge;
  298.         }
  299.         printf("\n");
  300.     }
  301. }
  302.  
  303. void main()
  304. {
  305.     LGraph* pG;
  306.  
  307.     // 自定义"图"(自己输入数据)
  308.     //pG = create_lgraph();
  309.     // 采用已有的"图"
  310.     pG = create_example_lgraph();
  311.  
  312.     // 打印图
  313.     print_lgraph(*pG);
  314.     DFSTraverse(*pG);
  315.     BFS(*pG);
  316. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/998102
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号