图基础

图的定义

• 图(Graph)是由定点的又穷非空集合和定点之间边的集合组成,通常表示为:G(V,E),其中G表示一个图,V是图G顶点的集合,E是图G中边的集合

• 线性表中我们把数据元素叫元素,树中叫结点,在图中数据元素我们则称之为顶点(Vertex)

• 线性表可以没有数据元素,称为空表,树中可以没有结点,叫做空树,大部分国内教材强调图的顶点集合V要又穷非空,而国外允许空

• 线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图结构中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的

图的各种定义

• 无向边:若顶点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)

图的顶点与边之间的关系

• 对于无向图G=(V,E),如果边(V1,V2)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接.边(V1,V2)依附(incident)于顶点V1和V2,或者说边(V1,V2)与顶点相关联

• 顶点V的度(Degree)是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3

• 对于有向图G=(V,E),如果有<V1,V2>∈E则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1

• 以顶点V为头的弧的数目称为V的入度(InDegree),即为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V)

• 下图顶点A的入度是2,出度是2,所以顶点A的度是3

• 无向图G=(V,E)中从顶点V1到顶点V2的路径(Path)

• 下图用红线列举了从顶点B到顶点D的四种不同路径

• 如果G是有向图,则路径也是有向的

• 下图用红线列举顶点B到顶点D的两种路径,而顶点A到顶点B就不存在路径

• 路径的长度是路径上的边或弧的数目

• 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)

• 序列中顶点不重复出现的路径称为简单路径,除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环

• 下图左侧是简单环,右侧不是简单环

连通图

• 在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图(ConnectedGraph)

• 下图左侧不是连通图,右侧是连通图

• 无向图中的极大连通子图称为连通分量

• 注意以下概念:

  • 首先要是子图,并且子图是要连通的

  • 连通子图含有极大顶点数

  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边

• 在有向图G中,如果对于没一对Vi到Vj都存在路径,则称G是强连通图

• 有向图中的极大强连通子图称为有向图的强连通分量

• 下图左侧并不是强连通图,右侧是.并且右侧是左侧的极大连通子图,也是左侧的强连通分量

• 连通图的生成树:连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边

图:

其中一种生成树:

• 如果一个有向图恰有一个顶点入度为0,其余顶点的入度均为1,则是一颗有向树

图的存储结构

邻接矩阵(无向图)

• 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息

• 我们可以设置两个数组,定点数组为vertex4={v0,v1,v2,v3},边数组arc4位对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)

• 对称矩阵:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j]i.即从矩阵的左上角到右下角的主对角线为轴,右上角的元素与左下角相对应的元全都是相等的

• 有了这个二维数组组成的对称矩阵,我们就可以很容易的知道图中的信息:

  • 要判定任意两顶点是否有边无边就非常容易了

  • 要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行(或第i列)的元素之和

  • 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点

邻接矩阵(有向图)

• 可见顶点数组vertex4={v0,v1,v2,v3},弧数组arc4也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由v1到v0有弧,得到arc[1][0]=1,而v0到v1没有弧,因此arc0=0

• 另外有向图是有讲究的,要考虑入度和出度,顶点v1的入度为1,正好是v1列的各数之和,顶点v1的出度为2,正好是第v1行的各数之和

邻接矩阵(网)

• 每条边上带有权的图就叫网

(v1,v1)为0

这里的无穷表示一个计算机允许的,大于所有边上权值的值

邻接表

• 对于边数相对顶点较少的图,邻接矩阵会极大的浪费空间,因此我们可以考虑另外一种存储结构方式,例如把数组与链表结合一起来存储,这种方式在图结构也适用,我们成为邻接表(AdjacencyList)

• 邻接表的处理方法是这样的:

  • 图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以比较容易的读取顶点信息,更加方便

  • 图中每个顶点vi的所有邻接点构成一个线性表,由于连接点的个数不确定,所以我们选择用单链表来存储

• 若是有向图,邻接表结构也是类似的,我们先来看下把顶点当弧尾建立的邻接表,这样很容易就可以得到每个顶点的出度

• 但有时为了便于确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表:

• 此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现

• 对于带权值得网图,可以在邻接表结点定义中再增加一个数据域来存储权值即可

十字链表

• 邻接表固然优秀,但也有不足,例如对有向图的处理上,有时候需要再建立一个逆邻接表

• 有没有可能把邻接表和逆邻接表结合起来呢,那就是十字链表(Orthognal List)

• 重新定义定点表结构:

data | firstIn | firstOut

• 重新定义定边表结构:

tailVexa | headVex | headLink | tailLink

• 十字链表的好处就是把邻接表和逆邻接表整合在一起了,这样既容易找到vi为尾的弧,也容易找到一vi为头的弧,因而容易求得顶点的出度和入度

• 十字链表除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表也是非常好的数据结构模型

邻接多重表

• 如果我们在无向图的应用中,关注的重点是定点的话,那么邻接表是不错的选择,但如果我们更关注的是边的操作,比如对已经访问过的边做标记,或者删除某一条边等操作,邻接表就显得不那么方便了

• 因此我们也仿照十字链表的方式,对边表结果进行改装,重新定义的边表结构如下

iVex | iLink | jVex | jLink

• 其中iVex和jVex是某条边依附的两个定点在顶点表中的下标.iLink指向依附顶点iVex的下一条边,jLink指向依附顶点jVex的下一条边

• 也就是说在邻接多重表中，边表存放的是一条边，而不是一个定点

边集数组

• 边集数组是由两个一维数组构成,一个是存储定点的信息,另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成