有向图

Author Avatar
Brian Lee 9月 12, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:有向图


术语

一幅有 方向性的图 (或有向图 )是由一组 顶点 和一组 有方向的边 组成的,每条有方向的边都连接着有序的一对顶点。

称一条有向边由第一个顶点 指出指向 第二个顶点。

一个顶点的 出度 为由该顶点指出的边的总数,一个顶点的 入度 为指向该顶点的边的总数。

一条有向边的第一个顶点成为它的 ,第二个顶点称为它的

在一幅有向图中,有向路径 由一系列顶点组成,对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。

有向环 为一条至少含有一条边且起点和终点相同的有向路径。简单有向环 是一条除了起点和终点必须相同之外,不含有重复的顶点和边的环。

路径或环的 长度 即为其中所包含的边数。


图示

图示


表示

使用邻接表表示

表示


数据类型

public class DiGraph {
    private int V;
    private int E;
    private Bag<Integer>[] adj;

    public DiGraph(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<>();
    }
    //输入初始化构造函数
    public DiGraph() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();
        int e = in.nextInt();
        for (int i = 0; i < e; i++) {
            int v = in.nextInt();
            int w = in.nextInt();
            addEdge(v, w);
        }
    }
    public int V() {
        return V;
    }
    public int E() {
        return E;
    }
    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
    public DiGraph reverse() {
        DiGraph R = new DiGraph(V);
        for (int v = 0; v < V; v++)
            for (int w : adj[v])
                R.addEdge(w, v);
        return R;
    }
    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;
    }
}

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_2_Directed_Graph/S4_2_2_DiGraph


有向图的深度优先搜索

图示

DFS

使用

使用DFS可以检测有向图的可达性,即解决“是否存在一条从s到达给定顶点v的有向路径”或“是否存在一条从结合中的任意顶点到达给定顶点v的有向路径”等问题。

递归代码

public class DiDFS {
    private boolean[] marked;
      //单源
    public DiDFS(DiGraph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }
      //多源
    public DiDFS(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 v) {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }
    public boolean marked(int v) {
        return marked[v];
    }
}

非递归代码

public class DiDFS_Nonrecur {
    private boolean[] marked;

    public DiDFS_Nonrecur(DiGraph G, int s) {
        marked = new boolean[G.V()];
        Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
        for (int v = 0; v < G.V(); v++) {
            adj[v] = G.adj(v).iterator();
        }
        Stack<Integer> stack = new Stack<>();
        marked[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (adj[v].hasNext()) {
                int w = adj[v].next();
                if (!marked[w]) {
                    marked[w] = true;
                    stack.push(w);
                }
            }
            else {
                stack.pop();
            }
        }
    }

    public DiDFS_Nonrecur(DiGraph G,Iterable<Integer> sources) {
        marked = new boolean[G.V()];
        Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
        for (int v = 0; v < G.V(); v++) {
            adj[v] = G.adj(v).iterator();
        }
        for (int s : sources) {
            Stack<Integer> stack = new Stack<>();
            marked[s] = true;
            stack.push(s);
            while (!stack.isEmpty()) {
                int v = stack.peek();
                if (adj[v].hasNext()) {
                    int w = adj[v].next();
                    if (!marked[w]) {
                        marked[w] = true;
                        stack.push(w);
                    }
                }
                else {
                    stack.pop();
                }
            }
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }
}

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_2_Directed_Graph/S4_2_3_DiDFS


深度优先搜索路径

代码

public class DiDFSPath {
    private boolean[] marked;
    private int[] edgeTo;
    private int s;

    public DiDFSPath(DiGraph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }
    private void dfs(DiGraph 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> stack = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) {
            stack.push(x);
        }
        stack.push(s);
        Queue<Integer> queue = new LinkedList<>();
        while (!stack.isEmpty()) {
            queue.offer(stack.pop());
        }
        return queue;
    }
}

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_2_Directed_Graph/S4_2_3_DiDFSPath


广度优先搜索路径

代码

public class DiBFSPath {
    private final int INFINITY = Integer.MAX_VALUE;
    private boolean[] marked;
    private int [] edgeTo;
    private int[] distTo;
    private int s;

    public DiBFSPath(DiGraph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        distTo = new int[G.V()];
        this.s = s;
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = INFINITY;
        }
        bfs(G, s);
    }
    private void bfs(DiGraph G, int s) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        marked[s] = true;
        distTo[s] = 0;
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    marked[w] = true;
                    distTo[w] = distTo[v] + 1;
                    edgeTo[w] = v;
                    q.offer(w);
                }
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public int distTo(int v) {
        return distTo[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))   return null;
        Stack<Integer> stack = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) {
            stack.push(x);
        }
        stack.push(s);
        Queue<Integer> queue = new LinkedList<>();
        while (!stack.isEmpty()) {
            queue.offer(stack.pop());
        }
        return queue;
    }
}

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_2_Directed_Graph/S4_2_3_DiBFSPath


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/09/12/DiGraph/