数据结构之图(术语、存储结构、遍历) | 您所在的位置:网站首页 › 人员矩阵图是什么意思 › 数据结构之图(术语、存储结构、遍历) |
1、相关术语
顶点(Vertex)、弧(Arc)、弧头(初始点)、弧尾(终结点)、边(Edge)、有向图(Directed graph)、无向图(Undigraph)、完全图(Completed grapg)、有向完全图、稀疏图(Sparse graph)、稠密图(Dense graph)、权(weigh)、网(network)、无向网、有向网、子图(Subgraph)、邻接点(Adjacent)、度(Degree)、入度(Indegree)、出度(Outdegree)、路径(path)、回路(环)、简单路径、简单回路(简单环)、连通、连通图(Connected graph)、连通分量(Connected Component)、强连通图、强连通分量(有向图中的极大强连通子图)、生成树、极小连通子图、有向树。 无向图:G=(V, {E})、0≤边≤n(n-1)/2 有向图:G=(V, {A})、0≤弧≤n(n-1) 连通图:在无向图G中,如果图中任意两个顶点vi, vj属于V,vi和vj都是连通的,则图G是连通图。 连通分量:无向图中的极大连通子图 图例:
强连通图:在有向图G中,如果每一对顶点vi, vj属于V且vi不等于vj,从vi到vj与从vj到vi都存在路径,则图G是连通图。 强连通分量:有向图的极大强连通子图。
生成树:一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。 如果在生成树上添加一条边,必定构成一个环:因为这条边使得它依附的那两个顶点之间有了第二条路径。 一个有n个顶点的生成树有且仅有n-1条边。如果一个图有n和顶点和小于n-1条的边,则是非连通图。如果多余n-1条边,则一定有环。但有n-1条边的图不一定是生成树。 2、存储结构 2.1邻接矩阵(数组表示法)(无向图、有向图、无向网、有向网) 用两个数组来表示图。一个一维数组存储图中数据元素(顶点)的信息,一个二维数组(邻接矩阵)存储图中数据元素之间的关系(边或弧)的信息。 若图G是无向图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
下图就是一个无向图:
从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。 从这个矩阵中,很容易知道图中的信息。 (1)要判断任意两顶点是否有边无边就很容易了; (2)要计算某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和; (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]=1的vj就是邻接点; 而有向图有入度和出度之分:顶点vi的入度为是第i列各数之和,顶点vi的出度是第i行的各数之和。 若图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
wij表示(vi,vj)或上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值,也就是一个不可能的极限值。下图是一个有向网图和它的邻接矩阵: 注:这个边数组(邻接矩阵)的对角线应该是无穷大。 可以看出: (1)第i行权重大于0、小于无穷的个数之和为顶点vi的出度(OD(vi)); (2 |
CopyRight 2018-2019 实验室设备网 版权所有 |