圖的遍歷
概念：指的是從圖中的任一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪(fǎng)問(wèn)一次且只訪(fǎng)問(wèn)一次。
鄰接矩陣及鄰接表的創(chuàng)建
鄰接矩陣及鄰接表的創(chuàng)建：
圖的存儲(chǔ)結(jié)構(gòu)-無(wú)向鄰接矩陣與無(wú)向鄰接表（C語(yǔ)言）.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-460466.html
深度優(yōu)先遍歷（DFS）
鄰接矩陣的深度優(yōu)先遍歷
結(jié)構(gòu)定義
#include<stdio.h>
#include<stdlib.h>
#include <stdbool.h> //提供_Bool 類(lèi)型
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFINITY 65535
_Bool visited[MAXVEX]; //訪(fǎng)問(wèn)標(biāo)志的數(shù)組
typedef struct {
VertexType vexts[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numNodes, numEdges;
} MGraph;
鄰接矩陣的深度優(yōu)先遍歷操作
/* 鄰接矩陣的深度優(yōu)先遍歷操作 */
void DFSTraverse(MGraph G)
{
for (int i = 0; i < G.numNodes; i++) //初始化所有頂點(diǎn)狀態(tài)為未訪(fǎng)問(wèn)
visited[i] = false;
for (int i = 0; i < G.numNodes; i++)
if (!visited[i]) //對(duì)未訪(fǎng)問(wèn)鄰接頂點(diǎn)遞歸調(diào)用DFS，如果為連通圖僅訪(fǎng)問(wèn)一次
DFS(G, i);
}
鄰接矩陣的深度優(yōu)先遞歸算法
/* 鄰接矩陣的深度優(yōu)先遞歸算法 */
void DFS(MGraph G, int i)
{
visited[i] = true; //賦值為真
printf("%c ", G.vexts[i]);
for (int j = 0; j < G.numNodes; j++)
if (G.arc[i][j] ！= INFINITY && !visited[j]) //對(duì)未訪(fǎng)問(wèn)鄰接頂點(diǎn)遞歸調(diào)用
DFS(G, j);
}
鄰接表的深度優(yōu)先遍歷
結(jié)構(gòu)定義
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char VertexType; //頂點(diǎn)類(lèi)型
typedef int EdgeType; //邊上權(quán)值
#define MAXVEX 100 // 最大頂點(diǎn)數(shù)
#define MAXVEX 9
_Bool visited[MAXVEX]; //訪(fǎng)問(wèn)標(biāo)志的數(shù)組
typedef struct EdgeNode { //邊表結(jié)點(diǎn)
int adjvex; //領(lǐng)接點(diǎn)域，存儲(chǔ)對(duì)應(yīng)下標(biāo)
EdgeType info; //存儲(chǔ)權(quán)值，如果是非網(wǎng)圖可以省略
struct EdgeNode* next; //指向下一個(gè)鄰接點(diǎn)
}EdgeNode;
typedef struct VertexNode { //頂點(diǎn)結(jié)點(diǎn)
VertexType data; //頂點(diǎn)域
EdgeNode* firstedge; //邊表頭指針
}VertexNode;
typedef struct VertexNode AdjList[MAXVEX]; //鄰接表類(lèi)型
typedef struct {
AdjList adjList;
int numNodes, numEdges; //圖當(dāng)前頂點(diǎn)數(shù)與邊數(shù)
}GraphAdjList;
void CreateALGRAph(GraphAdjList*); //建立圖的鄰接表結(jié)構(gòu)
int LocateVex(GraphAdjList, VertexType); //查找頂點(diǎn)
void DFSTraverse(GraphAdjList G);
void DFS(GraphAdjList, int); //鄰接表的深度優(yōu)先遞歸算法
鄰接表的深度優(yōu)先遍歷操作
/* 鄰接表的深度優(yōu)先遍歷操作 */
void DFSTraverse(GraphAdjList G)
{
for (int i = 0; i < G.numNodes; i++) //初始化所有頂點(diǎn)狀態(tài)為未訪(fǎng)問(wèn)
visited[i] = false;
for (int i = 0; i < G.numNodes; i++)
if (!visited[i]) //對(duì)未訪(fǎng)問(wèn)鄰接頂點(diǎn)遞歸調(diào)用DFS，如果為連通圖僅訪(fǎng)問(wèn)一次
DFS(G, i);
}
鄰接表的深度優(yōu)先遞歸算法
/* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList G, int i)
{
EdgeNode* p;
visited[i] = true;
printf("%c", G.adjList[i].data);
p = G.adjList[i].firstedge;
while (p)
{
if (!visited[p->adjvex]) //對(duì)未訪(fǎng)問(wèn)鄰接頂點(diǎn)遞歸調(diào)用
DFS(G, p->adjvex);
p = p->next;
}
}
廣度優(yōu)先遍歷（BFS）
鄰接矩陣的廣度遍歷
結(jié)構(gòu)定義
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char VertexType; //頂點(diǎn)類(lèi)型
typedef int EdgeType; //邊的權(quán)值類(lèi)型
#define MAXVEX 100
#define INFINITY 65535 //表示無(wú)窮大
#define MAXSIZE 9 //隊(duì)列最大長(zhǎng)度
_Bool visited[MAXVEX]; //訪(fǎng)問(wèn)標(biāo)志的數(shù)組
typedef struct {
VertexType vexts[MAXVEX]; //頂點(diǎn)表
EdgeType arc[MAXVEX][MAXVEX]; //鄰接矩陣
int numNodes, numEdges; //圖當(dāng)前頂點(diǎn)數(shù)與邊數(shù)
}MGraph;
鄰接矩陣的廣度遍歷算法
/* 鄰接矩陣的廣度遍歷算法 */
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
Q.front = Q.rear = 0; //初始化
for (i = 0; i < G.numNodes; i++)
visited[i] = false;
for (i = 0; i < G.numNodes; i++) //對(duì)每個(gè)頂點(diǎn)做循環(huán)
{
if (!visited[i]) //如果未訪(fǎng)問(wèn)過(guò)
{
visited[i] = true; //訪(fǎng)問(wèn)
printf("%c ", G.vexts[i]);
EnQueue(&Q, i); //入隊(duì)
while (Q.front != Q.rear) //隊(duì)不為空
{
DeQueue(&Q, &i); //隊(duì)首元素出隊(duì)
for (j = 0; j < G.numNodes; j++)
{
if (G.arc[i][j] !=INFINITY && !visited[j]) //此頂點(diǎn)存在且邊未訪(fǎng)問(wèn)過(guò)
{
visited[j] = true;
printf("%c ", G.vexts[j]);
EnQueue(&Q, j); //將此頂點(diǎn)入隊(duì)
}
}
}
}
}
}
鄰接表的廣度優(yōu)先遍歷
結(jié)構(gòu)定義
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char VertexType; //頂點(diǎn)類(lèi)型
typedef int EdgeType; //邊上權(quán)值
#define MAXVEX 100 // 最大頂點(diǎn)數(shù)
#define MAXSIZE 9 //隊(duì)列最大長(zhǎng)度
_Bool visited[MAXVEX]; //訪(fǎng)問(wèn)標(biāo)志的數(shù)組
typedef struct EdgeNode { //邊表結(jié)點(diǎn)
int adjvex; //領(lǐng)接點(diǎn)域，存儲(chǔ)對(duì)應(yīng)下標(biāo)
EdgeType info; //存儲(chǔ)權(quán)值，如果是非網(wǎng)圖可以省略
struct EdgeNode* next; //指向下一個(gè)鄰接點(diǎn)
}EdgeNode;
typedef struct VertexNode { //頂點(diǎn)結(jié)點(diǎn)
VertexType data; //頂點(diǎn)域
EdgeNode* firstedge; //邊表頭指針
}VertexNode;
typedef struct VertexNode AdjList[MAXVEX]; //鄰接表類(lèi)型
typedef struct {
AdjList adjList;
int numNodes, numEdges; //圖當(dāng)前頂點(diǎn)數(shù)與邊數(shù)
}GraphAdjList;
鄰接表的遍歷算法
/* 鄰接表的遍歷算法 */
void BFSTraverse(GraphAdjList G)
{
int i;
EdgeNode* p;
Queue Q;
Q.front = Q.rear = 0; //初始化
for (i = 0; i < G.numNodes; i++)
visited[i] = false;
for (i = 0; i < G.numNodes; i++) //對(duì)每個(gè)頂點(diǎn)做循環(huán)
{
if (!visited[i]) //如果未訪(fǎng)問(wèn)過(guò)
{
visited[i] = true; //訪(fǎng)問(wèn)
printf("%c ", G.adjList[i].data);
EnQueue(&Q, i); //入隊(duì)
while (Q.front != Q.rear) //隊(duì)不為空
{
DeQueue(&Q, &i);
p = G.adjList[i].firstedge;
while (p)
{
if (!visited[p->adjvex])
{
visited[p->adjvex] = true;
printf("%c ", G.adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->next;
}
}
}
}
}
廣度優(yōu)先遍歷所需隊(duì)列代碼
/* 循環(huán)隊(duì)列順序儲(chǔ)存*/
typedef struct {
int data[MAXVEX];
int front; //頭指針
int rear; //尾指針，如果隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置
}Queue;
/* 入隊(duì)列 */
void EnQueue(Queue* Q, int e)
{
if ((Q->rear + 1) % MAXSIZE == Q->front) //隊(duì)滿(mǎn)
exit(-1);
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
}
/* 刪除頭元素，用e返回 */
void DeQueue(Queue* Q, int* e)
{
if (Q->front == Q->rear) //如果為空
exit(-1);
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
}
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-460466.html
到了這里，關(guān)于圖的遍歷-深度優(yōu)先遍歷與廣度優(yōu)先遍歷（C語(yǔ)言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
