图是最为复杂的数据结构。如果数据元素之间存在一对多或者多对多的关系，那么这种数据的组织结构就叫作图结构。
图的基本概念
图的定义
图Graph是由顶点（图中的节点被称为图的顶点）的非空有限集合V与边的集合E（顶点之间的关系）构成的。
若图G中的每一条边都没有方向，则称G为无向图。
若图G中的每一条边都有方向，则称G为有向图。
图的常见术语
顶点的度
依附于某顶点v的边数称为该顶点的度，记作TD(v)。
有向图中还有入度和出度的概念。
- 有向图的顶点v的入度指以顶点v的终点的弧的数目，记作
ID(v)。 - 顶点v的出度指以v为起始点的弧的数目，记作
OD(v)。
入度和出度的和为有向图顶点v的度，即TD(v)=ID(v)+OD(v)。
路径
见图知意。就是顶点之间的连线。
路径上所包含的边数m-1为该路径的长度。如图中V1到V3之间的路径长度为2。
有向图的路径是有向的，其中每一条边均为有向边。
带权图的路径长度为所有边上的权值之和。
子图
对于图G=(V,E)和图G'=(V',E')，若存在V'∈V，E'∈E，则称图G'为G的子图。
上图中：
G'中顶点的集合V'={v0,v1,v2,v4}是G中顶点集合V={v0,v1,v2,v3,v4}的子集。G'中边的集合E'={(v0,v4),v1,v2}也是G中边的集合E={(v0,v1),(v1,v2),(v2,v3),(v3,v4),(v4,v0)}的子集。
所以G'是G的一个子图。
连通图
若无向图的两个顶点之间有路径，则称这两个顶点之间是连通的。
如果无向图中任意两个顶点都是连通的，则称该无向图为连通图，否则该无向图为非连通图。
无向图的最大连通子图为该图的连通分量。连通图的连通分量只有一个，就是它本身。
从图的遍历角度来说，从连通图的任意顶点出发进行深度优先搜索或广度优先搜索，都可以访问到图中的所有顶点。
对于非连通图，则需要分别从不同连通分量中的顶点出发进行搜索，才能访问到图中的所有顶点。
对于有向图，若图中一对顶点之间有双向的路径，则称这两点之间是连通的。
若有向图中任意两点之间都是连通的，则称该有向图是强连通的。
有向图中最大连通子图被称为有向图的强连通分量。强连通的有向图只有一个强连通分量，就是它本身。
非强连通的有向图可能存在多个强连通分量，也可能不存在强连通分量。
- 左图为强连通图。
- 中间不是强连通图，但有一个强连通分量。
- 右图既不是强连通图，也没有强连通分量。
生成树
若图G为包含n个顶点的连通图，则G中包含其全部n个顶点的一个极小连通子图被称为G的生成树。G的生成树一定包含且仅包含G的n-1条边。
左图为图G，右图为G的生成树。
如果连通图是一个网络，图的边上带权，则其生成树中的边也带权。那么称该网络中所有带权生成树中权值总和最小的生成树为最小生成树，也叫作最小代价生成树。
图的存储形式
常见的图的存储形式有两种：
- 邻接矩阵存储
- 邻接表存储
一般情况下，稠密图多采用邻接矩阵存储，稀疏图多采用邻接表存储。
邻接矩阵存储法也称数组存储法，其核心思想是利用两个数组来存储一个图。
- 一个是一维数组，用来存放图中顶点的数据。
- 一个是二维数组，用来表示顶点之间的相互关系。
具体来讲。一个具有n个顶点的图G可定义一个数组vertex[n]，将该图顶点的数据信息分别存放在对应的数组元素上，也就是将顶点$v_i$的数据信息存放在vertex[i]中。
再定义一个数组A[n][n]，称为邻接矩阵，用来存放顶点之间的关系信息。
$A[i][j]=\begin{cases}
1\quad当顶点i与顶点j之间有边时\
0\quad当顶点i与顶点j之间无边时
\end{cases}$
通过这样一个邻接矩阵就可以把一个图中顶点之间的关系表现出来。
有了邻接矩阵我们就可以对数组vertex中的顶点元素进行操作。
如果通过邻接矩阵表示具有n个顶点的图，则需要占用n×n个存储单元保存顶点之间边的信息，所以空间复杂度为$O(n^2)$。
因此邻接矩阵更适合存储稠密图，如果存储稀疏图，则会造成空间浪费。
邻接表存储法是一种顺序存储的与链式分配相结合的存储方法。
由链表和顺序数组组成。其中链表存放边的信息，数组存放顶点的信息。
具体来讲，要为图中每个顶点分别建立一个链表，具有n个顶点的图的邻接表包含n个链表。
每个链表前面设置一个头节点，称为顶点节点。
- 顶点域
data用来存放顶点的数据信息 - 指针域
firstArc指向依附于该顶点的第1条边。
通常将一个图的**n**个顶点节点放到一个数组中进行管理，并用该数组的下标表示顶点在图中的位置。
链表的节点被称为边节点，表示依附于对应的顶点的一条边。
adjvex域存放该边的另一端点在顶点数组的下标。weight存放边的权重，对于无权重的图，此项可以忽略。next是指针域，指向下一个边节点。最后一个边节点的next域为null
邻接表由一个顶点数组和一组边链表组成。
顶点数组中存放图的顶点信息，链表中存放图的边信息。
在邻接表中，第$i$个单链表中的节点表示依附于顶点$v_i$的边。
所谓依附于顶点$v_i$的边，对于有向图来说，就是以顶点$v_i$为尾的边。即从$v_i$指向其他顶点的边。
对于无向图来说。就是与该顶点连接的边 。
所以在无向图的邻接表中，顶点$v_i$的度恰好是第$i$个链表中边节点的数量。
在有向图的邻接表中，第$i$个链表中边节点的数量只是顶点$v_i$的出度。
邻接表的实现
邻接表的定义
前面已经说过，邻接表包含由顶点节点构成的数组以及依附于每个顶点的边链表。
所以要实现邻接表，需要定义这两部分。
先定义图的顶点类VNode，邻接表中顶点数组的元素就是该类的对象。
// 顶点类型（数组中的结点类型）
class VNode {
int data; // 图中顶点中的数据信息，这里是整型（也可定义为其他类型）
ArcNode firstarc; // 指向单链表，即指向该顶点的第一条边
}
VNode类中包含两个成员变量：
data中存放的是该顶点的数据信息，这里定义的data是int类型，在实际应用中也可以定义为其他类型。firstArc是指向单链表的指针，它是ArcNode类的变量，ArcNode类就是邻接表中单链表的节点类型。
再定义边节点类ArcNode，也就是邻接表中单链表的节点类型。
// 边结点类型（单链表中的结点类型）
class ArcNode {
int adjvex; // 该边指向的顶点在数组中的位置（数组下标）
ArcNode next; // 指向下一条边的指针
ArcNode(int adjvex) {
this.adjvex = adjvex;
}
}
ArcNode类中也包含两个成员变量：
adjvex中保存的是该链表节点代表的边指向的另一端顶点在数组中的下标。next域中保存的是下一个链表节点的地址，也就是指向下一个边节点。
基于以上两个类，就可以定义邻接表存储的图类型。
public class MyGraph {
private VNode[] vNodes; // VNode类型的数组，用来存放图中的全部的顶点
}
MyGraph类为我们定义的图类型。在该类中包含了一个VNode类的数组，用来存放每个顶点的信息，包括顶点中的数据和该顶点指向边链表的指针。
图的创建
下面介绍如何用createGraph()函数创建一个图。
先定义好图中顶点之间的连接关系，再使用邻接表结构创建图。
图中包含5个顶点，顶点中的数据分别是2、9、6、3、7，不妨设顶点$v_0=2$,$v_1=9$,$v_2=6$,$v_3=3$,$v_4=7$。如果用邻接表存储该图，则邻接表的结构如下图所示：
创建邻接表的过程分为两步：
- 创建图的顶点数组
创建顶点之间的边，也就是创建每个顶点节点指向的单链表
public void createGraph(int v[], int arc[]) { // 创建一个图，图中的顶点元素由数组v[]指定，边由数组arc[]指定 vNodes = new VNode[v.length]; // 创建包含v.length个顶点数组 // 首先初始化图中的顶点 for (int i = 0; i < v.length; i++) { vNodes[i] = new VNode(); vNodes[i].data = v[i]; // 给第i个顶点赋值 vNodes[i].firstarc = null; // 初始化firstarc为null } // 创建邻接表中的链表（建立顶点之间边的关系） int index = 0; ArcNode p, q = null; for (int i = 0; i < v.length; i++) { // 内层的for循环负责为顶点vNodes[i]创建存放边信息的链表 for (; index < arc.length && arc[index] != -1; index++) { p = new ArcNode(arc[index]); if (vNodes[i].firstarc == null) { firstarc = p; // 顶点vNodes[i]的第一条边 } else { q.next = p; // 将依附于vNodes[i]的其他边连接到链表中 } q = p; } index++; } }函数
public void createGraph()的作用是创建一个图的邻接表结构。该函数有两个参数int v[], int arc[]。v[]是一个数组，里面存储图中每个顶点的元素，因为图的顶点数据为整型元素，所以这里是一个整型数组。如果顶点中的数据是其他类型，则数组v[]的类型也要随之改变。arc[]是一个整型数组，该数组的作用是定义依附于每个顶点的边信息。
如果我们要创建上图中的邻接表，那么在调用函数时，参数v[]就要指定为{2,9,6,3,7}，参数arc[]要指定为{1,2,-1,1,0,-1,0,4,-1,3}。数组arc[]中的-1为分割符，用来分割不同的顶点。数组中的非-1元素为顶点单链表节点中的数据，也就是顶点数组的下标。
通过执行函数createGraph()可以在内存中创建一个图的邻接表结构，该邻接表的顶点数组就是MyGraph类的vNodes成员变量。
图的遍历
图的遍历方式有两种，一种是深度优先搜索遍历，一种是广度优先搜素遍历。
深度优先搜索遍历
深度优先搜索遍历从图中的一个顶点出发，先访问该顶点，再依次从该顶点的未被访问过的邻接点开始继续深度优先搜索遍历。
所以深度优先搜索遍历具有递归结构，是一种基于递归思想的遍历算法。
// 深度优先搜索一个连通图，从vNodes[vIndex]结点开始遍历
private void DFS(int vIndex) {
visit(vIndex); // 访问顶点vNodes[vIndex],这里就是打印出该顶点中的数据信息
visited[vIndex] = 1; // 将顶点vIndex对应的访问标记置1
int w = getFirstAdj(vIndex); // 找到顶点v的第一个邻接点，如果无邻接点，返回-1，如果有则返回该顶点在vNodes中的下标
while (w != -1) {
if (visited[w] == 0) {
// 该顶点未被访问
DFS(w); // 递归地进行深度优先搜索*/
}
w = getNextAdj(vIndex, w); // 找到顶点v的下一个邻接点，如果无邻接点，返回-1，如果有则返回该顶点在vNodes中的下标
}
}
private void visit(int vIndex) {
System.out.print(vNodes[vIndex].data + " ");
}
// 对图G=(V,E)进行深度优先搜索的主算法
public void travelByDFS() {
visited = new int[vNodes.length]; // 创建数组visited[]，用于记录遍历图时已访问的结点
for (int i = 0; i < vNodes.length; i++) {
visited[i] = 0; // 将标记数组初始化为0
}
for (int i = 0; i < vNodes.length; i++) {
if (visited[i] == 0) {
// 若有顶点未被访问，从该顶点开始继续深度优先搜索(访问不同的连同分量)
DFS(i);
}
}
}
为了遍历图中每一个顶点，需要在代码中设置一个访问标志数组visited[]，该数组可以定义为MyGraph类的一个成员变量。数组visited[]在主算法函数travelByDFS()中被初始化，其大小要跟图中顶点的数量，即邻接表数组vNode[]的长度一致。
在遍历过程中约定visited[vIndex] == 1，表示图中第vIndex个顶点已经被访问过。visited[vIndex] == 0则表示该顶点未被访问。
在遍历图时，首先要调用主算法函数travelByDFS()。该函数会将visited[]数组中的每一个元素都初始化为0，表示初始时任何顶点 都没有被访问。然后从第1个没有被访问的顶点开始，即满足visited[i]=0的顶点，调用递归函数DFS(i)，深度优先搜索遍历整个图。
函数DFS(i)是一个递归函数。在函数DFS(int vIndex)中首先通过visit()函数访问当前顶点vIndex，然后将顶点vIndex对应的访问标记visited[vIndex]置为1，表明该顶点已被访问。
通过getFirstAdj()函数获取当前顶点vIndex的第1个邻接点，将其在vNodes[]中的下标赋值给w，如果顶点vIndex无邻接点，则返回-1.
然后通过一个循环从顶点vIndex的第1个邻接点w开始深度优先搜索。搜索完vIndex的第1个邻接点，调用函数getNextAdj()得到vIndex的下一个邻接点，并将其在vNodes中的下标赋值给w，然后从w开始深度优先搜索，直到getNextAdj()返回-1，表明顶点vIndex的所有邻接点都已被访问。
根据图结构的具体形式给出函数
getFirstAdj()及getNextAdj()的实现：
// 返回第一邻接点在数组中的下标
private int getFirstAdj(int vIndex) {
if (vNodes[vIndex].firstarc != null) {
return vNodes[vIndex].firstarc.adjvex;
}
return -1;
}
// 返回顶点v的下一个邻接点在数组中的下标
private int getNextAdj(int vIndex, int w) {
ArcNode p;
p = vNodes[vIndex].firstarc;
while (p != null) {
if (p.adjvex == w && p.next != null) {
return p.next.adjvex;
}
p = p.next;
}
return -1;
}
我们不能仅仅通过一个递归函数DFS()来遍历整个图，是因为DFS()只能遍历到从起始顶点v开始所有与v相通的顶点，即一个连通分量。
如果改图是不连通的，那么仅通过函数DFS()无法遍历所有顶点。所以我们需要对DFS()
外层函数travelByDFS()会通过一个循环操作找出visited[i]==0的顶点，然后调用DFS()从该顶点开始深度优先搜索遍历，这样就可以保证访问到图中的每一个连通分量，从而实现图的遍历。
广度优先搜索遍历
广度优先搜索遍历的思想与深度优先搜索遍历的思想不同，它是一种按层次遍历的算法。
它的遍历顺序是先访问顶点$v_0$，再访问离顶点$v_0$最近的顶点$v_1$、$v_n$，然后再访问离顶点$v_1$、$v_n$最近的顶点，这样就形成以$v_0$为中心，一层一层向外扩展的访问路径。
void BFS(int vIndex) {
visit(vIndex); // 访问顶点vNodes[vIndex],这里就是打印出该顶点中的数据信息
visited[vIndex] = 1; // 将顶点v对应的访问标记置1
MyQueue queue = new MyQueue(); // 创建一个队列用来存放图顶点对象
queue.enQueue(vIndex); // 顶点下标vIndex入队列
while (queue.getQueueLength() != 0) {
int v = queue.deQueue(); // 将队头元素取出
int w = getFirstAdj(v); // 找到顶点v的第一个邻接点，如果无邻接点，返回-1
while (w != -1) {
if (visited[w] == 0) {
visit(w);
queue.enQueue(w); /* 顶点w入队列 */
visited[w] = 1;
}
w = getNextAdj(v, w); /* 找到顶点v的下一个邻接点，如果无邻接点返回-1 */
}
}
}
/* 对图G=(V,E)进行广度优先搜索的主算法 */
void travelByBFS() {
visited = new int[vNodes.length]; // 创建数组visited[]，用于记录遍历图时已访问的结点
for (int i = 0; i < vNodes.length; i++) {
visited[i] = 0; // 将标记数组初始化为0
}
for (int i = 0; i < vNodes.length; i++) {
if (visited[i] == 0) {
// 若有顶点未被访问，从该顶点开始继续深度优先搜索(访问不同的连同分量)
BFS(i);
}
}
}
在遍历图时，首先要调用主算法函数travelByBFS()。该函数将visited[]数组中的每个元素都初始化为0，表示初始时任何顶点都没有被访问。然后从第1个没有被访问的顶点开始，即满足visited[i]==0条件的顶点，调用函数BFS(i)，从该顶点开始广度优先搜索遍历整个图。
函数BFS()实现了图的广度优先搜索遍历，可以遍历一个连通图。函数BFS(vIndex)先访问顶点vIndex，再将顶点vIndex对应的访问标记visited[vIndex]置为1，表明该顶点已被访问，然后创建一个队列queue，并将该顶点在顶点数组vNodes[]中的下表vIndex入队列。这里我们使用的是之前我们实现的MyQueue类。
接下来进入二重循环，实现以下操作：
- 从队列中取出头元素
v。 - 调用函数
getFirstAdj(v)得到该顶点的第1个邻接点在vNodes[]中的下标，并赋值给w。 - 如果顶点
w还未被访问，即visited[vIndex] == 0，则调用函数visit()访问顶点w，并将w入队列，对应的访问标记visited[w]置为1。 - 调用函数
getNextAdj(v,w)得到顶点v的下一个邻接点w，如果存在邻接点，则跳回到步骤3。如果不存在邻接点，则跳回到步骤1。
循环执行上述操作，直到队列为queue为空，表明该连通图中的每一个顶点都已被访问。这里的函数getFirstAdj()和getNextAdj()的实现与深度优先搜索遍历一样，因为构成该图的邻接表数据结构是相同的。
| 出队列元素 | 入队列元素 | 队列状态 |
|---|---|---|
| - | 0 | 0 |
| 0 | 1、2、3 | 1、2、3 |
| 1 | - | 2、3 |
| 2 | - | 3 |
| 3 | 4 | 4 |
| 4 | - | - |
需要注意的是，入队列和出队列的元素都是顶点在数组**vNode[]**中的下标，并不是顶点中的数据元素。
有些顶点在出队列后并没有继续访问它的邻接点并将邻接点入队列，这是因为它的邻接点在之前已经被访问过了。
只有那些没有被访问过的邻接点才会被访问并进入队列。
为什么不能直接顺序访问顶点数组
vNodes[]中的每一个元素？
这里所讲的遍历是按照图的逻辑结构，也就是图中每个顶点之间的关系，对一个图的各个连通分量进行遍历。
在图的遍历过程中，可能存在一些额外操作，比如计算带权有向图的边权之和，计算两顶点之间路径的距离等。
这些操作都必须依赖图的遍历来实现，仅靠访问图中的每个顶点是无法实现的。
案例分析-迷宫问题
如图为一个环形迷宫，S为迷宫的入口，E为迷宫的出口，请给出该迷宫的走法。
迷宫问题有很多解法，将迷宫抽象为图结构，再利用图的遍历来求解是一种比较常用的方法。
图的深度优先搜索遍历是一种试探性地遍历算法。例如，对于相邻的顶点A、B，顶点B已被访问，接下来访问顶点A，如果顶点A没有与之相邻且未被访问的顶点，就要回退到前一个顶点B，然后沿着下一个分支继续探索。这个过程与走迷宫的过程十分相似，当在迷宫中“碰壁”时，就相当于走到了图中的顶点A，此时就要回退到之前的分岔路口，然后沿着另外的路径继续寻找迷宫出口。
我们可以将迷宫的中的起点、分岔路口、阻挡通路的墙壁都抽象为图中的顶点，将迷宫中的路径抽象为图中的边，那么一个迷宫就相当于一个无向图，我们要做的就是在这个无向图中寻找从顶点S到顶点E的通路。
我们这里说的是通路，而非路径，通路商允许包含重复的顶点。
我们可以借助图的深度优先搜索遍历算法解决这个问题，但是要在深度优先搜索遍历的基础上对算法加以改造，以适应题目的要求。
图的遍历要求将图中每个顶点都不重不漏地访问一次，例如在遍历上图中的图结构时。当访问到顶点B时，因为B已没有未被访问过的相邻顶点，所以算法会退回到顶点A，但是并不访问顶点A，因为A已被访问过了，然后访问下一个与A相邻的顶点D，这样顶点A不会被重复访问。但是在走迷宫算法中，A这个顶点仍然要被加入到结果序列，只有这样才能构成一个完整通路，也就是：A-B-A-D。
在迷宫中寻找一条从S到E的通路，并不意味着要把图中的每个顶点都访问一遍。这跟现实中走迷宫是一样的，只要找到迷宫的出口即可，无需走完迷宫的每一条路和每一个分岔路口。这也是走迷宫问题和图的遍历最本质的区别。
将迷宫抽象成无向图之后，无向图只包含一个联通分量，所以在解决走迷宫问题时，不需要考虑无向图有多个连通分量的情况。
import java.util.ArrayList;
public class Maze {
private VNode[] vNodes;
int[] visited;
ArrayList<Character> res;
// 创建一个迷宫
public void createMaze(char v[], int arc[]) {
vNodes = new VNode[v.length];
res = new ArrayList<Character>();
for (int i = 0; i < v.length; i++) {
vNodes[i] = new VNode();
vNodes[i].data = v[i];
vNodes[i].firstarc = null;
}
int index = 0;
ArcNode p, q = null;
for (int i = 0; i < v.length; i++) {
for (; index < arc.length && arc[index] != -1; index++) {
p = new ArcNode(arc[index]);
if (vNodes[i].firstarc == null) {
vNodes[i].firstarc = p;
} else {
q.next = p;
}
q = p;
}
index++;
}
}
// 寻找走迷宫的一条通路
public void findPath() {
visited = new int[vNodes.length];
for (int i = 0; i < vNodes.length; i++) {
visited[i] = 0;
}
res = new ArrayList<Character>();
for (int i = 0; i < vNodes.length; i++) {
if (vNodes[i].data == 'S') {
DFS(i); // 从迷宫入口进入
}
}
}
private boolean DFS(int vIndex) {
if (visit(vIndex)) {
return true;
}
visited[vIndex] = 1;
int w = getFirstAdj(vIndex);
while (w != -1) {
if (visited[w] == 0) {
if (DFS(w)) {
return true;
}
res.add(vNodes[vIndex].data);
}
w = getNextAdj(vIndex, w);
}
return false;
}
private boolean visit(int vIndex) {
res.add(vNodes[vIndex].data);
if (vNodes[vIndex].data == 'E') {
System.out.println(res);
return true;
}
return false;
}
private int getFirstAdj(int vIndex) {
if (vNodes[vIndex].firstarc != null) {
return vNodes[vIndex].firstarc.adjvex;
}
return -1;
}
private int getNextAdj(int vIndex, int w) {
ArcNode p;
p = vNodes[vIndex].firstarc;
while (p != null) {
if (p.adjvex == w && p.next != null) {
return p.next.adjvex;
}
p = p.next;
}
return -1;
}
public static void main(String[] args) {
char v[] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'S' };
int arc[] = {
1, 3, 7, -1, 0, -1, 4, -1, 0, 4, 5, -1, 2, 3, -1, 3, -1, 7, -1, 0, 6, -1 };
Maze maze = new Maze();
maze.createMaze(v, arc);
System.out.println();
maze.findPath();
}
}
// 边结点类型（单链表中的结点类型）
class ArcNode {
int adjvex; // 该边指向的顶点在数组中的位置（数组下标）
ArcNode next; // 指向下一条边的指针
ArcNode(int adjvex) {
this.adjvex = adjvex;
}
}
// 顶点类型（数组中的结点类型）
class VNode {
char data; // 图中顶点中的数据信息，这里是整型（也可定义为其他类型）
ArcNode firstarc; // 指向单链表，即指向该顶点的第一条边
}
上述代码中定义了一个迷宫类Maze，它包含三个成员变量：数组vNodes用来保存图结构的顶点信息，数组visited用来记录vNodes中对应顶点是否已被访问过，数组res用来保存最终的结果序列。
函数createMaze()的作用是创建一个迷宫，也就是创建一个图结构。该函数与前面介绍的createGraph函数类似，这里不再赘述。
函数findPath()的作用是寻找一条走迷宫的通路。该函数跟前面介绍过的函数travelByDFS()类似，都是以图中的一个顶点为起点，并调用函数DFS()深度优先搜索图结构。
但是由于该图结构本身只有一个连通分量，所以在函数findPath()中只需调用一次**DFS(0)**。
函数DFS的作用是深度优先搜索图结构，但是与传统的遍历算法略有不同，在这个DFS()函数中调用的visit()函数不仅会访问顶点信息，还会判断当前访问的顶点是否是迷宫的出口E，如果当前访问的顶点是E，则将结果序列res中记录下来的行走路径打印出来，然后返回true，说明已经找到了一条通路，可以提前结束遍历。
另外在DFS()函数中，当递归调用了函数DFS()并返回后，又回退到第vIndex个顶点，此时需要将顶点信息vNodes[index].data加入结果序列。
