图是若干节点(vertices)和若干连接这些节点的边(edge)组成的集合。
节点的名字不是十分重要，我们用 0 到 V-1 的数字来标记 V 个节点，用v-w表示节点v和节点w相连的一条边，w-v表示同一条边。
以上关于无向图的定义允许出现下面两种情况：1. 自循环：即一条边连接着一个节点和它自己。 2.平行边：两条边连接着相同的一对节点。
总览（Glossary）
关于图有很多概念或定义：
- 如果有一条边连接着两个节点，那么我们就说这两个节点是互相邻近的(adjacent)。
- 一个节点的度(degree)指的是与这个节点相接的边的条数。
- 一个子图(subgraph)是一个图中所有边的子集(包括与之相关的节点)组成的图。
- 一条路径(path)是一条节点序列，用边连接起来。
- 一个简单路径(simple path)是一条不含重复节点的路径。
- 一个环(cycle)是一条路径，其中至少有两个节点相同。
- 一个简单环(simple cycle)是一条没有重复节点（除了必须的首尾两个节点外）和重复边的环。
- 路径和环的长度(length)是它们所含边的条数。
- 如果存在一条路径包含两个节点，就说两个节点是连通的(connected)。
我们通常处理的都是简单路径和简单环，所以，在下面的叙述中，将去掉“简单”二字，但指的是简单环和简单路径。
————————————————————————
如果对每一个节点，都存在一条路径到其他的任何节点，我们就说这个图是连通的。一个不不连通的图有若干个最大连通子图（称为连通部分——Connected Components）组成，它们之间是没有路径的。
————————————————————————
如果将节点看成实际中的物体，而将边看成绳子。那么一个图是连通的就表示：如果我们拎起其中一个节点，整个图还是一整块；而如果图是不连通，我们就只能拎起它的一部分。
- 一个无环图(acyclic)是一个不含任何环的图。
- 一棵树(tree)就是一个连通的无向图。
- 一个互相分离的树的集合称为森林(forest)。
- 一个连通图的生成树(spanning tree)是一个包含这个图所有节点的子图，同时也是一棵树。
- 一个不连通图的生成森林(spanning tree)是一个生成树的集合，每个生成树与这个图的每个最大连通子图对应。
一个有 V 个节点的图 G 是一棵树当且仅当它满足下列五个条件中的任意一条：
- G 有 V-1 条边，不含有环
- G 有 V-1 条边，而且是连通的
- G 是连通的，但是去掉任意一条边都会使它变得不连通
- G 是无环图，但是添加任意一条边都会产生一个环
- G 中的每一对节点间只有一条路径相连
一个图的密度指的是连通节点对的边的比例。一个稀疏图(sparse)只有少数边显示出来，而一个紧密图只有少数边没有显示出来。如下图所示：
一个二分图(bipartite graph)的所有节点可以分为两类，使每条边连接的两个节点属于不同类。
图的数据结构
API
public class Graph
Graph(int V) # create a V-vertex graph with no edges
Graph(In in) # read a graph from input stream in
int V() # numbers of vertices
int E() # numbers of edges
void addEdge(int v, int w) # add edge v-w to this graph
Iterable<Integer> adj(int v) # vertices adjacent to v
String toString() # string representation
选择数据结构
下一步，我们需要确定一种数据结构来实现图。这种数据结构需要满足下面两个基本要求：
- 必须有空间(space)来适应在实际应用中可能会遇到的各种图。
- 基于这种数据结构开发的API必须是高效的(time-efficient)。
考虑以下三种选项：
- 一个邻接矩阵。我们维持一个V×V的布尔矩阵，如果节点v和节点w连通，那么(v,w)位置的值就为1，否则为0。这种数据结构不满足第一条要求，因为在实际应用中，常常遇到上百万节点的图，而需要V2个布尔值显然是不允许的。
- 一个存储边的数组。我们定义一个表示边的类（包含两个int），然后用数组存储所有的边。这样的数据结构不满足第二条要求。要实现adj()方法，就需要遍历所有的边，这显然是不可取的。
- 一个邻接链表的数组。我们维持一个长为V的数组，数组下标代表节点编号，每个数组元素是一个链表。这样的数据结构满足上面的两个要求。
除了性能方面的考虑，有时候，实际应用的需要也限制了我们选择数据结构。比如，允许平行边的话，就不能使用邻接矩阵，因为它无法表示平行边。
邻接链表数据结构
我们使用Bag数据结构的链表表示来实现邻接链表，因为邻接链表中元素的相对位置是没有意义的，只与它们插入的先后顺序有关。不同的邻接链表数组可能表示同一个图。这样的数据结构可以达到下面的性能特点：
- 空间使用量与V+E成正比
- 添加一条边的时间复杂度为O(1)
遍历节点v的邻近节点所用时间与v的度成正比
public class Graph { private final int V; private int E; private Bag<Integer>[] adj; public Graph(int V) { this.V = V; this.E = 0; adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag<Integer>() } public Graph(In in) { this(in.readInt()); int E = in.readInt(); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); addEdge(v,w); } } public int V() { return V; } public int E() { return E; } public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); E++; } public Iterable<Integer> adj(int v) { return adj[v]; } }
当然，我们需要考虑其他操作：比如添加/删除节点，这时候需要使用符号表来替代数组；删除边/检查图中是否包含某个边，这时候可以用集合(SET)来代替Bag(链表实现)。在下面的实现中，为了算法的简洁易懂，我们依然使用Bag。
| underlying data structure |
space | add edge v-w | check whether w is adjacent to v |
iterate through vertices adjacent to v |
|---|---|---|---|---|
| list of edges | E | 1 | E | E |
| adjacency matrix | V2 | 1 | 1 | V |
| adjacency lists | E+V | 1 | degree(V) | degree(V) |
| adjacency sets | E+V | logV | logV | logV+ degree(V) |
深度优先搜索（Depth-First Search）
迷宫搜索
搜索一个图和搜索一个迷宫是类似的，用迷宫的道路代替图中的边，用路口代替图中的节点，可以使问题更加形象一些。
一种搜索迷宫的方法称为 Tremaux Exploration，它的步骤是：
- 选择一条未走过的路径，边走边展开一条绳子
- 当你第一次经过道路或路口时，标记它们
- 当你遇到一个已标记的路口时，沿原路返回，边走边收起这段路绳子
- 当遇到一个路口，与这个路口相连所有的道路都已走过时，搜索结束
DFS
深度优先搜索模仿了这个迷宫搜索方法，甚至更简洁一些：
- 把标记一个节点为已经过的
递归地经过与这个节点相连的所有未标记的节点
public class DepthFirstSearch { private boolean[] marked; private int count; public DepthFirstSearch(Graph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } private void dfs(Graph G, int v) { marked[v] = true; count++; for (int w : G.adj(v)) if (!marked[w]) dfs(G, w); } public boolean marked(int w) { return marked[w]; } public int count() { return count; } }
————————————————————————
DFS 标记出所有与某个给定节点连通的所有节点， 耗费的时间与这些节点的度的总和成正比
————————————————————————
单向路径（One-way passages）
DFS（或者 Tremaux）刚好将每条路径的两个方向都走了一遍。具体来说，在Tremaux搜索中，我们要么是第一次经过某路径，要么是遇到了一个已标记的路口所以从这条路径原路返回；在DFS中，我们要么是在递归调用中第一次遇到边v-w（如果w未被标记），要么是跳过这条边（如果w已被标记）。
DFS产生的路径很大程度上依赖于整个图的表示方式（邻接链表中的元素顺序），具体的搜索过程如下图所示：
找出路径
利用DFS，我们可以解决这样的问题：给定一个图和图中的一个节点s，能否找出一条路径从s到指定的一个节点v。目前，我们先考虑找到任意一条路径，后面再考虑找到满足特定条件的路径。
public class DepthFirstPaths
{
private boolean[] marked; // Has dfs() been called for this vertex?
private int[] edgeTo; // last vertex on known path to this vertex
private final int s; // source
public DepthFirstPaths(Graph G, int s)
{
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}
private void dfs(Graph G, int v)
{
marked[v] = true;
for(int w: G.adj(v))
if (!marked[w])
{
edgeTo[w] = v;
dfs(G, w);
}
}
public boolean hasPathTo(int v)
{ return marked[v]; }
public Iterable<Integer> pathTo(int v)
{
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<Integer>();
for(int x = v; x != s; x = edgeTo(x))
path.push(x);
path.push(s);
return path;
}
}
————————————————————————
DFS 允许我们在正比于路径长度的时间内向客户端代码返回从一个给定的节点到任意一个节点的路径
————————————————————————
广度优先搜索（Breadth-First Search)
我们常常需要解决下面这种问题：给定一个图和图中的一个节点s，能否找到从s到某一节点v的最短路径。解决这个问题最经典的办法称为广度优先搜索（BFS）。
原理
如果继续比作迷宫搜索，使用广度优先搜素就类似于有一队无穷多的人在搜索一个迷宫，每一队在身后展开一根绳子。当遇到路口时，一条队伍分成多条队伍；当两支或两支以上队伍碰面时，合并为一条队伍（使用最先到达队伍的绳子继续）。
对于BFS，我们使用队列来进行实现，具体步骤如下：
- 从队列中取出下一个节点v，并标记它（表示已经过）
把v的邻接节点中所有未标记的节点放入队列
public class BreadthFirstPaths { private boolean[] marked; private int[] edgeTo; private final int s; public BreadthFirstPaths(Graph G, int s) { marked = new boolean[G.V()]; edgeTo = new int[G.V()]; this.s = s; bfs(G, s); } private void bfs(Graph G, int s) { Queue<Integer> queue = new Queue<Integer>(); marked[s] = true; queue.enqueue(s); while(!q.isEmpty()) { int v = queue.dequeue(); for (int w : G.adj(v)) if (!marked[w]) { edgeTo[w] = v; marked[w] = true; queue.enqueue(w); } } } public boolean hasPathTo(int v) { return marked[v]; } public Iterable<Integer> pathTo(int v) // Omitted, Same as for DFS }
————————————————————————
对于任意一个从s可到达的节点v，BFS计算出了一条最短的从s到v的路径。在最坏的情况下，BFS消耗的时间与 V+E 成正比。
————————————————————————
DFS和BFS的联系
DFS和BFS都可以总结为下面一个过程：我们把源节点放入某种数据结构中，然后执行以下步骤直到数据结构为空：
- 从数据结构中取出下一个节点v，并标记它
- 把所有与v邻近的未标记节点放入数据结构中
对DFS来说，这样的数据结构是LIFO的栈，取出的是最新加入的元素；对BFS来说，这样的数据结构是FIFO的队列，取出的最早加入的元素。
DFS总是寻找最远的节点，只有当遇到死胡同是才会选择稍近一些的节点；BFS则正相反，只有把最近的节点都经过了才会向远处探索。
所以，DFS生成的路径更长更曲折；BFS生成的路径更短更直接。
连通部分（Connected Component）
我们判断两个节点是否连通，需要每次进行dfs查找，但我们对具体路径并不关心，只在乎两个节点是否连通。在下面的CC类中，我们先对整张图进行处理，存储下每个节点所处连通部分的信息，这样，每次查询的时间复杂度都为常数级别。
API
public class CC
CC(Graph G) // 构造函数
boolean connected(int v, int w) // 节点v和节点w是否连通？
int count() // 连通部分的数量
int id(int v) // 节点v所在连通部分的序号
实现
CC类添加两个属性，分别是id[]数组（长度等于图中节点数）和count整型变量。
public CC(Graph G)
{
marked = new boolean[G.V()];
id = new int[G.V()];
for (int s = 0; s < G.V(); s++)
if (!marked[s])
{
dfs(G,s);
count++;
}
}
在构造函数中，每当dfs递归标记完一个连通部分的所有节点时，count增1。
private void dfs(Graph G, int v)
{
marked[v] = true;
id[v] = count;
for (int w : G.adj(v))
if (!marked[w])
dfs(G,w);
}
与之前的dfs稍有不同的是，每次除了标记节点以外，还将count存进节点所对应的id数组中的位置，来标记节点所处的连通部分的序号。
public boolean connected(int v, int w)
{ return id[v] == id[w]; }
————————————————————————
DFS使用正比于$V+E$的时间和空间开销来进行预处理（构造函数），以支持复杂度为常数的连通查询操作。
————————————————————————
Union-Find VS DFS-based CC
理论上说，DFS比Union-Find快，因为它保证了连通查询的复杂度为常数级别，而Union-Find并没有这样的保证。但实际中，这点差别是很微小的，Union-Find甚至更快，因为它不需要建立起对整个图的完整表示。最重要的差别是，Union-Find是一个在线算法，而DFS需要先处理整个图。
回路/环的检测
我们在属性里添加一个boolean变量hasCycle，用来表示图中是否含有环；并对dfs方法做细微修改，来进行环的探测。
private void dfs(Graph G, int v, int u)
{
marked[v] = true;
for (int w : G.adj(v))
if (!marked[v])
dfs(G, w, v);
else if (w != u) hasCycle = true;
}
基本原理是：深度优先查找到最深处后，递归地回溯比较。如果某个节点的邻近节点已被标记，但却不是它的前驱（上一层被查找的节点），那就说明这个图含有环。下面是一个例子：
两色染色问题（图是否是二分的）
我们在属性中添加一个boolean数组color，用来记录节点的颜色；并添加一个boolean变量，表示这个图是否是二分的，初始默认为True。
private void dfs(Graph G, int v)
{
marked[v] = true;
for (int w : G.adj(v))
if (!marked[w])
{
color[w] = !color[v];
dfs(G, w);
}
else if (color[w] == color[v]) isTwoColorable = false;
}
我们在递归前加一条语句，给未染色的节点染上与它相邻节点不同的色；在递归后添加一句判断，如果相邻的两个节点颜色相同，则说明这个图不是二分的。
符号图（Symbol Graph）
符号图的节点可能是字符串等，而不是简单的整数索引。我们定义构造符号图的输入格式如下：
- 节点名为字符串
- 有一个特定的分隔符来隔开节点名（例如空格或分号）
- 每一行代表一个边的集合，第一个节点与后面的每一个节点相连
API
public class SymbolGraph
SymbolGraph(String filename, String delim)
boolean contains(String key)
int index(String key)
String name(int v)
Graph G() //返回生成的图
一个符号表包含以下数据结构：
- 一个符号表st，包含字符串类型的键(节点名称)，和整数类型的值(索引)。
- 一个字符串数组keys[]用作倒置索引，使能通过整数索引查找出节点名称
- 一个用节点名称指向的整数索引建立起来的图
分离度的计算
利用广度优先算法