第四章 图
4.1 无向图
定义：图是由一组顶点和一组能够将两个顶点相连的边组成的。
边(edge)仅仅是两个顶点(vertex)之间的连接。我们称之为「无向图」。
在绘制一幅图的时候，用圆圈表示顶点，用连接两个顶点的线段表示边，就能直观的看出图的结构。但是图的定义和绘出的图像是无关的。例如下面两幅图：
image-20200725171924988.png
这两幅图片是相同的。
4.1.1术语
在研究图之前，有一些术语需要掌握，如下
image-20200725202211009.png
4.1.2表示无向图的数据配型
首先我们定义一个无向图的基本API
image-20200725202109421.png
4.1.2.1 图的几种表示方法
- 邻接矩阵。我们可以使用一个V*V的布尔矩阵。当顶点v和顶点w之间有边相连接的时候，定义v行w列的元素值为true，否则为false。
- 边的数组。我们可以使用一个Edge类，包含两个int实例变量。
- 邻接表数组。我们可以使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表。如下图所示
image-20200725202653283.png
这里我们主要使用邻接表的数据结构
Graph数据类型
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 i = 0; i < v; i++) {
adj[i]=new Bag<Integer>(); //将所有链表初始化为空
}
}
/**
* 顶点数目
* @return V
*/
public int getV() {
return V;
}
/**
* 得到边数目
* @return Edge
*/
public int getE() {
return E;
}
/**
* 添加一条边
* @param v 顶点v
* @param w 顶点w
*/
public void addEdge(int v,int w){
adj[v].add(w); //将w添加到v的链表中
adj[w].add(v); //将v添加到w的链表中
E++;
}
public Iterable<Integer> adj(int v){
return adj[v];
}
}
这个Graph的实现使用了一个由顶点索引的整形链表数组。每条边都会出现两次，即当存在一条连接v与w的边的时候，w会出现在v的链表中，v也会出现在w的链表中.
另一些常用的图处理代码
1.计算顶点v的度数
public static int degree(Graph G,int v){
int degree=0;
for (int w:G.adj(v)) degree++;
return degree;
}
2.计算所有顶点最大的度数
public static int maxDegree(Graph G){
int max=0;
for (int i = 0; i < G.V; i++) {
if(degree(G,i)>max) max=degree(G,i);
}
return max;
}
3.图的邻接表的字符串表示
public String toString(){
String s=V+" vertices,"+E+" edges\n";
for (int v = 0; v < V; v++) {
s+=v+": ";
for (int w:this.adj(v)) {
s+=w+" ";
}
s+="\n";
}
return s;
}
4.计算自环
public static int numberOfSelfLoops(Graph g){
int count=0;
for (int v = 0; v < g.V; v++) {
for(int w:g.adj(v))
if(w==v)
count++;
}
return count/2; //每条边被记过两次
}
另外，背包Bag的数组结构如下，这是一个只进不出的数据结构
class Bag<Item> implements Iterable<Item>{
private Node first; //链表的首节点
private class Node{
Item item; //节点的值
Node next; //下一项
}
public void add(Item item){
//添加一个Node节点
Node oldNode=first;
first=new Node();
first.item=item;
first.next=oldNode;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
//使Bag可以迭代
private Node current=first;
@Override
public boolean hasNext() {
return current!=null;
}
@Override
public Item next() {
Item item=current.item;
current=current.next;
return item;
}
}
}
4.1.3深度优先搜索
在讨论深度优先搜索之前，我们先来讨论迷宫问题。
在一个由各种通道和路口组成的迷宫中找到出路，要搜索迷宫中的所有通道，我们需要：
选择一条没有标记过的通道，在你走过的路上铺上一条绳子
标记所有你第一次路过的路口和通道
当来到一个标记过的路口的时候(用绳子)返回上个路口
当回退到的路口没有可走的通道的时候继续回退
887365228-587b6f2b6781a_articlex.png
4028153888-587b6f3fba7c5_articlex.gif
我们继续看图的搜索算法，搜索一个图，只需要用一个递归方法来遍历所有顶点。在访问一个顶点的时候：
将它标记为已经访问；
-
递归的访问它的所有没有被标记过的邻居顶点
这种访问被称为「深度优先搜索(DFS)」
深度优先搜索的每条边会被访问两次，而且在第二次会发现这个顶点已经被访问过，下面是深度优先搜索的访问轨迹
image-20200725210216247.png
深度优先搜索的应用可以有
- 连通性 给定一幅图，判定两个点是否连通？或者图中有多少个连通子图？
- 单点路径 给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出这条路径”
下面是深度优先搜索的代码：
/**
* 深度优先搜索
*/
public class DepthFirstSearch {
private boolean[] marked;
private int count;
/**
*
* @param G G是给的图
* @param s s是起点的边
*/
public DepthFirstSearch(Graph G,int s){
marked=new boolean[G.getV()];
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 getCount() {
return count;
}
}
4.1.4寻找路径
算法基于深度优先搜索实现Paths。添加了一个实例变量edgeTo[ ]整形数组。这个数组可以找到从每个连通s的顶点回到s的路径，为了做到这一点，当v-w第一次访问任意w的时候，将edgeTo[w]设置为v来记住这条路径。换句话说，v-w是s到w路径上最后一条已知的边。这样，搜索的结果就是一颗以起点为根节点的树。
image-20200725210216247.png
[图片上传失败...(image-32020e-1595745527938)]
下面是使用深度优先搜索查找图中的路径代码：
/**
* 深度优先搜索寻找路径
*/
public class DepthFirstPaths {
private boolean[] marked;//这个顶点是否调用过dfs
private int[] edgeTo;//从起点到一个顶点的已知路径上的最后一个顶点
private final int s;//起点
public DepthFirstPaths(Graph G, int s) {
this.s = s;
marked = new boolean[G.getV()];
edgeTo = new int[G.getV()];
dfs(G, s);
}
private void dfs(Graph g, int w) {
marked[w] = true;
for (int v : g.adj(w)) {
if (!marked[v]) {
edgeTo[v] = w;
dfs(g, v);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> stack = new Stack<>();
for (int x = v; v != s; x = edgeTo[x]) {
stack.push(x);
}
stack.push(s);
return stack;
}
}
学完了深度优先搜索，及时的应用才是最有效的，这里选取两道LeetCode的题目
4.1.5广度优先搜索
深度优先搜索得到的路径不仅取决于图的结构，还取决于图的表示和递归调用的性质。
我们经常对一下的问题感兴趣：
单点最短路径。给定一幅图和一个起点s，是否“从s到给定目的顶点v是否存在一条路径，如果存在，找到其中最短的那条路径”
解决这个问题的方法称为，广度优先搜索。
深度优先搜索好像是一个人在走迷宫，广度优先搜索则好像一组人在一起朝各个方向走这个迷宫。当两个探险者相遇的时候，会合二为一。
image-20200726084337876.png
实现
广度优先搜索使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。现将起点加入队列，然后重复以下步骤
- 取队列中的下一个顶点v并且标记它。
- 将与v相邻的所有未被标记过的顶点加入队列
下面是广度优先搜索的代码：
public class BreadthFirstPaths {
private boolean[] marked;//顶点是否被访问过
private int[] edgeTo; //到达该顶点的已知路径的最后一个顶点
private final int s; //起点
public BreadthFirstPaths(Graph g, int s) {
this.s = s;
marked = new boolean[g.getV()];
edgeTo = new int[g.getV()];
bfs(g, s);
}
private void bfs(Graph g, int s) {
marked[s] = true; //标记起点
Queue<Integer> queue = new ArrayDeque<>();
queue.add(s); //加入队列
while (!queue.isEmpty()) {
int v = queue.remove(); //从队列中删去下一顶点
for (int w : g.adj(v)) {
if (!marked[w]) { //..对于每个未被标记的顶点
edgeTo[w] = v; //保存最短路径的最后一条边
marked[w] = true; //标记它
queue.add(w); //加入队列中
}
}
}
}
public boolean hasPathTo(int w) {
return marked[w];
}
public Iterable<Integer> pathTo(int w) {
if (!hasPathTo(w)) return null;
Stack<Integer> stack = new Stack<>();
for (int i = w; i != s; i = edgeTo[w]) {
stack.push(i);
}
stack.push(s);
return stack;
}
}
同样，不做题是不可以掌握的，选一道LeetCode题目
4.1.6联通分量
深度优先搜索的一个直接应用就是找出一幅图片的所有联通分量，我们定义一组API
image-20200726085143221.png
实现
/**
* 联通分量
*/
public class CC {
private boolean[] marked;
private int[] id; //顶点所在的联通分量的标识符
private int count;//联通分量数目
public CC(Graph g) {
marked=new boolean[g.getV()];
id=new int[g.getV()];
for (int v = 0; v < g.getV(); v++) {
if(!marked[v]){
dfs(g,v);
count++;
}
}
}
private void dfs(Graph g,int v){
id[v]=count;
marked[v]=true;
for (int w:g.adj(v)){
if(!marked[w]){
dfs(g,w);
}
}
}
public boolean connected(int v,int w){
return id[v]==id[w];
}
}
我们最后使用「深度优先搜索」回答两个问题
检测环
我们需要检测图中是否有环，假设没有自环，并且两个顶点之间没有平行边
/*
检测图是不是无环图
*/
public class Cycle {
private boolean[] marked;
private boolean hasCycle;
public Cycle(Graph graph) {
marked=new boolean[graph.getV()];
for (int s = 0; s < graph.getV(); s++) {
if(!marked[s])
dfs(graph,s,s);
}
}
private void dfs(Graph g,int v,int u){
marked[v]=true;
for(int w:g.adj(v)){
if(!marked[w])
dfs(g,w,v);
else if(w!=u) hasCycle=true;
}
}
}
比较抽象，1->2->3->1的无向图
image-20200726090550367.png
双色问题
能够用两种颜色将图的所有顶点超色，让任意一条边的两个端口的颜色都不相同吗？
这个问题等价于：这是一幅二分图吗？
/**
* 二分图
*/
public class TwoColor {
private boolean[] marked;
private boolean[] color;
private boolean isTwoColorable=true;
public TwoColor(Graph g){
marked=new boolean[g.getV()];
color=new boolean[g.getV()];
for (int s = 0; s < g.getV(); s++) {
if(!marked[s])
dfs(g,s);
}
}
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;
}
}
}
