Depth first traversal based on adjacency table

One   Diagram to create

Two   Code

package graph;

import java.util.Scanner;

public class DFSAL {
    static final int MaxVnum = 100;  //  Maximum number of vertices 
    //  Access flag array , Its initial value is "false"
    static Boolean visited[] = new Boolean[MaxVnum];

    static {
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
    }

    static int locatevex(DFSAL.ALGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) //  Find the subscript of vertex information 
            if (x == G.Vex[i].data)
                return i;
        return -1; //  Did not find 
    }

    //  Insert an edge 
    static void insertedge(DFSAL.ALGraph G, int i, int j) {
        graph.AdjNode s = new graph.AdjNode();
        s.v = j;
        s.next = G.Vex[i].first;
        G.Vex[i].first = s;
    }

    //  Create a directed graph adjacency table 
    static void CreateALGraph(DFSAL.ALGraph G) {
        int i, j;
        char u, v;

        System.out.println(" Please enter the number of vertices and edges :");
        Scanner scanner = new Scanner(System.in);
        G.vexnum = scanner.nextInt();
        G.edgenum = scanner.nextInt();
        System.out.println(" Please enter vertex information :");

        for (i = 0; i < G.vexnum; i++)// Enter vertex information , Store vertex information array 
            G.Vex[i].data = scanner.next().charAt(0);
        for (i = 0; i < G.vexnum; i++)
            G.Vex[i].first = null;
        System.out.println(" Please enter two vertices of each edge in turn u,v");

        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            i = locatevex(G, u); //  Find vertices  u  Storage subscript for 
            j = locatevex(G, v); //  Find vertices  v  Storage subscript for 
            if (i != -1 && j != -1)
                insertedge(G, i, j);
            else {
                System.out.println(" Input vertex information error ！ Please re-enter ！");
                G.edgenum++; //  This input does not count 
            }
        }
    }

    //  Output adjacency table 
    static void printg(DFSAL.ALGraph G) {
        System.out.println("---------- The adjacency table is as follows ：----------");
        for (int i = 0; i < G.vexnum; i++) {
            graph.AdjNode t = G.Vex[i].first;
            System.out.print(G.Vex[i].data + "：  ");
            while (t != null) {
                System.out.print("[" + t.v + "]\t");
                t = t.next;
            }
            System.out.println();
        }
    }

    static void dfsAl(ALGraph G, int v) {// Depth first traversal based on adjacency table 
        int w;
        graph.AdjNode p;
        System.out.println(G.Vex[v].data + "\t");

        visited[v] = true;
        p = G.Vex[v].first;
        //  Check in turn  v  All the adjacency points of 
        while (p != null) {
            w = p.v; // w  by  v  The adjacency point 
            if (!visited[w]) // w  Not visited 
                dfsAl(G, w);//  from  w  set out , Recursive depth first traversal 
            p = p.next;
        }
    }

    public static void main(String[] args) {
        DFSAL.ALGraph G = new DFSAL.ALGraph();
        for (int i = 0; i < G.Vex.length; i++) {
            G.Vex[i] = new graph.VexNode();
        }
        CreateALGraph(G); //  Create a directed graph adjacency table 
        printg(G); //  Output adjacency table 
        System.out.println(" Please enter the starting point of the traversal graph ：");
        Scanner scanner = new Scanner(System.in);
        char c = scanner.next().charAt(0);
        int v = locatevex(G, c);// Find vertices u Storage subscript for 
        if (v != -1) {
            System.out.println(" Breadth first search traversal graph results ：");
            dfsAl(G, v);
        } else
            System.out.println(" Input vertex information error ！ Please re-enter ！");
    }

    //  Define the adjacent contact type 
    static class AdjNode {
        int v; //  Adjacency subscript 
        graph.AdjNode next; //  Point to the next adjacent point 
    }

    //  Define vertex types 
    static class VexNode {
        char data; // VexType Is the data type of the vertex , Defined as needed 
        graph.AdjNode first; //  Point to the first adjacent contact 
    }

    //  Define adjacency table types 
    static class ALGraph {
        graph.VexNode Vex[] = new graph.VexNode[CreateALGraph.MaxVnum];
        int vexnum; //  Number of vertices 
        int edgenum; //  Number of edges 
    }
}

3、 ... and   test