Graph

圖（Graph）是一種用來表示物件之間關係的數據結構。

它由節點（或稱為頂點）和邊組成，節點代表物件，而邊則代表這些物件之間的關係。

圖可分為有向圖和無向圖，具體取決於邊是否有方向。

資料結構圖有許多應用，例如在社交網路、網路路由、計算機科學等領域中。

而今天要介紹的 Breadth-First Search (BFS) 和 Depth-First Search (DFS) 是兩種用於在圖中搜索節點的算法，它們之間有密切的關係，但在搜索過程中的策略不同。

BFS

// Breadth-First Search

import java.util.LinkedList

// Graph class
class Graph(val vertices: Int) {
    val adjacencyListArray = Array(vertices) { LinkedList<Int>() }
    fun addEdge(src: Int, dest: Int) {
        adjacencyListArray[src].add(dest)
    }
}

class BFS {
    fun bfs(graph: Graph, start: Int) {
        val visited = BooleanArray(graph.vertices)
        val queue = LinkedList<Int>()
        visited[start] = true
        queue.add(start)
        while (queue.size != 0) {
            val current = queue.poll()
            print("$current ")
            val edges = graph.adjacencyListArray[current]
            for (edge in edges) {
                if (!visited[edge]) {
                    visited[edge] = true
                    queue.add(edge)
                }
            }
        }
    }
}

// GRAPH
// 0-----1
// |    /|
// |  /  |
// |/    |
// 2-----3

// main function
fun main(args: Array<String>) {
    val graph = Graph(4)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    println("Following is Breadth First Traversal " + "(starting from vertex 2)")
    val bfs = BFS()
    bfs.bfs(graph, 2)
}

BFS（廣度優先搜索）：

• BFS 以一個起始節點為基礎，然後依次擴展搜索到與該節點直接相鄰的節點。
• 它使用佇列（queue）來實現，先進先出的原則，確保將先探索完所有與起始節點距離為1的節點，再探索距離為2的節點，以此類推。
• BFS 通常用於解決尋找最短路徑或尋找特定節點的問題，因為它能確保首次訪問某個節點時，該節點到起始節點的路徑是最短的。

BFS 適用於廣泛的搜索，並可用於尋找最短路徑

DFS

// Depth-First Search

import java.util.LinkedList

// Graph class
class Graph(val vertices: Int) {
    val adjacencyListArray = Array(vertices) { LinkedList<Int>() }
    fun addEdge(src: Int, dest: Int) {
        adjacencyListArray[src].add(dest)
    }
}

class DFS {
    fun dfs(graph: Graph, start: Int) {
        val visited = BooleanArray(graph.vertices)
        dfsUtil(graph, start, visited)
    }

    private fun dfsUtil(graph: Graph, current: Int, visited: BooleanArray) {
        visited[current] = true
        print("$current ")
        val edges = graph.adjacencyListArray[current]
        for (edge in edges) {
            if (!visited[edge]) {
                dfsUtil(graph, edge, visited)
            }
        }
    }
}

// GRAPH
// 0-----1
// |    /|
// |  /  |
// |/    |
// 2-----3

// main function
fun main(args: Array<String>) {
    val graph = Graph(4)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    println("Following is Breadth First Traversal " + "(starting from vertex 2)")
    val dfs = DFS()
    dfs.dfs(graph, 2)
}

DFS（深度優先搜索）：

• DFS 選擇一條邊，然後盡可能深入地探索下去，直到達到最深處再返回，然後繼續探索其他未訪問的分支。
• 它使用堆疊（stack）來實現，後進先出的原則，這使得它更適合處理深度搜索。
• DFS 常用於解決追蹤所有可能路徑或尋找圖中的特定結構（例如，檢查是否存在循環）的問題。

DFS則適用於深度搜索，用於尋找結構或跟蹤路徑

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！

Reference

• DFS vs BFS (in detail)