測試時用的圖是，可以使用其他類型的圖代替。

graph.h #ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED#define MAXV 100 //最大頂點個數 #define INF 32767 //INF表示∞ typedef int InfoType;//以下定義鄰接矩陣類型 typedef struct {int no; //頂點編號InfoType info; //頂點其他信息，在此存放帶權圖權值 } VertexType; //頂點類型typedef struct //圖的定義 {int edges[MAXV][MAXV]; //鄰接矩陣int n,e; //頂點數，弧數VertexType vexs[MAXV]; //存放頂點信息 } MGraph; //圖的鄰接矩陣類型 //以下定義鄰接表類型 typedef struct ANode //弧的結點結構類型 {int adjvex; //該弧的終點位置struct ANode *nextarc; //指向下一條弧的指針InfoType info; //該弧的相關信息,這里用于存放權值 } ArcNode;typedef int Vertex;typedef struct Vnode //鄰接表頭結點的類型 {Vertex data; //頂點信息int count; //存放頂點入度,只在拓撲排序中用ArcNode *firstarc; //指向第一條弧 } VNode;typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型typedef struct {AdjList adjlist; //鄰接表int n,e; //圖中頂點數n和邊數e } ALGraph; //圖的鄰接表類型 void ArrayToList(int *Arr, int n, ALGraph *&); //用普通數組構造圖的鄰接表 #endif // GRAPH_H_INCLUDEDgraph.cpp #include <stdio.h> #include <malloc.h> #include "graph.h" //功能：由一個反映圖中頂點鄰接關系的二維數組，構造出用鄰接矩陣存儲的圖 //參數：Arr - 數組名，由于形式參數為二維數組時必須給出每行的元素個數，在此將參數Arr聲明為一維數組名（指向int的指針） // n - 矩陣的階數 // g - 要構造出來的鄰接矩陣數據結構 void ArrayToList(int *Arr, int n, ALGraph *&G) {int i,j,count=0; //count用于統計邊數，即矩陣中非0元素個數ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));G->n=n;for (i=0; i<n; i++) //給鄰接表中所有頭節點的指針域置初值G->adjlist[i].firstarc=NULL;for (i=0; i<n; i++) //檢查鄰接矩陣中每個元素for (j=n-1; j>=0; j--)if (Arr[i*n+j]!=0) //存在一條邊，將Arr看作n×n的二維數組，Arr[i*n+j]=Arr[i][j]（n是有多少列）{p=(ArcNode *)malloc(sizeof(ArcNode)); //創建一個節點*pp->adjvex=j;p->info=Arr[i*n+j];p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入*p,和鏈表的操作一樣G->adjlist[i].firstarc=p;}G->e=count; } main.cpp #include <stdio.h> #include <malloc.h> #include "graph.h" void BFS(ALGraph *G, int v) {ArcNode *p;int w,i;int queue[MAXV],front=0,rear=0; //定義循環隊列int visited[MAXV]; //定義存放節點的訪問標志的數組for (i=0; i<G->n; i++) visited[i]=0; //訪問標志數組初始化printf("%2d",v); //輸出被訪問頂點的編號visited[v]=1; //置已訪問標記rear=(rear+1)%MAXV;queue[rear]=v; //v進隊while (front!=rear) //若隊列不空時循環{front=(front+1)%MAXV;w=queue[front]; //出隊并賦給wp=G->adjlist[w].firstarc; //找w的第一個的鄰接點while (p!=NULL){if (visited[p->adjvex]==0){printf("%2d",p->adjvex); //訪問之visited[p->adjvex]=1;rear=(rear+1)%MAXV; //該頂點進隊queue[rear]=p->adjvex;}p=p->nextarc; //找下一個鄰接頂點}}printf("\n"); } int main() {ALGraph *G;int A[5][5]={{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}};ArrayToList(A[0], 5, G);printf(" 由2開始廣度遍歷:");BFS(G, 2);printf(" 由0開始廣度遍歷:");BFS(G, 0);return 0; }

總結

以上是生活随笔為你收集整理的第十一周项目实践4 BFS(广度优先搜索)基本模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。