#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<deque>using namespace std;template <typename T> class Graph {private:int Ne,Nv;//Nv為頂點(diǎn)數(shù),Ne為邊數(shù)T *weight;//wieght為權(quán)重?cái)?shù)組char *data;//data保存頂點(diǎn)數(shù)據(jù)int *visited;//用于遍歷 void coreDFS(int j){for(int i=0;i<Nv;i++){if(*(weight+j*Nv+i)==1 && !visited[i])//有鄰接點(diǎn){printf("%c",data[i]);visited[i]=true;coreDFS(i);//找下一個(gè)節(jié)點(diǎn)并打印} } }public:Graph(int numV){Nv = numV;Ne = 0;weight = (T*)calloc(numV*numV*sizeof(int),1);data = (char*)calloc(numV,1);visited = (int*)calloc(numV*sizeof(int),1);//初始化數(shù)據(jù) }bool initVertexData(const char *d){if(strlen(d)>=Nv){strncpy(data,d,Nv);//只復(fù)制Nv個(gè)節(jié)點(diǎn)數(shù)據(jù) return true;}else{return false;}}bool insertEdge(char i,char j,T w)//有向圖還是無向圖 {int pi = strchr(data,i)-data;int pj = strchr(data,j)-data;if(pi<Nv&&pj<Nv){*(weight+pi*Nv+pj) = w;*(weight+pj*Nv+pi) = w;Ne++;//邊數(shù)加1 return true;}else{return false;}}void DFS(){memset(visited,0,Nv*sizeof(int));printf("\n");for(int i=0;i<Nv;i++)//對(duì)每個(gè)節(jié)點(diǎn)做一次深度遍歷 {if(!visited[i]){visited[i]=true;printf("%c",data[i]);coreDFS(i);}}printf("\n");}void BFS(){memset(visited,0,Nv*sizeof(int));//標(biāo)記為沒有訪問過deque<int> q;printf("\n");for(int i=0;i<Nv;i++)//進(jìn)行廣度優(yōu)先搜索 {q.push_back(i);while(!q.empty()){int k = q.front();q.pop_front(); if(!visited[k]){//沒有訪問，先訪問 printf("%c",data[k]);visited[k]=true;//標(biāo)記為已訪問 }for(int j=0;j<Nv;j++){if(*(weight+i*Nv+j)==1 && !visited[j]){printf("%c",data[j]);visited[j] = true;q.push_back(j);//下一次要遍歷的頂點(diǎn) }}}}printf("\n");}void showSelf(){for(int i=0;i<Nv;i++){for(int j=0;j<Nv;j++){printf("%d\t",*(weight+i*Nv+j));}printf("\n");}}//用于調(diào)試，打印鄰接表 };int main() { Graph<int> g = Graph<int>(5);//建立一個(gè)有5個(gè)頂點(diǎn)的圖,weight為int型g.initVertexData("abcde");g.insertEdge('a','b',1);g.insertEdge('a','c',1);g.insertEdge('c','e',1);g.insertEdge('a','d',1);g.insertEdge('e','d',1);cout << "深度遍歷:";g.DFS();cout << "廣度遍歷:";g.BFS();g.showSelf();return 0; }

遍歷的圖：

結(jié)果:

總結(jié)

以上是生活随笔為你收集整理的C/C++实现图的广度和深度遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。