久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

搜索
分享

圖的廣度優(yōu)先搜索（鄰接表）

 goodwangLib 2013-11-15

圖的遍歷(Traversing Graph)是指從圖中某一頂點出發(fā)訪問圖中其余頂點，且使每個頂點僅被訪問一次,。

廣度優(yōu)先搜索(Breadth First Search)

       廣度優(yōu)先搜索假設從圖中某個頂點v出發(fā),，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后再分別從這些鄰接點出發(fā)依次訪問它們的鄰接點,，并使先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問（因此需要用隊列來存儲頂點）,，直到圖中所有已被訪問的頂點的鄰接點都被訪問為止。如果此時圖中還有未被訪問的頂點,，則另選圖中未被訪問的頂點作為起點,，重復上述過程，直到圖中所有頂點都被訪問為止,。

采用鄰接表存儲圖的具體實現(xiàn)如下：

  1. #include <iostream>  
  2. #include <queue>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. using namespace std;  
  6.   
  7. #define VERTEXNUM 100 //頂點個數(shù)  
  8. typedef char VertexType;  
  9. typedef int EdgeType;  
  10. typedef enum{FALSE, TRUE} Boolean;  
  11. Boolean visited[VERTEXNUM];  
  12.   
  13. /*************************************** 
  14.  * 
  15.  * 鄰接表存儲結(jié)構(gòu)  
  16.  * 
  17.  * *************************************/  
  18. typedef struct node  
  19. {  
  20.     int adjvex; //頂點位置  
  21.     struct node *next; //指向下一條邊的指針  
  22. }EdgeNode;  
  23.   
  24. typedef struct vnode  
  25. {  
  26.     VertexType vertex; //頂點信息  
  27.     EdgeNode *firstedge; //指向第一條依附該頂點的邊的指針  
  28. }AdjList[VERTEXNUM];  
  29.   
  30. typedef struct  
  31. {  
  32.     AdjList vertexs; //鄰接表  
  33.     int vernum, edgenum; //圖中當前的頂點和邊數(shù)  
  34. }Graph;  
  35.   
  36. /*************************************** 
  37.  * 
  38.  * 建立圖的鄰接表 
  39.  * 
  40.  * *************************************/  
  41. void MakeGraph(Graph *graph)  
  42. {  
  43.   
  44.     int v1, v2;  
  45.     int i, j, k;  
  46.     printf("請輸入圖的頂點數(shù)n和邊數(shù)e:\n");  
  47.     scanf("%d%d", &graph->vernum, &graph->edgenum);  
  48.     printf("請輸入頂點信息(頂點號<CR>)每個頂點以回車作為結(jié)束:\n");  
  49.   
  50.     for(i = 0; i < graph->vernum; i++)  
  51.     {  
  52.         getchar();  
  53.         scanf("%c", &graph->vertexs[i].vertex);  
  54.         graph->vertexs[i].firstedge = NULL; //初始第一條邊為空  
  55.     }  
  56.   
  57.     printf("請輸入每條邊對應的兩個頂點的序號(格式為i,j):\n");  
  58.     EdgeNode *p;  
  59.     for(k = 0; k < graph->edgenum; k++)  
  60.     {  
  61.         scanf("%d,%d", &i, &j);  //讀入邊<vi,vj>的序號  
  62.         p = (node *)malloc(sizeof(node)); //生成新的結(jié)點  
  63.         p->adjvex = j - 1;  
  64.         p->next = graph->vertexs[i - 1].firstedge;  
  65.         graph->vertexs[i - 1].firstedge = p;  
  66.     }  
  67. }  
  68.   
  69. /*************************************** 
  70.  * 
  71.  * 廣度優(yōu)先遍歷 
  72.  * 
  73.  * *************************************/  
  74. void BFS(Graph *graph)  
  75. {  
  76.     int i, j, k;  
  77.     queue<int> q;  
  78.     EdgeNode *p;  
  79.     for(i = 0; i < graph->vernum; i++) //初始化訪問標識數(shù)組  
  80.         visited[i] = FALSE;  
  81.   
  82.     for(i = 0; i < graph->vernum; i++)  
  83.     {  
  84.         if(!visited[i])  
  85.         {  
  86.             visited[i] = TRUE;  
  87.             printf("廣度優(yōu)先遍歷:結(jié)點%c\n", graph->vertexs[i].vertex);  
  88.             q.push(i); //入棧  
  89.             while(!q.empty())  
  90.             {  
  91.                 j = q.front();   
  92.                 q.pop();  //出棧  
  93.                 p = graph->vertexs[j].firstedge;  
  94.                 while(p)  
  95.                 {  
  96.                     if(!visited[p->adjvex])  
  97.                     {  
  98.                         printf("廣度優(yōu)先遍歷:結(jié)點%c\n", graph->vertexs[p->adjvex].vertex);  
  99.                         visited[p->adjvex] = TRUE;  
  100.                         q.push(p->adjvex);  
  101.                     }  
  102.                     p = p->next;  
  103.                 }  
  104.             }  
  105.         }  
  106.     }  
  107. }  
  108.   
  109. int main()  
  110. {  
  111.     Graph *graph = (Graph *)malloc(sizeof(Graph));  
  112.     MakeGraph(graph); //建立圖的鄰接表  
  113.     BFS(graph); //廣度優(yōu)先遍歷  
  114.   
  115.     return 0;  
  116. }  

圖一中的圖,，運行上述程序得到的結(jié)果如圖二。

圖一


圖二

    本站是提供個人知識管理的網(wǎng)絡存儲空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式,、誘導購買等信息,，謹防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請點擊一鍵舉報,。
    轉(zhuǎn)藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多