图论基础和表示
一、概念及其介绍
图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问。
图是用来对对象之间的成对关系建模的数学结构，由"节点"或"顶点"(Vertex）以及连接这些顶点的"边"（Edge）组成。
值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。下面左图是一个典型的无向图结构，右图则属于有向图。本章节介绍的图都是无向图。
图的分类：无权图和有权图，连接节点与节点的边是否有数值与之对应，有的话就是有权图，否则就是无权图。
图的连通性：
在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称 i 和 j 是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。
完全图：
完全是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
自环边：
一条边的起点终点是一个点。
平行边：
两个顶点之间存在多条边相连接。
二、适用说明
图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程，许多实际问题可以用图来表示。因此，图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时，网络有时被定义为一个图，其中属性(例如名称)之间的关系以节点和或边的形式关联起来。
三、图的表达形式
邻接矩阵：
1 表示相连接，0 表示不相连。
邻接表：
只表达和顶点相连接的顶点信息
邻接表适合表示稀疏图 (Sparse Graph)
邻接矩阵适合表示稠密图 (Dense Graph)
this
.
m
=
0
;
this
.
directed
=
directed
;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
// false为boolean型变量的默认值
g
=
new
boolean
[
n
]
[
n
]
;
// 返回节点个数
public
int
V
(
)
{
return
n
;
}
// 返回边的个数
public
int
E
(
)
{
return
m
;
}
// 向图中添加一个边
public
void
addEdge
(
int
v ,
int
w
)
{
assert
v
>=
0
&&
v
<
n
;
assert
w
>=
0
&&
w
<
n
;
if
(
hasEdge
(
v , w
)
)
return
;
g
[
v
]
[
w
]
=
true
;
if
(
!
directed
)
g
[
w
]
[
v
]
=
true
;
m
++;
// 验证图中是否有从v到w的边
boolean
hasEdge
(
int
v ,
int
w
)
{
assert
v
>=
0
&&
v
<
n
;
assert
w
>=
0
&&
w
<
n
;
return
g
[
v
]
[
w
]
;
（2）邻接表
src/runoob/graph/SparseGraph.java 文件代码：
package
runoob.graph
;
import
java.util.Vector
;
* 邻接表
public
class
SparseGraph
{
// 节点数
private
int
n
;
// 边数
private
int
m
;
// 是否为有向图
private
boolean
directed
;
// 图的具体数据
private
Vector
<
Integer
>
[
]
g
;
// 构造函数
public
SparseGraph
(
int
n ,
boolean
directed
)
{
assert
n
>=
0
;
this
.
n
=
n
;
this
.
m
=
0
;
this
.
directed
=
directed
;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g
=
(
Vector
<
Integer
>
[
]
)
new
Vector
[
n
]
;
for
(
int
i
=
0
;
i
<
n
;
i
++
)
g
[
i
]
=
new
Vector
<
Integer
>
(
)
;
// 返回节点个数
public
int
V
(
)
{
return
n
;
}
// 返回边的个数
public
int
E
(
)
{
return
m
;
}
// 向图中添加一个边
public
void
addEdge
(
int
v,
int
w
)
{
assert
v
>=
0
&&
v
<
n
;
assert
w
>=
0
&&
w
<
n
;
g
[
v
]
.
add
(
w
)
;
if
(
v
!=
w
&&
!
directed
)
g
[
w
]
.
add
(
v
)
;
m
++;
// 验证图中是否有从v到w的边
boolean
hasEdge
(
int
v ,
int
w
)
{
assert
v
>=
0
&&
v
<
n
;
assert
w
>=
0
&&
w
<
n
;
for
(
int
i
=
0
;
i
<
g
[
v
]
.
size
(
)
;
i
++
)
if
(
g
[
v
]
.
elementAt
(
i
)
==
w
)
return
true
;
return
false
;
