目录
1.图的基本概念
2.图的相关定义
3.图的顶点与边之间的关系
4.连通图
5.图的存储结构
(1).邻接矩阵(无向图)
(2).邻接矩阵(有向图)
(3).邻接矩阵(网)
1.图的基本概念
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
注意:在图中数据元素叫做“顶点”;任意两个顶点之间都可能有关系,顶点之间的逻辑关系用“边”来表示,边集可以是空的(只有顶点),但是顶点集合一般要求有穷非空。
2.图的相关定义
-
无向边:若顶点Vi到Vj之间的边没有方向。则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。
如上图G1是一个无向图,G1={V1,E1},其中
—V1={A,B,C,D};
—E1={(A,B),(B,C),(C,D),(D,A),(A,C)}
- 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。
上图G2是一个有向图,G2={V2,E2},其中
—V2={A,B,C,D},
—E2={<B,A>,<B,C>,<C,A>,<A,D>}
- 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。以下两个则不属于简单图:
- 无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。如下图:
- 有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。如下图:
- 稀疏图和稠密图:这里的稀疏和稠密是有些模糊的概念,都是相对而言的,通常认为边或弧数小于n*logn(n是顶点个数)的图称为稀疏图,反之称为稠密图。
- 带权的图:有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight),带权的图通常称为网(Network)。 如下图:
- 子图:假设有两个图G1=(V1,E1)和G2=(V2,E2),如果V2⊆V1,E2⊆E1,则称G2为G1的子图(Subgraph)。
3.图的顶点与边之间的关系
- 邻接点:对于无向图G=(V,E),如果边(V1,V1)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。边(V1,V2)依附于顶点V1和V2,或者说(V1,V2)与顶点V1和V2相关联。对于有向图G=(V,E),如果有<V1,V2>∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。
- 度(Degree):顶点V的度是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3。
- 入度、出度:以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为:TD(V)=ID(V)+OD(V)。如下图顶点A的入度是2,出度是1,所以顶点A的度是3。
- 路径的长度是路径上的边或弧的数目。
- 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。
- 序列中顶点不重复出现的路径称为简单路径,除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。如下图,左侧是简单环,右侧不是简单环。
4.连通图
定义:在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图。如下图,左侧不是连通图,右侧是连通图:
连通分量:无向图中的极大连通子图称为连通分量。
注意:首先要是子图,并且子图是要连通的;连通子图含有极大顶点数;具有极大顶点数的连通子图包含依附于这些顶点的所有边。
强连通图:在有向图中,如果对于每一对Vi到Vj都存在路径,则称G是强连通图。
强连通分量:有向图中的极大强连通子图称为有向图的强连通分量。下图中右侧是强连通图,左侧不是。并且右侧是左侧的极大强连通子图,也是左侧的强连通分量。
5.图的存储结构
(1).邻接矩阵(无向图)
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
顶点数组: | V0 | V1 | V2 | V3 |
V0 | V1 | V2 | V3 | |
V0 | 0 | 1 | 1 | 1 |
V1 | 1 | 0 | 1 | 0 |
V2 | 1 | 1 | 0 | 1 |
V3 | 1 | 0 | 1 | 0 |
如上,我们设置了两个数组,顶点数组为vertex[4]={V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。
上面第二个表是以对角线为对称轴的对称表,由此我们引入了对称矩阵的概念:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j][i](0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角对应的元全都是相等的。
从这个二维数组组成的对称矩阵我们可以很容易的知道图中的信息:根据0或1来判定任意两个顶点之间是否有边;某个顶点的度就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和;求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1的就是邻接点。
(2).邻接矩阵(有向图)
无向图的边构成了一个对称矩阵,看起来浪费了一半的空间,那如果我们是存放有向图会怎样呢?
顶点数组: | V0 | V1 | V2 | V3 |
V0 | V1 | V2 | V3 | |
V0 | 0 | 0 | 0 | 1 |
V1 | 1 | 0 | 1 | 0 |
V2 | 1 | 1 | 0 | 0 |
V3 | 0 | 0 | 0 | 0 |
可见顶点数组vertex[4]={V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由V1到V0有弧,的到arc[1][0]=1,而V0到V1没有弧,因此arc[0][1]=0。
有向图要考虑入度和出度,顶点V1的入度为1,正好是第V1列的各数之和,顶点V1的出度为2,正好是第V2行的各数之和。
(3).邻接矩阵(网)
在图的定义中我们提到了网这个概念,事实上也就是每条边上都带有权的图叫做网。
顶点数组: | V0 | V1 | V2 | V3 |
V0 | V1 | V2 | V3 | |
V0 | 0 | ∞ | ∞ | 18 |
V1 | 8 | 0 | 2 | ∞ |
V2 | 4 | ∞ | 0 | ∞ |
V3 | ∞ | ∞ | ∞ | 0 |
这里的“∞”表示一个计算机允许的,大于所有边上权值的值。
征战尚未结束,你我仍需努力!文章来源:https://www.toymoban.com/news/detail-753405.html
后续更精彩~~文章来源地址https://www.toymoban.com/news/detail-753405.html
到了这里,关于数据结构——图(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!