首页
学习
活动
专区
工具
TVP
发布

邻接矩阵学习

邻接矩阵:是表示顶点之间相邻关系的矩阵。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间的关系(边或弧)的数据,这个二维数组称为邻接矩阵。...邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。 设G=(V,E)是一个图,其中V={v1,v2,.....,vn}。...G的邻接矩阵是一个具有下列性质的n阶方阵: ①对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0,有向图则不一定如此。...特点: 无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。...用邻接矩阵表示法表示图如图8.7 所示。 用邻接矩阵表示法表示网图如图8.8 所示。 ?

1.4K10
您找到你想要的搜索结果了吗?
是的
没有找到

邻接表与邻接矩阵

邻接矩阵无向图 graph 表示?有向图 digraph 表示?...若采用邻接矩阵表示,则需要申请空间大小为 的二维数组,在二位数组中保存每两个顶点之间的连通关系,则无论有向图或无向图,邻接矩阵方式的存储空间复杂度皆为 。...若只记录图中顶点是否连通,不记录权值大小,则可以使用一个二进制位来表示二维数组的每个元素,并且根据无向图的特点可知,无向图的邻接矩阵沿对角线对称,所以可以选择记录一半邻接矩阵的形式来节省空间开销。...两种存储结构对比根据邻接表和邻接矩阵的结构特性可知,当图为稀疏图、顶点较多,即图结构比较大时,更适宜选择邻接表作为存储结构。...当图为稠密图、顶点较少时,或者不需要记录图中边的权值时,使用邻接矩阵作为存储结构较为合适。

1.8K00

图的邻接矩阵存储结构

图的邻接矩阵存储结构 一、知识框架 二、存储方式(这里只讨论邻接矩阵存储方式) 在图的邻接矩阵存储结构中,顶点信息使用一维数组存储,边信息的邻接矩阵使用二维数组存储。...无向图和其对应的邻接矩阵 有向图 三、代码实现 1.头文件AdjMGraph.h 针对的是下面这个有向图 #pragma once //图的邻接矩阵存储结构 #include "SeqList.h..." typedef struct { SeqList Vertices; //存放顶点的顺序表 int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵 int...\n"); return; } G->edge[v1][v2] = MaxWeight; G->numOfEdges--; } /* 取第一个邻接顶点 对于邻接矩阵来说,顶点v的第一个邻接顶点...,就是邻接矩阵的顶点v行中 从第一个矩阵元素开始的非0且非无穷大的顶点 */ int GetFirstVex(AdjMGraph G, int v) //在图G中寻找序号为v的顶点的第一个邻接顶点 //

54170

数据结构 图的邻接矩阵

图的邻接矩阵的存储方式是用两个数组来实现的,一个一维数组存储顶点信息,一个二维数组存储线(无向图)或弧(有向图)的信息。...设图G有n个顶点,则邻接矩阵是一个n × n的方阵,定义为: 无向图的邻接矩阵,两个顶点有边则为1,否则,为0;因为是无向图arc[i][j] = arc[j][i],所以矩阵为对称矩阵,对角线为自己到自己的边...,邻接矩阵中,行之和或者列之和都为各顶点度的总数。...设图G有是网图,有n个顶点,则邻接矩阵是一个n × n的方阵,定义为: 无向网图和无向图差不多,就是加了权值,两个顶点之间无边的话距离是∞。 如果是有向图,邻接矩阵就不是对称矩阵了。...vertextype; //定义定点的存储信息为字符型 typedef int arctype; //定义边的权值为int型 //图的邻接矩阵的存储结构 typedef struct {

58210

数据结构(八):邻接表与邻接矩阵

邻接矩阵 无向图 graph 表示 graph_adjacency_matrix 有向图 digraph 表示 digraph_adjacency_matrix 若采用邻接矩阵表示,则需要申请空间大小为...的二维数组,在二位数组中保存每两个顶点之间的连通关系,则无论有向图或无向图,邻接矩阵方式的存储空间复杂度皆为 。...若只记录图中顶点是否连通,不记录权值大小,则可以使用一个二进制位来表示二维数组的每个元素,并且根据无向图的特点可知,无向图的邻接矩阵沿对角线对称,所以可以选择记录一半邻接矩阵的形式来节省空间开销。...两种存储结构对比 根据邻接表和邻接矩阵的结构特性可知,当图为稀疏图、顶点较多,即图结构比较大时,更适宜选择邻接表作为存储结构。...当图为稠密图、顶点较少时,或者不需要记录图中边的权值时,使用邻接矩阵作为存储结构较为合适。

1.4K30

数据结构:图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。...设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: ? 我们来看一个实例,图7-4-2的左图就是一个无向图。 ? 我们再来看一个有向图样例,如图7-4-3所示的左图。 ?...设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: ? 如图7-4-4左图就是一个有向网图。 ?...顶点类型应由用户定义  */ typedef struct {     VertexType vexs[MAXVEX];/* 顶点表 */     EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵...,可看作边表 */     int numNodes, numEdges;/* 图中当前的顶点数和边数  */ } MGraph; /* 建立无向网图的邻接矩阵表示 */ void CreateMGraph

4.3K80
领券