fork(1) download 
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Queue;
  5. import java.util.Stack;
  6.  
  7. /**
  8.  * Implementation of a directed unweighted Graph using Adjacency Matrix
  9.  * 
  10.  * Complexity: addEdge, removeEdge, hasEdge O(1) / outEdges, inEdges O(n) /
  11.  * Space O(n^2)
  12.  */
  13. class AdjMatrixGraph {
  14. 	int size;
  15. 	private boolean[][] matrix;
  16. 	public static final byte WHITE = 1;
  17. 	public static final byte GREY = 2;
  18.  
  19. 	public AdjMatrixGraph(int size) {
  20. 		this.size = size;
  21. 		this.matrix = new boolean[size][size];
  22. 	}
  23.  
  24. 	public void addEdge(int nodeA, int nodeB) {
  25. 		matrix[nodeA][nodeB] = true;
  26. 	}
  27.  
  28. 	public void removeEdge(int nodeA, int nodeB) {
  29. 		matrix[nodeA][nodeB] = false;
  30. 	}
  31.  
  32. 	public boolean hasEdge(int nodeA, int nodeB) {
  33. 		return matrix[nodeA][nodeB];
  34. 	}
  35.  
  36. 	public List<Integer> outEdges(int i) {
  37. 		List<Integer> edges = new ArrayList<Integer>();
  38. 		for (int j = 0; j < size; j++) {
  39. 			if (matrix[i][j]) {
  40. 				edges.add(j);
  41. 			}
  42. 		}
  43. 		return edges;
  44. 	}
  45.  
  46. 	public List<Integer> inEdges(int i) {
  47. 		List<Integer> edges = new ArrayList<Integer>();
  48. 		for (int j = 0; j < size; j++) {
  49. 			if (matrix[j][i]) {
  50. 				edges.add(j);
  51. 			}
  52. 		}
  53. 		return edges;
  54. 	}
  55.  
  56. 	public int nVertices() {
  57. 		return size;
  58. 	}
  59.  
  60. 	public void breadthFirstSearch(int root) {
  61. 		boolean[] seen = new boolean[nVertices()];
  62. 		Queue<Integer> q = new LinkedList<Integer>();
  63. 		q.add(root);
  64. 		seen[root] = true;
  65. 		while (!q.isEmpty()) {
  66. 			int i = q.remove();
  67. 			for (Integer j : outEdges(i)) {
  68. 				if (!seen[j]) {
  69. 					q.add(j);
  70. 					seen[j] = true;
  71. 				}
  72. 			}
  73. 		}
  74. 	}
  75.  
  76. 	public void depthFirstSearch(int r) {
  77. 		byte[] c = new byte[nVertices()];
  78. 		Stack<Integer> s = new Stack<Integer>();
  79. 		s.push(r);
  80. 		while (!s.isEmpty()) {
  81. 			int i = s.pop();
  82. 			if (c[i] == WHITE) {
  83. 				c[i] = GREY;
  84. 				for (int j : outEdges(i))
  85. 					s.push(j);
  86. 			}
  87. 		}
  88. 	}
  89.  
  90. 	public static void main(String[] args) {
  91. 		AdjMatrixGraph graph = new AdjMatrixGraph(10);
  92.  
  93. 		graph.addEdge(1, 3);
  94. 		graph.addEdge(2, 4);
  95. 		graph.addEdge(6, 8);
  96. 		graph.addEdge(3, 2);
  97.  
  98. 		System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8));
  99. 		System.out.println("Edge from 2 to 4 is : " + graph.hasEdge(2, 4));
  100. 		System.out.println("Edge from 3 to 2 is : " + graph.hasEdge(3, 2));
  101. 		System.out.println("Edge from 1 to 3 is : " + graph.hasEdge(1, 3));
  102.  
  103. 		graph.removeEdge(6, 8);
  104. 		System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8));
  105.  
  106. 	}
  107. }
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
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
https://ideone.com/ZZm7rW
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!