[DAY24] C#基礎與實作(常見演算法-深度優先搜尋)

15th鐵人賽

2023-10-07 01:49:12

788 瀏覽

分享至

C# 程式基礎

常見演算法：

深度優先搜尋 (Depth-First Search, DFS)：

DFS是一種常見的圖形搜索演算法，用於遍歷和搜索圖形或樹狀結構。通常用於查找路徑、尋找連通性、拓撲排序等問題。DFS的基本思想是沿著一條路徑盡可能深入地遍歷，直到無法繼續為止，然後返回並嘗試其他路徑。

基本概念：
- DFS使用遞迴或類似遞迴的堆疊（Stack）來實現。
- 運行方式如下：
  1. 從起始節點（或根節點）開始遍歷，將起始節點標記為已訪問。
  2. 選擇一個未訪問的相鄰節點，並重複步驟1。如果沒有未訪問的相鄰節點，返回上一個節點。
  3. 重複步驟2，直到所有節點都被訪問。
步驟：
1. 建立一個佇列或堆疊（或使用遞迴函數）來跟蹤節點的遍歷順序。
2. 從起始節點開始，將其標記為已訪問並加入佇列或堆疊。
3. 進入迴圈，處理佇列或堆疊的頂部節點，並檢查其未訪問的相鄰節點。
4. 如果找到未訪問的相鄰節點，將其標記為已訪問並加入佇列或堆疊。
5. 重複步驟3和4，直到佇列或堆疊變為空。

程式實作：

using System;
using System.Collections.Generic;

class Graph
{
    private int V;
    private List<int>[] adj;

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; ++i)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write(v + " ");
        foreach (int i in adj[v])
        {
            if (!visited[i])
            {
                DFSUtil(i, visited);
            }
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph g = new Graph(7);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 3);
        g.AddEdge(1, 4);
        g.AddEdge(2, 5);
        g.AddEdge(2, 6);

        Console.WriteLine("深度優先搜尋結果:");
        g.DFS(0);
    }
}