实现常用数据结构(图)——图的基础概念

图的逻辑结构

1) 有向图和无向图

有向图: 若 E 是有向边(也称弧)的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为<v, w>，其中 v,w 是顶点，v 称为弧尾，w 称为弧头，<v, w>称为从 v 到 w 的弧，也称 v 邻接到 w。

无向图: 若 E 是无向边(简称边)的有限集合时，则图 G 为无向图。边是顶点的无序对，记为(v, w)或(w,v)。可以说 w 和 v 互为邻接点。边(v, w)依附于 w 和 v,或称边(v, w)和 v, w 相关联。

2) 简单图和多重图

一个图 G 如果满足:① 不存在重复边; ② 不存在顶点到自身的边，那么称图 G 为简单图。

若图 G 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边和自身关联，则称图 G 为多重图。

3) 完全图

对于无向图，|E|的取值范围为 0 到 n(n -1)/2,有 n(n - 1)/2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。

对于有向图，E1 的取值范围为 0 到 n(n-1),有 n(n -1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

4) 子图

设有两个图 G=(V, E)和 G’=(V’,E’)，若 V’是 V 的子集，且 E’是 E 的子集，则称 G’是 G 的子图。若有满足 V(G’)= V(G)的子图 G’，则称其为 G 的生成子图。

5) 连通、连通图和连通分量

在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。

6) 强连通图和强连通分量

在有向图中，如果有一对顶点 v 和 w，从 v 到 w 和从 w 到 v 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

7) 生成图、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n,则它的生成树含有 n-1 条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

8) 度、入度和出度

在无向图中，顶点 v 的度是指依附于顶点 v 的边的条数，记为 TD(v)。

在有向图中，顶点 v 的度分为入度和出度, 入度是以顶点 v 为终点的有向边的数目,记为 ID(v);而出度是以顶点 v 为起点的有向边的数目，记为 OD(v)。

9) 边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

10) 稠密图和习俗图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 G 满足|E| < |V|*log|V|时，可以将 G 视为稀疏图。

11) 路径、路径长度和回路

顶点 Vp 到顶点 Vq，之间的一条路径是指顶点序列 Vp, Vi1, Vi2, Vi3,…, Vim, Vq，当然关联的边也可理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n 个顶点，并且有大于 n-1 条边，则此图一定有环。

12) 简单路径和简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

13) 距离

从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷(∞)。

14) 有向树

一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树。

图的存储结构

图一般用一下几种方法进行存储.

邻接矩阵法

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

type Map struct {
 NodeSize int
 data     [][]int
}

func InitMap(n int) *Map {
 var data [][]int
 for i := 0; i < n; i++ {
  data = append(data, []int{})
  for j := 0; j < n; j++ {
   data[i] = append(data[i], math.MaxInt32)
  }
 }
 return &Map{
  NodeSize: n,
  data:     data,
 }
}

邻接表和逆邻接表

所谓邻接表，是指对图 G 中的每个顶点 Vi 建立一个单链表, 第 i 个单链表中的结点表示依附于顶点 Vi 的边(对于有向图则是以顶点 Vi 为尾的弧)，这个单链表就称为顶点 Vi 的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储 (称为顶点表), 所以在邻接表中存在两种结点: 顶点表结点和边表结点。

// VNode 边表结构
type VNode struct {
 cIdx int
 next *VNode
}

// ArcNode 点结构
type ArcNode struct {
 data  int
 first *VNode
}

// Map 图结构
type Map struct {
 NodeSize int
 LineSize int
 nodeList []ArcNode
}

func InitMap(n int) *Map {
 var l []ArcNode
 for i := 0; i < n; i++ {
  l = append(l, ArcNode{
   data:  i,
   first: nil,
  })
 }
 return &Map{
  NodeSize: n,
  LineSize: 0,
  nodeList: l,
 }
}

十字链表法

十字链表是有向图的一种链式存储结构。在十字链表中,对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下图所示。

弧结点中有 5 个域: 尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的位置; 链域 nextIn 指向弧头相同的下一条弧;链域 nextOut 指向弧尾相同的下一条弧。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

// VNode 弧结构
type VNode struct {
 start   int
 end     int
 nextIn  *VNode
 nextOut *VNode
}

// ArcNode 点结构
type ArcNode struct {
 data     int
 firstIn  *VNode
 firstOut *VNode
}

// Map 图结构
type Map struct {
 LineSize int
 NodeSize int
 NodeList []ArcNode
}

func InitMap(n int) *Map {
 var l []ArcNode
 for i := 0; i < n; i++ {
  l = append(l, ArcNode{
   data:     i,
   firstIn:  nil,
   firstOut: nil,
  })
 }
 return &Map{
  LineSize: 0,
  NodeSize: n,
  NodeList: l,
 }
}

邻接多重表

邻接多重表是无向图的另一种链式存储结构。

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。

在邻接多重表中, 所有依附于同一顶点的边串联在同一链表中, 由于每条边依附于两个顶点 , 因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

// VNode 边结构
type VNode struct {
 i     int
 iNext *VNode
 j     int
 jNext *VNode
}

// ArcNode 点结构
type ArcNode struct {
 data  int
 first *VNode
}

// Map 图结构
type Map struct {
 NodeSize int
 LineSize int
 NodeList []ArcNode
}

func InitMap(n int) *Map {
 var l []ArcNode
 for i := 0; i < n; i++ {
  l = append(l, ArcNode{
   data:  i,
   first: nil,
  })
 }
 return &Map{
  NodeSize: n,
  LineSize: 0,
  NodeList: l,
 }
}