uopspop

Untitled

Sep 21st, 2019
162
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class GraphAdjacentMatrix_TopologicalSort_DFS {
  2.  
  3.     private boolean adjMatrix[][];
  4.     private int numVertices;
  5.     private boolean visited[];
  6.  
  7.     public GraphAdjacentMatrix_TopologicalSort_DFS(int numVertices) {
  8.         this.numVertices = numVertices;
  9.         adjMatrix = new boolean[numVertices][numVertices];
  10.         visited = new boolean[numVertices];
  11.     }
  12.  
  13.     public void setEdge(int i, int j) {
  14.         adjMatrix[i][j] = true;
  15. //        adjMatrix[j][i] = true; // directed
  16.     }
  17.  
  18.     public void delEdge(int i, int j) {
  19.         adjMatrix[i][j] = false;
  20. //        adjMatrix[j][i] = false; // directed
  21.     }
  22.  
  23.     public boolean isEdge(int i, int j) {
  24.         return adjMatrix[i][j];
  25.     }
  26.  
  27.     public int first(int v1){
  28.         boolean[] ary = this.adjMatrix[v1];
  29.         int firstNeighborIndex = this.numVertices; // return n if none
  30.         for (int i = 0; i < ary.length; i++) {
  31.             if (ary[i] != false){
  32.                 firstNeighborIndex = i;
  33.                 break;
  34.             }
  35.         }
  36.         return firstNeighborIndex;
  37.     }
  38.  
  39.     public int next(int v1, int v2){
  40.         boolean[] ary = this.adjMatrix[v1];
  41.         int nextNeighborIndex = this.numVertices; // return n if none
  42.         for (int i = v2 + 1; i < ary.length; i++) {
  43.             if (ary[i] != false){
  44.                 nextNeighborIndex = i;
  45.                 break;
  46.             }
  47.         }
  48.         return nextNeighborIndex; // return n if none
  49.     }
  50.  
  51.     public void topSort_DFS(int v){
  52.         topSort_DFS(this.adjMatrix, v);
  53.     }
  54.  
  55.     public void topSort_DFS(boolean[][] graph, int v){
  56.         Previsit(graph, v);
  57.         // mark the current node
  58.         visited[v] = true;
  59.         // find neighbor
  60.         for (int nextV = this.first(v); nextV < this.numVertices; nextV = this.next(v, nextV)) {
  61.             if (!visited[nextV]){
  62.                 topSort_DFS(graph, nextV);
  63.             }
  64.         }
  65.         Postvisit(graph, v);
  66.     }
  67.  
  68.     private void Previsit(boolean[][] graph, int v) {
  69. //        System.out.println("Previsit: " + v); // do not print anything for topologicalSort implemented in DFS
  70.     }
  71.  
  72.     private void Postvisit(boolean[][] graph, int v) {
  73.         System.out.println("Postvisit: " + v); // we will get an reverse order
  74.     }
  75.  
  76.  
  77.     public String toString() {
  78.         StringBuilder s = new StringBuilder();
  79.         for (int i = 0; i < numVertices; i++) {
  80.             s.append(i + ": ");
  81.             for (boolean j : adjMatrix[i]) {
  82.                 s.append((j?1:0) + " ");
  83.             }
  84.             s.append("\n");
  85.         }
  86.         return s.toString();
  87.     }
  88.  
  89.     public static void main(String[] args) {
  90.         GraphAdjacentMatrix_TopologicalSort_DFS gam = new GraphAdjacentMatrix_TopologicalSort_DFS(8);
  91.  
  92.         // directed graph
  93.         gam.setEdge(1, 2);
  94.         gam.setEdge(1, 3);
  95.         gam.setEdge(2, 6);
  96.         gam.setEdge(2, 5);
  97.         gam.setEdge(2, 4);
  98.         gam.setEdge(3, 4);
  99.         gam.setEdge(4, 5);
  100.         gam.setEdge(5, 7);
  101.  
  102.         System.out.println("DFS: ");
  103.         gam.topSort_DFS( 1);
  104.  
  105.         System.out.println();
  106.     }
  107.  
  108. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×