1. Toy模板网首页
  2. > Toy博客

数据结构 | 图的遍历

10月前 作者：-拟墨画扇- 分类：Toy博客 阅读(40) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构 | 图的遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、数据结构定义

1、图

#define MaxVertexNum 100 // 最大可存储的节点数目

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

typedef struct GraphMatrix {
	VexterType Vexs[MaxVertexNum];				//结点 
	EdgeType Edges[MaxVertexNum][MaxVertexNum];	//边
	int vexnum, arcnum;							//当前点数和边数
}*MGraph;

int visited[MaxVertexNum]; // 记录是否访问该节点，访问过为1，否则为0

使用邻接矩阵法存储图的信息，其中

  • 一维矩阵 Vexs[] 存储节点信息
  • 二维矩阵 Edges[][] 存储边的信息
  • 一维矩阵 visited[] 记录当前节点是否被访问过，用于后面的遍历

本文所使用的图的结构如下：

图的遍历,数据结构,数据结构,深度优先,宽度优先,广度优先,算法

对应的 Vexs[] 为：A,B,C,D,E,F（对应的数组下标从0到5）

对应的 Edges[][] 如下：

图的遍历,数据结构,数据结构,深度优先,宽度优先,广度优先,算法

 2、队列

/*队列*/
typedef int QueueType;
typedef struct QueueNode {
	QueueType data;
	struct QueueNode* next;
}QueueNode;

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

图的广度优先遍历BFS需要使用队列进行辅助

二、方法概览

1、队列

void initQueue(LinkQueue* Q);//初始化队列
int isQueueEmpty(LinkQueue* Q);//判断队列是否为空
void enQueue(LinkQueue* Q, QueueType data);//入队
int deQueue(LinkQueue* Q, QueueType* data);//出队

2、图

void printGraph(MGraph G);//打印图的邻接矩阵
MGraph initGraph();//初始化图并输入数据
int adjacent(MGraph G, int x, int y);//判断是否存在某条边(x,y)
int firstNeighbor(MGraph G, int v);//求点v的第一个邻接点
int nextNeighbor(MGraph G, int v, int w);//求点v的邻接点w的下一个邻接点

void visit(MGraph G, int v);//访问该节点的信息
void BFS(MGraph G, LinkQueue Q, int v);// 广度优先遍历
void BFSTraverse(MGraph G);//广度优先遍历 主函数
void DFS(MGraph G, int v);//深度优先遍历
void DFSTraverse(MGraph G);//深度优先遍历 主函数

三、方法详解

1、队列

//初始化队列
void initQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueueNode*)malloc(sizeof(QueueNode)); // 分配头节点
	Q->front->next = NULL; //初始化为空
}
//判断队列是否为空
int isQueueEmpty(LinkQueue* Q) {
	if (Q->front == Q->rear) return 1;
	else return 0;
}
//入队
void enQueue(LinkQueue* Q, QueueType data) {
	QueueNode* news = (QueueNode*)malloc(sizeof(QueueNode));
	news->data = data; // 创建新节点，插入队列尾部 
	news->next = NULL;
	Q->rear->next = news;
	Q->rear = news;
}
//出队
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; // 若原队列只有一个节点，删除后变空 
	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");
	}
}

// 初始化图并输入数据
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;	 
		}
	}

	/* 输入图的结点矩阵 Vexs[MaxVertexNum] */
	int v[6] = { 'A','B','C','D','E','F' };
	for (i = 0; i < G->vexnum; i++)
		G->Vexs[i] = v[i];

	/* 输入图的边权 */
	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;
}

// 求点v的第一个邻接点
// 若有返回顶点号，否则返回-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;
}

// 求点v的邻接点w的下一个邻接点
// 若有返回顶点号，否则返回-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）图的深度优先遍历DFS

// 访问该节点的信息
void visit(MGraph G,int v) {
	printf("%c ",G->Vexs[v]);
}

// 深度优先遍历
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);
	}
}

// 深度优先遍历 主函数
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）图的广度优先遍历BFS

// 访问该节点的信息
void visit(MGraph G,int v) {
	printf("%c ",G->Vexs[v]);
}

// 广度优先遍历
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);
			}
		}
	}
}

// 广度优先遍历 主函数
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);
	}
}

四、运行结果

        main方法代码如下：

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

	printf("\n广度优先遍历 : ");
	BFSTraverse(G);

	printf("\n深度优先遍历 : ");
	DFSTraverse(G);
	return 0;
}

        运行结果如下：

图的遍历,数据结构,数据结构,深度优先,宽度优先,广度优先,算法文章来源地址https://www.toymoban.com/news/detail-764045.html

 五、源代码

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

#define MaxVertexNum 100 // 最大可存储的节点数目

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

typedef struct GraphMatrix {
	VexterType Vexs[MaxVertexNum];				//结点 
	EdgeType Edges[MaxVertexNum][MaxVertexNum];	//边
	int vexnum, arcnum;							//当前点数和边数
}*MGraph;

int visited[MaxVertexNum]; // 记录是否访问该节点，访问过为1，否则为0


/*队列*/
typedef int QueueType;
typedef struct QueueNode {
	QueueType data;
	struct QueueNode* next;
}QueueNode;

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

void initQueue(LinkQueue* Q);//初始化队列
int isQueueEmpty(LinkQueue* Q);//判断队列是否为空
void enQueue(LinkQueue* Q, QueueType data);//入队
int deQueue(LinkQueue* Q, QueueType* data);//出队


void printGraph(MGraph G);//打印图的邻接矩阵
MGraph initGraph();//初始化图并输入数据
int adjacent(MGraph G, int x, int y);//判断是否存在某条边(x,y)
int firstNeighbor(MGraph G, int v);//求点v的第一个邻接点
int nextNeighbor(MGraph G, int v, int w);//求点v的邻接点w的下一个邻接点

void visit(MGraph G, int v);//访问该节点的信息
void BFS(MGraph G, LinkQueue Q, int v);// 广度优先遍历
void BFSTraverse(MGraph G);//广度优先遍历 主函数
void DFS(MGraph G, int v);//深度优先遍历
void DFSTraverse(MGraph G);//深度优先遍历 主函数



//初始化队列
void initQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueueNode*)malloc(sizeof(QueueNode)); // 分配头节点
	Q->front->next = NULL; //初始化为空
}
//判断队列是否为空
int isQueueEmpty(LinkQueue* Q) {
	if (Q->front == Q->rear) return 1;
	else return 0;
}
//入队
void enQueue(LinkQueue* Q, QueueType data) {
	QueueNode* news = (QueueNode*)malloc(sizeof(QueueNode));
	news->data = data; // 创建新节点，插入队列尾部 
	news->next = NULL;
	Q->rear->next = news;
	Q->rear = news;
}
//出队
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; // 若原队列只有一个节点，删除后变空 
	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");
	}
}
// 初始化图并输入数据
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;
		}
	}

	/* 输入图的结点矩阵 Vexs[MaxVertexNum] */
	int v[6] = { 'A','B','C','D','E','F' };
	for (i = 0; i < G->vexnum; i++)
		G->Vexs[i] = v[i];

	/* 输入图的边权 */
	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;
}
// 求点v的第一个邻接点
// 若有返回顶点号，否则返回-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;
}
// 求点v的邻接点w的下一个邻接点
// 若有返回顶点号，否则返回-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;
}
// 访问该节点的信息
void visit(MGraph G,int v) {
	printf("%c ",G->Vexs[v]);
}
// 广度优先遍历
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);
			}
		}
	}
}
// 广度优先遍历 主函数
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);
	}
}
// 深度优先遍历
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);
	}
}
// 深度优先遍历 主函数
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广度优先遍历 : ");
	BFSTraverse(G);

	printf("\n深度优先遍历 : ");
	DFSTraverse(G);
	return 0;
}

到了这里，关于数据结构 | 图的遍历的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E) ，其中： 顶点集合V = {x|x属于某

    2024年02月04日
    浏览(73)
  • 【数据结构】图的创建和深度（DFS）广度（BFS）优先遍历

    【数据结构】图的创建和深度（DFS）广度（BFS）优先遍历

    图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)，其中，G标示一个图， V是图G中 顶点的集合 ， E是图G中 边的集合 。 图分为 无向图 和 有向图 无向图： 若顶点Vi到Vj之间的边没有方向，则称这条边为无向边（Edge），用序偶对(Vi,Vj)表示。 有向图： 若从

    2024年02月05日
    浏览(61)

  • 【数据结构】3个例题带你理解图的遍历：深度优先搜索

    1、定义 2、性能分析 3）算法实现 💟作者简介：大家好呀！我是 路遥叶子 ，大家可以叫我 叶子 哦！❣️     📝个人主页：【叶子博客】 🏆博主信息： 四季轮换叶，一路招摇胜！ 🐋希望大家多多支持😘一起进步呀#

    2024年02月08日
    浏览(44)
  • 数据结构实验6 ：图的存储与遍历（邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS）

    数据结构实验6 ：图的存储与遍历（邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS）

    利用邻接矩阵存储无向图，并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2，其中n1表示顶点数（则顶点编号为0至n1-1），n2表示图中的边数。 之后有n2行输入，每行输入表示一条边，格式是“顶点1 顶点2”，把边插入图中。 例如： 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(67)
  • 算法数据结构——图的遍历之深度优先搜索算法（Depth First Search）

    算法数据结构——图的遍历之深度优先搜索算法（Depth First Search）

    深度优先搜索算法 （Depth First Search）：英文缩写为 DFS。是一种用于搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。 深度优先搜索采用了回溯思想，该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜

    2024年02月09日
    浏览(50)
  • 数据结构与算法基础-学习-24-图的遍历之DFS（深度优先搜索）和BFS（广度优先搜索）

    数据结构与算法基础-学习-24-图的遍历之DFS（深度优先搜索）和BFS（广度优先搜索）

    目录 一、遍历定义 二、遍历实质 三、DFS 四、BFS 五、宏定义 六、自定义类型 七、函数实现 1、DFS（邻接矩阵实现） 2、DFS（邻接表实现） 3、BFS（邻接矩阵实现） 4、BFS（邻接表实现） 5、打印邻接矩阵遍历顺序  6、打印邻接表遍历顺序 八、遍历算法效率分析 1、DFS 2、BFS 九

    2024年02月03日
    浏览(74)
  • 【数据结构】图的广度优先遍历

    【数据结构】图的广度优先遍历

    广度优先遍历，类似于树的层次遍历，又是熟悉的队列实现。首先将第一个顶点添加到队列中，然后讲该顶点的所有邻接顶点都加入队列中，再将该顶点输出。如此重复直到遍历完整个图。 Q:队列，用于存放顶点。 front,rear:队头和队尾指针，用于入队和出队。 p:工作指针，用

    2024年02月05日
    浏览(49)

  • 数据结构--5.3图的遍历（广度优先遍历）

    广度优先遍历：         广度优先遍历（BreadthFirstSearch），又称为广度优先搜索，简称BFS。 要实现对图的广度遍历，我们可以利用队列来实现。  （参考队列）（上述为结构）

    2024年02月10日
    浏览(47)

  • 【数据结构与算法】图的搜索——广度优先遍历、最小生成树

    邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍. 邻接矩阵:用于最短路径算法. 该数据结构维护一个不相交动态集的集合，每个集合有一个代表，不关心谁做代表。 支持三种操作： MAKE_SET(x) FIND_SET(x) UNION(x,y

    2024年02月19日
    浏览(50)

  • 图的深度、广度优先探索（数据结构）

    2024年02月14日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包