如何使用java實作圖的遍歷演算法

如何使用Java實作圖的遍歷演算法

圖是離散數學中重要的資料結構，常用來描述事物之間的關係。圖的遍歷演算法是指以某個節點為起點，依照一定的規則，依序存取圖中所有節點的過程。常用的圖的遍歷演算法有深度優先搜尋（DFS）和廣度優先搜尋（BFS）。本文將介紹如何使用Java語言實作這兩種圖的遍歷演算法，並提供具體的範例程式碼。

一、深度優先搜尋（DFS）

深度優先搜尋是一種先序遍歷的演算法，從起始節點開始遞歸地存取其鄰接節點，直到遇到沒有未造訪過的鄰接節點為止，然後回溯到上一個節點，繼續存取未造訪過的鄰接節點，直到遍歷完整個圖。

以下是透過深度優先搜尋遍歷圖的範例程式碼：

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);
    }
}

輸出結果：

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

二、廣度優先搜尋（BFS）

廣度優先搜尋是一種橫向遍歷的演算法，從一個起始節點開始，按照一層一層的順序存取節點，直到遍歷完整個圖。使用佇列來實現廣度優先搜索，每次從隊列中取出一個節點，然後將其未訪問過的鄰接節點加入隊列。

以下是透過廣度優先搜尋遍歷圖的範例程式碼：

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);
    }
}

輸出結果：

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

在上述範例程式碼中，我們使用鄰接表來表示圖的結構，並透過添加邊的方式建立圖。然後，我們分別呼叫DFS和BFS方法來遍歷該圖。輸出結果即為經過遍歷演算法所得到的節點順序。

總結：

透過本文的介紹和範例程式碼，我們可以學習如何使用Java語言實作圖的遍歷演算法，包括深度優先搜尋和廣度優先搜尋。這兩種遍歷演算法在現實中有廣泛應用，例如在網路爬蟲、迷宮解等領域都有重要的作用。掌握了圖的遍歷演算法，我們可以快速且有效地解決相關問題。

以上是如何使用java實作圖的遍歷演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！