NGenerics - DataStructure / Algorithm Library
摘要提示
- 問題起點: 作者在示範資料結構時誤以為 SortedList 允許重複鍵，進而尋找更完善的資料結構實作庫。
- 套件發現: 在 CodePlex 找到 NGenerics，涵蓋多種資料結構與演算法，猶如課本解答本。
- 資料結構範圍: 實作包含 Heap、BinaryTree、CircularQueue、PriorityQueue、Graph 等。
- 演算法範圍: 內建 Dijkstra、Kruskal、Prim 等圖論演算法，並附原始碼可研究。
- 文件限制: 官方文件不像 MSDN 標示時間複雜度，但可透過閱讀原始碼彌補。
- 範例改寫: 以「高速公路最短路徑/成本」為例，使用 Graph 與 Dijkstra 改寫原本上百行程式。
- 建圖方式: 以字串為節點，邊權重代表成本（如油錢），利用 AddVertex、AddEdge 建立圖。
- 最短路徑計算: 使用 GraphAlgorithms.DijkstrasAlgorithm 由起點擴散計算到各點的最小成本。
- 模型調整: 因節點無權重，需以有向邊並將收費站費用併入邊權重處理。
- 可擴充性: 目前 API 僅回傳結果（成本），若需路徑須改原始碼或用 IVisitor/委派擴充。
全文重點
作者在撰寫關於「如何學好寫程式」與資料結構教學示例時，因為誤將 .NET 的 SortedList 當作可接受重複鍵而遭同事提醒，遂決定尋找一套成熟且對 .NET 友善、同時完整支援 IList/ICollection/IEnumerable 等介面的資料結構/演算法函式庫，以避免自行重複造輪、品質也未必勝出的情形。經由 CodePlex 發現 NGenerics，此套件提供大量常用資料結構（如 Heap、BinaryTree、CircularQueue、PriorityQueue、Graph）與多種演算法實作，彷彿教科書實作版。除了先前文章提到的基本結構之外，NGenerics 還涵蓋數學、圖論與各種排序演算法，適合學習與實務應用。雖文件未如 MSDN 詳列時間複雜度，但因附原始碼，可自行閱讀或調整。
為展示 NGenerics 的實用性，作者挑選較具挑戰的「高速公路路徑/成本計算」案例來重寫。以 NGenerics.DataStructures.General 底下的 Graph 類別作為模型，將地點（如基金、七堵收費站、汐止系統等）視為節點，路段視為邊，並以油耗成本作為邊權重；透過 AddVertex 與 AddEdge 逐一建立圖。接著使用 NGenerics.Algorithms 下的 GraphAlgorithms.DijkstrasAlgorithm 從指定起點（如機場端）計算到各節點的最小成本，進而讀取目標節點（如基金）之權重作為結果。由於圖模型中節點沒有權重，若要計入收費站費用，需將道路建模為有向邊（南下/北上分開），並把過路費加進邊的權重，才能正確反映方向性費用差異。
作者指出現有演算法介面僅回傳結果（各點最小成本），未直接提供路徑過程與行經順序，因此若要印出完整路徑需調整原始碼，例如多傳遞委派或採用套件定義的 IVisitor 走訪節點以擷取沿途資訊。整體而言，NGenerics 以簡潔 API 大幅縮短開發時間、降低出錯機率，且具教學研究價值；但在文件（複雜度標示）與 API 輸出（缺少路徑）上仍有可改進之處。作者鼓勵讀者動手試用與閱讀原始碼，以充分發揮此類演算法函式庫的威力。
段落重點
背景與動機：從 SortedList 誤用談起
作者在系列文中示範集合結構時，疏忽了 System.Collections.Generic.SortedList 的鍵必須唯一，經同事提醒後意識到自行實作資料結構既耗時也難以完全兼容 .NET 介面（ICollection、IEnumerable 等）。為追求穩定、可讀與可維護的實作，決定尋找社群已有的成熟函式庫，避免重複造輪與潛在錯誤。
發現 NGenerics：意外挖到完整的資料結構寶庫
在 CodePlex 上找到 NGenerics，驚訝其涵蓋面廣且實作齊全，從 Heap、BinaryTree 到 CircularQueue、PriorityQueue、Graph 等，幾乎可對照資料結構教科書逐項驗證。此發現扭轉作者原要自行補強結構的計畫，轉而採用現有高品質實作，提高教學與開發效率。
範圍與文件評述：涵蓋圖論與排序，但缺複雜度標示
NGenerics 不只囊括基本容器，也含數學、圖論與多種排序演算法，適合深入研究。然而官方文件不像 MSDN 一樣清楚列示時間複雜度與效能細節，學習曲線稍增。不過套件附上完整原始碼，願意閱讀者仍能掌握演算法實作與複雜度，亦可依需求調整行為。
例題選擇：以高速公路成本/最短路徑展示實用性
為顯示使用 NGenerics 的效益，作者挑戰改寫先前「高速公路」案例，而非簡單通訊錄查詢。該案例涉及多節點多路段、需計算最短成本（油錢、過路費），原本手寫程式碼超過百行。改用 NGenerics 後，建模更直觀、計算更簡潔，也易於擴充特殊邊權重規則。
使用 Graph 建模：節點為地點，邊權重代表成本
以 NGenerics.DataStructures.General.Graph
使用 Dijkstra 計算：從起點擴散求最小成本
改寫計算僅需呼叫 GraphAlgorithms.DijkstrasAlgorithm，指定原始圖與起點（如「機場端」），即能得到含各節點最小成本的結果結構；再讀取目標節點（如「基金」）的 Weight 即為所需油錢成本。此步驟將原本繁瑣的最短路徑實作濃縮為數行程式碼，顯示演算法庫帶來的生產力提升。
收費站與方向性：以有向邊與複合權重處理
由於圖模型中節點不帶權重，若要納入收費站（節點）費用，需將道路轉為有向邊：南下與北上視為不同邊，並把過路費加進對應方向之邊權重，達到將節點成本轉化為邊成本的效果。此建模技巧是圖論常見手法，讓 Dijkstra 仍可直接應用於含過路費的路網。
API 限制與擴充：結果有成本無路徑，建議讀碼加鉤子
目前 NGenerics 的 Dijkstra 實作僅回傳結果圖與各節點成本，未直接提供路徑重建或走訪序列，導致「怎麼走」不如「要花多少」容易取得。作者建議讀者善用其開源特性，透過修改原始碼、加入委派或利用 IVisitor 介面，在演算法走訪過程收集前驅節點以重建路徑，或輸出完整的導航資訊。
小結與建議：善用演算法庫，事半功倍
本文以一個實務案例展示 NGenerics 的威力：寫法簡潔、涵蓋廣泛、可讀可改。雖文件對複雜度不夠友善、API 在路徑輸出上尚可加強，但開源特性使其適合學習、實驗與生產。作者鼓勵讀者實際試用並閱讀原始碼，既能加速開發，也能深化對資料結構與演算法的理解。
資訊整理
知識架構圖
- 前置知識：學習本主題前需要掌握什麼？
- C# 與 .NET 基礎（泛型、委派、例外處理）
- 常見集合介面與使用方式（ICollection、IEnumerable）
- 基本資料結構與圖論概念（圖、頂點/邊、權重、導向/無向）
- 基本演算法思維與複雜度觀念（特別是最短路徑與最小生成樹）
- 核心概念：本文的 3-5 個核心概念及其關係
- NGenerics 函式庫：提供資料結構與演算法的實作（來源於 CodePlex，含原始碼）
- 圖與演算法模型：Graph
作為資料結構，GraphAlgorithms 提供演算法（Dijkstra、Kruskal、Prim） - 權重建模：將成本映射到邊的權重（油錢、過路費），必要時以導向圖表達方向性成本
- 使用與限制：現成 API 易用但可能僅回傳結果（例如距離/成本），路徑還原需擴充或讀源碼
- 技術依賴：相關技術之間的依賴關係
- .NET/C# 基礎 → 使用 NGenerics 類型與泛型 → 建立 Graph
結構 → 呼叫 GraphAlgorithms（需先正確建模權重/邊） - 集合介面（ICollection、IEnumerable）→ 提升在 .NET 生態系的可用性與相容性
- Dijkstra 要求非負權重 → 權重建模需避免負值
- .NET/C# 基礎 → 使用 NGenerics 類型與泛型 → 建立 Graph
- 應用場景：適用於哪些實際場景？
- 路網/導航：最短距離或最低成本路徑（油錢、過路費、方向性差異）
- 網路/電信規劃：最小生成樹（Kruskal/Prim）用於連線成本最小化
- 專案與依賴分析：任務圖、資源流、成本加總
- 教學與原始碼學習：資料結構與演算法的實作參考
學習路徑建議
- 入門者路徑：零基礎如何開始？
- 安裝與引用 NGenerics；熟悉 C# 泛型與基本集合
- 了解圖的基本概念（頂點、邊、權重、導向 vs 無向）
- 用 Graph
建立小型路網；手動加入頂點/邊與權重 - 呼叫 GraphAlgorithms.DijkstrasAlgorithm 計算最短成本，讀取頂點 Weight
- 進階者路徑：已有基礎如何深化？
- 研讀 Dijkstra、Kruskal、Prim 的理論與適用條件
- 練習將方向性成本（例如單向收費）建模為導向邊
- 閱讀 NGenerics 原始碼，了解演算法回傳結果的結構與限制
- 思考以委派或 IVisitor 擴充，取得路徑細節與訪問順序
- 實戰路徑：如何應用到實際專案？
- 建模真實路網資料（轉換節點命名與邊權重計算：油耗×距離＋收費）
- 實作路徑回溯與呈現（儲存前驅節點或擴充演算法回傳資訊）
- 加入單元測試（路徑正確性、成本一致性、方向性測試）
- 壓力測試與效能分析（節點/邊規模擴大，觀察時間/空間表現）
關鍵要點清單
- NGenerics 概觀: .NET/C# 的資料結構與演算法函式庫，提供豐富結構與圖演算法實作 (優先級: 高)
- Graph
使用: 以泛型表示頂點型別，支援新增頂點/邊與權重設定 (優先級: 高) - GraphAlgorithms.DijkstrasAlgorithm: 計算從來源點到各點的最短成本，要求非負權重 (優先級: 高)
- 權重建模策略: 將實際成本（距離、油錢、過路費）映射到邊的 weight (優先級: 高)
- 導向 vs 無向: 若點本身有成本或方向性差異，需改為導向邊以吸收成本 (優先級: 高)
- 路徑還原限制: 現成 Dijkstra 實作僅回傳結果權重，不直接給路徑，需要擴充或讀源碼 (優先級: 高)
- IVisitor/委派擴充: 透過造訪節點或自訂回呼記錄前驅資訊，以取得完整路徑 (優先級: 中)
- MST 演算法: Kruskal 與 Prim 用於最小生成樹，適合網路/佈線成本最小化 (優先級: 中)
- 接口相容性: 實作 ICollection、IEnumerable 等介面，利於與 .NET 生態整合 (優先級: 中)
- SortedList Key 唯一性: System.Collections.Generic.SortedList 的鍵必須唯一，建模時需避免重複 (優先級: 中)
- 命名空間結構: 主要使用 NGenerics.DataStructures.General（Graph）與 NGenerics.Algorithms（演算法） (優先級: 中)
- 原始碼可讀性: 官方文件未明載時間複雜度，可直接閱讀原始碼理解實作 (優先級: 中)
- 測試與驗證: 小圖手動驗證結果，逐步擴至大圖並加入單元測試 (優先級: 中)
- 成本組合建模: 將多種成本（油錢、收費）合併為單一邊權重以便演算法運作 (優先級: 高)
- 應用實例: 高速公路路網從「機場端」到「基金」的最小油錢/總成本計算示例 (優先級: 中)
