编程人 cdmana.com

Data structure graph depth first search algorithm (Java language)

  The detailed code can be seen in github:

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

How to implement depth 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 depth first search algorithm 
    public static void DFSTraverse(IGraph g)throws Exception{
        visited = new boolean[g.getVexNum()];
        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) {
                DFS(g,v);
            }
        }
        System.out.println();
    }

    public static void DFS(IGraph g,int v) throws Exception {
        // This node has been accessed 
        visited[v]=true;
        System.out.print(g.getVex(v).toString()+" ");
        for(int w = g.firstAdjVex(v);w>=0;w=g.nextAdjVex(v,w)){
            if(!visited[w]){
                DFS(g,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