Advertisement
Guest User

Graph

a guest
Dec 11th, 2013
476
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Graph<E> {
  2.  
  3.     int num_nodes;
  4.     GraphNode<E> adjList[];
  5.  
  6.     @SuppressWarnings("unchecked")
  7.     public Graph(int num_nodes, E[] list) {
  8.         this.num_nodes = num_nodes;
  9.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  10.         for (int i = 0; i < num_nodes; i++)
  11.             adjList[i] = new GraphNode<E>(i, list[i]);
  12.     }
  13.  
  14.     @SuppressWarnings("unchecked")
  15.     public Graph(int num_nodes) {
  16.         this.num_nodes = num_nodes;
  17.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  18.         for (int i = 0; i < num_nodes; i++)
  19.             adjList[i] = new GraphNode<E>(i, (E) new Object());
  20.     }
  21.  
  22.     int adjacent(int x, int y) {
  23.         return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  24.     }
  25.  
  26.     void addEdge(int x, int y) {
  27.         if (!adjList[x].containsNeighbor(adjList[y])) {
  28.             adjList[x].addNeighbor(adjList[y]);
  29.         }
  30.     }
  31.  
  32.     void deleteEdge(int x, int y) {
  33.         adjList[x].removeNeighbor(adjList[y]);
  34.     }
  35.  
  36.     void dfsNonrecursive(int node) {
  37.         boolean visited[] = new boolean[num_nodes];
  38.         for (int i = 0; i < num_nodes; i++)
  39.             visited[i] = false;
  40.         visited[node] = true;
  41.         System.out.println(node + ": " + adjList[0].getInfo());
  42.         Stack<Integer> s = new Stack<Integer>();
  43.         s.push(node);
  44.  
  45.         GraphNode<E> pom;
  46.  
  47.         while (!s.isEmpty()) {
  48.             pom = adjList[s.peek()];
  49.             GraphNode<E> tmp = null;
  50.             for (int i = 0; i < pom.getNeighbors().size(); i++) {
  51.                 tmp = pom.getNeighbors().get(i);
  52.                 if (!visited[tmp.getIndex()])
  53.                     break;
  54.             }
  55.             if (tmp != null && !visited[tmp.getIndex()]) {
  56.                 visited[tmp.getIndex()] = true;
  57.                 System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
  58.                 s.push(tmp.getIndex());
  59.             } else
  60.                 s.pop();
  61.         }
  62.     }
  63.  
  64.     @Override
  65.     public String toString() {
  66.         String ret = new String();
  67.         for (int i = 0; i < this.num_nodes; i++)
  68.             ret += i + ": " + adjList[i] + "\n";
  69.         return ret;
  70.     }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement