图论
基本概念
图是由顶点的有穷非空集合以及顶点的边的集合组成,通常表示为G(V,E)
; V是顶点的集合、E是边的集合;
基本术语
-
无向边
:若顶点Vi和Vj之间的边没有方向,称这条边为无向边(Edge),用(Vi,Vj)
来表示。 -
无向图
(Undirected graphs):图中任意两个顶点的边都是无向边。 -
有向边
:若从顶点Vi到Vj的边有方向,称这条边为有向边,也称为弧(Arc),用<Vi, Vj>
来表示,其中Vi称为弧尾
(Tail),Vj称为弧头
(Head)。 -
有向图
(Directed graphs):图中任意两个顶点的边都是有向边。 -
简单图
:不存在自环(顶点到其自身的边)和重边(完全相同的边)的图 -
无向完全图
:无向图中,任意两个顶点之间都存在边。 -
有向完全图
:有向图中,任意两个顶点之间都存在方向相反的两条弧。 -
稀疏图
;有很少条边或弧的图称为稀疏图,反之称为稠密图。 -
权
(Weight):表示从图中一个顶点到另一个顶点的距离或耗费。 -
网
:带有权重的图 -
度:与特定顶点相连接的边数;
-
出度、入度
:有向图中的概念,出度表示以此顶点为起点的边的数目,入度表示以此顶点为终点的边的数目; -
环
:第一个顶点和最后一个顶点相同的路径; -
简单环
:除去第一个顶点和最后一个顶点后没有重复顶点的环; -
连通图
:任意两个顶点都相互连通的图; -
极大连通子图
:包含尽可能多的顶点(必须是连通的),即找不到另外一个顶点,使得此顶点能够连接到此极大连通子图的任意一个顶点; -
连通分量
:极大连通子图的数量; -
强连通图
:此为有向图的概念,表示任意两个顶点a,b,使得a能够连接到b,b也能连接到a 的图; -
生成树
:n个顶点,n-1条边,并且保证n个顶点相互连通(不存在环); -
最小生成树
:此生成树的边的权重之和是所有生成树中最小的; -
AOV网(Activity On Vertex Network ):在有向图中若以顶点表示活动,有向边表示活动之间的先后关系
-
AOE网(Activity On Edge Network):在带权有向图中若以顶点表示事件,有向边表示活动,边上的权值表示该活动持续的时间
有向图与无向图
1.无向图(undirected graph)
如果一个图结构中,所有的边都没有方向性,那么这种图便称为无向图。典型的无向图,如图二所示。由于无向图中的边没有方向性,这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边,可以表示为(V2, V6),也可以表示为(V6,V2)。
图二 无向图
对于图二无向图,对应的顶点集合和边集合如下:
V(G)= {V1,V2,V3,V4,V5,V6}
E(G)= {(V1,V2),(V1,V3),(V2,V6),(V2,V5),(V2,V4),(V4,V3),(V3,V5),(V5,V6)}
2.有向图(directed graph)
一个图结构中,边是有方向性的,那么这种图就称为有向图,如图三所示。由于图的边有方向性,我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边,例如<V2,V6>表示从顶点V2到顶点V6,而<V6,V2>表示顶点V6到顶点V2。
图三 有向图
对于图三有向图,对应的顶点集合和边集合如下:
V(G)= {V1,V2,V3,V4,V5,V6}
E(G)= {<V2,V1>,<V3,V1>,<V4,V3>,<V4,V2>,<V3,V5>,<V5,V3>,<V2,V5>,<V6,V5>,<V2,V6>,<V6,V2>}
注意:
无向图也可以理解成一个特殊的有向图,就是边互相指向对方节点,A指向B,B又指向A。
邻接链表与邻接矩阵
图最常见的表示形式为邻接链表和邻接矩阵。邻接链接在表示稀疏图时非常紧凑而成为了通常的选择,相比之下,如果在稀疏图表示时使用邻接矩阵,会浪费很多内存空间,遍历的时候也会增加开销。但是,这不是绝对的。如果图是稠密图,邻接链表的优势就不明显了,那么就可以选择更加方便的邻接矩阵。
还有,顶点之间有多种关系的时候,也不适合使用矩阵。因为表示的时候,矩阵中的每一个元素都会被当作一个表。