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 | import java.util.ArrayList;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.Stack;/** * Implementation of a directed unweighted Graph using Adjacency Matrix * * Complexity: addEdge, removeEdge, hasEdge O(1) / outEdges, inEdges O(n) / * Space O(n^2) */public class AdjMatrixGraph { int size; private boolean[][] matrix; public static final byte WHITE = 1; public static final byte GREY = 2; public AdjMatrixGraph(int size) { this.size = size; this.matrix = new boolean[size][size]; } public void addEdge(int nodeA, int nodeB) { matrix[nodeA][nodeB] = true; } public void removeEdge(int nodeA, int nodeB) { matrix[nodeA][nodeB] = false; } public boolean hasEdge(int nodeA, int nodeB) { return matrix[nodeA][nodeB]; } public List<Integer> outEdges(int i) { List<Integer> edges = new ArrayList<Integer>(); for (int j = 0; j < size; j++) { if (matrix[i][j]) { edges.add(j); } } return edges; } public List<Integer> inEdges(int i) { List<Integer> edges = new ArrayList<Integer>(); for (int j = 0; j < size; j++) { if (matrix[j][i]) { edges.add(j); } } return edges; } public int nVertices() { return size; } public void breadthFirstSearch(int root) { boolean[] seen = new boolean[nVertices()]; Queue<Integer> q = new LinkedList<Integer>(); q.add(root); seen[root] = true; while (!q.isEmpty()) { int i = q.remove(); for (Integer j : outEdges(i)) { if (!seen[j]) { q.add(j); seen[j] = true; } } } } public void depthFirstSearch(int r) { byte[] c = new byte[nVertices()]; Stack<Integer> s = new Stack<Integer>(); s.push(r); while (!s.isEmpty()) { int i = s.pop(); if (c[i] == WHITE) { c[i] = GREY; for (int j : outEdges(i)) s.push(j); } } } public static void main(String[] args) { AdjMatrixGraph graph = new AdjMatrixGraph(10); graph.addEdge(1, 3); graph.addEdge(2, 4); graph.addEdge(6, 8); graph.addEdge(3, 2); System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8)); System.out.println("Edge from 2 to 4 is : " + graph.hasEdge(2, 4)); System.out.println("Edge from 3 to 2 is : " + graph.hasEdge(3, 2)); System.out.println("Edge from 1 to 3 is : " + graph.hasEdge(1, 3)); graph.removeEdge(6, 8); System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8)); }} |
Output of this Program:
Edge from 6 to 8 is : true Edge from 2 to 4 is : true Edge from 3 to 2 is : true Edge from 1 to 3 is : true Edge from 6 to 8 is : false