有向图，边是单向的：每条边所连接的两个顶点都是一个有序对，它的邻接性是单向的。 我们称一条有向边由第一个顶点指出并指向第二个顶点。 一个顶点的出度(out degree)由该顶点指出的边的总数。 一个顶点的入度(in degree)为指向该顶点的边的总数。 一条有向边的第一个顶点称为它的头，第二个顶点称为它的尾。
public interface Digraph {
/**
* @Description: Number of vertex.
* @return
*/
public int V();
/**
* @Description: Number of edge.
* @return
*/
public int E();
/**
* @Description: Add an edge between two vertex. v->w.
* @param v
* @param w
*/
public void addEdge(int v, int w);
/**
* @Description: Return vertex point out from v.
* @param v
* @return
*/
public Iterable<Integer> adj(int v);
/**
* @Description: Get the reverse graph of current graph.
* @return
*/
public Digraph reverse();
/**
* @Description: Print current graph.
*/
public void display();
}public class DigraphImpl implements Digraph {
private final int V; //Number of vertex in current digraph
private int E; //Number of edges.
private ListBag<Integer>[] adj;
@SuppressWarnings("unchecked")
public DigraphImpl(int V){
this.V = V;
adj = (ListBag<Integer>[])new ListBag[V];
for (int i = 0; i < V; i++) {
adj[i] = new ListBag<Integer>();
}
this.E = 0;
}
@SuppressWarnings("unchecked")
public DigraphImpl(FileInputStream in) {
Scanner s = null;
s = new Scanner(in);
this.V = s.nextInt();
this.E = s.nextInt();
adj = new ListBag[V];
for (int i = 0; i < V; i++) {
adj[i] = new ListBag<Integer>();
}
for(int i = 0; i < E; i ++){
int v = s.nextInt();
int w = s.nextInt();
adj[v].add(w);
}
s.close();
}
@Override
public int V() { return this.V; }
@Override
public void addEdge(int v, int w) { //只增加一条有向边
adj[v].add(w);
E++;
}
@Override
public int E() { return E; }
@Override
public Iterable<Integer> adj(int v) {
return adj[v];
}
@Override
public Digraph reverse() {
DigraphImpl g = new DigraphImpl(V);
for(int v = 0; v < V; v++)
for(int w : adj(v))
addEdge(w, v);
return g;
}
@Override
public void display() {
for(int i = 0; i < V; i++){
StringBuilder sb = new StringBuilder(i + ": ");
for(int w : adj[i]){
sb.append(w + "|");
}
System.out.println(sb.toString());
}
}
} public static void main(String[] args) throws IOException {
FileInputStream in = new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyDG.txt"));
Digraph graph = new DigraphImpl(in);
in.close();
graph.display();
}0: 5|1| 1: 2: 0|3| 3: 5|2| 4: 3|2| 5: 4| 6: 9|4|8|0| 7: 6|9| 8: 6| 9: 11|10| 10: 12| 11: 4|12| 12: 9|
可达性的重要实际应用是在内存管理系统中，一个顶点表示一个对象，一条边表示一个对象的引用。
public class DirectedDFS {
private final boolean[] marked;
public DirectedDFS(Digraph g, int s){
this.marked = new boolean[g.V()];
dfs(g, s);
}
public DirectedDFS(Digraph g, Iterable<Integer> sources){
marked = new boolean[g.V()];
for(int s : sources)
if(!marked[s]) dfs(g, s);
}
private void dfs(Digraph g, int s) {
marked[s] = true;
for(int w : g.adj(s))
if(!marked[w]) dfs(g, w);
}
public boolean mark(int v){
return marked[v];
}
}- 测试
public static void main(String[] args) throws FileNotFoundException {
Digraph g = new DigraphImpl(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyDG.txt")));
Bag<Integer> bag = new ListBag<Integer>();
bag.add(1);
bag.add(2);
bag.add(6);
DirectedDFS d = new DirectedDFS(g, bag);
StringBuilder sb = new StringBuilder();
for(int v = 0; v < g.V(); v++){
if(d.mark(v)) sb.append(v + " ");
}
System.out.println(sb.toString());
}0 1 2 3 4 5 6 8 9 10 11 12
通过DFPath实现
public class DepthFirstPathDirectedGraph implements Path {
private final DigraphImpl g;
private int s;
private final boolean[] marked; //Used to mark if current vertex has been accessed.
private final int[] edgeTo; //Used to save the vertex ahead of current vertex.
public DepthFirstPathDirectedGraph(DigraphImpl g, int s){
this.s = s;
this.g = (DigraphImpl) g;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
dfs(g, s);
}
public DepthFirstPathDirectedGraph(String file, int s) throws FileNotFoundException{
g = new DigraphImpl(new FileInputStream(new File(file)));
this.s = s;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
dfs(g, s);
}
@Override
public boolean hasPathTo(int v) {
return edgeTo[v] != 0;
}
@Override
public Iterable<Integer> pathTo(int v) {
Bag<Integer> path = new ListBag<Integer>();
path.add(v);
while(edgeTo[v] != s){
path.add(edgeTo[v]);
v = edgeTo[v];
}
return path;
}
private void dfs(DigraphImpl g, int v){
marked[v] = true;
for(int w : g.adj(v)){
if(!marked[w]){
edgeTo[w] = v;
dfs(g, w);
}
}
}
}- 测试
public static void main(String[] args) throws FileNotFoundException {
DigraphImpl g = new DigraphImpl(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyDG.txt")));
DepthFirstPathDirectedGraph p = new DepthFirstPathDirectedGraph(g, 6);
Iterable<Integer> pathTo = p.pathTo(0);
System.out.print(6 + " ");
for(Integer w : pathTo) System.out.print(w + " ");
System.out.println();
// System.out.println(p.hasPathTo(10));
}6 9 11 4 3 2 0
通过BFPath实现
public class BreadFirstPathDirectedGraph implements Path {
private final Digraph g;
private int s;
private final boolean[] marked;
private final int[] edgeTo;
public BreadFirstPathDirectedGraph(Digraph g, int s) {
this.g = g;
this.s = s;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
bfs(g, s);
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
Stack<Integer> path = new Stack<>();
path.push(v);
while(s != edgeTo[v]){
path.push(edgeTo[v]);
v= edgeTo[v];
}
return path;
}
private void bfs(Digraph g, int s){
LinkedBlockingQueue<Integer> q = new LinkedBlockingQueue<>();
marked[s] = true;
q.offer(s);
while(!q.isEmpty()){
int v = q.poll();
for(int w : g.adj(v)){
if(!marked[w]){
edgeTo[w] = v;
marked[w] = true;
q.offer(w);
}
}
}
}
}- 测试和DFS完全一致。
public class DirectedCycle {
private final boolean[] marked;
private final int[] edgeTo;
private Stack<Integer> cycle = null; //有向环上的所有顶点
private final boolean[] onStack; //递归调用的栈上的所有顶点
public DirectedCycle(Digraph g){
onStack = new boolean[g.V()];
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
int size = g.V();
for(int v = 0; v < size; v++)
if(!marked[v]) dfs(g, v);
}
private void dfs(Digraph g, int v){
//在此次的遍历中，记录当前的位置可能在环上。如果结束了没有在环上则改回false
onStack[v] = true;
marked[v] = true;
for(int w : g.adj(v)){
if(this.hasCycle()) return;
else if(!marked[w]){ //当前结点未被访问过，一定不是闭环，递归调用
edgeTo[w] = v;
dfs(g, w);
}
else if(onStack[w]){ //在此次的遍历中，当前点已经在环上，说明已经构成了cycle.v的下一个结点构成了闭环。
//创建stack对象，并添加元素。
cycle = new Stack<>();
for(int x = v; x != w; x = edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false;
}
public boolean hasCycle(){
return cycle != null;
}
public Iterable<Integer> cycle(){
return cycle;
}
}- 测试
public static void main(String[] args) throws FileNotFoundException {
Digraph g = new DigraphImpl(new FileInputStream(new File("src/ca/mcmaster/chapter/four/graph/tinyDG.txt")));
DirectedCycle cycle = new DirectedCycle(g);
StringBuilder sb = new StringBuilder();
for(int i : cycle.cycle()){
sb.append(i + " ");
}
System.out.println(sb.toString());
}3 4 5 3
- 有向图的遍历分成三种。
- 前序遍历
前序遍历就是dfs()的调用顺序，将顶点加入队列。
- 后序遍历
后序遍历，就是递归调用之后将顶点加入队列中。
- 逆后序遍历
逆后序遍历和后序遍历相似，但是是将顶点加入栈中。
public class DepthFirstOrder {
private final boolean[] marked;
private final Queue<Integer> pre; //前序遍历。和dfs的顺序一致，当访问到了一个顶点，就将顶点加入队列。
private final Queue<Integer> post; //后序遍历，顶点遍历完成的顺序。从递归的最内部开始加入遍历，相当于完成后立刻加入队列之中。
private final Stack<Integer> reversePost;
public DepthFirstOrder(Digraph g){
pre = new LinkedBlockingQueue<Integer>();
post = new LinkedBlockingQueue<>();
reversePost = new Stack<>();
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 this.pre;
}
public Iterable<Integer> post(){
return this.post();
}
public Iterable<Integer> reversePost(){
return this.reversePost;
}
}给定一张有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。 有环图画不出拓扑图，因为有环图无法确定环上定点的顺序。 一幅有向无环图的拓扑顺序即为所有顶点的逆后序排列。
public class Topological {
private Iterable<Integer> order;
public Topological(Digraph g){
DirectedCycle dc = new DirectedCycle(g);
if(!dc.hasCycle()){
DepthFirstOrder dfo = new DepthFirstOrder(g);
order = dfo.reversePost(); //depth first order的逆后序就是拓扑图的顺序。
}
}
public Iterable<Integer> order(){
return order;
}
public boolean isDAG(){
return order != null;
}
}
通过对强连通分量的研究可以将不同的对象进行分类，将具有相似性质的对象统一处理。
- 接口
public interface SCC {
/**
* @Description: Check if v and w are connected.
* @param v
* @param w
* @return
*/
public boolean strongConnected(int v, int w);
/**
* @Description: The number of strong connected component.
* @return
*/
public int count();
/**
* @Description: Which of the strong component belongs to.
* @param v
* @return
*/
int id(int v);
}- Kosaraju算法计算强连通分量
public class StrongCircleComponent implements SCC {
private boolean[] marked;
private int[] id;
private int count;
public StrongCircleComponent(Digraph g) {
marked = new boolean[g.V()];
id = new int[g.V()];
DepthFirstOrder order = new DepthFirstOrder(g.reverse());//获得g的反转图
for(int s : order.reversePost()){ //按照逆后序读取元素（拓扑图顺序）
if(!marked[s]){
dfs(g, s); 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);
}
@Override
public boolean strongConnected(int v, int w) {
return id[v] == id[w];
}
@Override
public int count() {
return count;
}
@Override
public int id(int v) {
return id[v];
}
}- Kosaraju证明
- 每次和s强连通的顶点都会在构造函数调用dfs(g, s)时被访问到。
反证法： 假设有一个和s强连通的顶点v不会被访问到，说明v曾经被访问过。 如果v曾经被访问过,s和v为强连通分量，s应被访问过。 s当前正在被访问，矛盾。
- 构造函数dfs(G,s)所到达的任意顶点v都必然是和s强连通的。
A和B强连通充要条件：A和B在图中连通，B和A在反向图中也连通。