0

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("");
    }
  • Try using a [debugger](https://stackoverflow.com/q/25385173/16653700) to run through your program and find out why your traversal isn't dfs. – Alias Cartellano Apr 14 '22 at 22:54
  • 1
    Welcome to SO. Please read the help about how to ask a question. If you provide a minimal complete, runnable program that has the problem you're seeing, you're much more likely to get the help you want. Expecting people to study big chunks of code to figure out your error won't often succeed. As others have said, when a program doesn't work, there's a gap between what's in your head and what the code is doing. Ways to narrow the gap are (with small example data) - 1) careful manual stepping 2) printing intermediate values 3) using a debugger. – Gene Apr 15 '22 at 01:26
  • To do BSF you need to enter into the queue only the adjacent neighbors. It seems that you are adding also "deeper" members by fetching `temp = temp.next;` – c0der Apr 20 '22 at 11:15

0 Answers0