赞
踩
目录
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
注意:在图中数据元素叫做“顶点”;任意两个顶点之间都可能有关系,顶点之间的逻辑关系用“边”来表示,边集可以是空的(只有顶点),但是顶点集合一般要求有穷非空。
无向边:若顶点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)}
上图G2是一个有向图,G2={V2,E2},其中
—V2={A,B,C,D},
—E2={<B,A>,<B,C>,<C,A>,<A,D>}
定义:在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图。如下图,左侧不是连通图,右侧是连通图:
连通分量:无向图中的极大连通子图称为连通分量。
注意:首先要是子图,并且子图是要连通的;连通子图含有极大顶点数;具有极大顶点数的连通子图包含依附于这些顶点的所有边。
强连通图:在有向图中,如果对于每一对Vi到Vj都存在路径,则称G是强连通图。
强连通分量:有向图中的极大强连通子图称为有向图的强连通分量。下图中右侧是强连通图,左侧不是。并且右侧是左侧的极大强连通子图,也是左侧的强连通分量。
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
顶点数组: | 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的就是邻接点。
无向图的边构成了一个对称矩阵,看起来浪费了一半的空间,那如果我们是存放有向图会怎样呢?
顶点数组: | 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行的各数之和。
在图的定义中我们提到了网这个概念,事实上也就是每条边上都带有权的图叫做网。
顶点数组: | V0 | V1 | V2 | V3 |
V0 | V1 | V2 | V3 | |
V0 | 0 | ∞ | ∞ | 18 |
V1 | 8 | 0 | 2 | ∞ |
V2 | 4 | ∞ | 0 | ∞ |
V3 | ∞ | ∞ | ∞ | 0 |
这里的“∞”表示一个计算机允许的,大于所有边上权值的值。
征战尚未结束,你我仍需努力!
后续更精彩~~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。