今天我们就来学习“数据结构入门系列”中最后一个数据结构“图”。图是很常用的数据结构，比如计算机网络、社交网络、谷歌地图都需要用到此数据结构，掌握图的知识可以完善我们的数据结构知识体系，也能帮助我们解决算法中更为复杂的问题。
简单来说，图是一种用来表示相连数据的数据结构，类似我们的社交网络，图中有很多的节点，每个节点代表一个数据，每个节点可以和其他节点相连。其中每个节点叫做顶点（vertice），连接顶点之间的线叫做相连线（edge）。下图就是一个用来表示社交网络的图数据结构：
在此图中，我们含有5个顶点和6条相连线，每个顶点包含了人名，而连接线代表相连人名之间是朋友关系。如果我们要更正式地表示图，那么图就可以用一对（V，E）集合来表示，其中V是一堆顶点的集合，而E是一堆相连线的集合，请看下图：
在此图中：V = {a, b, c, d, e}，E = {ab, ac, bd, cd, de}
上面提到的图是无向图，而常见的图有以下三种：
- 无向图（Undirected Graph）：在无向图中，每个顶点和其他顶点通过相连线连接。
- 有向图（Directed Graph）：有向图中的相连线是有方向的。
- 权重图（Weighted Graph）：在权重图中，每条相连线有各自的权重。
下图是有向图：
此图可以用来表示用户之间相互关注的情况，如果Mark指向Alice，则代表Mark关注了Alice。下图是权重图：
此图可以用来表示两个好友之间的亲密程度，数值越高代表越亲密。可见不同的图可以用来表示不同的关系，而有向图是最常见的图，我们接下来就用Java实现有向图。
有向图的实现（Directed Graph）
有向图的实现有两种，一种是用矩阵（Matrix）的形式来实现，另一种是用链表（List）的形式来实现。
如果我们使用矩阵来实现有向图，来看一个例子：
每行代表相应的顶点，如果M[i][j] = 1，那么就代表顶点 i 连向 j，如果是0，则表达顶点间没有联系。用矩阵的方式来实现图的优势很明显，我们可以很快地判断两个顶点之间是否相连，可是用矩阵实现的空间复杂度很高，我们需要O(V^2)来记录所有的数据，不管顶点之间是否有相连线。为了解决空间复杂度的问题，我们可以使用链表的方式来实现图：
在链表实现中，我们实际上使用了储存链表的数组来表示图，图的左侧用数组来实现，代表我们的所有顶点，而每个顶点含有一个链表，链表上储存了该顶点指向的顶点。以下是Java的实现代码：
public class ListGraph {
ArrayList<ArrayList<Integer>> graphs;
public ListGraph(int v) {
graphs = new ArrayList<>(v);
for (int i = 0; i < v; i++) {
graphs.add(new ArrayList<>());
}
}
public void addEdge(int start, int end) {
graphs.get(start).add(end);
}
public void removeEdge(int start, int end) {
graphs.get(start).remove((Integer)end);
}
}有向图的实现很简单，我们直接使用Java中的ArrayList来代表左侧的数组和数组上的链表，其中两个重要方法addEdge和removeEdge直接使用ArrayList自带的方法add和remove即可。使用链表的形式来实现图，我们可以只记录有用的数据，省下了很多空间。了解完图的链表实现，我们来了解一下如何遍历图：
图的遍历（Graph Traversal）
遍历图有两种常见的方式，一种是深度优先搜索（Depth-first Search），另一种是宽度优先搜索（Breadth-first search）。首先我们来学习深度优先搜索：
深度优先搜索（Depth-First Search）
图的深度优先和树的前序遍历（Pre-order Traversal）有点类似。在深度优先遍历中，我们假设初始状态所有顶点都没被访问，然后从每一顶点v出发，先访问该顶点，然后依次从它的各个未被访问的邻接点出发，深度优先遍历图，直到图中所有和v相通的顶点都被访问到。若遍历完后，还有其他顶点没被访问到，则另选一个未被访问的顶点作为起始点，重复上述过程，直到所有顶点都被访问完为止。
下面以“有向图”为例，来对深度优先搜索进行演示：
对于上面的图，我们从顶点A开始搜索：
以下是具体的遍历步骤：
- 访问A
- 访问B（在访问A之后，接下来应该访问的是A出发的另一个顶点，既顶点B）
- 访问C（在访问B之后，接下来访问的是从B出发的另一个顶点，既C，E，F。在此图中，我们按照字母排序顺序访问，因此先访问C。）
- 访问E（接下来访问与C连接的另一个顶点E。）
- 访问D（接下来访问从E出发的顶点B和D，因为B已被访问过，所以访问顶点D。）
- 访问F（接下来回溯“访问A的另一个连接顶点F”）
- 访问G
因此访问顺序是：A -> B -> C -> E -> D -> F -> G。
在图的深度优先搜索中，我们尽可能先遍历一个顶点可以达到的最深处，其中可能会出现的问题就是会有循环出现，所以我们需要一个数组来记录哪些节点已经被访问过。以下是Java的回溯实现代码：
public class GraphTraversal {
ListGraph graph;
boolean[] visited;
public GraphTraversal(ListGraph listGraph) {
this.graph = listGraph;
visited = new boolean[listGraph.graphs.size()];
}
public void DFSTraversal(int v) {
if(visited[v]) return;
visited[v] = true;
System.out.print(v + " -> ");
Iterator<Integer> neighbors = graph.graphs.get(v).listIterator();
while (neighbors.hasNext()) {
int nextNode = neighbors.next();
if (!visited[nextNode]) {
DFSTraversal(nextNode);
}
}
}
public void DFS() {
for (int i = 0; i < graph.graphs.size(); i++) {
if (!visited[i]) {
DFSTraversal(i);
}
}
}
}广度优先搜索（Breadth-First Search)
广度优先搜索算法也叫做“宽度优先搜索”或“横向优先搜索”，其方法是从图中的某一顶点v出发，在访问了v之后依次访问v的各个没有访问到的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，使得先被访问的顶点的邻接点先与后被访问顶点的邻接点被访问，直到图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问到的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。
下面以“有向图”为例，对广度优先搜索进行演示：
以下是访问步骤：
- 访问A
- 访问B
- 依次访问C，E，F（在B被访问之后，接下来访问B的邻接点，既C，E，F。）
- 依次访问D，G（在访问完C，E，F之后，再依次访问他们出发的另一个顶点。还是按照C，E，F的顺序访问，C的已经全部访问过了，那么就只剩下E，E；先访问E的邻接点D，再访问F的邻接点G。
访问顺序是：A -> B -> C -> E -> F -> D -> G。
在实现中，我们需要使用queue来储存接下来要遍历的顶点（每层的邻接点），在Java中我们通过Deque来实现Queue，以下是代码：
public void BFSTraversal(int v) {
Deque<Integer> queue = new ArrayDeque<>();
visited[v] = true;
queue.offerFirst(v);
while (queue.size() != 0) {
Integer cur = queue.pollFirst();
System.out.print(cur + " -> ");
Iterator<Integer> neighbors = graph.graphs.get(cur).listIterator();
while (neighbors.hasNext()) {
int nextNode = neighbors.next();
if (!visited[nextNode]) {
visited[nextNode] = true;
queue.offerLast(nextNode);
}
}
}
}
public void BFS() {
for (int i = 0; i < graph.graphs.size(); i++) {
if (!visited[i]) {
BFSTraversal(i);
}
}
}以上就是图的两种遍历方法：深度优先遍历和广度优先遍历。简单来说，深度优先遍历就是选择一条路径走到头再回来，而广度深度优先就是将最近的邻接点先访问完，再向更远的顶点延伸。
Leetcode相关题目和源代码
Leetcode题目
- Island Perimeter (463)
- Number of Islands (200)
- Max Area of Island (695)
- Number of Closed Islands (1254)
- Rotting Oranges (994)
- Sliding Puzzle (773)
GitHub源代码