在线性表中，元素间只有简单的前后关系，一个元素有且仅有一个直接前驱和一个直接后继。在树结构中，元素间有一对多的层级关系，一个元素最多只有一个双亲，但可以有多个孩子。
相较于线性表和树，图结构显得要更加的复杂，它用来表示元素间的多对多关系。就像人际关系一样，张三可以有很多朋友，李四也可以有很多朋友，且张三的朋友也很可能是李四的朋友。
如下就是一个典型的图结构。
1. 数学知识回顾
在了解图结构前，有必要先回顾一下高中的数学知识。
1. ∈指「属于」，表示元素和集合的关系。
假设集合A={a,b,c}，则元素a∈A，读作“a属于A”。反之，元素d∉A，读作“d不属于A”。
2. 集合间的关系。
对于两个集合A与B，如果集合A中任意一个元素都属于B，则集合A是集合B的子集，记作A⊆B（或B⊇A），读作“A含于B”（或“B包含A”）。当A不是B的子集时，记作 A⊈B（或B⊉A）。
例如：A={1,2}，B={1,2,3}，则A⊆B。
真子集：若A⊆B、且A≠B，则称A是B的真子集，记作 A_⫋_B。
空集：不含任何元素的集合，记作 Ø。
3. 求和符号∑。
∑符号表示求和，读音为sigma。
其中i表示下界，n表示上界，k从i开始取数，一直取到n，进行求和。
2. 图的定义
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图由顶点（Vertex）和边（Edge）组成，线性表中没有元素时称为「空表」，树中没有结点时称为「空树」，图不一样，不存在「空图」，V是顶点的有穷非空集合，这意味着图中至少包含一个顶点。
在图中，任意两个顶点都可能有关系，顶点间的逻辑关系叫作「边」（Edge），边集可以是空的。
1. 无向图和有向图
若顶点A到B之间的边没有方向，则称这条边为「无向边」，用无序偶对(A,B)表示，如果图中所有的边都是无向边，则称该图为「无向图」。
若顶点A到B之间的边有方向，则称这条边为「有向边」，也称为「弧」，用有序偶对<A,B>表示，A称为「弧尾」，B称为「弧头」。如果图中所有的边都是有向边，则称该图为「有向图」。
无向边用“()”表示，有向边用“<>”表示。
2. 简单图
在图中，若不存在顶点到其自身的边、且同一条边不重复出现，则称这样的图为「简单图」。
很明显，以下两种都不是简单图。
3. 完全图
若图中任意两个顶点之间都存在边，则称该图为「完全图」。另外根据有向图和无向图的划分，完全图又细分为「有向完全图」和「无向完全图」。
特征：含有n个顶点的无向完全图，具有n(n-1)/2条边。含有n个顶点的有向完全图，具有n(n-1)条边。
4. 稀疏图和稠密图
有很少条边或弧的图称为「稀疏图」，反之，有很多条边或弧的图称为「稠密图」。一个图是稀疏还是稠密是相对而言的，没有一个明确规定。
5. 权(Weight)和网(Network)
若图中的边或弧具有与其相关的数字，这个数字叫作「权」，权可以表示顶点间的距离或耗费。这种带权的图也被称作「网」。
如下代表中国四个一线城市距离的网，图中的权就代表了城市间的距离。
6. 子图
假设有两个图，G=(V,E)，G=(V,E)，如果V⊆V且E⊆E，则称图G是图G的「子图」。
7. 邻接点和度
假设有无向图G=(V,E)，如果边(A,B)∈E，则称顶点A和B互为「邻接点」(Adjacent)。
顶点A相关联的边的数量称作顶点的「度」(Degree)，记为TD(A)。
对于有向图G=(V,E)，如果弧<A,B>∈E，则称顶点A邻接到顶点B，顶点B邻接至顶点A。以顶点A为头的弧的数量称为A的「入度」，记为ID(A)。以顶点A为尾的弧的数量称为A的「出度」，记为OD(A)。顶点A的度 = 入度+出度。
8. 路径和回路
假设有无向图G=(V,E)，从顶点A到顶点B的「路径」是一个顶点序列。两个顶点间存在多条路径，如下列举了顶点B到顶点D的四种路径。
如果G是有向图，则路径也是有向的。
路径的长度就是路径上的边或弧的数量。
第一个顶点到最后一个顶点相同的路径称为「回路」，也叫作「环」。序列中顶点不重复出现的路径称作「简单路径」，除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为「简单回路」或「简单环」。
如下两个图中标红的路径都形成了回路。左图除顶点B外，A、C、D都没有重复出现，因此是一个简单回路。右图中，除顶点B外，顶点C重复了，因此不是一个简单回路。
9. 连通图和连通分量
在无向图G中，若顶点A到顶点B有路径，则称A和B是连通的。如果图中任意两个顶点都是连通的，则称该图为「连通图」。
无向图中的极大连通子图称为「连通分量」，它强调：
- 首先要是子图。
- 子图要是连通的。
- 连通子图包含极大顶点数。
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
在有向图中，对于任意弧<V,V>，从V到V和从V`到V都存在路径，则称该图为「强连通图」。有向图中的极大强连通子图称作有向图的「强连通分量」。
如下左图A到D存在路径，但是D到A不存在，因此它不是强连通图。右图虽然不存在弧<A,C>，但是通过A>B>C发现A到C也是存在路径的，它是强连通图。并且，右图是左图的极大强连通子图，即右图是左图的强连通分量。
10. 生成树和森林
一个连通图的「生成树」是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成树的n-1条边。
这句话不太好理解，说白了，对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵生成树。
连通图中的生成树必须满足以下 2 个条件：
- 包含连通图中所有的顶点。
- 任意两顶点之间有且仅有一条通路。
因此，连通图具有这样的特征：顶点数=边的数量+1。
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。入度为0的顶点其实就是有向树根结点，其余顶点入度为1代表树的非根结点的双亲只有一个。
生成树是对应连通图来说，而生成森林是对应非连通图来说的。
对于一个非连通图，可分解为多个连通分量，每个连通分量又对应n(n>0)个生成树，因此，与非连通图对应的，由多棵生成树组成的集合叫作「生成森林」。
3. 图的实现
图的概念介绍完了，比较多。接下来看如何用Java语言实现图。
图的结构比较复杂，无法单纯的用数组表示。对于多重链表，如果顶点的度相差很大的话，势必又会导致大量的指针域空间浪费的问题，这里介绍图的五种表示方法。
3.1 邻接矩阵
首先，顶点和边是两种东西，应该分开存储。顶点不分大小、主次，因此用数组来存储是合适的。而边或弧表示的是顶点间的关系，一维数组无法搞定，可以使用二维数组来存储。
邻接矩阵：使用两个数组来表示图，一维数组存储顶点，二维数组存储边或弧。对于无向图，二维数组中存储0代表无边，1代表有边。对于有向图，二维数组需要区分排和列的方向，依然是存储0代表无边，1代表有边。对于网，由于边或弧有权重，因此存储一个绝对不可能的值∞代表无边，具体的权重为值进行存储。
如下所示，右侧分别使用一维数组和二维数组来表示左图。如何判断顶点间是否存在边？只需判断二维数组arr[i][j]是否为1即可。如何统计顶点的度？只需要求二维数组中第i行或列的和。
【实现】
// 邻接矩阵
public class MatrixGraph<E> {
private E[] vertex;
private int[][] edges;
public MatrixGraph(E[] vertex, int[][] edges) {
this.vertex = vertex;
this.edges = edges;
}
public void show() {
System.out.println("顶点的集合:");
StringJoiner joiner = new StringJoiner(",", "[", "]");
for (E e : vertex) {
joiner.add(e.toString());
}
System.out.println(joiner.toString());
System.out.println("定点的度:");
for (int i = 0; i < vertex.length; i++) {
int degree = 0;
for (int j = 0; j < edges[i].length; j++) {
degree += edges[i][j];
}
System.out.println(vertex[i] + ":" + degree);
}
System.out.println("边的集合:");
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j < edges[i].length; j++) {
if (edges[i][j] == 1) {
System.out.println("(" + vertex[i] + "," + vertex[j] + ")");
}
}
}
}
public static void main(String[] args) {
new MatrixGraph<Character>(new Character[]{'A', 'B', 'C', 'D'},
new int[][]{
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
}).show();
}
}
控制台输出：
顶点的集合:
[A,B,C,D]
定点的度:
A:3
B:2
C:3
D:2
边的集合:
(A,B)
(A,C)
(A,D)
(B,A)
(B,C)
(C,A)
(C,B)
(C,D)
(D,A)
(D,C)
【优点】
代码实现简单，效率高。
【缺点】
对于N个顶点的图，邻接矩阵的表示需要长度为N的一维数组和N*N的二维数组，对于稀疏图来说，会浪费大量的内存空间。
3.2 邻接表
为了解决邻接矩阵浪费空间的问题，于是就有了「邻接表」表示法。
邻接表：依然使用数组保存顶点，使用链表来保存边的信息，同一个顶点的多条边通过一个单向链表来连接。
要判断顶点间是否有边，遍历链表即可。统计顶点的度，遍历链表即可。
对于无向图，结构如下，如果要表示网，在边中增加Weight属性即可。
如下，使用邻接表法来表示左图。
对于有向图就比较棘手了，一般采用以顶点为弧尾来来存储链表，这样统计顶点的出度很方便，如果要统计顶点的入度，就必须遍历整个图。还有一种解决方式是，同时建立一个以顶点为弧头的逆邻接表，这样统计入度很方便，但是要维护两份链表。
【实现】(无向图)
// 邻接表
public class AdjacencyListGraph<E> {
private int size;
private Vertex<E>[] table;
public AdjacencyListGraph() {
this.table = new Vertex[16];
}
// 添加顶点
public Vertex<E> add(E e) {
Vertex<E> vertex = new Vertex<>(e, null);
table[size++] = vertex;
return vertex;
}
public void show() {
System.out.println("顶点的集合:");
StringJoiner joiner = new StringJoiner(",", "[", "]");
for (int i = 0; i < size; i++) {
joiner.add(table[i].data.toString());
}
System.out.println(joiner.toString());
System.out.println("定点的度:");
for (int i = 0; i < size; i++) {
int degree = 0;
Edge edge = table[i].firstEdge;
while (edge != null) {
degree++;
edge = edge.next;
}
System.out.println(table[i].data + ":" + degree);
}
System.out.println("边的集合:");
for (int i = 0; i < size; i++) {
Vertex<E> vertex = table[i];
Edge edge = vertex.firstEdge;
while (edge != null) {
System.out.println("(" + vertex.data + "," + table[edge.index].data + ")");
edge = edge.next;
}
}
}
// 添加边
public void addEdge(Vertex<E> vertex, int index) {
Edge newEdge = new Edge(index, null);
Edge edge = vertex.firstEdge;
if (edge == null) {
vertex.firstEdge = newEdge;
} else {
// 尾插
while (edge.next != null) {
edge = edge.next;
}
edge.next = newEdge;
}
}
public static class Vertex<E> {
private E data;
private Edge firstEdge;
public Vertex(E data, Edge firstEdge) {
this.data = data;
this.firstEdge = firstEdge;
}
}
private static class Edge {
private int index;
private Edge next;
public Edge(int index, Edge next) {
this.index = index;
this.next = next;
}
}
public static void main(String[] args) {
AdjacencyListGraph<String> graph = new AdjacencyListGraph<>();
// 设置顶点
Vertex<String> A = graph.add("A");
Vertex<String> B = graph.add("B");
Vertex<String> C = graph.add("C");
Vertex<String> D = graph.add("D");
// 设置边
graph.addEdge(A, 1);
graph.addEdge(A, 2);
graph.addEdge(A, 3);
graph.addEdge(B, 0);
graph.addEdge(B, 2);
graph.addEdge(C, 0);
graph.addEdge(C, 1);
graph.addEdge(C, 3);
graph.addEdge(D, 0);
graph.addEdge(D, 2);
graph.show();
}
}
【优点】
解决了稀疏图浪费空间的问题。
【缺点】
对于有向图不太友好。
3.3 十字链表
邻接表对于有向图来说，是有缺陷的。邻接表关心出度，要了解入度就必须遍历整个图。逆邻接表关心入度，要了解出度就必须遍历整个图。有没有可能将邻接表和逆邻接表结合起来呢？有，这就是「十字链表」。
十字链表：使用数组来存储顶点，双重链表来存储有向边，结构如下：Data存储数据，firstIn入边表头指针，firstOut出边表头指针。tailVex弧尾下标，headVex弧头下标，headLink下一个入边表指针，tailLink下一个出边表指针。
如下，使用十字链表法表示左边的图：
【实现】
// 十字链表法
public class OrthogonalListGraph<E> {
private int size;
private Vertex<E>[] table;
public OrthogonalListGraph() {
this.table = new Vertex[16];
}
// 添加顶点
public Vertex<E> addVertex(E e) {
return table[size++] = new Vertex<>(e, null, null);
}
// 添加入边
public void addInEdge(Vertex<E> vertex, int tailIndex, int headIndex) {
Edge inEdge = vertex.firstIn;
if (inEdge == null) {
vertex.firstIn = new Edge(tailIndex, headIndex, null, null);
} else {
while (inEdge.headLink != null) {
inEdge = inEdge.headLink;
}
inEdge.headLink = new Edge(tailIndex, headIndex, null, null);
}
}
// 添加出边
public void addOutEdge(Vertex<E> vertex, int tailIndex, int headIndex) {
Edge outEdge = vertex.firstOut;
if (outEdge == null) {
vertex.firstOut = new Edge(tailIndex, headIndex, null, null);
} else {
while (outEdge.tailLink != null) {
outEdge = outEdge.tailLink;
}
outEdge.tailLink = new Edge(tailIndex, headIndex, null, null);
}
}
public void show() {
System.out.println("顶点的集合:");
StringJoiner joiner = new StringJoiner(",", "[", "]");
for (int i = 0; i < size; i++) {
joiner.add(table[i].data.toString());
}
System.out.println(joiner.toString());
System.out.println("顶点的出度:");
for (int i = 0; i < size; i++) {
int degree = 0;
Edge edge = table[i].firstOut;
while (edge != null) {
degree++;
edge = edge.tailLink;
}
System.out.println(table[i].data + ":" + degree);
}
System.out.println("顶点的入度:");
for (int i = 0; i < size; i++) {
int degree = 0;
Edge edge = table[i].firstIn;
while (edge != null) {
degree++;
edge = edge.headLink;
}
System.out.println(table[i].data + ":" + degree);
}
System.out.println("边的集合:");
Set<String> set = new HashSet<>();
for (int i = 0; i < size; i++) {
Vertex<E> vertex = table[i];
Edge edge = vertex.firstIn;
while (edge != null) {
set.add(String.format("<%s,%s>", table[edge.tailIndex].data, table[edge.headIndex].data));
edge = edge.headLink;
}
edge = vertex.firstOut;
while (edge != null) {
set.add(String.format("<%s,%s>", table[edge.tailIndex].data, table[edge.headIndex].data));
edge = edge.tailLink;
}
}
set.stream().forEach(System.out::println);
}
private static class Vertex<E> {
private E data;
private Edge firstIn;//入边头指针
private Edge firstOut;//出边头指针
public Vertex(E data, Edge firstIn, Edge firstOut) {
this.data = data;
this.firstIn = firstIn;
this.firstOut = firstOut;
}
}
private static class Edge {
private int tailIndex;//弧尾顶点下标
private int headIndex;//弧头顶点下标
private Edge headLink;//入边表指针
private Edge tailLink;//出边表指针
public Edge(int tailIndex, int headIndex, Edge headLink, Edge tailLink) {
this.tailIndex = tailIndex;
this.headIndex = headIndex;
this.headLink = headLink;
this.tailLink = tailLink;
}
}
public static void main(String[] args) {
OrthogonalListGraph<String> graph = new OrthogonalListGraph<>();
Vertex<String> A = graph.addVertex("A");
Vertex<String> B = graph.addVertex("B");
Vertex<String> C = graph.addVertex("C");
graph.addOutEdge(A, 0, 1);
graph.addOutEdge(A, 0, 2);
graph.addInEdge(B, 0, 1);
graph.addOutEdge(B, 1, 2);
graph.addInEdge(C, 0, 2);
graph.addInEdge(C, 1, 2);
graph.show();
}
}
控制台输出：
顶点的集合:
[A,B,C]
顶点的出度:
A:2
B:1
C:0
顶点的入度:
A:0
B:1
C:2
边的集合:
<A,B>
<A,C>
<B,C>
3.4 邻接多重表
对于无向图来说，邻接表关注的是顶点，要判断顶点间有没有关系，或者统计顶点的度都很方便。但是，一旦要对边进行操作，例如：删除边、标记边，就非常的麻烦。
如下，若要删除边(A,D)，需要移除右侧链表中的两个节点。
邻接多重表：顶点和边的结构如下，边中ivex和jvex分别是依附于这条边的两个顶点所在下标，ilink是指向依附于顶点ivex的下一条边，jlink指向依附于顶点jvex的下一条边。
如下所示，右侧使用邻接多重表来表示左图。
使用邻接多重表来表示图，边的操作就很容易实现了。要新增边，创建一个节点加入到链表即可。要删除边，将对应的link指针设为null即可。
3.5 边集数组
采用两个一维数组实现，一个数组存顶点信息，一个数组存边的信息。
边结构如下，begin存储边的起点下标，end存储边的终点下标，weight存储权重。
如下所示，使用边集数组来表示左侧有向图。
边集数组关注的是边的集合，适合对边依次进行处理的操作。如果要判断顶点的度就要遍历整个图了，效率并不高。
4. 总结
图是一种非常有用的数据结构，它比线性表和树要复杂的多，图的概念也非常多，不过好在有规矩可循，大可不必死记硬背。介绍图用到了高中的集合知识，顺便回顾了一下数学。介绍了图的诸多定义和概念，以及图的五种实现方式，不同的实现方式特点各不相同，需要灵活运用。