Topological Sort Graph Algorithm
Generate topologically sorted order for directed acyclic graph,
Here we are going to consider graph as a “Directed Graph”, Please visit my below article for more details about Directed and Undirected Graph
Input :
Output :
B > P > A > C > D > H > G > I > Q > R >
Algorithm
|
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 |
package com.omt.learn.algo; import java.util.Stack; import com.omt.learn.algo.util.graph.Graph; import com.omt.learn.algo.util.graph.Node; import com.omt.learn.algo.util.graph.State; public class TopologicalSortGraphAlgorithm { public static void main(String[] args) { generatePackageSequence(generateGraph()); } public static void generatePackageSequence(Graph graph) { Stack<Node> stackOfVertex = new Stack(); Stack<Node> foundNode = new Stack<>(); for (Node n : graph.getVertices()) { if (!n.isVisited() && !n.isFoundAlready()) { n.setState(State.FOUND); foundNode.push(n); iterate(foundNode, stackOfVertex); } } String sequenceOfVisit = ""; while (!stackOfVertex.isEmpty()) { sequenceOfVisit += stackOfVertex.pop().getVertex() + " > "; } System.out.println(sequenceOfVisit); } private static void iterate(Stack<Node> foundNode, Stack<Node> stackOfVertex) { if (foundNode.isEmpty()) { return; } Node c = foundNode.peek(); if ((c.getAdjacent() == null || c.getAdjacent().isEmpty()) && !c.isVisited()) { stackOfVertex.push(c); foundNode.pop(); c.setState(State.VISITED); } else { boolean isAnyNewInsert = false; for (Node n : c.getAdjacent()) { if (!n.isFoundAlready() && !n.isVisited()) { isAnyNewInsert = true; n.setState(State.FOUND); foundNode.push(n); } } if (!isAnyNewInsert) { stackOfVertex.push(c); foundNode.pop(); c.setState(State.VISITED); } } iterate(foundNode, stackOfVertex); } public static Graph generateGraph() { Graph graph = new Graph(); Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node q = new Node("Q"); Node r = new Node("R"); Node g = new Node("G"); Node h = new Node("H"); Node i = new Node("I"); Node p = new Node("P"); a.addAdjacent(c); b.addAdjacent(c); b.addAdjacent(p); c.addAdjacent(d); c.addAdjacent(q); p.addAdjacent(r); q.addAdjacent(r); d.addAdjacent(h); d.addAdjacent(g); g.addAdjacent(i); graph.addVertex(a); graph.addVertex(b); graph.addVertex(c); graph.addVertex(d); graph.addVertex(q); graph.addVertex(r); graph.addVertex(g); graph.addVertex(h); graph.addVertex(i); graph.addVertex(p); return graph; } } |
