编程人 cdmana.com

Data structure graph breadth first search algorithm (Java language)

  The detailed code can be seen in github:

https://github.com/AbitGo/myClassWork/tree/master/workspace_ds

How to realize breadth first search algorithm of graph

Detailed code implementation :

package com.company.ch6;

import com.company.ch3.queue.LinkSqeue;

public class GraphFS {
    private static boolean[] visited;

    // The implementation of breadth first search algorithm 
    public static void BFSTraverse(IGraph g) throws Exception {
        visited = new boolean[g.getVexNum()];
        // Initialize all , however java When initializing, it's all false
        for (int v = 0; v < g.getVexNum(); v++) {
            visited[v] = false;
        }
        for (int v = 0; v < g.getVexNum(); v++) {
            // If not currently accessed 
            if (visited[v] == false) {
                BFS(g,v);
            }
        }
        System.out.println();
    }

    public static void BFS(IGraph g,int v) throws Exception {
        // This node has been accessed 
        visited[v]=true;
        System.out.print(g.getVex(v).toString()+" ");
        // Create a queue 
        LinkSqeue linkSqeue = new LinkSqeue();
        // The team 
        linkSqeue.offer(v);
        // When the queue is not empty 
        while (!linkSqeue.isEmpty()){
            // Team leader element out of the team , And assign it to u
            int u = (Integer) linkSqeue.poll();
            //w For the first adjacent point , And read down in turn 
            for(int w = g.firstAdjVex(u);w>=0;w=g.nextAdjVex(u,w)){
                // When the front adjacent contact has not been read , Then we flip the State 
                if(!visited[w]){
                    visited[w]=true;
                    System.out.print(g.getVex(w).toString()+" ");
                    linkSqeue.offer(w);
                }
            }
        }
    }
}

Test class :

package com.company.ch6;

public class MGraphTest {
    public static void main(String[] args) throws Exception {
        // Undirected graph 
        Object[] param1_1_1= {"UDN",5,5,"ABCDE"};
        String[] param1_1_2 = {"AB1","BC2","AD3","AE4","CE5"};
        MGraph mGraph1 = new MGraph();
        mGraph1.createGraph(param1_1_1,param1_1_2);
        GraphFS.BFSTraverse(mGraph1);
        GraphFS.DFSTraverse(mGraph1);

        // Directed graph 
        Object[] param1_2_1= {"UDN",5,5,"ABCDE"};
        String[] param1_2_2 = {"AB1","BC2","AD3","AE4","CE5"};
        MGraph mGraph2 = new MGraph();
        mGraph2.createGraph(param1_2_1,param1_2_2);
        GraphFS.BFSTraverse(mGraph2);
        GraphFS.DFSTraverse(mGraph2);
    }
}

test result :

"C:\Program Files\Java\jdk1.8.0_101\bin\java.exe" 
 Create undirected network 
A B D E C 
A B C E D 
 Create undirected network 
A B D E C 
A B C E D 

 

Scroll to Top