图的典型应用
图的种类:
无向图(简单连接),有向图(连接有方向),加权图(连接带有权值),加权有向图(连接有方向,又带有权值)
特殊的图:
- 自环,即一条边连接顶点和自身的一条边
-
2.平行边:连接同一对顶点的边
image.png
4.1.1 术语
1.两个顶点通过一条边连接,称两个顶点是相邻, 称该连接依附于这两个顶点.
2.顶点度,等于依附于该顶点的边的总数
3.子图,所有边的一个子集以及他们依附的边组成的图
4.路径
5.联通,两个顶点存在一条连接双方的路径,称两顶点是联通的.
定义:
如果从任意一个顶点都存在一条路径到达任意一个其他的顶点,称连通图;一副非连通的图有若干个联通的部分组成,他们都是极大联通子图.
定义:
树是一个无环的连通图.互不相连的树的集合组成森林.
树的重要特性,就是没有环.
图的密度:已经连接的顶点对/所有可能连接的顶点对.
稀疏图,稠密图.
无向图的API:
Graph(int v)//创建含有V个顶点但不包含边的图
Graph(In in)//从标准输入流in读入一副图
int V()
int E()
void addEdge(int v,int w)//向图中添加一条边 v-w
Iterable<Integer> adj(int v) //和v相邻的所有顶点
toString()
图的表示方法:(需要满足的要求: A.必须为可能在应用中碰到的各种类型的图预留足够的空间 B.graph的实例实现方法必须够快)
有3中思路:
1.邻接矩阵:
采用一个二维 boolean 矩阵boolean[][],按照顺序记录每第i个顶点到第i个顶点直接的连接,有连接为true,无连接false. 但是空间的耗费需要V2 ,因为百万顶点的图很常见.所以这中方法不符合A.
2.边的数组:
可以用一个Edge类 包含两个顶点,构成一条边.但是需要计算 V() ,需要遍历整个边的数量.才能找到.不满足B
3.邻接表数组:
用顶点建立一个索引列表.其中的每个元素都是该顶点相邻的顶点列表.这种数据结构能同时满足A,B要求.如下图:
4.1.2.2 邻接表的数据结构
通过采用邻接表存储,每条边都会出现两次.
如图表示.
这种Graph的表示有下面特征:
1.使用空间与V+E 成正比
2.添加一条边的时间为常数
3.遍历顶点v的相邻顶点所需时间和v的度成正比.
对于这些操作,这样的特性已经是最优的,这可以满足对图的操作需要,而且支持平行边,和自环.边的插入顺序决定了graph的邻接表的顶点的出现顺序.
4.1.3深度优先搜索
package algorithm.sortAlgorithm.Graph;
/**
* Created by leon on 18-2-9.
* 图的处理API
*/
public interface Search {
/**
* v 和s 是联通吗
*
* @param v
* @return
*/
boolean marked(int v);
/**
* 与s联通的顶点总数
*
* @return
*/
int count();
}
package algorithm.sortAlgorithm.Graph;
/**
* Created by leon on 18-2-9.
* 深度优先搜索,从起点位置,遍历他的一个没有mark的邻接顶点,递归遍历这个邻接顶点,
* 用一个mark数组标示已经遍历过的顶点.
*/
public class DeepFirstSearch implements Search {
private boolean[] marked;
private int count;
/**
* 找到与起点s联通的所有顶点
*
* @param graph
* @param s
* @return
*/
public DeepFirstSearch(Graph graph, int s) {
//创建mark数组
marked = new boolean[graph.V()];
dfs(graph, s);
}
private void dfs(Graph g, int s) {
marked[s] = true;
for (int vertex : g.adj(s)) {
if (!marked(vertex)) {
dfs(g, vertex);
}
}
}
@Override
public boolean marked(int v) {
return marked[v];
}
@Override
public int count() {
return count;
}
}
4.1.3.1 走迷宫
命题A .
深度优先搜索标记与起点联通所有顶点所需要时间和顶点的度成正比.
4.1.3.2 单项通道
连通性: 给定一幅图,回答”两个给定的顶点之间是否连通?”或者”图中有多少个连通子图”
单点路径:给定一幅图和一个起点s,回答”从s到指定的点v是否存在一条路径?如果有找出来”
4.1.4寻找路径
深度优先算法:
package algorithm.sortAlgorithm.Graph;
import java.util.Stack;
/**
* Created by leon on 18-2-9.
* 深度优先方式寻找路径,
* 需要使用两个数组存储.
* mark[] =>标记已经访问过的顶点
* edgeTo[n]=m, 表示到n顶点的最后顶点为m,这里的值为最后的连接n的顶点值.
*/
public class DeepFirstPaths implements Paths {
private boolean[] marked;
private int[] edgeTo;
private int startV;
/**
* @param g
* @param s 起始顶点
*/
public DeepFirstPaths(Graph g, int s) {
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
startV = s;
dfs(g, s);
}
/**
* 深度优先遍历
*
* @param g
* @param v
*/
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);
}
}
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
if (hasPathTo(v)) {
return null;
}
Stack<Integer> pathStack = new Stack<>();
for (int end = v; end != startV; end = edgeTo[end]) {
pathStack.push(end);
}
pathStack.push(startV);
return pathStack;
}
}
4.1.5 广度优先搜索
单点最短路径.给定一幅图和一个起点s 回答”从s到v 是否存在一条路径?如果有找出其最短的那条”解决这个问题方法 需要采用广度优先搜索.这也是许多图算法的基石.深度优先就像一个人在走迷宫,而广度优先则像一组人朝着各自方向在走迷宫,如果遇到岔路时会分裂出更多人搜索,当两个人交汇时,会合二为一(继续采用最短的路径).
广度优先遍历算法:1.取下一个顶点放到队列中;2.队列顶点出对,并取出其相邻的未标记的顶点加入队列.3.循环队列的数据.
广度优先搜索算法:采用优先遍历,增加一个marked[] 数组,marked[k]=true;表示顶点K已经标示过.结果用edgeTo[]数组表示,edgeTo[k]=N表示从根节点s到指定顶点k的最短路径上一个顶点为N;
package algorithm.algorithmbook.graph;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* 广度优先搜索
*
* @author leon
* @date 18-2-11.
*/
public class BreadthFirstPaths implements Paths {
private boolean[] marked;
private int[] edgeTo;
private final int start;
public BreadthFirstPaths(Graph graph, int vertex) {
marked = new boolean[graph.V()];
edgeTo = new int[graph.V()];
start = vertex;
bfs(graph, start);
}
/**
* 广度优先搜索算法
*
* @param graph 图
* @param v 根顶点
*/
private void bfs(Graph graph, int v) {
Queue<Integer> needTraveselQueue = new LinkedList<>();
marked[v] = true;
needTraveselQueue.offer(v);
while (!needTraveselQueue.isEmpty()) {
int popV = needTraveselQueue.poll();
if (graph.adj(popV) != null) {
for (int vertex : graph.adj(popV)) {
if (!marked[vertex]) {
//标记
marked[vertex] = true;
edgeTo[vertex] = popV;
needTraveselQueue.offer(vertex);
}
}
}
}
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
if (hasPathTo(v)) {
return null;
}
Stack<Integer> pathStack = new Stack<>();
for (int end = v; end != start; end = edgeTo[end]) {
pathStack.push(end);
}
pathStack.push(start);
return pathStack;
}
}
命题B:
对于从s到可到达的任意顶点v,广度优先搜索都能找到一条从s→v的最短路径.(这里规定顶点的邻接顶点排在前面的比后面的优先级高)
命题B续:
度优先搜索的时间最坏情况下与V+E成正比.
深度优先搜索与广度优先搜索比较:
1.深度优先不断深入图中,并在栈中保存所有的分叉顶点;广度优先像扇面一样扫描图,用一个队列保存访问过的最前段的顶点.
2.深度优先是搜索离起点更远的顶点,直到遇到死胡同才返回来访问近处的顶点;广度先访问起点附近的所有结点,只有临近的结点都访完了才向前进.
3.深度优先的曲线一般较长较曲折;广度优先的曲线较短而且直接.
4.1.6连通分量
连通分量的概念:在图中有多个连通的图组成的大图,那么小图就是大图的连通分量;要求解连通分量,其实就是深度优先遍历大图的所有未连通的顶点.
package algorithm.algorithmbook.graph;
/**
* description: 连通子图
*
* @author leon
* @date 18-2-12.
*/
public class ConectedComponet {
//记录每一个顶点属于哪一个连通区
private int[] id;
//自连通图的个数false
private int count;
private boolean[] marked;
public ConectedComponet(Graph g) {
id = new int[g.V()];
marked = new boolean[g.V()];
//对每个顶点,进行深度优先遍历==>依次对顶点的相邻顶点深度遍历.
for (int s = 0; s < g.V(); s++) {
//保证每个连通子图是之前没有被 遍历过的,
if (!marked[s]) {
dfs(g, s);
//深度优先遍历完,说明遍历过的都是统一连通子图,count+1
count++;
}
}
}
private void dfs(Graph graph, int v) {
marked[v] = true;
id[v] = count;
for (int s : graph.adj(v)) {
if (marked[s]) {
dfs(graph, s);
}
}
}
/**
* n 和 w 是否是连通的?
*
* @param n
* @param w
* @return
*/
public boolean isConnected(int n, int w) {
return id[n] == id[w];
}
/**
* 一共有几个连通图
*
* @return
*/
public int count() {
return count;
}
/**
* v属于那个连通图 (0 ~ n-1)
*
* @param v
* @return
*/
public int id(int v) {
return id[v];
}
}
命题c
深度优先搜索处理的时间和空间与V+E成正比,并且能在常数时间内处理图的连通性查询.
证明:
由代码可知每个邻接表的元素只会查询一次,一共有2E个元素(每条边有2条)
4.1.6.2 union-find 算法(动态连通性)
4.1.6.2.1 quik-find
package algorithm.algorithmbook.graph;
/**
* description: union-find 动态连通性接口
*
* @author leon
* @date 18-2-12.
*/
public interface IUnionFind extends IConnectedCompenont {
/**
* 在p q之间连接
*
* @param p
* @param q
*/
void union(int p, int q);
}
package algorithm.algorithmbook.graph;
import java.io.FileNotFoundException;
import java.io.IOException;
import algorithm.algorithmbook.StdIn;
/**
* description: 动态连通性实现
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind implements IUnionFind {
//用于记录每一个点属于那个 连通分量 ,初始化
protected int[] id;
//分量数
protected int count;
public UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
@Override
public void union(int p, int q) {
}
@Override
public boolean isConnected(int p, int q) {
return whichConnectedComponent(p) == whichConnectedComponent(q);
}
@Override
public int count() {
return count;
}
@Override
public int whichConnectedComponent(int p) {
return find(p);
}
public int find(int p) {
return 0;
}
public static void main(String[] args) {
try {
StdIn stdIn = new StdIn("tinnyUF.txt");
int num = stdIn.readInt();
UnionFind unionFind = new UnionFind(num);
while (!stdIn.isEmpty()) {
int p = stdIn.readInt();
int q = stdIn.readInt();
if (!unionFind.isConnected(p, q)) {
unionFind.union(p, q);
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException ioE) {
ioE.printStackTrace();
}
}
}
package algorithm.algorithmbook.graph;
/**
* description:实现Unionfind 的一种方法,quik-find
* <p>
* 基本思路:
* 把每个顶点属于一个分量,只要两个顶点的分量值相等,说明这两个点是连通的.
* 所有连通的点的分量值用最后一个点的分量值替换,最后得到的所有分量值id[],
* 存在多少组不相等的 说明有几个连通子图.
* <p>
* 判断find(int) 方法非常简单
* union(p,q)方法每次遍历所有的 顶点,把q最新的顶点分量值替换分量值和p相同的
* 最后得到连通的分量值都会是最后一个顶点的分量值
*
* @author leon
* @date 18-2-12.
*/
public class UnionFindQuikFind extends UnionFind {
public UnionFindQuikFind(int n) {
super(n);
}
@Override
public void union(int p, int q) {
int pv = find(p);
int qv = find(q);
//pq已经是连通了,不需要进行遍历操作
if (pv == qv) {
return;
}
//把最新的id[q] 替换 与p相连的(也就是分量和p相同的)
for (int i = 0; i < id.length; i++) {
if (find(i) == pv) {
id[i] = qv;
}
}
//每次连接后连通子图的数量-1,初始话是有count=n的
count--;
}
@Override
public int find(int p) {
return id[p];
}
}
quik-find 算法分析:
find方法显然很快.在union方法里面,时间复杂度处于O(n2)
(1)两次find()操作，访问2次数组
(2)扫描整个数组id[]，判断p和q是否在同一个连通f分量if(find(i)==pID)，访问N次数组
(3)①只有p，其余触点均不和p在同一连通分量 id[p] =qID,访问1次数组
②除了q本身，其余均和p在同一连通分量 id[i] = qID(i≠q)，访问 N-1次数组，故总的访问次数①2+N+1 = N+3②2+N+N-1 = 2N+1
4.1.6.2.2 quik-union算法
- 原理
考虑一下，为什么以上的解法会造成“牵一发而动全身”？
因为每个节点所属的组号都是单独记录，各自为政的，没有将它们以更好的方式组织起来，当涉及到修改的时候，除了逐一通知、修改，别无他法。所以现在的问题就变成了，如何将节点以更好的方式组织起来，组织的方式有很多种，但是最直观的还是将组号相同的节点组织在一起，想想所学的数据结构，什么样子的数据结构能够将一些节点给组织起来？常见的就是链表，图，树，什么的了。但是哪种结构对于查找和修改的效率最高？毫无疑问是树，因此考虑如何将节点和组的关系以树的形式表现出来。
如果不改变底层数据结构，即不改变使用数组的表示方法的话。可以采用parent-link的方式将节点组织起来。
举例而言，id[p]的值就是p节点的父节点的序号，如果p是树根的话，id[p]的值就是p，因此最后经过若干次查找，一个节点总是能够找到它的根节点，即满足id[root] = root的节点也就是组的根节点了，然后就可以使用根节点的序号来表示组号。所以在处理一个整数对的时候，将首先找到整数对中每一个节点的组号(即它们所在树的根节点的序号)，如果属于不同的组的话，就将其中一个根节点的父节点设置为另外一个根节点，相当于将一颗独立的树编程另一颗独立的树的子树。
package algorithm.algorithmbook.graph;
/**
* description: union-find 动态连通性接口
*
* @author leon
* @date 18-2-12.
*/
public interface IUnionFind extends IConnectedCompenont {
/**
* 在p q之间连接
*
* @param p
* @param q
*/
void union(int p, int q);
}
package algorithm.algorithmbook.graph;
import java.io.FileNotFoundException;
import java.io.IOException;
import algorithm.algorithmbook.StdIn;
/**
* description: 动态连通性实现
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind implements IUnionFind {
//用于记录每一个点属于那个 连通分量 ,初始化
protected int[] id;
//分量数
protected int count;
public UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
@Override
public void union(int p, int q) {
}
@Override
public boolean isConnected(int p, int q) {
return whichConnectedComponent(p) == whichConnectedComponent(q);
}
@Override
public int count() {
return count;
}
@Override
public int whichConnectedComponent(int p) {
return find(p);
}
public int find(int p) {
return 0;
}
public static void main(String[] args) {
try {
StdIn stdIn = new StdIn("tinnyUF.txt");
int num = stdIn.readInt();
UnionFind unionFind = new UnionFind(num);
while (!stdIn.isEmpty()) {
int p = stdIn.readInt();
int q = stdIn.readInt();
if (!unionFind.isConnected(p, q)) {
unionFind.union(p, q);
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException ioE) {
ioE.printStackTrace();
}
}
}
package algorithm.algorithmbook.graph;
/**
* description:这里采用的思路和quik-find 不一样.
* 考虑到quik-find 的union方法每次都要遍历整个顶点.
* 主要原因是这些点没有通过某种结构的数据结构连接起来,是一个孤立的点.
* 所以考虑采用树的结构把连通的分量连接起来,用 id[i]存储i的根节点,
* 如果两个点的根节点相同,那么他们就属于同一个连通分量
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind_QuikUnion extends UnionFind {
public UnionFind_QuikUnion(int n) {
super(n);
}
/**
* 这里的find 含义为查找p的根节点, 当id[p]==p ,说明是他的根节点
*
* @param p
* @return
*/
@Override
public int find(int p) {
//这里采用循环向上查找,直到找到p的根节点.一定能查到
while (id[p] != p) {
p = id[p];
}
return p;
}
@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
//p q的根节点不相同,把 q的根节点指派给p,形成一棵树
//使用id[pRoot]主要是找到额 pRoot的根节点,
id[pRoot] = qRoot;
count--;
}
}
Quik-union分析:
对数组元素访问:
1.最好情况下1
2.最坏情况下,整棵树是一个线性的表,需要遍历N-1次while循环,而 while循环中2次访问数组,最后一次达到根节点时不需要执行循环体.所以一共的次数为 2(N-1)+1=2N-1
基本的时间复杂度也需要 O(n2).
所以目前Quik-find 和Quik-union 的优劣程度还不是非常好区分.
4.1.6.2.3 加权quik-union算法
原理: 因为quik-union算法,在union(p,q)的时候是随意将一棵树合并到另一棵树上.
这里的大树指的是高度大小?还是指的结点数多少?
如果是小树合并到大树上,那么小树的高度+1,整棵树的高度不变.
如果大树合并到小树上,那么大树的高度+1,整棵树的高度也可能会变.
根据find(i) 方法,所要遍历查询数组的时间和树的高度有关.所以如果只允许把小树合并到大树上,则会减少整棵树的高度.从而减少遍历数组的次数.为此需要增加一个sz[] 来存储 每一个触点所在树的结点数,结点数越大说明是大树,而结点数小的则是小树.
package algorithm.algorithmbook.graph;
/**
* description:
* 加权 Quikunion算法
* 增加一个sz[i] ,表示i所在的树的总size大小.把小树合并到大树中,
* 从而保持树的构造是有规律,树的高度相对较小.从而会在后期的查找根节点
* 的时间复杂度保持到对数级别
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind_Weighted_QuikUnion extends UnionFind_QuikUnion {
//用于记录每个顶点所在树的大小,默认初始值为1
private int[] sz;
public UnionFind_Weighted_QuikUnion(int n) {
super(n);
for (int i = 0; i < n; i++) {
sz[i] = 1;
}
}
/**
* 主要的改进主要在union上面,把小树合并到大树中
*
* @param p
* @param q
*/
@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
//关键部分,进行合并了
if (sz[pRoot] > sz[qRoot]) {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
} else {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
count--;
}
}
命题H
对于N个触点,采用加权quik-union构造的森林的任意结点的深度对多为logN
对于加权quik-union算法,是一种唯一一可以解决大型实际问题的算法.处理N个触点M条链条的最多访问次数为cMlogN.
综合分析:
理论上深度优先搜索比union-find法快.
4.1.7 符号图
实际应用中通常图都是通过文件,网页定义的,使用的是字符串而非数字代替顶点,为了适应这样的应用我们必须定义拥有如下输入格式:
1 .顶点为字符串.
2.用指定的分隔符来隔开顶点
3.每一行都表示一条边的集合,每一条边都连着这一行的第一个名称表示的顶点和其他名称所表示的顶点
4.顶点树V和边数E是隐式定义的
package algorithm.algorithmbook.graph;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.HashMap;
import algorithm.algorithmbook.StdIn;
/**
* description:符号图,用index(String key) 和 name(v)将顶点和 索引连接起来
*
* @author leon
* @date 18-2-21.
*/
public class SymbolGraph {
private HashMap<String, Integer> st;//符号表-->索引
private String[] keys;//索引-->符号名
private Graph g;//图
/**
* @param fileName
* @param delim 顶点分隔符
*/
public SymbolGraph(String fileName, String delim) {
//第一次遍历,生成符号表, 以及索引数组
st = new HashMap<>();
StdIn in = null;
try {
in = new StdIn(fileName);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
try {
while (!in.isEmpty()) {
String[] a = in.readLine().split(delim);
for (int i = 0; i < a.length; i++) {
if (!st.containsKey(a[i])) {
st.put(a[i], st.size());//从 0,1,2,3...顺序计数
}
}
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
in.close();
} catch (IOException e) {
e.printStackTrace();
}
}
//创建反向索引
keys = new String[st.size()];
for (String key : st.keySet()) {
keys[st.get(key)] = key;//索引下标为st的 value
}
//第二次遍历,真正创建graph
g = new Graph(st.size());
try {
in = new StdIn(fileName);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
try {
while (!in.isEmpty()) {
String[] a = in.readLine().split(delim);
int v = st.get(a[0]);
//这里有可能一行有多个边??
for (int i = 1; i < a.length; i++) {
g.addEdge(v, st.get(a[i]));
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* key 是一个顶点吗
*
* @param key 顶点名
* @return boolean
*/
boolean contains(String key) {
return st.containsKey(key);
}
/**
* 返回key的索引
*
* @param key 顶点名
* @return 索引值
*/
int index(String key) {
return st.get(key);
}
/**
* 索引v的顶点名
*
* @param v 索引值
* @return 顶点名
*/
String name(int v) {
return keys[v];
}
/**
* 隐藏的graph对象
*
* @return
*/
Graph graph() {
return g;
}
}
4.1.7.4 间隔的度数.
图处理的经典问题之一就是找寻社交网络中两个人之间的度数.可以延伸到电影行业可以查询演员之间的间隔,也可以查询电影与电影之间的间隔,地图地理位置之间的距离(图的连通)
通过符号表,和广度优先搜索 ,可以先由符号表创建Graph,从索引index 开始进行广度优先查找图中的最短路径.
