FilesExpand file tree

 main

/

BFSIterative.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

48 lines (48 loc) · 1.57 KB

 main

/

BFSIterative.java

Top

File metadata and controls

• Code
• Blame

48 lines (48 loc) · 1.57 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.*;

public class BFSIterative {

static class Graph {

private final List<List<Integer>> adjList;

public Graph(int vertices) {

adjList = new ArrayList<>();

for (int i = 0; i < vertices; i++) {

adjList.add(new ArrayList<>());

}

}

public void addEdge(int src, int dest) {

adjList.get(src).add(dest);

adjList.get(dest).add(src); // For undirected graph

}

public void bfs(int start) {

boolean[] visited = new boolean[adjList.size()];

Queue<Integer> queue = new LinkedList<>();

visited[start] = true;

queue.add(start);

while (!queue.isEmpty()) {

int node = queue.poll();

System.out.print(node + " ");

for (int neighbor : adjList.get(node)) {

if (!visited[neighbor]) {

visited[neighbor] = true;

queue.add(neighbor);

}

}

}

}

}

public static void main(String[] args) {

Graph graph = new Graph(13);

graph.addEdge(1, 2);

graph.addEdge(1, 3);

graph.addEdge(1, 4);

graph.addEdge(2, 5);

graph.addEdge(2, 6);

graph.addEdge(5, 9);

graph.addEdge(5, 10);

graph.addEdge(4, 7);

graph.addEdge(4, 8);

graph.addEdge(7, 11);

graph.addEdge(7, 12);

System.out.println("Breadth-First Search (starting from node 0):");

graph.bfs(1);

}

}