Skip to content

Commit 2d47ce6

Browse files
realDuYuanChaorealDuYuanChao
authored
update DFS | BFS (examplehub#146)
1 parent 2005cf7 commit 2d47ce6

2 files changed

Lines changed: 92 additions & 25 deletions

File tree

‎src/main/java/com/examplehub/datastructures/graph/AdjacencyMatrix.java‎

Lines changed: 44 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,75 +1,94 @@
11
package com.examplehub.datastructures.graph;
22

3-
import java.util.ArrayList;
4-
import java.util.List;
5-
import java.util.Stack;
6-
import java.util.StringJoiner;
3+
import java.util.*;
74

85
public class AdjacencyMatrix<E> {
96
private final E[] vertex;
107
private final int[][] adj;
11-
private final boolean[] visited;
128
int numOfVertex;
139

1410
public AdjacencyMatrix(E[] vertex) {
1511
this.vertex = vertex;
1612
this.numOfVertex = vertex.length;
1713
this.adj = new int[numOfVertex][numOfVertex];
18-
this.visited = new boolean[numOfVertex];
1914
}
2015

2116
public AdjacencyMatrix(E[] vertex, int[][] adj) {
2217
this.vertex = vertex;
2318
this.adj = adj;
2419
this.numOfVertex = vertex.length;
25-
this.visited = new boolean[numOfVertex];
2620
}
2721

2822
public void addEdge(int i, int j) {
2923
adj[i][j] = adj[j][i] = 1;
3024
}
3125

32-
public void deepFirstSearch(StringJoiner joiner, int start) {
26+
public void removeEdge(int i, int j) {
27+
adj[i][j] = adj[j][i] = 0;
28+
}
29+
30+
public void deepFirstSearch(StringJoiner joiner, int start, boolean[] visited) {
3331
joiner.add(vertex[start].toString());
3432
visited[start] = true;
3533
for (int i = 0; i < numOfVertex; ++i) {
3634
if (adj[start][i] == 1 && !visited[i]) {
37-
deepFirstSearch(joiner, i);
35+
deepFirstSearch(joiner, i, visited);
3836
}
3937
}
4038
}
4139

42-
public int getVertexDegree(E v) {
43-
int row = -1;
44-
for (int i = 0; i < numOfVertex; i++) {
40+
private int getVertexIndex(E v) {
41+
for (int i = 0; i < numOfVertex; ++i) {
4542
if (vertex[i].equals(v)) {
46-
row = i;
43+
return i;
4744
}
4845
}
46+
return -1;
47+
}
48+
49+
public int getVertexDegree(E v) {
50+
int index = getVertexIndex(v);
4951
int sum = 0;
50-
for (int i = 0; i < numOfVertex; ++i) {
51-
sum += adj[row][i];
52+
for (int j = 0; j < numOfVertex; ++j) {
53+
sum += adj[index][j];
5254
}
5355
return sum;
5456
}
5557

5658
public String dfsPath() {
5759
StringJoiner joiner = new StringJoiner("->");
58-
deepFirstSearch(joiner, 0);
60+
boolean[] visited = new boolean[numOfVertex];
61+
deepFirstSearch(joiner, 0, visited);
5962
return joiner.toString();
6063
}
6164

62-
List<String> findAllPath(E startVertex, E endVertex) {
63-
int start = -1;
64-
int end = -1;
65-
for (int i = 0; i < numOfVertex; ++i) {
66-
if (startVertex == vertex[i]) {
67-
start = i;
68-
}
69-
if (endVertex == vertex[i]) {
70-
end = i;
65+
public String bfsPath() {
66+
StringJoiner joiner = new StringJoiner("->");
67+
boolean visited[] = new boolean[numOfVertex];
68+
breadthFirstSearch(joiner, 0);
69+
return joiner.toString();
70+
}
71+
72+
private void breadthFirstSearch(StringJoiner joiner, int start) {
73+
boolean[] visited = new boolean[numOfVertex];
74+
Queue<Integer> queue = new LinkedList<>();
75+
queue.offer(start);
76+
visited[start] = true;
77+
while (!queue.isEmpty()) {
78+
int popIndex = queue.poll();
79+
joiner.add(vertex[popIndex].toString());
80+
for (int j = 0; j < numOfVertex; ++j) {
81+
if (adj[popIndex][j] == 1 && !visited[j]) {
82+
queue.offer(j);
83+
visited[j] = true;
84+
}
7185
}
7286
}
87+
}
88+
89+
List<String> findAllPath(E startVertex, E endVertex) {
90+
int start = getVertexIndex(startVertex);
91+
int end = getVertexIndex(endVertex);
7392
return (start == -1 || end == -1) ? null : findAllPath(start, end);
7493
}
7594

‎src/test/java/com/examplehub/datastructures/graph/AdjacencyMatrixTest.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -66,4 +66,52 @@ void testFindAllPath() {
6666

6767
assertNull(adjacencyMatrix.findAllPath("A", "F"));
6868
}
69+
70+
@Test
71+
void testAddEdge() {
72+
String[] vertex = {"A", "B", "C", "D", "E"};
73+
AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
74+
adjacencyMatrix.addEdge(0, 1); /* A - B */
75+
adjacencyMatrix.addEdge(0, 2); /* A - C */
76+
adjacencyMatrix.addEdge(0, 3); /* A - D */
77+
adjacencyMatrix.addEdge(1, 3); /* B - D */
78+
adjacencyMatrix.addEdge(2, 3); /* C - D */
79+
adjacencyMatrix.addEdge(1, 4); /* B - E */
80+
adjacencyMatrix.addEdge(3, 4); /* D - E */
81+
82+
adjacencyMatrix.addEdge(1, 2); /* B - C */
83+
assertEquals("A->B->C->D->E", adjacencyMatrix.dfsPath());
84+
}
85+
86+
@Test
87+
void testRemoveEdge() {
88+
String[] vertex = {"A", "B", "C", "D", "E"};
89+
AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
90+
adjacencyMatrix.addEdge(0, 1); /* A - B */
91+
adjacencyMatrix.addEdge(0, 2); /* A - C */
92+
adjacencyMatrix.addEdge(0, 3); /* A - D */
93+
adjacencyMatrix.addEdge(1, 3); /* B - D */
94+
adjacencyMatrix.addEdge(2, 3); /* C - D */
95+
adjacencyMatrix.addEdge(1, 4); /* B - E */
96+
adjacencyMatrix.addEdge(3, 4); /* D - E */
97+
98+
adjacencyMatrix.removeEdge(0, 1);
99+
adjacencyMatrix.removeEdge(0, 2);
100+
assertEquals("A->D->B->E->C", adjacencyMatrix.dfsPath());
101+
}
102+
103+
@Test
104+
void testBFS() {
105+
String[] vertex = {"A", "B", "C", "D", "E"};
106+
AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
107+
adjacencyMatrix.addEdge(0, 1); /* A - B */
108+
adjacencyMatrix.addEdge(0, 2); /* A - C */
109+
adjacencyMatrix.addEdge(0, 3); /* A - D */
110+
adjacencyMatrix.addEdge(1, 3); /* B - D */
111+
adjacencyMatrix.addEdge(2, 3); /* C - D */
112+
adjacencyMatrix.addEdge(1, 4); /* B - E */
113+
adjacencyMatrix.addEdge(3, 4); /* D - E */
114+
115+
assertEquals("A->B->C->D->E", adjacencyMatrix.bfsPath());
116+
}
69117
}

0 commit comments

Comments
 (0)