Data Structures – Graphs (Depth First Traversal and Breadth First Traversal) (Java)

Data Structures – Graphs (Depth First Traversal and Breadth First Traversal) (Java)

<!-- more -->

Blog Description

The information involved in the article comes from the Internet and personal summary, which is intended to summarize personal learning and experience. If there is any infringement, please contact me to delete it, thank you!

Common Concepts of Graphs

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.

  • vertex
  • edge
  • path
  • Undirected graph

  • directed graph

  • weighted graph

representation of the graph

There are two ways to represent graphs: two-dimensional array representation (adjacency matrix); linked list representation (adjacency list).

adjacency matrix

The adjacency matrix is ​​a matrix that represents the adjacent relationship between vertices in the graph. For a graph of n vertices, the matrix is ​​row and col represent 1....n points.

adjacency list

The adjacency matrix needs to allocate n edge space for each vertex. In fact, many edges do not exist, which will cause a certain loss of space.

The implementation of the adjacency list only cares about the edges that exist, not the edges that don't exist. So no space is wasted, the adjacency list consists of array + linked list

Code

package com.guizimo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

    private ArrayList<String> vertexList; 
    private int[][] edges; 
    private int numOfEdges; 
    private boolean[] isVisited;
    
    public static void main(String[] args) {

        int n = 8;
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
        Graph graph = new Graph(n);
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }
        
        //Insert a node into the graph
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        //Traversal graph
        graph.showGraph();
        
        System.out.println("breadth-first traversal
        graph.dfs(); 
        System.out.println("depth-first traversal
        graph.bfs();
        
    }
    
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
    }
    

    public int getFirstNeighbor(int index) {
        for(int j = 0; j < vertexList.size(); j++) {
            if(edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    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
    private void dfs(boolean[] isVisited, int i) {
        System.out.print(getValueByIndex(i) + "->");
        isVisited[i] = true;
        int w = getFirstNeighbor(i);
        while(w != -1) {
            if(!isVisited[w]) {
                dfs(isVisited, w);
            }
            w = getNextNeighbor(i, w);
        }
        
    }
    
    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }
    
    //breadth-first traversal
    private void bfs(boolean[] isVisited, int i) {
        int u ; 
        int w ; 
        LinkedList queue = new LinkedList();
        System.out.print(getValueByIndex(i) + "=>");
        isVisited[i] = true;
        queue.addLast(i);
        
        while( !queue.isEmpty()) {
            u = (Integer)queue.removeFirst();
            w = getFirstNeighbor(u);
            while(w != -1) {
                if(!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w); 
            }
        }
        
    } 
    
    public void bfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }
    
    public int getNumOfVertex() {
        return vertexList.size();
    }
                       
    //traverse
    public void showGraph() {
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }
                       
    public int getNumOfEdges() {
        return numOfEdges;
    }

    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }
                       
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }
                       
    //Add adjacency matrix
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }
    
  //Insert weight
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}

Depth First Search of Graphs

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 visit the first adjacent node, and then use this visited adjacent node as the initial Node, visit its first adjacent node, it can be understood as follows: every time after visiting the current node, first visit the first adjacent node of the current node

algorithm
  • Visit the initial node v, and mark the node v as visited.
  • Find the first neighbor w of node v.
  • If w exists, continue to execute 4. If w does not exist, go back to step 1 and continue from the next node of v.
  • If w is not visited, perform depth-first traversal recursion on w (ie, treat w as another v, then go to step 123).
  • Find the next adjacent node of the w adjacent node of the node v, go to step 3
code
//depth-first traversal
private void dfs(boolean[] isVisited, int i) {
  System.out.print(getValueByIndex(i) + "->");
  isVisited[i] = true;
  int w = getFirstNeighbor(i);
  while(w != -1) {
    if(!isVisited[w]) {
      dfs(isVisited, w);
    }
    w = getNextNeighbor(i, w);
  }

}

public void dfs() {
  isVisited = new boolean[vertexList.size()];
  for(int i = 0; i < getNumOfVertex(); i++) {
    if(!isVisited[i]) {
      dfs(isVisited, i);
    }
  }
}

Breadth First Search of Graphs

Similar to a hierarchical search process, breadth-first traversal requires the use of a queue to maintain the order of visited nodes in order to visit their neighbors in this order

algorithm
  • Visit the initial node v and mark the node v as visited.
  • Node v into the queue
  • When the queue is not empty, continue to execute, otherwise the algorithm ends.
  • Get out of the queue and get the head node u.
  • Find the first neighbor w of node u.
  • If the adjacent node w of node u does not exist, go to step 3; otherwise, the following three steps are executed in a loop:

    • If node w has not been visited yet, visit node w and mark it as visited.
    • Node w into the queue
    • Find the next adjacent node w of node u after the adjacent node of w, go to step 6
code
//breadth-first traversal
private void bfs(boolean[] isVisited, int i) {
  int u ; 
  int w ; 
  LinkedList queue = new LinkedList();
  System.out.print(getValueByIndex(i) + "=>");
  isVisited[i] = true;
  queue.addLast(i);

  while( !queue.isEmpty()) {
    u = (Integer)queue.removeFirst();
    w = getFirstNeighbor(u);
    while(w != -1) {
      if(!isVisited[w]) {
        System.out.print(getValueByIndex(w) + "=>");
        isVisited[w] = true;
        queue.addLast(w);
      }
      w = getNextNeighbor(u, w); 
    }
  }

} 

public void bfs() {
  isVisited = new boolean[vertexList.size()];
  for(int i = 0; i < getNumOfVertex(); i++) {
    if(!isVisited[i]) {
      bfs(isVisited, i);
    }
  }
}

grateful

Shang Silicon Valley

and hard-working self, personal blogGitHub

Tags: Java

Posted by QSDragon on Thu, 19 May 2022 20:13:15 +0300