JAVA:实现 kahns algorithm卡恩算法(附完整源码)

package com.thealgorithms.datastructures.graphs;
import java.util.ArrayList;
import java.util.Map;
import java.util.LinkedHashMap;
import java.util.HashMap;
import java.util.Set;
import java.util.Queue;
import java.util.LinkedList;

/**
 * An algorithm that sorts a graph in toplogical order.
 */
/**
 * A class that represents the adjaceny list of a graph
 */
class AdjacencyList<E extends Comparable<E>> {

    Map<E, ArrayList<E>> adj;

    AdjacencyList() {
        adj = new LinkedHashMap<E, ArrayList<E>>();
    }

    /**
     * This function adds an Edge to the adjaceny list
     *
     * @param from , the vertex the edge is from
     * @param to, the vertex the edge is going to
     */
    void addEdge(E from, E to) {
        try {
            adj.get(from).add(to);
        } catch (Exception E) {
            adj.put(from, new ArrayList<E>());
            adj.get(from).add(to);
        }
        if (!adj.containsKey(to)) {
            adj.put(to, new ArrayList<E>());
        }
    }

    /**
     * @param v, A vertex in a graph
     * @return returns an ArrayList of all the adjacents of vertex v
     */
    ArrayList<E> getAdjacents(E v) {
        return adj.get(v);
    }

    /**
     * @return returns a set of all vertices in the graph
     */
    Set<E> getVertices() {
        return adj.keySet();
    }

    /**
     * Prints the adjacency list
     */
    void printGraph() {
        for (E vertex : adj.keySet()) {
            System.out.print(vertex + " : ");
            for (E adjacent : adj.get(vertex)) {
                System.out.print(adjacent + " ");
            }
            System.out.println();
        }
    }
}

class TopologicalSort<E extends Comparable<E>> {

    AdjacencyList<E> graph;
    Map<E, Integer> inDegree;

    TopologicalSort(AdjacencyList<E> graph) {
        this.graph = graph;
    }

    /**
     * Calculates the in degree of all vertices
     */
    void calculateInDegree() {
        inDegree = new HashMap<>();
        for (E vertex : graph.getVertices()) {
            if (!inDegree.containsKey(vertex)) {
                inDegree.put(vertex, 0);
            }
            for (E adjacent : graph.getAdjacents(vertex)) {
                try {
                    inDegree.put(adjacent, inDegree.get(adjacent) + 1);
                } catch (Exception e) {
                    inDegree.put(adjacent, 1);
                }
            }
        }
    }

    /**
     * Returns an ArrayList with vertices arranged in topological order
     */
    ArrayList<E> topSortOrder() {
        calculateInDegree();
        Queue<E> q = new LinkedList<E>();

        for (E vertex : inDegree.keySet()) {
            if (inDegree.get(vertex) == 0) {
                q.add(vertex);
            }
        }

        ArrayList<E> answer = new ArrayList<>();

        while (!q.isEmpty()) {
            E current = q.poll();
            answer.add(current);
            for (E adjacent : graph.getAdjacents(current)) {
                inDegree.put(adjacent, inDegree.get(adjacent) - 1);
                if (inDegree.get(adjacent) == 0) {
                    q.add(adjacent);
                }
            }
        }

        return answer;

    }
}

/**
 * A driver class that sorts a given graph in topological order.
 */
public class KahnsAlgorithm {

    public static void main(String[] args) {

        //Graph definition and initialization
        AdjacencyList<String> graph = new AdjacencyList<>();
        graph.addEdge("a", "b");
        graph.addEdge("c", "a");
        graph.addEdge("a", "d");
        graph.addEdge("b", "d");
        graph.addEdge("c", "u");
        graph.addEdge("u", "b");

        TopologicalSort<String> topSort = new TopologicalSort<>(graph);

        //Printing the order
        for (String s : topSort.topSortOrder()) {
            System.out.print(s + " ");
        }
    }
}

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154