深度優先遍歷

主要思路是從圖中一個未訪問的頂點 V 開始，沿著一條路一直走到底，然后從這條路盡頭的節點回退到上一個節點，再從另一條路開始走到底…，不斷遞歸重復此過程，直到所有的頂點都遍歷完成，它的特點是不撞南墻不回頭，先走完一條路，再換一條路繼續走。

廣度優先遍歷·

廣度優先遍歷圖是以頂點v為起始點，由近至遠，依次訪問和v有路徑相通而且路徑長度為1，2，……的頂點。為了使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問，需設置隊列存儲訪問的頂點。

代碼實現

鄰接矩陣結構的遍歷

//鄰接表的深度優先遍歷和廣度優先遍歷 #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */ typedef int EdgeType; /* 邊上的權值類型應由用戶定義 */#define MAXSIZE 9 /* 存儲空間初始分配量 */ #define MAXEDGE 15 #define MAXVEX 9 #define INFINITY 65535typedef struct {VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣，可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數和邊數 */ }MGraph;/* 用到的隊列結構與函數********************************** *//* 循環隊列的順序存儲結構 */ typedef struct {int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */ }Queue;/* 初始化一個空隊列Q */ Status InitQueue(Queue* Q) {Q->front = 0;Q->rear = 0;return OK; }/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */ Status QueueEmpty(Queue Q) {if (Q.front == Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE; }/* 若隊列未滿，則插入元素e為Q新的隊尾元素 */ Status EnQueue(Queue* Q, int e) {if ((Q->rear + 1) % MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear] = e; /* 將元素e賦值給隊尾 */Q->rear = (Q->rear + 1) % MAXSIZE;/* rear指針向后移一位置， *//* 若到最后則轉到數組頭部 */return OK; }/* 若隊列不空，則刪除Q中隊頭元素，用e返回其值 */ Status DeQueue(Queue* Q, int* e) {if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e = Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front = (Q->front + 1) % MAXSIZE; /* front指針向后移一位置， *//* 若到最后則轉到數組頭部 */return OK; } /* ****************************************************** */void CreateMGraph(MGraph* G) {int i, j;G->numEdges = 15;G->numVertexes = 9;/* 讀入頂點信息，建立頂點表 */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';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for (j = 0; j < G->numVertexes; j++){G->arc[i][j] = 0;}}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;for (i = 0; i < G->numVertexes; i++){for (j = i; j < G->numVertexes; j++){G->arc[j][i] = G->arc[i][j];}}}Boolean visited[MAXVEX]; /* 訪問標志的數組 *///鄰接矩陣深度優先遞歸算法 void DFS(MGraph G, int i) {int j;visited[i] = TRUE;printf("%c", G.vexs[i]);//打印頂點for (int j = 0; j < G.numVertexes; j++){if (G.arc[i][j] == 1 && !visited[j])DFS(G, j);} } //鄰接矩陣的深度遍歷操作 void DFSTraverse(MGraph G) {int i;for (int i = 0; i < G.numVertexes; i++){visited[i] = FALSE;}for (int i = 0; i < G.numVertexes; i++){if (!visited[i])/* 對未訪問過的頂點調用DFS，若是連通圖，只會執行一次 */ DFS(G, i);} }//鄰接矩陣的廣度遍歷算法.非遞歸方法 ，棧存儲法 void BFSTraverse(MGraph G) {Queue Q;for (int i = 0; i < G.numVertexes; i++){visited[i] = FALSE;}InitQueue(&Q); /* 初始化一輔助用的隊列 */for (int i = 0; i < G.numVertexes; i++){if (!visited[i]){visited[i] = TRUE;printf("%c", G.vexs[i]);EnQueue(&Q, i);while (!QueueEmpty(Q)){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);}}}}} } int main(void) {MGraph G;CreateMGraph(&G);printf("\n深度遍歷：");DFSTraverse(G);printf("\n廣度遍歷：");BFSTraverse(G);return 0; }

鄰接表結構的遍歷

在這里插入代碼片

總結

以上是生活随笔為你收集整理的大话数据结构 17：图的深度优先遍历和广度优先遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

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