Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit521e9af

Browse files
prashantdubeypngDivyansh1802
prashantdubeypng
andcommitted
feat: Add BreadthFirstSearch algorithm with proper structure and tests
- Removed incorrectly placed .class files and Main.java from root- Added BreadthFirstSearch.java with proper package structure- Implemented generic and integer-based BFS traversal methods- Added comprehensive test coverage in BreadthFirstSearchTest.java- Fixed bug in original BFS where 'src' was used instead of 'current' node- Follows project conventions and coding standardsFixesTheAlgorithms#7158Co-authored-by: Divyansh1802 <divyanshupadhyay1802@gmail.com>
1 parent43a7cf7 commit521e9af

File tree

5 files changed

+353
-0
lines changed

5 files changed

+353
-0
lines changed

‎Graph$Node.class‎

-378 Bytes
Binary file not shown.

‎Graph.class‎

-2.2 KB
Binary file not shown.

‎Main.class‎

-658 Bytes
Binary file not shown.
Lines changed: 182 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
packagecom.thealgorithms.datastructures.graphs;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.HashMap;
5+
importjava.util.HashSet;
6+
importjava.util.LinkedList;
7+
importjava.util.List;
8+
importjava.util.Map;
9+
importjava.util.Queue;
10+
importjava.util.Set;
11+
12+
/**
13+
* Breadth-First Search (BFS) algorithm for graph traversal.
14+
*
15+
* <p>
16+
* BFS is a graph traversal algorithm that explores all vertices at the present
17+
* depth level before moving on to vertices at the next depth level. It uses a
18+
* queue
19+
* data structure to keep track of vertices to visit.
20+
*
21+
* <p>
22+
* Time Complexity: O(V + E) where V is the number of vertices and E is the
23+
* number of edges.
24+
* Space Complexity: O(V) for the visited set and queue.
25+
*
26+
* <p>
27+
* References:
28+
* <ul>
29+
* <li>https://en.wikipedia.org/wiki/Breadth-first_search</li>
30+
* </ul>
31+
*
32+
* @author Divyansh1802
33+
* @author prashantdubeypng (fixes and refactoring)
34+
*/
35+
publicfinalclassBreadthFirstSearch {
36+
37+
privateBreadthFirstSearch() {
38+
// Utility class; do not instantiate.
39+
}
40+
41+
/**
42+
* Performs BFS traversal on a graph represented as an adjacency list.
43+
*
44+
* @param adjacencyList the graph represented as a map from vertex to list of
45+
* neighbors
46+
* @param source the starting vertex for traversal
47+
* @param <T> the type of vertices in the graph
48+
* @return a list of vertices in BFS order starting from the source
49+
* @throws IllegalArgumentException if source is null or not in the graph
50+
*/
51+
publicstatic <T>List<T>bfs(Map<T,List<T>>adjacencyList,Tsource) {
52+
if (source ==null) {
53+
thrownewIllegalArgumentException("Source vertex cannot be null");
54+
}
55+
if (adjacencyList ==null || !adjacencyList.containsKey(source)) {
56+
thrownewIllegalArgumentException("Source vertex must exist in the graph");
57+
}
58+
59+
List<T>result =newArrayList<>();
60+
Set<T>visited =newHashSet<>();
61+
Queue<T>queue =newLinkedList<>();
62+
63+
queue.offer(source);
64+
visited.add(source);
65+
66+
while (!queue.isEmpty()) {
67+
Tcurrent =queue.poll();
68+
result.add(current);
69+
70+
List<T>neighbors =adjacencyList.get(current);
71+
if (neighbors !=null) {
72+
for (Tneighbor :neighbors) {
73+
if (!visited.contains(neighbor)) {
74+
visited.add(neighbor);
75+
queue.offer(neighbor);
76+
}
77+
}
78+
}
79+
}
80+
81+
returnresult;
82+
}
83+
84+
/**
85+
* Performs BFS traversal on a graph represented using integer vertices.
86+
*
87+
* @param adjacencyList the graph represented as a list of lists of neighbors
88+
* @param numVertices the number of vertices in the graph
89+
* @param source the starting vertex for traversal (0-indexed)
90+
* @return a list of vertices in BFS order starting from the source
91+
* @throws IllegalArgumentException if source is out of bounds
92+
*/
93+
publicstaticList<Integer>bfs(List<List<Integer>>adjacencyList,intnumVertices,intsource) {
94+
if (source <0 ||source >=numVertices) {
95+
thrownewIllegalArgumentException("Source vertex is out of bounds");
96+
}
97+
if (adjacencyList ==null) {
98+
thrownewIllegalArgumentException("Adjacency list cannot be null");
99+
}
100+
101+
List<Integer>result =newArrayList<>();
102+
boolean[]visited =newboolean[numVertices];
103+
Queue<Integer>queue =newLinkedList<>();
104+
105+
queue.offer(source);
106+
visited[source] =true;
107+
108+
while (!queue.isEmpty()) {
109+
intcurrent =queue.poll();
110+
result.add(current);
111+
112+
if (current <adjacencyList.size()) {
113+
List<Integer>neighbors =adjacencyList.get(current);
114+
if (neighbors !=null) {
115+
for (intneighbor :neighbors) {
116+
if (neighbor >=0 &&neighbor <numVertices && !visited[neighbor]) {
117+
visited[neighbor] =true;
118+
queue.offer(neighbor);
119+
}
120+
}
121+
}
122+
}
123+
}
124+
125+
returnresult;
126+
}
127+
128+
/**
129+
* Creates an adjacency list graph from edges.
130+
*
131+
* @param numVertices the number of vertices
132+
* @param edges array of edges where each edge is {from, to}
133+
* @param undirected if true, adds edges in both directions
134+
* @return the adjacency list representation of the graph
135+
*/
136+
publicstaticList<List<Integer>>createGraph(intnumVertices,int[][]edges,booleanundirected) {
137+
List<List<Integer>>graph =newArrayList<>();
138+
for (inti =0;i <numVertices;i++) {
139+
graph.add(newArrayList<>());
140+
}
141+
142+
for (int[]edge :edges) {
143+
if (edge.length >=2) {
144+
intfrom =edge[0];
145+
intto =edge[1];
146+
if (from >=0 &&from <numVertices &&to >=0 &&to <numVertices) {
147+
graph.get(from).add(to);
148+
if (undirected) {
149+
graph.get(to).add(from);
150+
}
151+
}
152+
}
153+
}
154+
155+
returngraph;
156+
}
157+
158+
/**
159+
* Creates a Map-based adjacency list from string vertices.
160+
*
161+
* @param edges array of edges where each edge is {from, to}
162+
* @param undirected if true, adds edges in both directions
163+
* @return the adjacency list representation as a Map
164+
*/
165+
publicstaticMap<String,List<String>>createStringGraph(String[][]edges,booleanundirected) {
166+
Map<String,List<String>>graph =newHashMap<>();
167+
168+
for (String[]edge :edges) {
169+
if (edge.length >=2) {
170+
Stringfrom =edge[0];
171+
Stringto =edge[1];
172+
173+
graph.computeIfAbsent(from,k ->newArrayList<>()).add(to);
174+
if (undirected) {
175+
graph.computeIfAbsent(to,k ->newArrayList<>()).add(from);
176+
}
177+
}
178+
}
179+
180+
returngraph;
181+
}
182+
}
Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
packagecom.thealgorithms.datastructures.graphs;
2+
3+
importstaticorg.junit.jupiter.api.Assertions.assertEquals;
4+
importstaticorg.junit.jupiter.api.Assertions.assertThrows;
5+
importstaticorg.junit.jupiter.api.Assertions.assertTrue;
6+
7+
importjava.util.ArrayList;
8+
importjava.util.HashMap;
9+
importjava.util.List;
10+
importjava.util.Map;
11+
importorg.junit.jupiter.api.Test;
12+
13+
/**
14+
* Tests for {@link BreadthFirstSearch}.
15+
*/
16+
classBreadthFirstSearchTest {
17+
18+
@Test
19+
voidtestBfsWithIntegerGraphSimple() {
20+
// Create a simple graph: 0 -> 1 -> 2
21+
// | |
22+
// v v
23+
// 3 4
24+
int[][]edges = { {0,1 }, {0,3 }, {1,2 }, {1,4 } };
25+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(5,edges,false);
26+
27+
List<Integer>result =BreadthFirstSearch.bfs(graph,5,0);
28+
29+
assertEquals(5,result.size());
30+
assertEquals(0,result.get(0));// Source is first
31+
// BFS visits by level: 0 -> [1, 3] -> [2, 4]
32+
assertTrue(result.indexOf(1) <result.indexOf(2));// 1 before 2
33+
assertTrue(result.indexOf(1) <result.indexOf(4));// 1 before 4
34+
}
35+
36+
@Test
37+
voidtestBfsWithUndirectedGraph() {
38+
// Create an undirected graph
39+
int[][]edges = { {0,1 }, {1,2 }, {2,3 }, {3,4 } };
40+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(5,edges,true);
41+
42+
List<Integer>result =BreadthFirstSearch.bfs(graph,5,2);
43+
44+
assertEquals(5,result.size());
45+
assertEquals(2,result.get(0));// Source is first
46+
}
47+
48+
@Test
49+
voidtestBfsWithDisconnectedGraph() {
50+
// Graph with disconnected components: 0 -> 1, 2 -> 3 (separate components)
51+
int[][]edges = { {0,1 }, {2,3 } };
52+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(4,edges,false);
53+
54+
List<Integer>result =BreadthFirstSearch.bfs(graph,4,0);
55+
56+
// Should only visit reachable vertices from 0
57+
assertEquals(2,result.size());
58+
assertTrue(result.contains(0));
59+
assertTrue(result.contains(1));
60+
}
61+
62+
@Test
63+
voidtestBfsWithSingleVertex() {
64+
int[][]edges = {};
65+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(1,edges,false);
66+
67+
List<Integer>result =BreadthFirstSearch.bfs(graph,1,0);
68+
69+
assertEquals(1,result.size());
70+
assertEquals(0,result.get(0));
71+
}
72+
73+
@Test
74+
voidtestBfsWithCyclicGraph() {
75+
// Graph with a cycle: 0 -> 1 -> 2 -> 0
76+
int[][]edges = { {0,1 }, {1,2 }, {2,0 } };
77+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(3,edges,false);
78+
79+
List<Integer>result =BreadthFirstSearch.bfs(graph,3,0);
80+
81+
assertEquals(3,result.size());
82+
assertEquals(0,result.get(0));// Source is first
83+
}
84+
85+
@Test
86+
voidtestBfsWithMapBasedGraph() {
87+
Map<String,List<String>>graph =newHashMap<>();
88+
graph.put("A",List.of("B","C"));
89+
graph.put("B",List.of("D"));
90+
graph.put("C",List.of("E"));
91+
graph.put("D",newArrayList<>());
92+
graph.put("E",newArrayList<>());
93+
94+
List<String>result =BreadthFirstSearch.bfs(graph,"A");
95+
96+
assertEquals(5,result.size());
97+
assertEquals("A",result.get(0));// Source is first
98+
// B and C should come before D and E
99+
assertTrue(result.indexOf("B") <result.indexOf("D"));
100+
assertTrue(result.indexOf("C") <result.indexOf("E"));
101+
}
102+
103+
@Test
104+
voidtestBfsWithStringGraphCreation() {
105+
String[][]edges = { {"DELHI","MUMBAI" }, {"DELHI","PUNE" }, {"MUMBAI","GOA" } };
106+
Map<String,List<String>>graph =BreadthFirstSearch.createStringGraph(edges,true);
107+
108+
List<String>result =BreadthFirstSearch.bfs(graph,"DELHI");
109+
110+
assertEquals(4,result.size());
111+
assertEquals("DELHI",result.get(0));
112+
}
113+
114+
@Test
115+
voidtestBfsThrowsExceptionForNullSource() {
116+
Map<String,List<String>>graph =newHashMap<>();
117+
graph.put("A",List.of("B"));
118+
119+
assertThrows(IllegalArgumentException.class, () ->BreadthFirstSearch.bfs(graph,null));
120+
}
121+
122+
@Test
123+
voidtestBfsThrowsExceptionForSourceNotInGraph() {
124+
Map<String,List<String>>graph =newHashMap<>();
125+
graph.put("A",List.of("B"));
126+
127+
assertThrows(IllegalArgumentException.class, () ->BreadthFirstSearch.bfs(graph,"X"));
128+
}
129+
130+
@Test
131+
voidtestBfsThrowsExceptionForInvalidSourceIndex() {
132+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(3,newint[][] {},false);
133+
134+
assertThrows(IllegalArgumentException.class, () ->BreadthFirstSearch.bfs(graph,3, -1));
135+
assertThrows(IllegalArgumentException.class, () ->BreadthFirstSearch.bfs(graph,3,5));
136+
}
137+
138+
@Test
139+
voidtestBfsLevelOrderProperty() {
140+
// Test that BFS visits vertices level by level
141+
// 0
142+
// /|\
143+
// 1 2 3
144+
// | |
145+
// 4 5
146+
int[][]edges = { {0,1 }, {0,2 }, {0,3 }, {1,4 }, {3,5 } };
147+
List<List<Integer>>graph =BreadthFirstSearch.createGraph(6,edges,false);
148+
149+
List<Integer>result =BreadthFirstSearch.bfs(graph,6,0);
150+
151+
// Level 0: 0
152+
// Level 1: 1, 2, 3
153+
// Level 2: 4, 5
154+
assertEquals(0,result.get(0));
155+
// All level-1 vertices come before level-2 vertices
156+
intlevel1End =Math.max(result.indexOf(1),Math.max(result.indexOf(2),result.indexOf(3)));
157+
intlevel2Start =Math.min(result.indexOf(4),result.indexOf(5));
158+
assertTrue(level1End <level2Start);
159+
}
160+
161+
@Test
162+
voidtestBfsWithEmptyNeighborList() {
163+
Map<String,List<String>>graph =newHashMap<>();
164+
graph.put("A",newArrayList<>());
165+
166+
List<String>result =BreadthFirstSearch.bfs(graph,"A");
167+
168+
assertEquals(1,result.size());
169+
assertEquals("A",result.get(0));
170+
}
171+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp