搜尋此網誌

2012年5月22日 星期二

BFS implementation using queue and adjacency list

package graph;

import java.util.LinkedList;
import java.util.Queue;



public class BFS {
    
    public static int graph [][] = {
        {1,2},//0
        {0,3,4},//1
        {0,5,6},//2
        {1,7},//3
        {1,7},//4
        {2,7},//5
        {2,7},//6
        {3,4,5,6}//7
    };
    
    static Queue outPut = new LinkedList();
    static int visited [] = {-1,-1,-1,-1,-1,-1,-1,-1};//Initialize all unvisited.
    
    public static int [] findNeighbours(int v){
        return graph[v];
    }
    
    public static boolean isVisited(int v){
            if(visited[v]==1){
                return true;
            }else{
                return false;
            }
    }
    
    public static void main(String[] args) throws InterruptedException{
        outPut.offer(0);
        while(!outPut.isEmpty()){
            int vertex = (Integer)outPut.poll();
            if(!isVisited(vertex)){
                visited[vertex]=1;
                System.out.print(vertex);
                int neighbours []= findNeighbours(vertex);
                for(int i = 0 ;i<neighbours.length;i++){
                    if(!isVisited(neighbours[i])){
                        outPut.offer(neighbours[i]);
                    }
                }
                
            }
            
        }
        
        
    }
    

}

沒有留言:

張貼留言