12.11图的存储方式(邻接矩阵、邻接表),对应操作(插入,删除,查找),遍历,最小生成树

2023-12-14 20:53:23

构建树

先序输入

邻接输入

?图的邻接矩阵

无向图

有向图

邻接矩阵就是通过顶点数组,直接记录顶点来记录边,即两个顶点数组夹成的二维数组里记录的就是边的信息

#define MaxVertexNum 100	//顶点数目的最大值
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;	//带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum];	//顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵,边表
	int vexnum, arcnum;	//图的当前顶点数和弧树
}MGraph;

图有两个重要参数,即点和边。?

邻接表

其实就是相当于在邻接矩阵的基础上,去掉了那些NULL的结点,对于每个边只保留了非空的结点,也就形成了每个结点下的一串串链

即在顶点链表中,每个顶点有两个指针,一个指针(next)指向后续的顶点(与该顶点不一定连通,只是编号顺序);一个指针(dest)指向由该顶点通向的后续顶点(与该顶点一定连通)

#define MAXVEX 100	//图中顶点数目的最大值
type char VertexType;	//顶点类型应由用户定义
typedef int EdgeType;	//边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{
	int adjvex;	//该弧所指向的顶点的下标或者位置
	EdgeType weight;	//权值,对于非网图可以不需要
	struct EdgeNode *next;	//指向下一个邻接点
}EdgeNode;

/*顶点表结点*/
typedef struct VertexNode{
	Vertex data;	//顶点域,存储顶点信息
	EdgeNode *firstedge	//边表头指针
}VertexNode, AdjList[MAXVEX];

/*邻接表*/
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//图中当前顶点数和边数
}

无向图

有向图

插入操作

查找操作

这是每个新节点都插入到头部位置?

删除操作

图的遍历

DFS

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发,深度优先遍历图G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//访问顶点
	visited[v] = TRUE;	//设已访问标记
	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。
	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
	int v; 
	for(v=0; v<G.vexnum; ++v){
		visited[v] = FALSE;	//初始化已访问标记数据
	}
	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
		if(!visited[v]){
			DFS(G, v);
		}
	}
}

应用?

3、深度优先的生成树和生成森林

深度优先搜索会产生一棵深度优先生成树。 当然,这是有条件的,即对连通图调用DFS才能产生深度优先生成树,否则产生的将是深度优先生成森林,如下图所示。基于邻接表存储的深度优先生成树是不唯一的 。(因为邻接表自身存储就不是唯一的)

注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,若边的输入次序不同,生成的邻接表也不同。因此,对于同样一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的,基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的.

最小生成树

最小生成树是指一个连通无向图中包含所有顶点的树,并且其边的总权重最小。

最小生成树的概念是为了解决一类问题,即在一个连通图中找到一棵包含所有顶点的树,并且使得树的边的权重之和最小。最小生成树在实际应用中有着广泛的应用,例如在电力输送网络中确定最佳输电线路、在城市道路规划中确定最佳道路布局、在通信网络中确定最佳通信线路等。

以城市道路规划为例,假设一个城市有多个区域,我们希望在这些区域之间建立道路,使得每个区域都能够互相到达,并且总的道路长度最小。这就可以通过最小生成树来解决。图中的每个顶点表示一个区域,边的权重表示两个区域之间的道路长度。通过找到最小生成树,就可以确定哪些区域之间需要建立道路,并且选择长度最短的道路,从而实现最优的道路规划。

最小生成树的概念的引入,使得我们能够在图中找到一种最优的连接方式,并且在实际问题中能够进行合理的规划和决策。

文章来源:https://blog.csdn.net/m0_73553411/article/details/134921119
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。