圖的遍歷主要就是這兩種遍歷思想，深度優(yōu)先使用遞歸方式，需要棧結(jié)構(gòu)輔助實(shí)現(xiàn)。廣度優(yōu)先需要使用隊(duì)列結(jié)構(gòu)輔助實(shí)現(xiàn)。在遍歷過程中可以看出，對(duì)于連通圖，從圖的任意一個(gè)頂點(diǎn)開始深度或廣度優(yōu)先遍歷一定可以訪問圖中的所有頂點(diǎn)，但對(duì)于非連通圖，從圖的任意一個(gè)頂點(diǎn)開始深度或廣度優(yōu)先遍歷并不能訪問圖中的所有頂點(diǎn)。
一、深度遍歷
1 算法思想
深度優(yōu)先思想：假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問，則從某個(gè)頂點(diǎn)v出發(fā)，首先訪問該頂點(diǎn)，然后依次從它的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)尚有其他頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。
2 算法特點(diǎn)
深度優(yōu)先是一個(gè)遞歸的過程。首先，選定一個(gè)出發(fā)點(diǎn)后進(jìn)行遍歷，如果有鄰接的未被訪問過的節(jié)點(diǎn)則繼續(xù)前進(jìn)。若不能繼續(xù)前進(jìn)，則回退一步再前進(jìn)，若回退一步仍然不能前進(jìn)，則連續(xù)回退至可以前進(jìn)的位置為止。重復(fù)此過程，直到所有與選定點(diǎn)相通的所有頂點(diǎn)都被遍歷。
深度優(yōu)先是遞歸過程，帶有回退操作，因此需要使用棧存儲(chǔ)訪問的路徑信息。當(dāng)訪問到的當(dāng)前頂點(diǎn)沒有可以前進(jìn)的鄰接頂點(diǎn)時(shí)，需要進(jìn)行出棧操作，將當(dāng)前位置回退至出棧元素位置。
3 圖解過程
3.1 無向圖深度優(yōu)先搜索
以圖中所示無向圖說明深度優(yōu)先搜索遍歷過程。
（1）首先選取頂點(diǎn)A為起始點(diǎn)，輸出A頂點(diǎn)信息，且將A入棧，并標(biāo)記A為已訪問頂點(diǎn)。
（2）A的鄰接頂點(diǎn)有C、D、F，從中任意選取一個(gè)頂點(diǎn)前進(jìn)。這里我們選取C頂點(diǎn)為前進(jìn)位置頂點(diǎn)。輸出C頂點(diǎn)信息，將C入棧，并標(biāo)記C為已訪問頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)C。
（3）頂點(diǎn)C的鄰接頂點(diǎn)有A、D和B，此時(shí)A已經(jīng)標(biāo)記為已訪問頂點(diǎn)，因此不能繼續(xù)訪問。從B或者D中選取一個(gè)頂點(diǎn)前進(jìn)，這里我們選取B頂點(diǎn)為前進(jìn)位置頂點(diǎn)。輸出B頂點(diǎn)信息，將B入棧，標(biāo)記B頂點(diǎn)為已訪問頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)B。
（4）頂點(diǎn)B的鄰接頂點(diǎn)只有C、E，C已被標(biāo)記，不能繼續(xù)訪問，因此選取E為前進(jìn)位置頂點(diǎn)，輸出E頂點(diǎn)信息，將E入棧，標(biāo)記E頂點(diǎn)，當(dāng)前位置指向E。
（5）頂點(diǎn)E的鄰接頂點(diǎn)均已被標(biāo)記，此時(shí)無法繼續(xù)前進(jìn)，則需要進(jìn)行回退。將當(dāng)前位置回退至頂點(diǎn)B，回退的同時(shí)將E出棧。
（6）頂點(diǎn)B的鄰接頂點(diǎn)也均被標(biāo)記，需要繼續(xù)回退，當(dāng)前位置回退至C，回退同時(shí)將B出棧。
（7）頂點(diǎn)C可以前進(jìn)的頂點(diǎn)位置為D，則輸出D頂點(diǎn)信息，將D入棧，并標(biāo)記D頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)D。
（8）頂點(diǎn)D沒有前進(jìn)的頂點(diǎn)位置，因此需要回退操作。將當(dāng)前位置回退至頂點(diǎn)C，回退同時(shí)將D出棧。
（9）頂點(diǎn)C沒有前進(jìn)的頂點(diǎn)位置，繼續(xù)回退，將當(dāng)前位置回退至頂點(diǎn)A，回退同時(shí)將C出棧。
（10）頂點(diǎn)A前進(jìn)的頂點(diǎn)位置為F，輸出F頂點(diǎn)信息，將F入棧，并標(biāo)記F。將當(dāng)前位置指向頂點(diǎn)F。
（11）頂點(diǎn)F的前進(jìn)頂點(diǎn)位置為G，輸出G頂點(diǎn)信息，將G入棧，并標(biāo)記G。將當(dāng)前位置指向頂點(diǎn)G。
（12）頂點(diǎn)G沒有前進(jìn)頂點(diǎn)位置，回退至F。當(dāng)前位置指向F，回退同時(shí)將G出棧。
（13）頂點(diǎn)F沒有前進(jìn)頂點(diǎn)位置，回退至A，當(dāng)前位置指向A，回退同時(shí)將F出棧。
（14）頂點(diǎn)A沒有前進(jìn)頂點(diǎn)位置，繼續(xù)回退，棧為空，則以A為起始的遍歷結(jié)束。若圖中仍有未被訪問的頂點(diǎn)，則選取未訪問的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過程。直至所有頂點(diǎn)均被訪問。
（15）采用深度優(yōu)先搜索遍歷順序?yàn)锳->C->B->E->D->F->G。
3.2 有向圖深度優(yōu)先搜索
以圖中所示有向圖說明深度優(yōu)先搜索遍歷過程。
（1）以頂點(diǎn)A為起始點(diǎn)，輸出A，將A入棧，并標(biāo)記A。當(dāng)前位置指向A。
（2）以A為尾的邊只有1條，且邊的頭為頂點(diǎn)B，則前進(jìn)位置為頂點(diǎn)B，輸出B，將B入棧，標(biāo)記B。當(dāng)前位置指向B。
（3）頂點(diǎn)B可以前進(jìn)的位置有C與F，選取F為前進(jìn)位置，輸出F，將F入棧，并標(biāo)記F。當(dāng)前位置指向F。
（4）頂點(diǎn)F的前進(jìn)位置為G，輸出G，將G入棧，并標(biāo)記G。當(dāng)前位置指向G。
（5）頂點(diǎn)G沒有可以前進(jìn)的位置，則回退至F，將F出棧。當(dāng)前位置指向F。
（6）頂點(diǎn)F沒有可以前進(jìn)的位置，繼續(xù)回退至B，將F出棧。當(dāng)前位置指向B。
（7）頂點(diǎn)B可以前進(jìn)位置為C和E，選取E，輸出E，將E入棧，并標(biāo)記E。當(dāng)前位置指向E。
（8）頂點(diǎn)E的前進(jìn)位置為D，輸出D，將D入棧，并標(biāo)記D。當(dāng)前位置指向D。
（9）頂點(diǎn)D的前進(jìn)位置為C，輸出C，將C入棧，并標(biāo)記C。當(dāng)前位置指向C。
（10）頂點(diǎn)C沒有前進(jìn)位置，進(jìn)行回退至D，回退同時(shí)將C出棧。
（11）繼續(xù)執(zhí)行此過程，直至棧為空，以A為起始點(diǎn)的遍歷過程結(jié)束。若圖中仍有未被訪問的頂點(diǎn)，則選取未訪問的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過程。直至所有頂點(diǎn)均被訪問。
4 算法分析
當(dāng)圖采用鄰接矩陣存儲(chǔ)時(shí)，由于矩陣元素個(gè)數(shù)為n2，因此時(shí)間復(fù)雜度就是O(n2)。
當(dāng)圖采用鄰接表存儲(chǔ)時(shí)，鄰接表中只是存儲(chǔ)了邊結(jié)點(diǎn)(e條邊，無向圖也只是2e個(gè)結(jié)點(diǎn))，加上表頭結(jié)點(diǎn)為n（也就是頂點(diǎn)個(gè)數(shù)），因此時(shí)間復(fù)雜度為O(n+e)。
5 鄰接矩陣的深度優(yōu)先遍歷
typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */
typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */
#define MAXSIZE 9 /* 存儲(chǔ)空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef struct
{
VertexType vexs[MAXVEX]; /* 頂點(diǎn)表 */
EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣，可看作邊表 */
int numVertexes, numEdges; /* 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù) */
}MGraph;
/*4.1 構(gòu)建一個(gè)鄰接矩陣*/
void CreateMGraph(MGraph *G)
{
int i, j;
//1. 確定圖的頂點(diǎn)數(shù)以及邊數(shù)
G->numEdges=15;
G->numVertexes=9;
/*2.讀入頂點(diǎn)信息，建立頂點(diǎn)表 */
G->vexs[0]='A';
G->vexs[1]='B';
G->vexs[2]='C';
G->vexs[3]='D';
G->vexs[4]='E';
G->vexs[5]='F';
G->vexs[6]='G';
G->vexs[7]='H';
G->vexs[8]='I';
/*3. 初始化圖中的邊表*/
for (i = 0; i < G->numVertexes; I++)
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
/*4.將圖中的連接信息輸入到邊表中*/
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=1;
G->arc[3][8]=1;
G->arc[4][5]=1;
G->arc[4][7]=1;
G->arc[5][6]=1;
G->arc[6][7]=1;
/*5.無向圖是對(duì)稱矩陣.構(gòu)成對(duì)稱*/
for(i = 0; i < G->numVertexes; I++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*4.2 DFS遍歷*/
Boolean visited[MAXVEX]; /* 訪問標(biāo)志的數(shù)組 */
//1. 標(biāo)識(shí)頂點(diǎn)是否被標(biāo)記過;
//2. 選擇從某一個(gè)頂點(diǎn)開始(注意:非連通圖的情況)
//3. 進(jìn)入遞歸,打印i點(diǎn)信息,標(biāo)識(shí); 邊表
//4. [i][j] 是否等于1,沒有變遍歷過visted
void DFS(MGraph G,int i){
//1.
visited[i] = TRUE;
printf("%c",G.vexs[I]);
//2.0~numVertexes
for(int j = 0; j < G.numVertexes;j++){
if(G.arc[i][j] == 1 && !visited[j])
DFS(G, j);
}
}
void DFSTravese(MGraph G){
//1.初始化
for(int i=0;i<G.numVertexes;i++){
visited[i] = FALSE;
}
//2.某一個(gè)頂點(diǎn)
for(int i = 0;i<G.numVertexes;i++){
if(!visited[I]){
DFS(G, i);
}
}
}
6 鄰接表的深度優(yōu)先遍歷
#define MAXSIZE 9 /* 存儲(chǔ)空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */
typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */
/* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{
VertexType vexs[MAXVEX]; /* 頂點(diǎn)表 */
EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */
int numVertexes, numEdges; /* 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù) */
}MGraph;
/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點(diǎn) */
{
int adjvex; /* 鄰接點(diǎn)域,存儲(chǔ)該頂點(diǎn)對(duì)應(yīng)的下標(biāo) */
int weight; /* 用于存儲(chǔ)權(quán)值,對(duì)于非網(wǎng)圖可以不需要 */
struct EdgeNode *next; /* 鏈域,指向下一個(gè)鄰接點(diǎn) */
}EdgeNode;
typedef struct VertexNode /* 頂點(diǎn)表結(jié)點(diǎn) */
{
int in; /* 頂點(diǎn)入度 */
char data; /* 頂點(diǎn)域,存儲(chǔ)頂點(diǎn)信息 */
EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes,numEdges; /* 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/*4.1 構(gòu)建一個(gè)鄰接矩陣*/
void CreateMGraph(MGraph *G)
{
int i, j;
//1. 確定圖的頂點(diǎn)數(shù)以及邊數(shù)
G->numEdges=15;
G->numVertexes=9;
/*2.讀入頂點(diǎn)信息，建立頂點(diǎn)表 */
G->vexs[0]='A';
G->vexs[1]='B';
G->vexs[2]='C';
G->vexs[3]='D';
G->vexs[4]='E';
G->vexs[5]='F';
G->vexs[6]='G';
G->vexs[7]='H';
G->vexs[8]='I';
/*3. 初始化圖中的邊表*/
for (i = 0; i < G->numVertexes; I++)
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
/*4.將圖中的連接信息輸入到邊表中*/
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=1;
G->arc[3][8]=1;
G->arc[4][5]=1;
G->arc[4][7]=1;
G->arc[5][6]=1;
G->arc[6][7]=1;
/*5.無向圖是對(duì)稱矩陣.構(gòu)成對(duì)稱*/
for(i = 0; i < G->numVertexes; I++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*4.2 利用鄰接矩陣構(gòu)建鄰接表*/
void CreateALGraph(MGraph G,GraphAdjList *GL){
//1.創(chuàng)建鄰接表,并且設(shè)計(jì)鄰接表的頂點(diǎn)數(shù)以及弧數(shù)
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes = G.numVertexes;
(*GL)->numEdges = G.numEdges;
//2. 從鄰接矩陣中將頂點(diǎn)信息輸入
for (int i = 0; i < G.numVertexes; i++) {
//頂點(diǎn)入度為0
(*GL)->adjList[i].in = 0;
//頂點(diǎn)信息
(*GL)->adjList[i].data = G.vexs[i];
//頂點(diǎn)邊表置空
(*GL)->adjList[i].firstedge = NULL;
}
//3. 建立邊表
EdgeNode *e;
for (int i = 0; i < G.numVertexes; i++) {
for (int j = 0; j < G.numVertexes; j++) {
if (G.arc[i][j] == 1) {
//創(chuàng)建邊表中的鄰近結(jié)點(diǎn) i->j
e = (EdgeNode *)malloc(sizeof(EdgeNode));
//鄰接序號(hào)為j
e->adjvex = j;
//將當(dāng)前結(jié)點(diǎn)的指向adjList[i]的頂點(diǎn)邊表上
e->next = (*GL)->adjList[i].firstedge;
(*GL)->adjList[i].firstedge = e;
//頂點(diǎn)j 上的入度++;
(*GL)->adjList[j].in++;
// //創(chuàng)建邊表中的鄰近結(jié)點(diǎn) j->i
// e = (EdgeNode *)malloc(sizeof(EdgeNode));
// //鄰接序號(hào)為j
// e->adjvex = I;
// //將當(dāng)前結(jié)點(diǎn)的指向adjList[i]的頂點(diǎn)邊表上
// e->next = (*GL)->adjList[j].firstedge;
// (*GL)->adjList[j].firstedge = e;
// //頂點(diǎn)j 上的入度++;
// (*GL)->adjList[i].in++;
}
}
}
}
Boolean visited[MAXSIZE]; /* 訪問標(biāo)志的數(shù)組 */
/* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
//2.打印頂點(diǎn) A
printf("%c ",GL->adjList[i].data);
p = GL->adjList[i].firstedge;
//3.
while (p) {
if(!visited[p->adjvex])
DFS(GL,p->adjvex);
p = p->next;
}
}
/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{
//1. 將訪問記錄數(shù)組默認(rèn)置為FALSE
for (int i = 0; i < GL->numVertexes; i++) {
/*初始化所有頂點(diǎn)狀態(tài)都是未訪問過的狀態(tài)*/
visited[i] = FALSE;
}
//2. 選擇一個(gè)頂點(diǎn)開始DFS遍歷. 例如A
for(int i = 0; i < GL->numVertexes; I++)
//對(duì)未訪問過的頂點(diǎn)調(diào)用DFS, 若是連通圖則只會(huì)執(zhí)行一次.
if(!visited[I])
DFS(GL, i);
}
二、廣度遍歷
1 算法思想
廣度優(yōu)先思想：從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。
2 算法特點(diǎn)
廣度優(yōu)先類似于樹的層次遍歷，是按照一種由近及遠(yuǎn)的方式訪問圖的頂點(diǎn)。在進(jìn)行廣度優(yōu)先時(shí)需要使用隊(duì)列存儲(chǔ)頂點(diǎn)信息。
3 圖解過程
3.1 無向圖的廣度優(yōu)先搜索
（1）選取A為起始點(diǎn)，輸出A，A入隊(duì)列，標(biāo)記A，當(dāng)前位置指向A。
（2）隊(duì)列頭為A，A出隊(duì)列。A的鄰接頂點(diǎn)有B、E，輸出B和E，將B和E入隊(duì)，并標(biāo)記B、E。當(dāng)前位置指向A。
（3）隊(duì)列頭為B，B出隊(duì)列。B的鄰接頂點(diǎn)有C、D，輸出C、D，將C、D入隊(duì)列，并標(biāo)記C、D。當(dāng)前位置指向B。
（4）隊(duì)列頭為E，E出隊(duì)列。E的鄰接頂點(diǎn)有D、F，但是D已經(jīng)被標(biāo)記，因此輸出F，將F入隊(duì)列，并標(biāo)記F。當(dāng)前位置指向E。
（5）隊(duì)列頭為C，C出隊(duì)列。C的鄰接頂點(diǎn)有B、D，但B、D均被標(biāo)記。無元素入隊(duì)列。當(dāng)前位置指向C。
（6）隊(duì)列頭為D，D出隊(duì)列。D的鄰接頂點(diǎn)有B、C、E，但是B、C、E均被標(biāo)記，無元素入隊(duì)列。當(dāng)前位置指向D。
（7）隊(duì)列頭為F，F(xiàn)出隊(duì)列。F的鄰接頂點(diǎn)有G、H，輸出G、H，將G、H入隊(duì)列，并標(biāo)記G、H。當(dāng)前位置指向F。
（8）隊(duì)列頭為G，G出隊(duì)列。G的鄰接頂點(diǎn)有F，但F已被標(biāo)記，無元素入隊(duì)列。當(dāng)前位置指向G。
（9）隊(duì)列頭為H，H出隊(duì)列。H的鄰接頂點(diǎn)有F，但F已被標(biāo)記，無元素入隊(duì)列。當(dāng)前位置指向H。
（10）隊(duì)列空，則以A為起始點(diǎn)的遍歷結(jié)束。若圖中仍有未被訪問的頂點(diǎn)，則選取未訪問的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過程。直至所有頂點(diǎn)均被訪問。
3.2 有向圖的廣度優(yōu)先搜索
（1）選取A為起始點(diǎn)，輸出A，將A入隊(duì)列，標(biāo)記A。
（2）隊(duì)列頭為A，A出隊(duì)列。以A為尾的邊有兩條，對(duì)應(yīng)的頭分別為B、C，則A的鄰接頂點(diǎn)有B、C。輸出B、C，將B、C入隊(duì)列，并標(biāo)記B、C。
（3）隊(duì)列頭為B，B出隊(duì)列。B的鄰接頂點(diǎn)為C，C已經(jīng)被標(biāo)記，因此無新元素入隊(duì)列。
（4）隊(duì)列頭為C，C出隊(duì)列。C的鄰接頂點(diǎn)有E、F。輸出E、F，將E、F入隊(duì)列，并標(biāo)記E、F。
（5）隊(duì)列頭為E，E出隊(duì)列。E的鄰接頂點(diǎn)有G、H。輸出G、H，將G、H入隊(duì)列，并標(biāo)記G、H。
（6）隊(duì)列頭為F，F(xiàn)出隊(duì)列。F無鄰接頂點(diǎn)。
（7）隊(duì)列頭為G，G出隊(duì)列。G無鄰接頂點(diǎn)。
（8）隊(duì)列頭為H，H出隊(duì)列。H鄰接頂點(diǎn)為E，但是E已被標(biāo)記，無新元素入隊(duì)列。
（9）隊(duì)列為空，以A為起始點(diǎn)的遍歷過程結(jié)束，此時(shí)圖中仍有D未被訪問，則以D為起始點(diǎn)繼續(xù)遍歷。選取D為起始點(diǎn)，輸出D，將D入隊(duì)列，標(biāo)記D。
（10）隊(duì)列頭為D，D出隊(duì)列，D的鄰接頂點(diǎn)為B，B已被標(biāo)記，無新元素入隊(duì)列。
（11）隊(duì)列為空，且所有元素均被訪問，廣度優(yōu)先搜索遍歷過程結(jié)束。廣度優(yōu)先搜索的輸出序列為：A->B->E->C->D->F->G->H。
3.4 算法分析
假設(shè)圖有V個(gè)頂點(diǎn)，E條邊，廣度優(yōu)先搜索算法需要搜索V個(gè)節(jié)點(diǎn)，時(shí)間消耗是O(V)，在搜索過程中，又需要根據(jù)邊來增加隊(duì)列的長度，于是這里需要消耗O(E)，總得來說，效率大約是O(V+E)。
5 鄰接矩陣的廣度優(yōu)先遍歷
typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */
#define MAXSIZE 9 /* 存儲(chǔ)空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef struct
{
VertexType vexs[MAXVEX]; /* 頂點(diǎn)表 */
EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣，可看作邊表 */
int numVertexes, numEdges; /* 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù) */
}MGraph;
/*4.1 構(gòu)建一個(gè)鄰接矩陣*/
void CreateMGraph(MGraph *G)
{
int i, j;
//1. 確定圖的頂點(diǎn)數(shù)以及邊數(shù)
G->numEdges=15;
G->numVertexes=9;
/*2.讀入頂點(diǎn)信息，建立頂點(diǎn)表 */
G->vexs[0]='A';
G->vexs[1]='B';
G->vexs[2]='C';
G->vexs[3]='D';
G->vexs[4]='E';
G->vexs[5]='F';
G->vexs[6]='G';
G->vexs[7]='H';
G->vexs[8]='I';
/*3. 初始化圖中的邊表*/
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
/*4.將圖中的連接信息輸入到邊表中*/
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=1;
G->arc[3][8]=1;
G->arc[4][5]=1;
G->arc[4][7]=1;
G->arc[5][6]=1;
G->arc[6][7]=1;
/*5.無向圖是對(duì)稱矩陣.構(gòu)成對(duì)稱*/
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*
4.2 ***需要用到的隊(duì)列結(jié)構(gòu)與相關(guān)功能函數(shù)***
*/
/* 循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) */
typedef struct
{
int data[MAXSIZE];
int front; /* 頭指針 */
int rear; /* 尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置 */
}Queue;
/* 初始化一個(gè)空隊(duì)列Q */
Status InitQueue(Queue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
/* 若隊(duì)列Q為空隊(duì)列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{
if(Q.front==Q.rear) /* 隊(duì)列空的標(biāo)志 */
return TRUE;
else
return FALSE;
}
/* 若隊(duì)列未滿，則插入元素e為Q新的隊(duì)尾元素 */
Status EnQueue(Queue *Q,int e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊(duì)列滿的判斷 */
return ERROR;
Q->data[Q->rear]=e; /* 將元素e賦值給隊(duì)尾 */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置， */
/* 若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
/* 若隊(duì)列不空，則刪除Q中隊(duì)頭元素，用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
if (Q->front == Q->rear) /* 隊(duì)列空的判斷 */
return ERROR;
*e=Q->data[Q->front]; /* 將隊(duì)頭元素賦值給e */
Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置， */
/* 若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
/******** Queue End **************/
/*4.3 鄰接矩陣廣度優(yōu)先遍歷-代碼實(shí)現(xiàn)*/
Boolean visited[MAXVEX]; /* 訪問標(biāo)志的數(shù)組 */
void BFSTraverse(MGraph G){
int temp = 0;
//1.
Queue Q;
InitQueue(&Q);
//2.將訪問標(biāo)志數(shù)組全部置為"未訪問狀態(tài)FALSE"
for (int i = 0 ; i < G.numVertexes; i++) {
visited[i] = FALSE;
}
//3.對(duì)遍歷鄰接表中的每一個(gè)頂點(diǎn)(對(duì)于連通圖只會(huì)執(zhí)行1次,這個(gè)循環(huán)是針對(duì)非連通圖)
for (int i = 0 ; i < G.numVertexes; i++) {
if(!visited[i]){
visited[i] = TRUE;
printf("%c ",G.vexs[i]);
//4. 入隊(duì)
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
//出隊(duì)
DeQueue(&Q, &i);
for (int j = 0; j < G.numVertexes; j++) {
if(G.arc[i][j] == 1 && !visited[j])
{ visited[j] = TRUE;
printf("%c ",G.vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
6 鄰接表的廣度優(yōu)先遍歷
#define MAXSIZE 9 /* 存儲(chǔ)空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */
typedef char VertexType; /* 頂點(diǎn)類型應(yīng)由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */
/* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{
VertexType vexs[MAXVEX]; /* 頂點(diǎn)表 */
EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */
int numVertexes, numEdges; /* 圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù) */
}MGraph;
/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點(diǎn) */
{
int adjvex; /* 鄰接點(diǎn)域,存儲(chǔ)該頂點(diǎn)對(duì)應(yīng)的下標(biāo) */
int weight; /* 用于存儲(chǔ)權(quán)值,對(duì)于非網(wǎng)圖可以不需要 */
struct EdgeNode *next; /* 鏈域,指向下一個(gè)鄰接點(diǎn) */
}EdgeNode;
typedef struct VertexNode /* 頂點(diǎn)表結(jié)點(diǎn) */
{
int in; /* 頂點(diǎn)入度 */
char data; /* 頂點(diǎn)域,存儲(chǔ)頂點(diǎn)信息 */
EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes,numEdges; /* 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/*4.1 構(gòu)建一個(gè)鄰接矩陣*/
void CreateMGraph(MGraph *G)
{
int i, j;
//1. 確定圖的頂點(diǎn)數(shù)以及邊數(shù)
G->numEdges=15;
G->numVertexes=9;
/*2.讀入頂點(diǎn)信息，建立頂點(diǎn)表 */
G->vexs[0]='A';
G->vexs[1]='B';
G->vexs[2]='C';
G->vexs[3]='D';
G->vexs[4]='E';
G->vexs[5]='F';
G->vexs[6]='G';
G->vexs[7]='H';
G->vexs[8]='I';
/*3. 初始化圖中的邊表*/
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
G->arc[i][j]=0;
}
}
/*4.將圖中的連接信息輸入到邊表中*/
G->arc[0][1]=1;
G->arc[0][5]=1;
G->arc[1][2]=1;
G->arc[1][8]=1;
G->arc[1][6]=1;
G->arc[2][3]=1;
G->arc[2][8]=1;
G->arc[3][4]=1;
G->arc[3][7]=1;
G->arc[3][6]=1;
G->arc[3][8]=1;
G->arc[4][5]=1;
G->arc[4][7]=1;
G->arc[5][6]=1;
G->arc[6][7]=1;
/*5.無向圖是對(duì)稱矩陣.構(gòu)成對(duì)稱*/
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*4.2 利用鄰接矩陣構(gòu)建鄰接表*/
void CreateALGraph(MGraph G,GraphAdjList *GL){
//1.創(chuàng)建鄰接表,并且設(shè)計(jì)鄰接表的頂點(diǎn)數(shù)以及弧數(shù)
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes = G.numVertexes;
(*GL)->numEdges = G.numEdges;
//2. 從鄰接矩陣中將頂點(diǎn)信息輸入
for (int i = 0; i < G.numVertexes; i++) {
//頂點(diǎn)入度為0
(*GL)->adjList[i].in = 0;
//頂點(diǎn)信息
(*GL)->adjList[i].data = G.vexs[i];
//頂點(diǎn)邊表置空
(*GL)->adjList[i].firstedge = NULL;
}
//3. 建立邊表
EdgeNode *e;
for (int i = 0; i < G.numVertexes; i++) {
for (int j = 0; j < G.numVertexes; j++) {
if (G.arc[i][j] == 1) {
//創(chuàng)建邊表中的鄰近結(jié)點(diǎn) i->j
e = (EdgeNode *)malloc(sizeof(EdgeNode));
//鄰接序號(hào)為j
e->adjvex = j;
//將當(dāng)前結(jié)點(diǎn)的指向adjList[i]的頂點(diǎn)邊表上
e->next = (*GL)->adjList[i].firstedge;
(*GL)->adjList[i].firstedge = e;
//頂點(diǎn)j 上的入度++;
(*GL)->adjList[j].in++;
// //創(chuàng)建邊表中的鄰近結(jié)點(diǎn) j->i
// e = (EdgeNode *)malloc(sizeof(EdgeNode));
// //鄰接序號(hào)為j
// e->adjvex = i;
// //將當(dāng)前結(jié)點(diǎn)的指向adjList[i]的頂點(diǎn)邊表上
// e->next = (*GL)->adjList[j].firstedge;
// (*GL)->adjList[j].firstedge = e;
// //頂點(diǎn)j 上的入度++;
// (*GL)->adjList[i].in++;
}
}
}
}
/*
5.2 ***需要用到的隊(duì)列結(jié)構(gòu)與相關(guān)功能函數(shù)***
*/
/* 循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) */
typedef struct
{
int data[MAXSIZE];
int front; /* 頭指針 */
int rear; /* 尾指針,若隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置 */
}Queue;
/* 初始化一個(gè)空隊(duì)列Q */
Status InitQueue(Queue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
/* 若隊(duì)列Q為空隊(duì)列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{
if(Q.front==Q.rear) /* 隊(duì)列空的標(biāo)志 */
return TRUE;
else
return FALSE;
}
/* 若隊(duì)列未滿,則插入元素e為Q新的隊(duì)尾元素 */
Status EnQueue(Queue *Q,int e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊(duì)列滿的判斷 */
return ERROR;
Q->data[Q->rear]=e; /* 將元素e賦值給隊(duì)尾 */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, */
/* 若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
/* 若隊(duì)列不空,則刪除Q中隊(duì)頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
if (Q->front == Q->rear) /* 隊(duì)列空的判斷 */
return ERROR;
*e=Q->data[Q->front]; /* 將隊(duì)頭元素賦值給e */
Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, */
/* 若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
/* *********************** Queue End ******************************* */
/*5.3 鄰接表廣度優(yōu)先遍歷*/
Boolean visited[MAXSIZE]; /* 訪問標(biāo)志的數(shù)組 */
void BFSTraverse(GraphAdjList GL){
//1.創(chuàng)建結(jié)點(diǎn)
EdgeNode *p;
Queue Q;
InitQueue(&Q);
//2.將訪問標(biāo)志數(shù)組全部置為"未訪問狀態(tài)FALSE"
for(int i = 0; i < GL->numVertexes; i++)
visited[i] = FALSE;
//3.對(duì)遍歷鄰接表中的每一個(gè)頂點(diǎn)(對(duì)于連通圖只會(huì)執(zhí)行1次,這個(gè)循環(huán)是針對(duì)非連通圖)
for(int i = 0 ;i < GL->numVertexes;i++){
//4.判斷當(dāng)前結(jié)點(diǎn)是否被訪問過.
if(!visited[i]){
visited[i] = TRUE;
//打印頂點(diǎn)
printf("%c ",GL->adjList[i].data);
EnQueue(&Q, i);
while (!QueueEmpty(Q)) {
DeQueue(&Q, &i);
p = GL->adjList[i].firstedge;
while (p) {
//判斷
if(!visited[p->adjvex]){
visited[p->adjvex] = TRUE;
printf("%c ",GL->adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->next;
}
}
}
}
}
