當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

数据结构与算法（7-2）图的遍历（深度优先遍历DFS、广度优先遍历BFS）（分别用邻接矩阵和邻接表实现）

發(fā)布時間：2023/11/27 生活经验 20 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构与算法（7-2）图的遍历（深度优先遍历DFS、广度优先遍历BFS）（分别用邻接矩阵和邻接表实现）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)原理

1、自己的原理圖

2、官方原理圖

一、鄰接矩陣的深度優(yōu)先遍歷（DFS）

1、原理圖

2、?過程：

3、總代碼

?二、鄰接表的深度優(yōu)先遍歷(DFS)：

1、原理圖：

?2、過程

3、總代碼

三、鄰接矩陣的廣度優(yōu)先遍歷?

1、原理圖

?2、過程

?3、總代碼

四、鄰接表的廣度優(yōu)先遍歷(BFS)

總代碼

深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)原理

1、自己的原理圖

2、官方原理圖

DFS（深度優(yōu)先遍歷）：以一個頂點為根，逐頂點地往下遍歷，遇到沒遍歷過的頂點則繼續(xù)遍歷；遇到遍歷過的頂點則回溯。（遞歸實現）

BFS（廣度優(yōu)先遍歷）：以一個頂點為根，逐層地往下遍歷，遇到遍歷的頂點遍歷；遍歷過的頂點則忽略。（隊列實現）

一、鄰接矩陣的深度優(yōu)先遍歷（DFS）

1、原理圖

2、?過程：

1、矩陣形式的話，先從根開始走，遇到0就繼續(xù)，遇到1直接跳到那一行（即跳到那一個元素），后面如此往復，用遞歸實現。

2、還有就是需要判斷結點是否已經遍歷過了，已經遍歷過的結點不再進入，由于每一列都是同一結點（待遍歷），可以通過一個判斷數組記錄每一個元素是否遍歷。

//深度優(yōu)先遍歷
void DFS(int index)
{int i, j;for (i = index; i < G.vertexNum; i++){for (j = 0; j < G.vertexNum; j++){if (i == 0 && j == 0){printf("%c", G.vertex[j]);							//輸出首元素(根)Judge[j] = 1;											//標記首列}if (G.edge[i][j] != 0 && Judge[j] == 0)		//鄰接矩陣有元素；且01數組無標記(即未被訪問){printf("%c", G.vertex[j]);if (Judge[j] == 0)									//未標記Judge[j] = 1;									//對列做標記DFS(j);}}}
}

3、總代碼

//圖的深度優(yōu)先遍歷（鄰接矩陣）
//需要創(chuàng)建一個列數組，按照矩陣的順序遍歷，為1就直接跳到那個結點
//增添一個數組，判斷每個結點是否遍歷過
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20
int ColumnArray[MAXSIZE];		//列矩陣（判斷有沒有走過）//鄰接矩陣
typedef struct
{char vertex[MAXSIZE];					//頂點int edge[MAXSIZE][MAXSIZE];		//鄰接頂點int vertexNum;								//頂點數量
}Graph;
Graph G;//輸入頂點
void InputVertex()
{int i = 0;char ch;printf("請輸入需要創(chuàng)建的圖頂點（不需要空格）：\n");do{scanf("%c", &ch);if (ch != '\n')G.vertex[i++] = ch;} while (ch != '\n');G.vertexNum = i;
}//查找（根據結點找索引）
int findIndex(char ch)
{int i;for (i = 0; i < G.vertexNum; i++){if (G.vertex[i] == ch)return i;}return -1;				//沒找到
}//創(chuàng)建圖
void InputEdge()
{int i, index;char ch;for (i = 0; i < G.vertexNum; i++){printf("請輸入%c指向的鄰接結點：\n", G.vertex[i]);scanf("%c", &ch);while (ch != '\n'){index = findIndex(ch);			//查找輸入結點的索引G.edge[i][index] = 1;scanf("%c", &ch);}}
}//01數組初始化
void InitColumnArray()
{int j;for (j = 0; j < G.vertexNum; j++)ColumnArray[j] = 0;							//標記未訪問
}//輸出測試
void Print()
{int i, j;for (i = 0; i < G.vertexNum; i++){printf("\n%c結點的鄰接結點為：\t", G.vertex[i]);for (j = 0; j < G.vertexNum; j++){if (G.edge[i][j] != 0)printf("%c\t", G.vertex[j]);}}
}//深度優(yōu)先遍歷
void DeepTraverse(int index)
{int i, j;for (i = index; i < G.vertexNum; i++){for (j = 0; j < G.vertexNum; j++){if (i == 0 && j == 0){printf("%c", G.vertex[j]);									//輸出首元素(根)ColumnArray[j] = 1;											//標記首列}if (G.edge[i][j] != 0 && ColumnArray[j] == 0)		//鄰接矩陣有元素；且01數組無標記(即未被訪問){printf("%c", G.vertex[j]);if (ColumnArray[j] == 0)									//未標記ColumnArray[j] = 1;										//對列做標記DeepTraverse(j);}}}
}int main()
{//創(chuàng)建圖InputVertex();InputEdge();InitColumnArray();printf("深度優(yōu)先遍歷結果：\n");//深度優(yōu)先遍歷DeepTraverse(0);//輸出測試//Print();return 0;
}

?二、鄰接表的深度優(yōu)先遍歷(DFS)：

1、原理圖：

?2、過程

和鄰接矩陣類似，也是使用遞歸，也是需要用一個判斷數組，表示每個頂點的鄰接矩陣是否遍歷過。只不過鄰接表需要傳一個參數lastIndex，利用這個參數把根結點輸出出去。先把指針指向firstchild，后面利用一個while循環(huán)挨個判斷鄰接結點是否遍歷過了，遍歷過則指針繼續(xù)后移；未遍歷過則遞歸調用DFS函數進入那個未遍歷的頂點，繼續(xù)一個一個判斷。

//深度優(yōu)先遍歷（按頂點操作）
//判斷的時候需要遍歷每一個鄰接頂點，而輸出的時候只需要把頂點數組的內容輸出即可
void DFS(EdgeNode* p1, int lastIndex)
{if (Judge[lastIndex] == 0)		//頂點未遍歷{Judge[lastIndex] = 1;		//標記（表示遍歷過）printf("%c", V[lastIndex].data);	//輸出根頂點（保存lastIndex目的就是便于追溯到頂點數組，把根頂點輸出）//開始遍歷后面的鄰接頂點while (p1 != NULL){if (Judge[p1->index] == 0)		//未遍歷（遍歷每一個頂點）{DFS(V[p1->index].firstEdge, p1->index);		//遞歸深度優(yōu)先遍歷（輸出只需要把頂點數組的東西輸出即可）}p1 = *(p1->next);								//后移（遍歷每一個鄰接頂點）}}
}

3、總代碼

//鄰接表的深度優(yōu)先遍歷(DFS)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>#define MAXSIZE 20
int length = 0;							//頂點數組長度
int Judge[MAXSIZE];	//列矩陣（記錄頂點是否已遍歷過）//鄰接頂點
typedef struct EdgeNode
{char data;int index;struct EdgeNode** next;		//二級指針
}EdgeNode, * pEdgeNode;//頂點數組（結構體數組）
typedef struct Vertex
{char data;EdgeNode* firstEdge;
}Vertex;
Vertex V[MAXSIZE];void Input()
{int i;char ch;printf("請輸入圖的所有頂點：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){V[i].data = ch;scanf("%c", &ch);}length = i;
}void InitVertex()
{int i;for (i = 0; i < length; i++){V[i].firstEdge = NULL;Judge[i] = 0;				//列數組初始化}
}//根據字符查找在頂點數組中的下標
int FindIndex(char ch)
{int i;for (i = 0; i < length; i++){if (ch == V[i].data)return i;}return -1;					//沒找到
}//創(chuàng)建圖
void CreateGraph()
{int i;char ch;pEdgeNode* p2 = NULL;				//二級指針for (i = 0; i < length; i++){printf("\n請輸入%c的鄰接頂點：\t", V[i].data);scanf("%c", &ch);//首個頂點if (ch != '\n'){V[i].firstEdge = (EdgeNode*)malloc(sizeof(EdgeNode));		//一級指針分配空間p2 = (pEdgeNode*)malloc(sizeof(pEdgeNode));					//二級指針分配空間p2 = &V[i].firstEdge;(*p2)->data = ch;(*p2)->index = FindIndex(ch);(*p2)->next = (pEdgeNode*)malloc(sizeof(pEdgeNode));	//二級指針分配空間*((*p2)->next) = NULL;scanf("%c", &ch);}while (ch != '\n'){p2 = (*p2)->next;																	//向后傳遞(*p2) = (EdgeNode*)malloc(sizeof(EdgeNode));						//一級指針分配空間(*p2)->data = ch;(*p2)->index = FindIndex(ch);(*p2)->next = (pEdgeNode*)malloc(sizeof(pEdgeNode));		//二級指針分配空間*((*p2)->next) = NULL;scanf("%c", &ch);}}
}//深度優(yōu)先遍歷（按頂點操作）
//判斷的時候需要遍歷每一個鄰接頂點，而輸出的時候只需要把頂點數組的內容輸出即可
void DFS(EdgeNode* p1, int lastIndex)
{if (Judge[lastIndex] == 0)		//頂點未遍歷{Judge[lastIndex] = 1;		//標記（表示遍歷過）printf("%c", V[lastIndex].data);	//輸出根頂點（保存lastIndex目的就是便于追溯到頂點數組，把根頂點輸出）//開始遍歷后面的鄰接頂點while (p1 != NULL){if (Judge[p1->index] == 0)		//未遍歷（遍歷每一個頂點）{DFS(V[p1->index].firstEdge, p1->index);		//遞歸深度優(yōu)先遍歷（輸出只需要把頂點數組的東西輸出即可）}p1 = *(p1->next);								//后移（遍歷每一個鄰接頂點）}}
}//輸出測試
void Print()
{int i;EdgeNode* p1;					//一級指針for (i = 0; i < length; i++){p1 = V[i].firstEdge;while (p1 != NULL){printf("%c", p1->data);p1 = *(p1->next);}}
}int main(){Input();InitVertex();CreateGraph();					//創(chuàng)建圖DFS(V[0].firstEdge ,0);			//深度優(yōu)先遍歷（從首結點開始）//Print();
}

三、鄰接矩陣的廣度優(yōu)先遍歷?

1、原理圖

?2、過程

先把根元素入隊并標記，然后取出根元素，依次判斷：1、當前根元素行鄰接數組是否有元素；2、當前元素是否標記過 -> 若有元素且未標記，則入隊該元素并標記；否則跳過。然后調用BFS()函數進行遞歸，直到隊列為空結束。（一個頂點一次循環(huán)判斷入隊）

1、入隊首元素并標記，調用BFS()

EnQueue(0);								//首元素入隊
Judge[0] = 1;							//標記首元素
BFS(DeQueue());						    //廣度優(yōu)先遍歷

2、 BFS()函數

//廣度優(yōu)先遍歷(BFS)
void BFS(int index)
{int j;printf("%c", G.vertex[index]);		//輸出for (j = 0; j < G.length; j++){if (G.edge[index][j] != 0 && Judge[j] == 0)			//有鄰接頂點且未入隊{Judge[j] = 1;						//標記EnQueue(j);							//入隊}}//遍歷隊列下一個元素index = DeQueue();			//取出當前隊首作為根//判斷隊列是否為空，空則退出，非空則繼續(xù)遍歷if (index == -1)return;elseBFS(index);					//遞歸進行下一個元素的廣度優(yōu)先遍歷
}

?3、總代碼

//鄰接矩陣的廣度優(yōu)先遍歷
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20
int Judge[MAXSIZE] = { 0 };//隊列結構體
typedef struct
{int rear;int front;int num[MAXSIZE];			//放入隊列的序號
}Queue;
Queue Q;//鄰接矩陣結構體
typedef struct
{char vertex[MAXSIZE];						//頂點數組int edge[MAXSIZE][MAXSIZE];			//邊數組int length;										//頂點數量
}Graph;
Graph G;//輸入頂點
void Input()
{int i;char ch;printf("請輸入全部頂點：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){G.vertex[i] = ch;scanf("%c", &ch);}G.length = i;					//頂點數量
}//初始化（鄰接結點數組和隊列）
void Init()
{int i, j;for (i = 0; i < G.length; i++){for (j = 0; j < G.length; j++){G.edge[i][j] = 0;}}Q.rear = 0;			//隊尾Q.front = 0;			//隊首
}//入隊
void EnQueue(int num)
{Q.num[Q.rear++] = num;
}//出隊
int DeQueue()
{if (Q.front == Q.rear)return -1;return Q.num[Q.front++];
}//根據字符返回下標
int FindIndex(char ch)
{int i;for (i = 0; i < G.length; i++){if (G.vertex[i] == ch)return i;}return -1;						//沒找到
}//創(chuàng)建圖
void CreateGraph()
{int i, index;char ch;for (i = 0; i < G.length; i++){printf("\n請輸入%c結點的鄰接結點：\t", G.vertex[i]);scanf("%c", &ch);while (ch != '\n'){index = FindIndex(ch);			//獲取列下標（被指向元素下標）G.edge[i][index] = 1;scanf("%c", &ch);}}
}//廣度優(yōu)先遍歷(BFS)
void BFS(int index)
{int j;printf("%c", G.vertex[index]);		//輸出for (j = 0; j < G.length; j++){if (G.edge[index][j] != 0 && Judge[j] == 0)			//有鄰接頂點且未入隊{Judge[j] = 1;						//標記EnQueue(j);							//入隊}}//遍歷隊列下一個元素index = DeQueue();			//取出當前隊首作為根//判斷隊列是否為空，空則退出，非空則繼續(xù)遍歷if (index == -1)return;elseBFS(index);					//遞歸進行下一個元素的廣度優(yōu)先遍歷
}//測試遍歷
void Print()
{int i, j;for (i = 0; i < G.length; i++){printf("\n%c鄰接結點：\t", G.vertex[i]);for (j = 0; j < G.length; j++)printf("%d ", G.edge[i][j]);}
}int main()
{Input();Init();CreateGraph();EnQueue(0);								//首元素入隊Judge[0] = 1;							//標記首元素printf("\n廣度優(yōu)先遍歷：");BFS(DeQueue());						//廣度優(yōu)先遍歷//Print();return 0;
}

四、鄰接表的廣度優(yōu)先遍歷(BFS)

?原理和上面的鄰接矩陣類似，以頂點為單位，往后判斷是否有需要入隊的元素（只用判斷是否遍歷過即可，因為接在頂點后面作為鄰接頂點，必然是鄰接頂點，所以不需要再像數組那樣判斷是否為鄰接頂點）。

1、首調用BFS

EnQueue(0);				//入隊首元素
Judge[0] = 1;			//判斷
BFS(DeQueue());		    //廣度優(yōu)先遍歷并出隊隊首元素

2、BFS()

//廣度優(yōu)先遍歷
void BFS(int index)
{int i;EdgeNode* p;printf("%c", G[index].vertex);		//輸出頂點p = G[index].firstEdge;					//指向頂點首指針while (p){if (Judge[p->index] == 0){Judge[p->index] = 1;			//標記EnQueue(p->index);			//入隊}p = *(p->next);						//后移}if (Q.front == Q.rear)					//隊列為空return;elseBFS(DeQueue());						//廣度優(yōu)先遍歷并出隊隊首元素
}

總代碼

//鄰接表的廣度優(yōu)先遍歷
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>#define MAXSIZE 20
int length;							//記錄頂點數組長度
int Judge[MAXSIZE] = { 0 };//鄰接頂點結構體
typedef struct EdgeNode
{char data;								//存放數據int index;								//數據在頂點結構體中的下標struct EdgeNode** next;		//二級指針
}EdgeNode, *pEdgeNode;//頂點結構體
typedef struct
{char vertex;EdgeNode* firstEdge;			//一級指針（指向首個鄰接頂點）
}Graph;
Graph G[MAXSIZE];//隊列結構體
typedef struct
{int num[MAXSIZE];				//存放頂點下標int front;								//隊首int rear;								//隊尾
}Queue;
Queue Q;//輸入頂點數組
void InputVertex()
{int i;char ch;printf("請輸入所有頂點：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){G[i].vertex = ch;scanf("%c", &ch);}length = i;					//頂點數組長度
}//初始化（*firstEdge和隊列初始化）
void Init()
{int i;for (i = 0; i < length; i++){G[i].firstEdge = NULL;}Q.front = 0;			//隊首Q.rear = 0;			//隊尾
}//入隊
void EnQueue(int num)
{Q.num[Q.rear++] = num;
}//出隊
int DeQueue()
{return Q.num[Q.front++];
}//根據數據查找下標
int FindIndex(char ch)
{int i;for (i = 0; i < length; i++){if (ch == G[i].vertex)return i;}return -1;
}//創(chuàng)建鄰接頂點鏈表
void CreateEdge()
{int i;char ch;pEdgeNode* p2=NULL;					//二級指針for (i = 0; i < length; i++){printf("請輸入%c頂點的鄰接頂點：\t", G[i].vertex);scanf("%c", &ch);//首個頂點if (ch != '\n'){G[i].firstEdge = (EdgeNode*)malloc(sizeof(EdgeNode));	//一級指針p2 = (pEdgeNode*)malloc(sizeof(pEdgeNode));					//二級指針p2 = &G[i].firstEdge;															//連接首指針(*p2)->data = ch;														(*p2)->index = FindIndex(ch);											(*p2)->next = (pEdgeNode*)malloc(sizeof(pEdgeNode));	//二級指針*((*p2)->next) = NULL;														//尾指針地址賦空scanf("%c", &ch);}//后面的頂點while (ch != '\n'){p2 = (*p2)->next;(*p2)= (EdgeNode*)malloc(sizeof(EdgeNode));						//一級指針 (*p2)->next = (pEdgeNode*)malloc(sizeof(pEdgeNode));		//二級指針(*p2)->data = ch;(*p2)->index = FindIndex(ch);*((*p2)->next) = NULL;scanf("%c", &ch);}}
}//廣度優(yōu)先遍歷
void BFS(int index)
{int i;EdgeNode* p;printf("%c", G[index].vertex);		//輸出頂點p = G[index].firstEdge;					//指向頂點首指針while (p){if (Judge[p->index] == 0){Judge[p->index] = 1;			//標記EnQueue(p->index);			//入隊}p = *(p->next);						//后移}if (Q.front == Q.rear)					//隊列為空return;elseBFS(DeQueue());						//廣度優(yōu)先遍歷并出隊隊首元素
}//測試輸出
void Print()
{int i; EdgeNode* p;for (i = 0; i < length; i++){p = G[i].firstEdge;printf("\n%c的鄰接頂點為：\t", G[i].vertex);while (p != NULL){printf("%c", p->data);p = *(p->next);}}
}int main()
{InputVertex();			//輸入頂點Init();						//初始化CreateEdge();			//創(chuàng)建鄰接頂點鏈表printf("\n廣度優(yōu)先遍歷：\t");EnQueue(0);				//入隊首元素Judge[0] = 1;			//判斷BFS(DeQueue());		//廣度優(yōu)先遍歷并出隊隊首元素//Print();						//測試輸出return 0;
}

才疏學淺，有些地方可能會有點錯誤的地方，還望大家斧正，Thanks?(･ω･)ﾉ

總結

以上是生活随笔為你收集整理的数据结构与算法（7-2）图的遍历（深度优先遍历DFS、广度优先遍历BFS）（分别用邻接矩阵和邻接表实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

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

上一篇：数据结构与算法（7-1）图的存储（邻接矩
下一篇： OpenCV（一）图像读取与新建、图像显