有向图
概述: 使用邻接表的数据结构表示有向图
1.有向图数据结构
public class DiGraph {
private int v; //顶点数目
private int e; //边数
private LinkedList<Integer>[] adj; //邻接表
//创建含有v个顶点但没有边的有向图
public DiGraph(int v) {
this.v = v;
this.e = 0;
adj = new LinkedList[v];
for(int i=0;i<v;++i)
adj[i] = new LinkedList<>();
}
//从输入流中读取一副有向图
public DiGraph(InputStream input) {
BufferedReader reader = new BufferedReader(new InputStreamReader(input));
String value = null;
try {
int v = Integer.parseInt(reader.readLine());
this.v = v;
adj = (LinkedList<Integer>[]) new LinkedList[v];
for(int i = 0 ; i < v;i++)
adj[i] = new LinkedList<>();
int e = Integer.parseInt(reader.readLine());
for(int i=0; i<e; i++){
String[] str = reader.readLine().split(" +");
addEdge(Integer.parseInt(str[0]),Integer.parseInt(str[1]));
}
} catch (IOException e1) {
e1.printStackTrace();
} finally {
try {
reader.close();
} catch (IOException e1) {
e1.printStackTrace();
}
}
}
//顶点总数
public int V(){ return v; }
//边总数
public int E(){ return e;}
//向图中添加一条边 v -> w
public void addEdge(int v,int w){
adj[v].add(w);
e++;
}
//由v指出的所有边连接的所有顶点
public Iterable<Integer> adj(int v){ return adj[v]; }
//该图的反向图
public DiGraph reverse(){
DiGraph r = new DiGraph(v);
for(int i=0;i<v;++i) {
for (int w : adj(i))
r.addEdge(w, i);
}
return r;
}
//字符串表示
public String toString(){
String s = V() + "vertices, " + E() + " edges\n";
for(int v = 0;v < V();v++){
s += v + ": ";
for(int w : adj(v))
s += w + " ";
s += "\n";
}
return s;
}
}2.使用深度优先搜索解决单点可达性
概述: 给定一副有向图和一个起点s,是否存在一条从s到达给定顶点v的有向路径
思路: 无向图的深度优先搜索稍作更改即可
public class DirectedDFS {
private boolean[] marked; //标记顶点是否被访问
//在有向图g中找到从s可达的所有顶点
public DirectedDFS(DiGraph g,int s) {
marked = new boolean[g.V()];
dfs(g,s);
}
//在g中找到从source中的所有顶点可达的所有顶点
public DirectedDFS(DiGraph g,Iterable<Integer> source){
marked = new boolean[g.V()];
source.forEach(e -> {
if(!marked[e]) dfs(g,e);
});
}
//与无向图的深度优先搜索相同
private void dfs(DiGraph g,int v){
marked[v] = true;
for(int w : g.adj(v))
if(!marked[w]) dfs(g,w);
}
//v是否可达
public boolean marked(int v){ return marked[v]; }
}3.有向图的路径
概述: 和无向图中深度优先搜索查找路径与广度优先搜索查找路径相同,只需将无向图对象改为有向图对象即可
4.有向图中的环
概述: 有向图中是否存在有向环,如果有找出一个有向环
思路: 对深度优先搜索稍作改动即可,递归遍历中内层遍历到外层经过的顶点则形成有向环
因此额外维护一个数组标记正在递归遍历的顶点,当层递归结束回到上层时取消标记
当递归内层访问到外层标记的顶点时形成有向环
即: 如果把递归调用看做入栈出栈过程,如果遍历到了栈内的已经标记过的顶点则形成有向环
public class DirectedCircle {
private boolean[] marked; //标记是否被访问
private int[] edgeTo; //记录路径
private ArrayDeque<Integer> circle; //有向环中的所有顶点(若存在)
private boolean[] onStack; //标记递归调用的栈上的所有顶点
public DirectedCircle(DiGraph g) {
onStack = new boolean[g.V()];
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
for(int v=0;v<g.V();++v)
if(!marked[v]) dfs(g,v);
}
private void dfs(DiGraph g,int v){ //深度优先搜索
onStack[v] = true; //递归进入: 入栈时标记该顶点为true
marked[v] = true; //标记当前顶点被遍历过
for(int w : g.adj(v)) {
if (hasCycle()) return;
else if(!marked[w]){
edgeTo[w] = v; //记录路径 v -> w
dfs(g,w);
}
else if(onStack[w]){ //如果遍历到已经遍历过的顶点,且在递归调用的栈中,则形成有向环
circle = new ArrayDeque<>();
for(int x=v;x!=w;x=edgeTo[x]) //将有向环保存到circle中
circle.push(x);
circle.push(w);
circle.push(v);
}
}
onStack[v] = false; //递归出去: 出栈时标记该顶点为false
}
//是否含有有向环
public boolean hasCycle(){ return circle != null;}
//有向环中的所有顶点
public Iterable<Integer> cycle(){ return circle; }
}5.有向图中基于深度优先搜索的顶点排序
意义: 有向无环图的逆后序排列即为该图的拓扑排序
public class DepthFirstOrder {
private boolean[] marked;
private Queue<Integer> pre; //所有顶点的前序排列
private Queue<Integer> post; //所有顶点的后序排列
private ArrayDeque<Integer> reversePost; //所有顶点的逆后序排列(若为有向无环图,则就是拓扑排序)
public DepthFirstOrder(DiGraph g) {
pre = new ArrayDeque<>();
post = new ArrayDeque<>();
reversePost = new ArrayDeque<>();
marked = new boolean[g.V()];
for(int v=0;v<g.V();++v)
if(!marked[v]) dfs(g,v);
}
private void dfs(DiGraph g, int v){
pre.offer(v); //前序排列: 递归进入时顺序
marked[v] = true;
for(int w : g.adj(v))
if(!marked[w]) dfs(g,w);
post.offer(v); //后序排列: 递归出去时顺序
reversePost.push(v);//逆后序排列: 后序排列的反序,后序排列压入栈中即可
}
public Iterable<Integer> pre(){ return pre; }
public Iterable<Integer> post(){ return post; }
public Iterable<Integer> reversePost(){ return reversePost; }
}6.拓扑排序
概述: 只有有向无环图才能进行拓扑排序
思路: 有向无环图的深度优先搜索的逆后序排列即为拓扑排序
public class TopoLogical {
private Iterable<Integer> order; //顶点拓扑排序
public TopoLogical(DiGraph g) {
if(!new DirectedCircle(g).hasCycle()) //1. 有向无环图
order = new DepthFirstOrder(g).reversePost(); //2.逆后序排列即为拓扑排序
}
public Iterable<Integer> order(){ return order; }
public boolean isDAG(){ return order != null; }
}7.找出有向图的所有强连通分量(kosaraju算法)
实现步骤:
1.求出给定的有向图g的反向图gr的逆后序排列
2.在g中进行标准的深度优先搜索,但是要按照第一步中获得的逆后序排列顺序进行
3.在构造函数中,所有在同一个dfs()调用中被访问的顶点都在同一个强连通分量中
简单思考:
将有向图的每个强连通分量看做一个整体,则形成一个新的有向无环图,
此时每个顶点表示一个强连通分量,我们只要每次只遍历一个顶点,就能找到一个强连通分量
证明: 参考算法第四版证明下面两条即可
1.每个和s强连通的顶点v都会在构造函数调用的dfs(g,s)中被访问到
反证: 假如一个和s强连通的顶点v不会再dfs(g,s)中被访问,因为存在s->v路径,所以v在之前肯定
被访问过,又s与v强连通即v->s存在路径,所以访问v时s一定被访问,后续就不会调用dfs(g,s),矛盾
2.构造函数的调用的dfs(g,s)所到达的任意顶点v都必然和s强连通
如果dfs(g,s)到达某顶点v,则g 中 s -> v 存在,且反向图gr的逆后序排列中s在v前面
目前只需要证明v->s存在即可证明s与v强连通,即只需证明反向图gr中s->v连通
因为gr逆后序排列中s在v前面,且gr中v->s连通(因为g中s-v连通),因此只有一种可能
case1: dfs(gr,v)调用并结束在dfs(gr,s)之前(不可能,v->s不连通)
case2: dfs(gr,v)调用并结束在dfs(gr,s)调用中间(必为此情况: 此时gr中s->v连通)
public class KosarajuSCC {
private boolean[] marked;
private int[] id; //维护顶点的强连通分量值
private int count; //连通分量个数
public KosarajuSCC(DiGraph g) {
marked = new boolean[g.V()];
id = new int[g.V()];
for(int s : new DepthFirstOrder(g.reverse()).reversePost()) //1,2.按照反向图的逆后序排列进行深度优先搜索
if(!marked[s]){
dfs(g,s); //3.每次执行访问到的所有顶点都在一个强连通分量中
++count;
}
}
private void dfs(DiGraph g,int v){
marked[v] = true;
id[v] = count; //标记当前顶点强连通分量值
for(int w : g.adj(v))
if(!marked[w]) dfs(g,w);
}
//顶点v与w是否强连通
public boolean stronglyConnected(int v,int w){ return id[v] == id[w]; }
//顶点v的强连通分量值
public int id(int v){ return id[v]; }
//强连通分量个数
public int count(){ return count; }
}