前言：在上一篇博客我們學(xué)習(xí)了圖的基本操作，包括圖的建立、結(jié)點(diǎn)插入與刪除等操作，怎么判斷我們建立的圖是否正確，很簡(jiǎn)單把它輸出出來(lái)就是，但是如何輸出它，這就是圖的遍歷問(wèn)題了。
一.圖的遍歷
圖的遍歷是指從圖中的某一頂點(diǎn)出發(fā)，按照某種搜索方法沿著圖中的邊對(duì)圖中的所有頂點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。注意到樹(shù)是一種特殊的圖，所以樹(shù)的遍歷實(shí)際上也可視為一種特殊的圖的遍歷。圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。
圖的遍歷比樹(shù)的遍歷要復(fù)雜得多，因?yàn)閳D的任意一個(gè)頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接，所以在訪問(wèn)某個(gè)頂點(diǎn)后，可能沿著某條路徑搜索又回到該頂點(diǎn)上。為避免同- .頂點(diǎn)被訪問(wèn)多次，在遍歷圖的過(guò)程中，必須記下每個(gè)已訪問(wèn)過(guò)的頂點(diǎn)，為此可以設(shè)一個(gè)輔助數(shù)組visited[]來(lái)標(biāo)記項(xiàng)點(diǎn)是否被訪問(wèn)過(guò)。圖的遍歷算法主要有兩種：廣度優(yōu)先搜索和深度優(yōu)先搜索。
二.廣度優(yōu)先搜索（BFS）
1.基本原理
廣度優(yōu)先搜索( Breadth-First-Search, BFS)類(lèi)似于二叉樹(shù)的層序遍歷算法?；舅枷胧?首先訪問(wèn)起始頂點(diǎn)v，接著由v出發(fā)，依次訪問(wèn)v的各個(gè)未訪問(wèn)過(guò)的鄰接頂點(diǎn)w1, w2…,wn，然后依次訪問(wèn)w1, w2…, wn;的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn);再?gòu)倪@些訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，訪問(wèn)它們所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，直至圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法也應(yīng)用了類(lèi)似的思想。換句話(huà)說(shuō)，廣度優(yōu)先搜索遍歷圖的過(guò)程是以v為起始點(diǎn)，由近至遠(yuǎn)依次訪問(wèn)和v有路徑相通且路徑長(zhǎng)度為1,2,… 的頂點(diǎn)。廣度優(yōu)先搜索是-種分層的查找過(guò)程，每向前走一步可能訪問(wèn)-批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況，因此它不是一個(gè)遞歸的算法。為了實(shí)現(xiàn)逐層的訪問(wèn)，算法必須借助一 個(gè)輔助隊(duì)列，以記憶正在訪問(wèn)的頂點(diǎn)的下一層頂點(diǎn)。
2.舉例說(shuō)明
假設(shè)從a結(jié)點(diǎn)開(kāi)始訪問(wèn)，a先入隊(duì)。此時(shí)隊(duì)列非空，取出隊(duì)頭元素a,由于b,c與a鄰接且未被訪問(wèn)過(guò)，于是依次訪問(wèn)b,c,并將b,c依次入隊(duì)。隊(duì)列非空，取出隊(duì)頭元素b,依次訪問(wèn)與b鄰接且未被訪問(wèn)的頂點(diǎn)d,e,并將d,e入隊(duì)(注意: a與b也鄰接，但a已置訪問(wèn)標(biāo)記，故不再重復(fù)訪問(wèn))。此時(shí)隊(duì)列非空，取出隊(duì)頭元素c,訪問(wèn)與c鄰接且未被訪問(wèn)的頂點(diǎn)f,g,并將f,g入隊(duì)。此時(shí)，取出隊(duì)頭元素d,但與d鄰接且未被訪問(wèn)的頂點(diǎn)為空，故不進(jìn)行任何操作。繼續(xù)取出隊(duì)頭元素e,將h入隊(duì)列…最終取出隊(duì)頭元素h后，隊(duì)列為空，從而循環(huán)自動(dòng)跳出。遍歷結(jié)果為abcdefgh。
三.深度優(yōu)先收索（DFS）
1.基本原理
與廣度優(yōu)先搜索不同，深度優(yōu)先搜索(Depth-First-Search, DFS)類(lèi)似于樹(shù)的先序遍歷。如其名稱(chēng)中所暗含的意思-樣，這種搜索算法所遵循的搜索策略是盡可能“深”地搜索一個(gè)圖。它的基本思想如下:首先訪問(wèn)圖中某- -起始頂點(diǎn)v,然后由v出發(fā)，訪問(wèn)與v鄰接且未被訪問(wèn)的任意一個(gè)頂點(diǎn)w，再訪問(wèn)與wi鄰接且未被訪問(wèn)的任意-一個(gè) 頂點(diǎn)…重復(fù)上述過(guò)程。當(dāng)不能再繼續(xù)向下訪問(wèn)時(shí)，依次退回到最近被訪問(wèn)的頂點(diǎn)，若它還有鄰接頂點(diǎn)未被訪問(wèn)過(guò)，則從該點(diǎn)開(kāi)始繼續(xù)上述搜索過(guò)程，直至圖中所有頂點(diǎn)均被訪問(wèn)過(guò)為止。
2.舉例說(shuō)明
以BFS例子的無(wú)向圖為例，深度優(yōu)先搜索的過(guò)程:首先訪問(wèn)a,并置a訪問(wèn)標(biāo)記;然后訪問(wèn)與a鄰接且未被訪問(wèn)的頂點(diǎn)b,置b訪問(wèn)標(biāo)記;然后訪問(wèn)與b鄰接且未被訪問(wèn)的頂點(diǎn)d,置d訪問(wèn)標(biāo)記。此時(shí)d已沒(méi)有未被訪問(wèn)過(guò)的鄰接點(diǎn)，故返回上一個(gè)訪問(wèn)過(guò)的頂點(diǎn)b,訪問(wèn)與其鄰接且未被訪問(wèn)的頂點(diǎn)e，置e .標(biāo)…以此類(lèi)推，直至圖中所有的頂點(diǎn)都被訪問(wèn)一次。遍歷結(jié)果為abdehcfg。
四.核心功能實(shí)現(xiàn)
1.BFS函數(shù)
void BFS(Graph *G,char x){
int n;
for(int i=0;i<G->vertex_num;i++){
if(G->vertex[i]==x) {
n=i;
break;
}
}
if(n == -1){
printf("Error: 結(jié)點(diǎn)不存在\n");
}
char queue[MAX_VERTEX_NUM], front = -1, rear = -1;
queue[++rear] = G->vertex[n];
visited[n] = true;
while(front !=rear){
char current_vertex=queue[++front];
printf("%c ",current_vertex);
for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){
if(!visited[w]){
queue[++rear]=G->vertex[w];
visited[w]=true;
}
}
}
}
2.DFS函數(shù)
//DFS函數(shù)
void DFS(Graph *G,char x){
int n;
for(int i=0;i<G->vertex_num;i++){
if(G->vertex[i]==x) {
n=i;
break;
}
}
if(n == -1){
printf("Error: 結(jié)點(diǎn)不存在\n");
}
printf("%c ",G->vertex[n]); //訪問(wèn)頂點(diǎn)
visited2[n]=true;
for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))
if(!visited2[w]){
DFS(G,G->vertex[w]);
}
}
//DFS相比BFS函數(shù)，它使用的是棧也就是遞歸操作
3.效率分析
BFS（廣度優(yōu)先搜索）和DFS（深度優(yōu)先搜索）是兩種不同的圖遍歷算法，它們的時(shí)間和空間復(fù)雜度分析也有所不同。
對(duì)于BFS算法，其時(shí)間復(fù)雜度為O(|V|+|E|)，其中|V|表示圖中節(jié)點(diǎn)的數(shù)量，|E|表示邊的數(shù)量。在BFS中，我們?cè)L問(wèn)每個(gè)節(jié)點(diǎn)一次，并且遍歷了所有與該節(jié)點(diǎn)相鄰的邊，因此時(shí)間復(fù)雜度為O(|V|+|E|)。對(duì)于空間復(fù)雜度，BFS需要使用一個(gè)隊(duì)列來(lái)存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn)，因此空間復(fù)雜度為O(|V|)，其中最壞情況下所有節(jié)點(diǎn)都在隊(duì)列中。因此，當(dāng)圖稠密時(shí)，即|E| ~ |V|^2時(shí)，BFS的空間復(fù)雜度可能會(huì)很高。
對(duì)于DFS算法，其時(shí)間復(fù)雜度與圖的連接性質(zhì)有關(guān)，最壞情況下可以達(dá)到O(|V|+|E|)。然而，實(shí)際應(yīng)用中，DFS的時(shí)間復(fù)雜度通常比BFS低。對(duì)于空間復(fù)雜度，DFS需要使用一個(gè)棧來(lái)存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn)，因此在最壞情況下，空間復(fù)雜度為O(|V|)，其中最壞情況下整個(gè)圖都是一條鏈。因此，當(dāng)圖非常深時(shí)，DFS的空間復(fù)雜度可能會(huì)很高。
總體而言，BFS和DFS的時(shí)間復(fù)雜度都是O(|V|+|E|)，其中|V|表示圖中節(jié)點(diǎn)數(shù)量，|E|表示邊數(shù)量。它們的主要區(qū)別在于空間復(fù)雜度上，BFS需要使用隊(duì)列存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn)，空間復(fù)雜度為O(|V|)，而DFS需要使用棧存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn)，空間復(fù)雜度為O(|V|)。因此，如果空間復(fù)雜度很重要，可以選擇DFS；如果需要找到最短路徑等問(wèn)題，可以選擇BFS。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-508628.html
五.完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 // 最大頂點(diǎn)數(shù)
typedef struct {
char vertex[MAX_VERTEX_NUM]; // 存放頂點(diǎn)信息
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存放邊信息
int vertex_num; // 頂點(diǎn)數(shù)
int edge_num; // 邊數(shù)
} Graph;
bool visited1[MAX_VERTEX_NUM]; //BFS訪問(wèn)標(biāo)記數(shù)組
bool visited2[MAX_VERTEX_NUM]; //DFS訪問(wèn)標(biāo)記數(shù)組
//求圖G中頂點(diǎn)x的第一個(gè)鄰接點(diǎn)下標(biāo)
int FirstNeighbor(Graph *G,char x){
int n = -1; //待查詢(xún)結(jié)點(diǎn)在數(shù)組里的下標(biāo)
for(int i=0;i<G->vertex_num;i++){
if(G->vertex[i]==x) {
n=i;
break;
}
}
if(n == -1){ // 如果查詢(xún)節(jié)點(diǎn)不存在
printf("Error: 結(jié)點(diǎn)不存在\n");
}
int count=0;
int nx; //第一個(gè)鄰接點(diǎn)在數(shù)組里的下標(biāo)
//現(xiàn)在知道了他在第n個(gè)，所以我們查詢(xún)邊矩陣第n行中第一個(gè)1在哪就知道第一個(gè)鄰接點(diǎn)是誰(shuí)
for(int j=0;j<G->vertex_num;j++){
if(G->edge[n][j]==1) count++;
if(count==1){
nx=j;
break;
}
}
return nx;
}
int NextNeighbor(Graph *G,char x,char y){
int n = -1; //待查詢(xún)結(jié)點(diǎn)在數(shù)組里的下標(biāo)
for(int i=0;i<G->vertex_num;i++){
if(G->vertex[i]==x) {
n=i;
break;
}
}
if(n == -1){ // 如果查詢(xún)節(jié)點(diǎn)不存在
printf("Error: 結(jié)點(diǎn)不存在\n");
}
int count=0;
int ny = -1; //存放返回鄰接點(diǎn)數(shù)組下標(biāo)
for(int j=0;j<G->vertex_num;j++){
if(G->vertex[j]==y) {
ny=j;
break;
}
}
int nx = -1; //存放返回鄰接點(diǎn)數(shù)組下標(biāo)
for(int j=ny+1;j<G->vertex_num;j++){
if(G->edge[n][j]==1){
nx=j;
break;
}
}
return nx;
}
void BFS(Graph *G,char x){
int n;
for(int i=0;i<G->vertex_num;i++){
if(G->vertex[i]==x) {
n=i;
break;
}
}
if(n == -1){
printf("Error: 結(jié)點(diǎn)不存在\n");
}
char queue[MAX_VERTEX_NUM], front = -1, rear = -1;
queue[++rear] = G->vertex[n];
visited1[n] = true;
while(front !=rear){
char current_vertex=queue[++front];
printf("%c ",current_vertex);
for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){
if(!visited1[w]){
queue[++rear]=G->vertex[w];
visited1[w]=true;
}
}
}
}
//你以為這就是執(zhí)行函數(shù)嗎？如果你這樣做存在多個(gè)連通分量絕對(duì)出錯(cuò)
//BFS執(zhí)行函數(shù)
void BFSTraverse(Graph *G){
for(int i=0;i<G->vertex_num;i++){
visited1[i]=false; //標(biāo)記數(shù)組初始化
}
for(int i=0;i<G->vertex_num;++i){
if(!visited1[i])
BFS(G,G->vertex[i]);
}
}
//DFS函數(shù)
void DFS(Graph *G,char x){
int n;
for(int i=0;i<G->vertex_num;i++){
if(G->vertex[i]==x) {
n=i;
break;
}
}
if(n == -1){
printf("Error: 結(jié)點(diǎn)不存在\n");
}
printf("%c ",G->vertex[n]); //訪問(wèn)頂點(diǎn)
visited2[n]=true;
for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))
if(!visited2[w]){
DFS(G,G->vertex[w]);
}
}
//DFS相比BFS函數(shù)，它使用的是棧也就是遞歸操作
//DFS執(zhí)行函數(shù)
void DFSTraverse(Graph *G){
for(int i=0;i<G->vertex_num;i++){
visited2[i]=false; //標(biāo)記數(shù)組初始化
}
for(int i=0;i<G->vertex_num;++i){
if(!visited2[i])
DFS(G,G->vertex[i]);
}
}
int main(){
Graph G;
G.vertex_num=5;
G.edge_num=6;
//人為構(gòu)造圖的頂點(diǎn)
for(int i=0;i<G.vertex_num;i++){
G.vertex[i]= 'A'+i;
}
for(int i=0; i<G.vertex_num; i++){
for(int j=0; j<G.vertex_num; j++){
G.edge[i][j]=0;
}
}
//人為構(gòu)造圖的邊
G.edge[0][1]=1;
G.edge[0][3]=1;
G.edge[1][2]=1;
G.edge[2][3]=1;
G.edge[1][4]=1;
G.edge[2][4]=1;
printf("BFS的遍歷結(jié)果為：");
BFSTraverse(&G);
printf("\n");
printf("DFS的遍歷結(jié)果為：");
DFSTraverse(&G);
return 0;
}
六.運(yùn)行結(jié)果
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-508628.html
到了這里，關(guān)于圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
