图（Java语言实现）

一、图的概念

顶点（Vertex）：图中的数据元素，我们称之为顶点，图至少有一个顶点（非空有穷集合）。
边（Edge）：顶点之间的关系用边表示。

1.图（Graph）

图 G 由顶点集 V 和边集 E 组成，记为 $G=(V,E)$ ，其中V(G)表示图G中顶点的有限非空集；$E(G)$ 表示图 G 中顶点之间的关系（边）集合。若 V = { v 1 , v 2 , … , v n } V = \{ v_1 , v_2 , … , v_n \} V={v1​,v2​,…,vn​}，则用 $|V|$ 表示图 G 中顶点的个数，也称图G的阶（Order），$E=\{(u,v)|u\in V,v\in V\}$，用 $|E|$表示图 G 中边的条数

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

上图所示为一张图（Graph），元素A、B、C、D、E、F分别为图的顶点（Vertex），两个元素之间的关系（连线）成为图的边（Edge）。

上面的图可以表示为：

$G=(V,E)$
V = { A , B , C , D , E , F } V = \{A, B, C, D, E, F\} V={A,B,C,D,E,F}
$E=\{(A,B),(A,C),(A,D),(B,E),(B,F),(C,E),(D,F)\}$
图的阶数$|V|=6$
图的边的条数 $|E|=7$。

2.无向图（Undirected Graph）与有向图（Directed Graph）

（1）无向图（Undirected Graph）

若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序时，记为 $(v,w)$ 或 $(w,v)$ ，因为 $(v,w)=(w,v)$ ，其中v、w是顶点。可以说顶点 w 和顶点 v 互为邻接点。边 $(v, w) $依附于顶点 w 和 v ，或者说边 $(v,w)$ 和顶点 v 、w 相关联。

简单来说，边没有方向的图就是无向图。

上图可表示为：

$G_u=(V_u,E_u)$
V u = { A , B , C , D , E } V_u = \{A, B, C, D, E\} Vu​={A,B,C,D,E}
$E_u=\{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)\}$

（2）有向图（Directed Graph）

若 E 是有向边（也称弧（Arcs））的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 $<v,w>$ ，其中 v 、 w 是顶点， v 称为弧尾， w 称为弧头， $<v,w>$ 称为从顶点v到顶点w的弧，也称v邻接到 w ，或 w 邻接自 v 。 $<v,w>\ne <w,v>$

简单来说，边有方向的图就是有向图。

上图可表示为：
$G_d=(V_d,E_d)$
V d = { A , B , C , D , E } V_d = \{A, B, C, D, E\} Vd​={A,B,C,D,E}
E d = { < A , B > , < A , C > , < A , D > , < A , E > , < B , A > , < B , C > , < B , E > , < C , D > } E_d = \{<A, B>, <A, C>, <A, D>, <A, E>, <B, A>, <B, C>, <B, E>, <C, D>\} Ed​={<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>}

3. 简单图（Simple Graph）与多重图（Multi Graph）

（1）简单图（Simple Graph）

不存在重复边并且不存在顶点到自身的边的图称为简单图

（2）多重图（Multi Graph）

允许两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联的图多重图。

4. 顶点的度（Degree）

度（Degree）：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
入度（Indegree）：入度是有向图中以顶点 v 为终点的有向边的数目，记为ID(v)；
出度（Outdegree）：出度是有向图中以顶点 v 为起点的有向边的数目，记为OD(v)。

在有向图中，顶点 v 的度等于其入度和出度之和，即
$TD(v)=ID(v)+OD(v)$。

度在有向图和无向图中都存在，而入度和出度只存在于无向图中。

5. 描述顶点关系的几个概念

• 路径（path）：顶点 v_p 到顶点 v_q 之间的一条路径是指顶点序列 { v p , v i 1 , v i 2 , . . . , v i m − 1 , v i m , v q } \{v_p, v_{i1}, v_{i2},... ,v_{im-1},v_{im},v_q\} {vp​,vi1​,vi2​,...,vim−1​,vim​,vq​}。

• 回路（circuit）：第一个顶点和最后一个顶点相同的路径称为回路或环。

• 简单路径（Simple Path）：在路径序列中，顶点不重复出现的路径称为简单路径。

• 简单回路（Simple Circuith）：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或环（Cycle）。

• 路径长度（Path Length）：路径上边的数目。

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

• 连通（connected）：无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的

• 强连通（Strongly Connected）：有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通。

• 弱连通（Weakly Connected）：若一张有向图的边替换为无向边后，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则称原来这张有向图是弱连通。

6.连通图（Connected Graph）与强连通图（Strongly Connected Graph）

连通图（Connected Graph）：若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。
强连通图（Strongly Connected Graph）：若有向图中任何一对顶点都是强连通的，则称此图为强连通图。
弱连通图（Weakly Connected Graph）：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

7. 子图（SubGraph）与生成子图（Spanning SubGraph）

设有两个图 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$，若 $V^{\prime }$是 $V$ 的子集，且 $E^{\prime }$是 $E$ 的子集，则称 $G^{\prime }$ 是 $G$ 的子图。

若有满足$V(G^{\prime })=V(G)$的子图 $G^{\prime }$，则称其为 G 的生成子图。

8. 连通分量（Connected Component）

连通分量（Connected Component）：无向图中的极大连通子图称为连通分量。
强连通分量（Strongly Connected Component）：有向图中极大强连通子图称为强连通分量。
弱连通分量（Weakly Connected Component）：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。一个有向图的基图的极大连通子图称为弱连通分量。

连通分量

强连通分量

8.生成树（Spanning Tree）和生成森林（Spanning Forest）

如果连通图的一个子图是一棵包含的所有顶点的树，则该子图称为G的生成树(SpanningTree)。

生成树的结果不是唯一的，如图展示的是一张连通图的两个生成树。

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林（Spanning Forest）。

如图展示的是一张非连通图的生成森林。

9.边的权值（Weight）

• 边的权（Weight）：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
• 带权图（Weighted Graph）：边上带有权值的图称为带权图，也称网（NetWork）。
• 带权路径长度（Weighted Path Length）：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

二、图的存储

1.邻接矩阵存储

2.邻接表存储

3.十字链表存储（存储有向图）

4.邻接多重表存储（存储无向图）