@Test public void testBfs() { System.out.println("bfs sort"); int[] ts = {0, 8, 1, 2, 7, 3, 6, 5, 4, 9, 10, 11, 12}; Graph graph = new AdjacencyMatrix(13, true); graph.addEdge(8, 7); graph.addEdge(7, 6); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(0, 3); graph.addEdge(0, 5); graph.addEdge(0, 6); graph.addEdge(2, 3); graph.addEdge(3, 4); graph.addEdge(3, 5); graph.addEdge(6, 4); graph.addEdge(6, 9); graph.addEdge(4, 9); graph.addEdge(9, 10); graph.addEdge(9, 11); graph.addEdge(9, 12); graph.addEdge(11, 12); assertTrue(Arrays.equals(ts, graph.sortbfs())); }
private void bfs(int v, int[] cc, int id) { cc[v] = id; Queue<Integer> queue = new LinkedList<>(); queue.offer(v); while (!queue.isEmpty()) { int t = queue.poll(); for (int i = 0; i < n; i++) { if (graph[t][i] != 0.0 && cc[i] == -1) { queue.offer(i); cc[i] = id; } } } }
AdjacencyMatrix implements Graph { private void bfs(int v, int[] cc, int id) { cc[v] = id; Queue<Integer> queue = new LinkedList<>(); queue.offer(v); while (!queue.isEmpty()) { int t = queue.poll(); for (int i = 0; i < n; i++) { if (graph[t][i] != 0.0 && cc[i] == -1) { queue.offer(i); cc[i] = id; } } } } }
AdjacencyMatrix implements Graph { private void bfs(int v, int[] cc, int id) { cc[v] = id; Queue<Integer> queue = new LinkedList<>(); queue.offer(v); while (!queue.isEmpty()) { int t = queue.poll(); for (int i = 0; i < n; i++) { if (graph[t][i] != 0.0 && cc[i] == -1) { queue.offer(i); cc[i] = id; } } } } AdjacencyMatrix(int n);  AdjacencyMatrix(int n, boolean digraph); }
AdjacencyMatrix implements Graph { private void bfs(int v, int[] cc, int id) { cc[v] = id; Queue<Integer> queue = new LinkedList<>(); queue.offer(v); while (!queue.isEmpty()) { int t = queue.poll(); for (int i = 0; i < n; i++) { if (graph[t][i] != 0.0 && cc[i] == -1) { queue.offer(i); cc[i] = id; } } } } AdjacencyMatrix(int n);  AdjacencyMatrix(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyMatrix setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); double[] dijkstra(int s, boolean weighted); @Override AdjacencyMatrix subgraph(int[] vertices); double[][] toArray(); double pushRelabel(double[][] flow, int source, int sink); @Override Matrix toMatrix(); }
AdjacencyMatrix implements Graph { private void bfs(int v, int[] cc, int id) { cc[v] = id; Queue<Integer> queue = new LinkedList<>(); queue.offer(v); while (!queue.isEmpty()) { int t = queue.poll(); for (int i = 0; i < n; i++) { if (graph[t][i] != 0.0 && cc[i] == -1) { queue.offer(i); cc[i] = id; } } } } AdjacencyMatrix(int n);  AdjacencyMatrix(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyMatrix setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); double[] dijkstra(int s, boolean weighted); @Override AdjacencyMatrix subgraph(int[] vertices); double[][] toArray(); double pushRelabel(double[][] flow, int source, int sink); @Override Matrix toMatrix();  }