uopspop

Untitled

Sep 21st, 2019
151
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3.  
  4. public class GraphAdjacentMatrix_DFS_BFS {
  5.  
  6.     private boolean adjMatrix[][];
  7.     private int numVertices;
  8.     private boolean visited[];
  9.  
  10.     public GraphAdjacentMatrix_DFS_BFS(int numVertices) {
  11.         this.numVertices = numVertices;
  12.         adjMatrix = new boolean[numVertices][numVertices];
  13.         visited = new boolean[numVertices];
  14.     }
  15.  
  16.     public void setEdge(int i, int j) {
  17.         adjMatrix[i][j] = true;
  18.         adjMatrix[j][i] = true;
  19.     }
  20.  
  21.     public void delEdge(int i, int j) {
  22.         adjMatrix[i][j] = false;
  23.         adjMatrix[j][i] = false;
  24.     }
  25.  
  26.     public boolean isEdge(int i, int j) {
  27.         return adjMatrix[i][j];
  28.     }
  29.  
  30.     public int first(int v1){
  31.         boolean[] ary = this.adjMatrix[v1];
  32.         int firstNeighborIndex = this.numVertices; // return n if none
  33.         for (int i = 0; i < ary.length; i++) {
  34.             if (ary[i] != false){
  35.                 firstNeighborIndex = i;
  36.                 break;
  37.             }
  38.         }
  39.         return firstNeighborIndex;
  40.     }
  41.  
  42.     public int next(int v1, int v2){
  43.         boolean[] ary = this.adjMatrix[v1];
  44.         int nextNeighborIndex = this.numVertices; // return n if none
  45.         for (int i = v2 + 1; i < ary.length; i++) {
  46.             if (ary[i] != false){
  47.                 nextNeighborIndex = i;
  48.                 break;
  49.             }
  50.         }
  51.         return nextNeighborIndex; // return n if none
  52.     }
  53.  
  54.     public void DFS(int v){
  55.         DFS(this.adjMatrix, v);
  56.     }
  57.  
  58.     public void DFS(boolean[][] graph, int v){
  59.         Previsit(graph, v);
  60.         // mark the current node
  61.         visited[v] = true;
  62.         // find neighbor
  63.         for (int nextV = this.first(v); nextV < this.numVertices; nextV = this.next(v, nextV)) {
  64.             if (!visited[nextV]){
  65.                 DFS(graph, nextV);
  66.             }
  67.         }
  68.         Postvisit(graph, v);
  69.     }
  70.  
  71.     public void BFS(int v){
  72.         BFS(this.adjMatrix, v);
  73.     }
  74.  
  75.     public void BFS(boolean[][] graph, int v){
  76.         Queue<Integer> queue = new LinkedList<>();
  77.  
  78.         visited[v] = true;
  79.         queue.add(v);
  80.  
  81.         while(queue.peek() != null){
  82.             Integer currV = queue.remove();
  83.             Previsit(graph, currV);
  84.             for (int nextV = this.first(currV); nextV < this.numVertices; nextV = this.next(currV, nextV)) {
  85.                 if (!visited[nextV]) {
  86.                     visited[nextV] = true;
  87.                     queue.add(nextV);
  88.                 }
  89.             }
  90.             Postvisit(graph, currV);
  91.         }
  92.  
  93.     }
  94.  
  95.     private void Previsit(boolean[][] graph, int v) {
  96.         System.out.println("Previsit: " + v);
  97.     }
  98.  
  99.     private void Postvisit(boolean[][] graph, int v) {
  100.         System.out.println("Postvisit: " + v);
  101.     }
  102.  
  103.  
  104.     public String toString() {
  105.         StringBuilder s = new StringBuilder();
  106.         for (int i = 0; i < numVertices; i++) {
  107.             s.append(i + ": ");
  108.             for (boolean j : adjMatrix[i]) {
  109.                 s.append((j?1:0) + " ");
  110.             }
  111.             s.append("\n");
  112.         }
  113.         return s.toString();
  114.     }
  115.  
  116.     public static void main(String[] args) {
  117.         GraphAdjacentMatrix_DFS_BFS gam = new GraphAdjacentMatrix_DFS_BFS(7);
  118.  
  119.         gam.setEdge(1, 3);
  120.         gam.setEdge(3, 1);
  121.         gam.setEdge(1, 5);
  122.         gam.setEdge(5, 1);
  123.         gam.setEdge(2, 3);
  124.         gam.setEdge(3, 2);
  125.         gam.setEdge(3, 4);
  126.         gam.setEdge(4, 3);
  127.         gam.setEdge(3, 6);
  128.         gam.setEdge(6, 3);
  129.         gam.setEdge(2, 6);
  130.         gam.setEdge(6, 2);
  131.         gam.setEdge(4, 6);
  132.         gam.setEdge(6, 4);
  133.         gam.setEdge(5, 6);
  134.         gam.setEdge(6, 5);
  135.  
  136. //        System.out.println("DFS: ");
  137. //        gam.DFS( 1);
  138.         System.out.println("BFS: ");
  139.         gam.BFS(1);
  140.  
  141.         System.out.println();
  142.     }
  143.  
  144. }
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.

×