图论入门

图的定义

有向图&无向图

有向图与无向图的定义

> 树是图的特列，只是图允许数据元素可拥有多个前驱，可以反映数据元素之间多对多的关系。

图(G)由两个集合V(G)和E(G)组成。记为G=(V, E)。 其中V是顶点的非空有限集合；E(G)是边的有限集合。

无向图G2中： V(G2)={1, 2, 3, 4, ,5 ,6, 7}; E(G2)={(1,2), (1,3), (2,3), (2,4), (2,5), (5,6), (5,7) }

E(G2)是无向边的有限集合，边是顶点的无序对。记为：（v,w）或（w,v)，并且（v, w)=(w, v).

有向图G1中： V(G1)={1, 2, 3, 4, 5, 6} E(G1)={ <1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3> }

E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对  记为 （v和w是顶点，v为弧尾，w为弧头）

完全图

不同顶点数的完全图

* 无向完全图（Undirected Complete Graph） * n个顶点的无向图最大边数：edges = n(n-1)/2 * 有向完全图（Directed Complete Graph） * n个顶点的有向图最大边数：edges = n(n-1)

图顶点的邻接关系

• 无向图：若$(v_i,v_j)$是一条无向边，则称顶点$v_i$ 和$v_j$ 互为邻接点，并称$(v_i,v_j)$依附或关联于顶点$v_i$ 和$v_j$.
• 有向图：若是一条有向边（弧），则称顶点$v_i$邻接于顶点$v_j$，并称顶点$v_j$ 是顶点$v_i$ 的邻接顶点.

顶点的度

• 无向图中顶点v的度为：依附于顶点v的边数
  • 依附：边(a, b) 依附于顶点a和b
• 有向图中顶点v的度为：顶点v的入度与出度之和
  • 入度（in-degree）：以顶点V为弧头的弧数
  • 出度（out-degree）：以顶点V为弧尾的弧数
  • degree(v) = in-degree(v) + out-degree(v)

生成树(Spanning Tree)

• 子图(subgraph): 子图是图的一部分，它本身也是一个图。
• 连通图(Connected Graph): 无向图中任意两个顶点都是连通的。
• 强连通图：有向图中任意两个顶点都有通向对方的路径。
• 生成树：无向图G是含有n个顶点的连通图。则：G的生成树是含有n个顶点且只有n-1条边的连通子图。
• 有向树：若一个有向图G恰有一个顶点的入度为0 。其余顶点的入度均为1，则它是一棵有向树。

图的抽象数据类型

ADT Graph{ 
	// 数据对象： 
	// V是具有相同特性的数据元素的集合，称为顶点集 
	// 数据关系： 
	R={VR} 
	// 基本操作： 
	GraphCreate(G, V, VR) // 以顶点集合V和弧集合VR构造图G				 
    GraphDestroy(G) // 删除图G，如果G存在，删除G 
	GraphLocateVertex(G, V) // 定位，返回顶点V在G中的位置 	 
    GraphGetVertex(G, V) // 取值操作，返回V的值
    GraphFirstAdj(G, V) // 查询G中V的第一个邻接顶点 
    GraphNextAdj(G, V, W) // 求V相对于W的下一个邻接点 
    GraphInsertVertex(G, V) // 插入顶点 
    GraphDeleteVertex(G, V) // 删除顶点 
    GraphInsertArc(G, V, W) // 插入弧 
    GraphDeleteArc(G, V) // 删除弧 
    DFSTtraverse(G, V, Visit()) // 深度遍历图G 
    BFSTtraverse(G, V, Visit()) // 广度遍历图
}ADT Graph

图的储存方式

---

顺序存储结构

• 邻接矩阵法（二维数组）

链式存储结构

• 邻接表法
• 十字链法
• 邻接多重表法

---

顺序存储结构

使用两个数组分别存储数据元素的信息和数据元素之间的关系

数组表示法

定义数据结构体：

#define M 100 // 顶点的最大个数 
typedef struct { 
	ElemType vertex; // 顶点信息 
}TVex; 
typedef struct { 
	int adj; // 弧的信息 
}TArc; 
typedef struct { 
	TVex vexs[M]; 
	TArc arcs[M][M]; 
}TGraph;

---

定义邻接矩阵(AdjMatrix):

$$\mathrm{AdjMatrix}[i][j]=\{\begin{array}{ll}1& \text{ if }\left({\mathrm{v}}_i,{\mathrm{v}}_j\right)\text{ or }⟨{\mathrm{v}}_i,{\mathrm{v}}_j⟩\in \mathrm{VR}\\ 0& \text{ else }\end{array}$$

邻接矩阵示意图

判定两个顶点 $v_i$ 与 $v_j$ 是否邻接, 只需判 $A[i,j]$ 是否为 1 求顶点的度:

• 无向图中: $\mathrm{Degree}\left(V_i\right)={\sum }_{j=1}^{n}A[i,j]={\sum }_{j=1}^{n}A[j,i]$ 顶点 $v_i$ 的度等于邻接矩阵中第i行 (i列) 的元素之和
• 有向图中: $\mathrm{Degree}\left(V_i\right)={\sum }_{j=1}^{n}A[i,j]+{\sum }_{j=1}^{n}A[j,i]$
• 顶点 $v_i$ 的度等于： $v_i$ 的出度 $+v_i$ 的入度
• 顶点 $v_i$ 的出度为邻接矩阵中第 $i$ 行元素之和
• 顶点 ${\mathbf{v}}_{\mathbf{i}}$ 的入度为邻接矩阵中第 $\mathbf{i}$ 列元素之和

---

如果 G是带权图: $w_{ij}$ 是边 $\left(v_i,v_j\right)$ 或弧 $<v_i,v_j>$ 的权 则其邻接矩阵定义为:

$$A[i,j]=\{\begin{array}{ll}{W}_{ij}& \text{ 若 }\left(v_i,v_j\right)\text{ 或 }<v_i,v_j>\text{ 是图 }\mathrm{G}\text{ 的边 }(\mathrm{i}\ne \mathrm{j})\\ \infty & \text{ 若 }\left(v_i,v_j\right)\text{ 或 }<v_i,v_j>\text{ 不是图 }\mathrm{G}\text{ 的边 }(\mathrm{i}\ne \mathrm{i})\\ 0& \text{ 所有对角线元素 }(\mathrm{i}=\mathrm{j})\end{array}$$

带权图的邻接矩阵示意图

---

链式存储结构-邻接表

数据结构体示意图

• 邻接表是图的一种链式存储结构
  • 对图中的每个顶点建立一个单链表
  • 单链表中的第i个结点表示依附于顶点$v_i$的顶点
• 每个链表结点包含两个域：
  • adjvex：记载与顶点$v_i$邻接的顶点信息
  • nextarc：指向下一个与顶点$v_i$邻接的结点
• 每个链表附设一个头结点：
  • data：存放顶点信息（如：姓名、编号等）
  • fristarc：指向链表的第一个结点

无向图的邻接表表示法

有向图的邻接表表示法