国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

數(shù)據(jù)結(jié)構(gòu) | 圖的遍歷

2年前作者：-擬墨畫扇-分類：Toy博客閱讀(27)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu) | 圖的遍歷。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

一、數(shù)據(jù)結(jié)構(gòu)定義

1、圖

#define MaxVertexNum 100 // 最大可存儲(chǔ)的節(jié)點(diǎn)數(shù)目

/*圖*/
typedef char VexterType;
typedef int EdgeType;

typedef struct GraphMatrix {
	VexterType Vexs[MaxVertexNum];				//結(jié)點(diǎn) 
	EdgeType Edges[MaxVertexNum][MaxVertexNum];	//邊
	int vexnum, arcnum;							//當(dāng)前點(diǎn)數(shù)和邊數(shù)
}*MGraph;

int visited[MaxVertexNum]; // 記錄是否訪問(wèn)該節(jié)點(diǎn)，訪問(wèn)過(guò)為1，否則為0

使用鄰接矩陣法存儲(chǔ)圖的信息，其中

  • 一維矩陣 Vexs[] 存儲(chǔ)節(jié)點(diǎn)信息
  • 二維矩陣?Edges[][] 存儲(chǔ)邊的信息
  • 一維矩陣 visited[] 記錄當(dāng)前節(jié)點(diǎn)是否被訪問(wèn)過(guò)，用于后面的遍歷

本文所使用的圖的結(jié)構(gòu)如下：

圖的遍歷,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,寬度優(yōu)先,廣度優(yōu)先,算法

對(duì)應(yīng)的 Vexs[] 為：A,B,C,D,E,F（對(duì)應(yīng)的數(shù)組下標(biāo)從0到5）

對(duì)應(yīng)的?Edges[][] 如下：

圖的遍歷,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,寬度優(yōu)先,廣度優(yōu)先,算法

?2、隊(duì)列

/*隊(duì)列*/
typedef int QueueType;
typedef struct QueueNode {
	QueueType data;
	struct QueueNode* next;
}QueueNode;

typedef struct {
	QueueNode* front, * rear;
}LinkQueue;

圖的廣度優(yōu)先遍歷BFS需要使用隊(duì)列進(jìn)行輔助

二、方法概覽

1、隊(duì)列

void initQueue(LinkQueue* Q);//初始化隊(duì)列
int isQueueEmpty(LinkQueue* Q);//判斷隊(duì)列是否為空
void enQueue(LinkQueue* Q, QueueType data);//入隊(duì)
int deQueue(LinkQueue* Q, QueueType* data);//出隊(duì)

2、圖

void printGraph(MGraph G);//打印圖的鄰接矩陣
MGraph initGraph();//初始化圖并輸入數(shù)據(jù)
int adjacent(MGraph G, int x, int y);//判斷是否存在某條邊(x,y)
int firstNeighbor(MGraph G, int v);//求點(diǎn)v的第一個(gè)鄰接點(diǎn)
int nextNeighbor(MGraph G, int v, int w);//求點(diǎn)v的鄰接點(diǎn)w的下一個(gè)鄰接點(diǎn)

void visit(MGraph G, int v);//訪問(wèn)該節(jié)點(diǎn)的信息
void BFS(MGraph G, LinkQueue Q, int v);// 廣度優(yōu)先遍歷
void BFSTraverse(MGraph G);//廣度優(yōu)先遍歷 主函數(shù)
void DFS(MGraph G, int v);//深度優(yōu)先遍歷
void DFSTraverse(MGraph G);//深度優(yōu)先遍歷 主函數(shù)

三、方法詳解

1、隊(duì)列

//初始化隊(duì)列
void initQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueueNode*)malloc(sizeof(QueueNode)); // 分配頭節(jié)點(diǎn)
	Q->front->next = NULL; //初始化為空
}
//判斷隊(duì)列是否為空
int isQueueEmpty(LinkQueue* Q) {
	if (Q->front == Q->rear) return 1;
	else return 0;
}
//入隊(duì)
void enQueue(LinkQueue* Q, QueueType data) {
	QueueNode* news = (QueueNode*)malloc(sizeof(QueueNode));
	news->data = data; // 創(chuàng)建新節(jié)點(diǎn)，插入隊(duì)列尾部 
	news->next = NULL;
	Q->rear->next = news;
	Q->rear = news;
}
//出隊(duì)
int deQueue(LinkQueue* Q, QueueType* data) {
	if (Q->front == Q->rear) return 0;
	QueueNode* del = Q->front->next;
	*data = del->data;
	Q->front->next = del->next;
	if (Q->rear == del)
		Q->rear = Q->front; // 若原隊(duì)列只有一個(gè)節(jié)點(diǎn)，刪除后變空 
	free(del);
	return 1;
}

2、圖

（1）基本操作

// 打印圖的鄰接矩陣
void printGraph(MGraph G) {
	int i, j;
	printf("G->Edges[][] = \n\t");

	for (i = 0; i < G->vexnum; ++i)
		printf(" %c \t", G->Vexs[i]);
	printf("\n");

	for (i = 0; i < G->vexnum; ++i) {
		printf(" %c \t", G->Vexs[i]);
		for (j = 0; j < G->vexnum; j++)
			printf(" %d \t", G->Edges[i][j]);
		printf("\n");
	}
}

// 初始化圖并輸入數(shù)據(jù)
MGraph initGraph() {
	int i, j;
	MGraph G = (MGraph)malloc(sizeof(struct GraphMatrix));
	G->vexnum = 6;
	G->arcnum = 14;

	/* 初始化圖的鄰接矩陣 Edges[MaxVertexNum][MaxVertexNum] */
	for (i = 0; i < G->vexnum; i++) {
		for (j = 0; j < G->vexnum; j++) {
			G->Edges[i][j] = 0;	 
		}
	}

	/* 輸入圖的結(jié)點(diǎn)矩陣 Vexs[MaxVertexNum] */
	int v[6] = { 'A','B','C','D','E','F' };
	for (i = 0; i < G->vexnum; i++)
		G->Vexs[i] = v[i];

	/* 輸入圖的邊權(quán) */
	int  start_vex[14] = { 0,0,0,1,1,1,2,2,3,3,4,4,5,5 };
	int    end_vex[14] = { 1,2,3,0,4,5,0,1,0,5,1,2,1,3 };
	for (i = 0; i < G->arcnum; i++)
		G->Edges[start_vex[i]][end_vex[i]] = 1;
	return G;
}

// 判斷是否存在某條邊(x,y)
int adjacent(MGraph G, int x, int y) {
	if (G->Edges[x][y] == 1)
		return 1;
	else
		return -1;
}

// 求點(diǎn)v的第一個(gè)鄰接點(diǎn)
// 若有返回頂點(diǎn)號(hào)，否則返回-1
int firstNeighbor(MGraph G, int v) {
	for (int i = 0; i < G->Vexs; i++) {
		if (G->Edges[v][i] == 1)
			return i;
	}
	return -1;
}

// 求點(diǎn)v的鄰接點(diǎn)w的下一個(gè)鄰接點(diǎn)
// 若有返回頂點(diǎn)號(hào)，否則返回-1
int nextNeighbor(MGraph G, int v, int w) {
	if (w < G->vexnum) {
		for (int i = w + 1; i < G->vexnum; i++) {
			if (G->Edges[v][i] == 1)
				return i;
		}
		return -1;
	}
	return -1;
}

（2）圖的深度優(yōu)先遍歷DFS

// 訪問(wèn)該節(jié)點(diǎn)的信息
void visit(MGraph G,int v) {
	printf("%c ",G->Vexs[v]);
}

// 深度優(yōu)先遍歷
void DFS(MGraph G, int v) {
	visit(G, v);
	visited[v] = 1;
	for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w)) {
		if (visited[w] == 0)
			DFS(G, w);
	}
}

// 深度優(yōu)先遍歷 主函數(shù)
void DFSTraverse(MGraph G) {
	for (int i = 0; i < G->vexnum; ++i) {
		visited[i] = 0;
	}
	for (int i = 0; i < G->vexnum; ++i) {
		if (visited[i] == 0)
			DFS(G, i);
	}
}

（3）圖的廣度優(yōu)先遍歷BFS

// 訪問(wèn)該節(jié)點(diǎn)的信息
void visit(MGraph G,int v) {
	printf("%c ",G->Vexs[v]);
}

// 廣度優(yōu)先遍歷
void BFS(MGraph G, LinkQueue Q, int v) {
	visit(G, v);
	visited[v] = 1;
	enQueue(&Q, v);
	while (!isQueueEmpty(&Q)) {
		deQueue(&Q, &v);
		for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w)) {
			if (visited[w] == 0) {
				visit(G, w);
				visited[w] = 1;
				enQueue(&Q, w);
			}
		}
	}
}

// 廣度優(yōu)先遍歷 主函數(shù)
void BFSTraverse(MGraph G) {
	for (int i = 0; i < G->vexnum; ++i) {
		visited[i] = 0;
	}
	LinkQueue Q;
	initQueue(&Q);
	for (int i = 0; i < G->vexnum; ++i) {
		if (visited[i] == 0)
			BFS(G, Q, i);
	}
}

四、運(yùn)行結(jié)果

? ? ? ? main方法代碼如下：

int main() {
	MGraph G = initGraph();
	printGraph(G);

	printf("\n廣度優(yōu)先遍歷 : ");
	BFSTraverse(G);

	printf("\n深度優(yōu)先遍歷 : ");
	DFSTraverse(G);
	return 0;
}

? ? ? ? 運(yùn)行結(jié)果如下：

圖的遍歷,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,寬度優(yōu)先,廣度優(yōu)先,算法文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-764045.html

?五、源代碼

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100 // 最大可存儲(chǔ)的節(jié)點(diǎn)數(shù)目

/*圖*/
typedef char VexterType;
typedef int EdgeType;

typedef struct GraphMatrix {
	VexterType Vexs[MaxVertexNum];				//結(jié)點(diǎn) 
	EdgeType Edges[MaxVertexNum][MaxVertexNum];	//邊
	int vexnum, arcnum;							//當(dāng)前點(diǎn)數(shù)和邊數(shù)
}*MGraph;

int visited[MaxVertexNum]; // 記錄是否訪問(wèn)該節(jié)點(diǎn)，訪問(wèn)過(guò)為1，否則為0


/*隊(duì)列*/
typedef int QueueType;
typedef struct QueueNode {
	QueueType data;
	struct QueueNode* next;
}QueueNode;

typedef struct {
	QueueNode* front, * rear;
}LinkQueue;

void initQueue(LinkQueue* Q);//初始化隊(duì)列
int isQueueEmpty(LinkQueue* Q);//判斷隊(duì)列是否為空
void enQueue(LinkQueue* Q, QueueType data);//入隊(duì)
int deQueue(LinkQueue* Q, QueueType* data);//出隊(duì)


void printGraph(MGraph G);//打印圖的鄰接矩陣
MGraph initGraph();//初始化圖并輸入數(shù)據(jù)
int adjacent(MGraph G, int x, int y);//判斷是否存在某條邊(x,y)
int firstNeighbor(MGraph G, int v);//求點(diǎn)v的第一個(gè)鄰接點(diǎn)
int nextNeighbor(MGraph G, int v, int w);//求點(diǎn)v的鄰接點(diǎn)w的下一個(gè)鄰接點(diǎn)

void visit(MGraph G, int v);//訪問(wèn)該節(jié)點(diǎn)的信息
void BFS(MGraph G, LinkQueue Q, int v);// 廣度優(yōu)先遍歷
void BFSTraverse(MGraph G);//廣度優(yōu)先遍歷 主函數(shù)
void DFS(MGraph G, int v);//深度優(yōu)先遍歷
void DFSTraverse(MGraph G);//深度優(yōu)先遍歷 主函數(shù)



//初始化隊(duì)列
void initQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueueNode*)malloc(sizeof(QueueNode)); // 分配頭節(jié)點(diǎn)
	Q->front->next = NULL; //初始化為空
}
//判斷隊(duì)列是否為空
int isQueueEmpty(LinkQueue* Q) {
	if (Q->front == Q->rear) return 1;
	else return 0;
}
//入隊(duì)
void enQueue(LinkQueue* Q, QueueType data) {
	QueueNode* news = (QueueNode*)malloc(sizeof(QueueNode));
	news->data = data; // 創(chuàng)建新節(jié)點(diǎn)，插入隊(duì)列尾部 
	news->next = NULL;
	Q->rear->next = news;
	Q->rear = news;
}
//出隊(duì)
int deQueue(LinkQueue* Q, QueueType* data) {
	if (Q->front == Q->rear) return 0;
	QueueNode* del = Q->front->next;
	*data = del->data;
	Q->front->next = del->next;
	if (Q->rear == del)
		Q->rear = Q->front; // 若原隊(duì)列只有一個(gè)節(jié)點(diǎn)，刪除后變空 
	free(del);
	return 1;
}


// 打印圖的鄰接矩陣
void printGraph(MGraph G) {
	int i, j;
	printf("G->Edges[][] = \n\t");

	for (i = 0; i < G->vexnum; ++i)
		printf(" %c \t", G->Vexs[i]);
	printf("\n");

	for (i = 0; i < G->vexnum; ++i) {
		printf(" %c \t", G->Vexs[i]);
		for (j = 0; j < G->vexnum; j++)
			printf(" %d \t", G->Edges[i][j]);
		printf("\n");
	}
}
// 初始化圖并輸入數(shù)據(jù)
MGraph initGraph() {
	int i, j;
	MGraph G = (MGraph)malloc(sizeof(struct GraphMatrix));
	G->vexnum = 6;
	G->arcnum = 14;

	/* 初始化圖的鄰接矩陣 Edges[MaxVertexNum][MaxVertexNum] */
	for (i = 0; i < G->vexnum; i++) {
		for (j = 0; j < G->vexnum; j++) {
			G->Edges[i][j] = 0;
		}
	}

	/* 輸入圖的結(jié)點(diǎn)矩陣 Vexs[MaxVertexNum] */
	int v[6] = { 'A','B','C','D','E','F' };
	for (i = 0; i < G->vexnum; i++)
		G->Vexs[i] = v[i];

	/* 輸入圖的邊權(quán) */
	int  start_vex[14] = { 0,0,0,1,1,1,2,2,3,3,4,4,5,5 };
	int    end_vex[14] = { 1,2,3,0,4,5,0,1,0,5,1,2,1,3 };
	for (i = 0; i < G->arcnum; i++)
		G->Edges[start_vex[i]][end_vex[i]] = 1;
	return G;
}
// 判斷是否存在某條邊(x,y)
int adjacent(MGraph G, int x, int y) {
	if (G->Edges[x][y] == 1)
		return 1;
	else
		return -1;
}
// 求點(diǎn)v的第一個(gè)鄰接點(diǎn)
// 若有返回頂點(diǎn)號(hào)，否則返回-1
int firstNeighbor(MGraph G, int v) {
	for (int i = 0; i < G->vexnum; i++) {
		if (G->Edges[v][i] == 1)
			return i;
	}
	return -1;
}
// 求點(diǎn)v的鄰接點(diǎn)w的下一個(gè)鄰接點(diǎn)
// 若有返回頂點(diǎn)號(hào)，否則返回-1
int nextNeighbor(MGraph G, int v, int w) {
	if (w < G->vexnum) {
		for (int i = w + 1; i < G->vexnum; i++) {
			if (G->Edges[v][i] == 1)
				return i;
		}
		return -1;
	}
	return -1;
}
// 訪問(wèn)該節(jié)點(diǎn)的信息
void visit(MGraph G,int v) {
	printf("%c ",G->Vexs[v]);
}
// 廣度優(yōu)先遍歷
void BFS(MGraph G, LinkQueue Q, int v) {
	visit(G, v);
	visited[v] = 1;
	enQueue(&Q, v);
	while (!isQueueEmpty(&Q)) {
		deQueue(&Q, &v);
		for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w)) {
			if (visited[w] == 0) {
				visit(G, w);
				visited[w] = 1;
				enQueue(&Q, w);
			}
		}
	}
}
// 廣度優(yōu)先遍歷 主函數(shù)
void BFSTraverse(MGraph G) {
	for (int i = 0; i < G->vexnum; ++i) {
		visited[i] = 0;
	}
	LinkQueue Q;
	initQueue(&Q);
	for (int i = 0; i < G->vexnum; ++i) {
		if (visited[i] == 0)
			BFS(G, Q, i);
	}
}
// 深度優(yōu)先遍歷
void DFS(MGraph G, int v) {
	visit(G, v);
	visited[v] = 1;
	for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w)) {
		if (visited[w] == 0)
			DFS(G, w);
	}
}
// 深度優(yōu)先遍歷 主函數(shù)
void DFSTraverse(MGraph G) {
	for (int i = 0; i < G->vexnum; ++i) {
		visited[i] = 0;
	}
	for (int i = 0; i < G->vexnum; ++i) {
		if (visited[i] == 0)
			DFS(G, i);
	}
}


int main() {
	MGraph G = initGraph();
	printGraph(G);

	printf("\n廣度優(yōu)先遍歷 : ");
	BFSTraverse(G);

	printf("\n深度優(yōu)先遍歷 : ");
	DFSTraverse(G);
	return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) | 圖的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包