How to implement graph traversal algorithm using java

How to use Java to implement graph traversal algorithm

Graph is an important data structure in discrete mathematics and is often used to describe the relationship between things. The graph traversal algorithm refers to the process of sequentially visiting all nodes in the graph starting from a certain node and following certain rules. Commonly used graph traversal algorithms include depth-first search (DFS) and breadth-first search (BFS). This article will introduce how to use Java language to implement these two graph traversal algorithms and provide specific sample codes.

1. Depth-first search (DFS)

Depth-first search is a pre-order traversal algorithm that recursively visits its adjacent nodes starting from a starting node until it encounters no future nodes. to the visited adjacent nodes, then backtrack to the previous node, and continue to visit unvisited adjacent nodes until the entire graph is traversed.

The following is a sample code for traversing the graph through depth-first search:

import java.util.*;
 
class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表
 
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
 
    void DFSUtil(int v, Boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");
 
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    void DFS(int v) {
        Boolean visited[] = new Boolean[V];
        Arrays.fill(visited, false);
 
        DFSUtil(v, visited);
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.DFS(2);
    }
}

Output results:

从顶点2开始的遍历结果：
2 0 1 3

2. Breadth-first search (BFS)

Breadth Priority search is a horizontal traversal algorithm that starts from a starting node and visits nodes layer by layer until the entire graph is traversed. Use a queue to implement breadth-first search, taking one node from the queue at a time, and then adding its unvisited adjacent nodes to the queue.

The following is a sample code for traversing a graph through breadth-first search:

import java.util.*;
 
class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表
 
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
 
    void BFS(int v) {
        boolean visited[] = new boolean[V];
 
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
        visited[v] = true;
        queue.add(v);
 
        while (queue.size() != 0) {
            v = queue.poll();
            System.out.print(v + " ");
 
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.BFS(2);
    }
}

Output results:

从顶点2开始的遍历结果：
2 0 3 1

In the above sample code, we use adjacency lists to represent the structure of the graph , and build the graph by adding edges. Then, we call the DFS and BFS methods respectively to traverse the graph. The output result is the node sequence obtained by the traversal algorithm.

Summary:

Through the introduction and sample code of this article, we can learn how to use Java language to implement graph traversal algorithms, including depth-first search and breadth-first search. These two traversal algorithms are widely used in reality, such as web crawlers, maze solving and other fields. Mastering the graph traversal algorithm, we can solve related problems quickly and effectively.

The above is the detailed content of How to implement graph traversal algorithm using java. For more information, please follow other related articles on the PHP Chinese website!