I tried to make a bfs implementation without using LinkedList and Iterator build-in class in java. The first thing i did was make a linklist class manually, and i think there is no problem. The second thing was make a graph class and i think there is no problem too because when i checked the graph representation output using adjacency list, everything is working fine. And the last thing was make a bfs method where the problem occur, when i checked the output it becomes a dfs, not bfs. Can anyone help me answer my question, i have stuck one day to think the solution, and i have tried many things too but it didnt work. Thank you.
This is my LinkList and Vertex class
class Vertex {
int vertex;
Vertex next;
public Vertex(int vertex){
this.vertex = vertex;
}
}
class LinkList {
Vertex first;
int nElement;
public LinkList(){
this.first = null;
this.nElement = 0;
}
public boolean isEmpty(){
return this.first == null;
}
public int size(){
return nElement;
}
public void insertFirst(Vertex input){
input.next = this.first;
this.first = input;
}
public void add(Vertex input){
if(this.isEmpty()){
this.insertFirst(input);
} else {
Vertex temp = this.first;
while(temp.next != null){
temp = temp.next;
}
temp.next = input;
}
nElement++;
}
public Vertex poll(){
Vertex temp = this.first;
this.first = this.first.next;
nElement--;
return temp;
}
public void printList(){
Vertex temp = this.first;
while(temp != null){
System.out.print(" -> " + temp.vertex);
temp = temp.next;
}
}
}
This is my Graph class
class Graph {
int N;
LinkList[] graphArray;
public Graph(int N){
this.N = N;
graphArray = new LinkList[N];
for(int i = 0; i < N; i++){
graphArray[i] = new LinkList();
}
}
public void addEdge(int from, int to) {
Vertex vertexFrom = new Vertex(from);
Vertex vertexTo = new Vertex(to);
graphArray[from].add(vertexTo);
graphArray[to].add(vertexFrom);
}
public void printGraphList(){
for(int n = 0; n < N; n++){
System.out.print("Adjacency list node-" + n);
System.out.print(": head");
graphArray[n].printList();
System.out.println("");
}
System.out.println("");
}
public void bfs(int start){
boolean[] visited = new boolean[N];
LinkList queue = new LinkList();
Vertex vertexStart = new Vertex(start);
visited[start] = true;
queue.add(vertexStart);
System.out.print("\nBFS : ");
while(queue.size() != 0){
vertexStart = queue.poll();
start = vertexStart.vertex;
System.out.print(start + " ");
LinkList list = graphArray[start];
Vertex temp = list.first;
while(temp != null){
int n = temp.vertex;
System.out.println(n);
if(!visited[n]){
visited[n] = true;
queue.add(temp);
}
temp = temp.next;
}
}
System.out.println("");
}
}
This is my bfs method where the problem happening
public void bfs(int start){
boolean[] visited = new boolean[N];
LinkList queue = new LinkList();
Vertex vertexStart = new Vertex(start);
visited[start] = true;
queue.add(vertexStart);
System.out.print("\nBFS : ");
while(queue.size() != 0){
vertexStart = queue.poll();
start = vertexStart.vertex;
System.out.print(start + " ");
LinkList list = graphArray[start];
Vertex temp = list.first;
while(temp != null){
int n = temp.vertex;
if(!visited[n]){
visited[n] = true;
queue.add(temp);
}
temp = temp.next;
}
}
System.out.println("");
}