Java 的高階演算法(圖演算法)

Contents

廣度優先搜索、深度優先搜索、最短路徑、套利、強連通分量和最大流量

從這 12.5 小時的課程，你會學到

了解資料結構的應用
了解圖和圖論的基礎知識
高效實施高級演算法（圖演算法）
學習圖遍歷( traversing )，例如廣度優先搜索和深度優先搜索
了解拓撲排序和環( cycle )檢測
了解最短路徑演算法（Dijkstra 和 Bellman-Ford 演算法）
了解生成樹( spanning trees )
了解強的連通分量( connected components )
了解 Hamiltonian 環( cycle )和 Eulerian 環( cycle )
了解最大流量（最大流量最小切割定理）

要求

網際網路連線
資料結構的基本知識

課程說明

本課程介紹高階演算法(圖演算法) ，主要關注圖遍歷( graph traversal )、最短路徑( shortest path )問題、生成樹( spanning trees )和最大流( maximum flow )問題，以及從 Google 網路爬蟲到股票市場套利( stock market arbitrage )情況的各種應用。

第 1 節 – 圖論基礎：

什麼是 G(V,E) 圖
鄰接矩陣表示
鄰接表表示

第 2 節 – 圖遍歷（廣度優先搜索）

什麼是廣度優先搜索？
如何在搜索引擎中使用 BFS 進行 WebCrawling？

第 3 節 – 圖遍歷（深度優先搜索）

什麼是深度優先搜索？
如何使用遞歸實施 DFS
DFS 的應用，例如拓撲排序和環( cycle )檢測
用 DFS 走出迷宮

第 4 節 – 拓撲排序

什麼是拓撲排序（拓撲排序）
有方向的無環圖 ( DAGs )
DAG 最短路徑和最長路徑
關鍵路徑方法和專案管理

第 5 節 – 環( cycle )檢測

什麼是圖的環( cycle )？
前邊緣和後邊緣
環( cycle )檢測算法（Tarjan’s algorithm with DFS）

第 6 節 – Dijkstra 的最短路徑演算法

G(V,E)圖中的最短路徑是什麼
Dijkstra 的最短路徑演算法

第 7 節 – Bellman-Ford 最短路徑演算法

Bellman-Ford 演算法
如何處理負環( cycle )
在外匯上尋找套利機會

第 8 節：- 生成樹（Kruskal 和 Prim 演算法）

什麼是生成樹？
聯合查找資料結構
Kruskal 演算法
Prim 演算法

第 9 節 – 強連通分量 (SCC，Strongly Connected Components )

什麼是強連通分量
Kosaraju 演算法
Tarjan 演算法

第 10 節 – 最大流量問題

著名的最大流量問題
如何將大多數困難問題簡化為最大流量問題
Ford-Fulkerson 演算法
二分匹配問題

第 9 節 – 旅行業務員問題和 Hamiltonian 環

旅行業務員問題（TSP，travelling salesman problem）
如何處理 NP-hard 問題
什麼是元啟發式( meat-heuristics )

第 10 節 – Eulerian 路徑

Eulerian 路徑和 Eulerian 環
Hierholzer 演算法和中國郵務遞送員問題

第 11 節 – 演算法分析

如何衡量演算法的運行時間
使用大 O (ordo)、大 Ω (omega) 和大 θ (theta) 符號進行運行時間分析
複雜度等級
多項式 (P) 和非確定性多項式 (NP) 演算法
O(1)、O(logN)、O(N) 和其他幾個運行時間複雜度

這門課程大約需要 11 個小時才能完成，但我強烈建議你把這些演算法輸入多次，以便更好地掌握它。你可以在最後一節課下載整個課程的原始碼。

如果你對有關演算法的高階主題感興趣，你一定要選修這門課程。這些方法可以用在很多領域: 從軟體工程到科學研究。

謝謝你參加這個課程，讓我們開始吧！

目標受眾

這門課程是為從科學家到軟體開發人員的每一個人開設的，只要你希望更瞭解演算法思維

講師簡介

Holczer Balazs 軟體工程師 ( 更多講師主講課程介紹 )

嗨！

我叫 Balazs Holczer。我來自匈牙利布達佩斯。我有物理學家資格，且一直是。目前我在一家跨國公司擔任模擬工程師。自從大學以來，我一直對演算法和資料結構以及它的實現感興趣，特別是在 Java 中。後來我熟悉了機器學習技術、人工智慧、數值方法和配方，如求解微分方程、線性代數、內插( interpolation )和外差( extrapolation )。這些事情可能在幾個領域被證明是非常重要的：軟體工程、研究與開發或投資銀行。對於 Black-Scholes 模型或 Merton 模型等定量模型，我有特別喜愛。

歡迎參觀我的網站並訂閱，如果你對這些話題感興趣！