技术博客

算法——图的排序

发表于 分类于 阅读次数：
本文字数： 6.3k 阅读时长 ≈ 6 分钟

引言

本文整理了常见的图排序相关算法，方便以后查阅。算法相关的文章均收录于<算法系列文章>。

图

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package bbm.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;

import static bbm.graph.BFS.Color.BLACK;
import static bbm.graph.BFS.Color.GRAY;
import static bbm.graph.BFS.Color.WHITE;

/**
 * 图的广度优先搜索，以链表的形式表述邻接关系, 这里我们利用队列来实现 BFS
 *
 * BFS 可以用来计算最短路径
 *
 * @author bbm
 */
public class BFS {

    public static class Node {
        String name;
        Color color = WHITE;
        int d = Integer.MAX_VALUE;
        Node pre = null;
        List<Node> neighbors = new LinkedList<>();

        public Node(String name) {
            this.name = name;
        }
    }

    public static enum Color {
        WHITE,
        GRAY,
        BLACK
    }

    public static void bfs(Node node) {
        LinkedBlockingQueue<Node> queue = new LinkedBlockingQueue<>();
        node.color = GRAY;
        node.d = 0;
        node.pre = null;
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            current.neighbors.forEach(neighbor -> {
                if (neighbor.color.equals(WHITE)) {
                    neighbor.color = GRAY;
                    neighbor.d = current.d + 1;
                    neighbor.pre = current;
                    queue.offer(neighbor);
                }
            });
            current.color = BLACK;
            System.out.println("Node " + current.name + ", d: " + current.d);
        }
    }

    public static void main(String[] args) {
        Node s = new Node("s");
        Node r = new Node("r");
        Node v = new Node("v");
        Node w = new Node("w");
        Node t = new Node("t");
        Node x = new Node("x");
        Node y = new Node("y");
        Node u = new Node("u");
        s.neighbors.add(w);
        s.neighbors.add(r);

        r.neighbors.add(s);
        r.neighbors.add(v);

        v.neighbors.add(r);

        w.neighbors.add(s);
        w.neighbors.add(t);
        w.neighbors.add(x);

        t.neighbors.add(u);
        t.neighbors.add(x);
        t.neighbors.add(w);

        x.neighbors.add(w);
        x.neighbors.add(t);
        x.neighbors.add(y);
        x.neighbors.add(u);

        y.neighbors.add(x);
        y.neighbors.add(u);

        u.neighbors.add(t);
        u.neighbors.add(x);
        u.neighbors.add(y);
        bfs(s);
        System.out.println("Path from s to y:");
        printPath(s, y);
        System.out.println();
    }

    private static void printPath(Node s, Node y) {
        if (s == y) {
            System.out.print(s.name + " ");
        } else {
            if (y.pre == null) {
                System.out.println("No path from " + s.name + " to " + y.name);
            } else {
                printPath(s, y.pre);
                System.out.print(y.name + " ");
            }
        }
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package bbm.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import static bbm.graph.DFS.Color.BLACK;
import static bbm.graph.DFS.Color.GRAY;
import static bbm.graph.DFS.Color.WHITE;

/**
 * 图的广度优先搜索，用颜色来表示是否已经开始处理某一个节点，白色：未处理，灰色：处理中，黑色：处理完
 *
 * 如果我们将每个节点的开始处理时间记为 startTime 处理完成时间记录为 endTime 那么我们可以通过 startTime 和 endTime 够成一个括号化结构
 * Node x, start:4 end:5 被包含在 Node y, start:3 end:6 之中，这实际上就是一个树形结构, 当 x 节点的 start 和 end 在 y 节点的
 * start end 范围内时，x 节点就是 y 节点的子节点
 *     y(3, 6)
 *     /
 *  x（4，5）
 *
 * 通过这个深度优先树，我们可以简单的通过检查是否有由子节点到父节点的边来判断图中是否有环
 * @author bbm
 */
public class DFS {
    public static class Node {
        String name;
        Color color = WHITE;
        int startTime;
        int endTime;
        Node pre = null;
        List<Node> neighbors = new LinkedList<>();

        public Node(String name) {
            this.name = name;
        }
    }

    public static enum Color {
        WHITE,
        GRAY,
        BLACK
    }

    public static int time = 0;

    public static void dfs(List<Node> graph) {
        graph.forEach(node -> {
            if (node.color.equals(WHITE)) {
                visit(node);
            }
        });
    }

    private static void visit(Node node) {
        time += 1;
        node.startTime = time;
        node.color = GRAY;
        node.neighbors.forEach(neighbor -> {
            if (neighbor.color.equals(WHITE)) {
                neighbor.pre = node;
                visit(neighbor);
            }
        });
        node.color = BLACK;
        time += 1;
        node.endTime = time;
        System.out.println("Node " + node.name + ", start:" + node.startTime + " end:" + node.endTime);
    }

    public static void main(String[] args) {
        Node u = new Node("u");
        Node v = new Node("v");
        Node w = new Node("w");
        Node x = new Node("x");
        Node y = new Node("y");
        Node z = new Node("z");
        u.neighbors.add(v);
        u.neighbors.add(x);

        v.neighbors.add(y);

        w.neighbors.add(y);
        w.neighbors.add(z);

        x.neighbors.add(v);

        y.neighbors.add(x);

        z.neighbors.add(z);
        List<Node> graph = Arrays.asList(u, v, w, x, y, z);
        dfs(graph);
    }
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package bbm.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import static bbm.graph.TopologicalOrder.Color.GRAY;
import static bbm.graph.TopologicalOrder.Color.WHITE;

/**
 * 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。
 *
 * 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英语：Topological sorting）：
 * 1. 序列中包含每个顶点，且每个顶点只出现一次；
 * 2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。
 *
 *
 * @author bbm
 */
public class TopologicalOrder {
    public static class Node {
        String name;
        Color color = WHITE;
        int startTime;
        int endTime;
        Node pre = null;
        List<Node> next = new LinkedList<>();

        public Node(String name) {
            this.name = name;
        }
    }

    public static enum Color {
        WHITE,
        GRAY,
        BLACK
    }

    public static int time = 0;

    public static void dfs(List<Node> graph) {
        graph.forEach(node -> {
            if (node.color.equals(WHITE)) {
                visit(node);
            }
        });
    }

    private static void visit(Node node) {
        time += 1;
        node.startTime = time;
        node.color = GRAY;
        node.next.forEach(neighbor -> {
            if (neighbor.color.equals(WHITE)) {
                neighbor.pre = node;
                visit(neighbor);
            }
        });
        node.color = Color.BLACK;
        time += 1;
        node.endTime = time;
    }

    public static void topologicalSort(List<Node> nodes) {
        dfs(nodes);
        nodes.sort((o1, o2) -> o2.endTime - o1.endTime);
        for (Node node : nodes) {
            System.out.print(node.name + " ");
        }
    }

    public static void main(String[] args) {
        Node w = new Node("袜子");
        Node n = new Node("内裤");
        Node k = new Node("裤子");
        Node x = new Node("鞋子");
        Node s = new Node("手表");
        Node c = new Node("衬衣");
        Node y = new Node("腰带");
        Node l = new Node("领带");
        Node j = new Node("夹克");
        w.next.add(x);
        n.next.addAll(Arrays.asList(k, x));
        k.next.addAll(Arrays.asList(x, y));
        c.next.addAll(Arrays.asList(y, l));
        y.next.add(j);
        l.next.add(j);
        List<Node> nodes = Arrays.asList(w, n, k, x, s, c, y, l, j);
        topologicalSort(nodes);
    }
}

参考内容

[1] 《算法导论》

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者： 贝克街的流浪猫
  • 本文链接： https://www.beikejiedeliulangmao.top/algorithm/graph-sort/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议，转载请注明出处！
  • 创作声明： 本文基于上述所有参考内容进行创作，其中可能涉及复制、修改或者转换，图片均来自网络，如有侵权请联系我，我会第一时间进行删除。