1. Basic introduction of figure

1.1 definition of drawing

• A graph is a data structure in which a node can have zero or more adjacent elements. The connection between two nodes is called an edge. Nodes can also be called vertices.

• Undirected graph: the connection between vertices has no direction, such as A-B, that is, a - > b or B - > a. the undirected graph is as follows
  

• Directed graph: the connection between vertices has directions, such as A-B, which can only be a - > 8, not B - > a. the directed weighted graph is as follows

1.2 representation of drawings

• There are two representations of graphs: two-dimensional array representation (adjacency matrix); Linked list representation (adjacency list).

• adjacency matrix

  • Adjacency matrix is a matrix that represents the adjacency relationship between vertices in a graph. For a graph with n vertices, row and col represent 1... N points.

• Adjacency table

  • Adjacency matrix needs to allocate n edge spaces for each vertex. In fact, many edges do not exist, which will cause a certain loss of space
  • The implementation of adjacency table only cares about the existing edge, not the nonexistent edge. Therefore, there is no waste of space. The adjacency table is composed of array + linked list

2. Introduction to depth first traversal of graph

2.1 introduction to graph traversal

• The so-called graph traversal is the access to nodes. There are so many nodes in a graph. How to traverse these nodes requires specific policies. Generally, there are two access policies:
  • Depth first traversal
  • breadth-first search

2.2 basic idea of depth first traversal

• Depth first search of graph. [dfs]
  • Depth first traversal: starting from the initial access node, the initial access node may have multiple adjacent nodes. The strategy of depth first traversal is to first access the first adjacent node, and then use the accessed adjacent node as the initial node to access its first adjacent node, It can be understood as follows: after accessing the current node every time, first access the first adjacent node of the current node.
  • It can be seen that such an access strategy is to give priority to vertical mining, rather than horizontal access to all adjacent nodes of a node.
  • Obviously, depth first search is a recursive process

2.3 depth first traversal algorithm steps

• Access the initial node v and mark node v as accessed.
• Find the first adjacent node w of node v.
• If w exists, continue to execute 4. If w does not exist, return to step 1 and continue from the next node of v.
• If W is not accessed, perform depth first traversal recursion on w (that is, treat w as another v, and then proceed to step 123)
• If W has been accessed, find the next adjacent node of the w adjacent node of node v and go to step 3.

3. Breadth first traversal of Graphs

3.1 basic idea of breadth first traversal

• Broad first search of graph. [bfs]
  • Similar to a hierarchical search process, breadth first traversal needs to use a queue to maintain the order of visited nodes, so as to access the adjacent nodes of these nodes in this order

3.2 breadth first traversal algorithm steps

• Visit the initial node v and mark node v as accessed.
• Node v in queue
• When the queue is not empty, continue to execute, otherwise the algorithm ends.
• Get out of the queue and get the queue head node u.
• Find the first adjacent node w of node u.
• If the adjacent node w of node u does not exist, go to step 3; Otherwise, the loop performs the following three steps:
  • If node w has not been accessed, access node W and mark it as accessed.
  • Node w in queue
  • Find the next adjacent node w of node u after the adjacent node W, and go to step 6.

4. Application example of figure

• Requirements: the code structure is shown in the figure below and traversal is realized
  

• Train of thought analysis

  • Store vertex String, using ArrayList
  • Save matrix int [] [] edges
  • Depth first traversal of Graphs
  • Breadth first traversal of Graphs

• code implementation

public class Graph {

    private final ArrayList<String> vertexList; //Store a collection of vertices
    private final int[][] edges; //Storage graph corresponding adjacency matrix
    private int numOfEdges; //Indicates the number of edges
    //Define the boolean [] array to record whether a node is accessed
    private boolean[] isVisited;

    public static void main(String[] args) {
        //Creation of test chart
        int n = 5; //Number of nodes
        String[] vertexs = {"A", "B", "C", "D", "E"};
        //Create graph object
        Graph graph = new Graph(n);
        //Adding vertices to a loop
        for (String vertex : vertexs) {
            graph.insertVertex(vertex);
        }
        //Add edge
        graph.insertEdge(0, 1, 1); //A-B
        graph.insertEdge(0, 2, 1); //A-C
        graph.insertEdge(1, 2, 1); //B-C
        graph.insertEdge(1, 3, 1); //B-D
        graph.insertEdge(1, 4, 1); //B-E

        //Display adjacency matrix
        graph.showGraph();

        //Test dfs traversal
        System.out.println("Depth first traversal");
        graph.dfs();

        System.out.println();
        //Test bfs traversal
        System.out.println("breadth-first search ");
        graph.bfs();
    }

    //constructor 
    //Number of n vertices
    public Graph(int n) {
        //Initialize matrix and vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
        //isVisited = new boolean[n];
    }

	
    //Common methods in Figure
    //Returns the number of nodes
    public int getNumOfVertex() {
        return vertexList.size();
    }

    //Get the number of edges
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //Return the data corresponding to node i (subscript): 0 - > "a" 1 - > "B" 2 - > "C"
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //Returns the weights of v1 and v2
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    //Display the matrix corresponding to the figure
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    //Insert Vertex 
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    //Add edge
    /**
     * @param v1     Indicates the subscript of the first point, that is, the number of vertices "a" - "B"'a '- > 0' B '- > 1
     * @param v2     Indicates the subscript corresponding to the second vertex
     * @param weight Representation weight
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    //Get the subscript w of the first adjacent node
    /**
     * @param index Subscript of current node
     * @return If it exists, it returns the corresponding subscript; otherwise, it returns - 1
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    //Obtain the next adjacent node according to the subscript of the previous adjacent node
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    //Depth first traversal algorithm
    //i is 0 for the first time
    public void dfs(boolean[] isVisited, int i) {
        //First access the node and output
        System.out.print(getValueByIndex(i) + "->");
        //Set the node as accessed
        isVisited[i] = true;

        // Find the first adjacent node w of node i
        int w = getFirstNeighbor(i);
        while (w != -1) { //Indicates that there are adjacent nodes
            if (!isVisited[w]) { //Not accessed
                dfs(isVisited, w);
            }
            //If node w has been accessed
            w = getNextNeighbor(i, w);
        }
    }

    //Reload dfs, traverse all nodes, and perform dfs
    private void dfs() {
        isVisited = new boolean[5];
        //Traverse all nodes and perform dfs [backtracking]
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    //A method of breadth first traversal of a node
    private void bfs(boolean[] isVisited, int i) {
        int u; //Indicates the subscript corresponding to the head node of the queue
        int w; //Represents the adjacent node w
        //Queue, which records the access order of nodes
        LinkedList queue = new LinkedList();
        //Access node and output node information
        System.out.print(getValueByIndex(i) + "=>");
        //Mark as accessed
        isVisited[i] = true;
        //Add node to queue
        queue.addLast(i);

        while (!queue.isEmpty()) {
            //Take out the subscript of the header node of the queue
            u = (Integer) queue.removeFirst();
            //Get the subscript w of the first adjacent node
            w = getFirstNeighbor(u);
            while (w != -1) { //find
                //Have you visited
                if (!isVisited[w]) {
                    System.out.print (getValueByIndex(w) + "=>");
                    //Mark has been accessed
                    isVisited[w] = true;
                    //Queue
                    queue.addLast(w);
                }
                //If visited, take u as the leading point and find the next adjacent node after w
                w = getNextNeighbor(u, w); //Reflect breadth first
            }
        }
    }

    //Traverse all nodes and conduct breadth first search
    public void bfs(){
        isVisited = new boolean[5];
        for (int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]){
                bfs(isVisited,i);
            }

        }
    }
}