图的基本概念
图是什么,图是一种数据结构,一种非线性结构,所谓的非线性结构,浅显地理解的话,就是图的存储不是像链表这样的线性存储结构,而是由两个集合所组成的一种数据结构。
一个图中有两类东西,一种是结点,一种结点之间的连线。要用一种数据结构来表示的话,首先我们需要一个集合来存储所有的点,我们用V这个集合来表示(vertex),还需要另一个集合来存储所有的边,我们用E来表示(Edge),那么一个图就可以表示为:
G = (V,E)
有的图的边是有方向的,有的是没有方向的。
(A,B)表示A结点与B结点之间无方向的边,<A,B>则表示方向为从A到B的一条边,当然,如果是<B,A>,则方向相反。因此从边的方向我们就可以把图分为有向图和无向图两种。
其它概念
一个图中的元素有很多,例如:
完全图,邻接节点,结点的度,路径,权,路径长度,子图,连通图和强连通图,生成树,简单路径和回路...
本文只说说容易混淆的概念,以后再慢慢写。
完全图,连通图,与强连通图
完全图可分为有向完全图和无向完全图两种,如果一个图的任意两个结点之间有且只有一条边,则称此图为无向完全图,若任意两个结点之间有且只有方向相反的两条边,则称为有向完全图。
那么连通图与完全图有什么区别呢?连通图是指在无向图中,若图中任意一对结点之间都有路径可达,则称这个无向图是连通图,而强连通图则是对应于有向图来说的,其特点与连通图是一样的。只不过是有向的,所以加了"强"。
连通图与完全图的区别就是,完全图要求任意两点之间有边,而连通图则是要求有路径。边和路径是有区别的。
邻接结点
一个结点的邻接节点,对于无向图来说,就是与这个结点相连的结点,至少有一个。
对于有向图来说,由于边是有方向的,所以一个结点的邻接节点是指以这个结点为开头,所指向的那些结点。
结点的度
度是针对结点来说的, 又分为出度和入度,看到“出度入度”,我们不难想到这是与边和边的方向有关的。
对于无向图来说,没有出度入度之分,一个结点的度就是经过这个结点的边的数目(或者是与这个结点相关联的边的数目),对于有向图来说,出度就是指以这个结点为起始的边的条数(箭头向外),入度则是以这个点为终点的边的条数(箭头向内)。出 = 箭头向外,入 = 箭头向内
权
权是指一条边所附带的数据信息,比如说一个结点到另一个结点的距离,或者花费的时间等等都可以用权来表示。带权的图也称为网格或网。
子图
跟一个集合有子集一样,图也有子图。可以类比理解。