Download presentation
Presentation is loading. Please wait.
1
JAVA 程式設計與資料結構 第二十一章 Graph
2
Definition Graph的表示法為G = (V,E)，其定義就是其中包含了一個nodes(or vertices)的集合（即為集合V）跟一個的arcs(or edges)的集合（即為集合E）。
3
Edge List Edge List可能是最簡單的一種表示Graph的結構，雖然它並不是最有效率。在Edge List的表示法，我們要著重的是如何表示edge。
4
Adjacency List Adjacency List承襲Edge List，只是增加了額外的資訊來支援直接取得incident edges。
5
Adjacency Matrix Adjacency Matrix使用矩陣(Matrix)來表示一個Graph。我們將Graph中Nodes跟Arcs的關係儲存在矩陣中，當需要使用的時候，再在矩陣中取得其對應關係。
6
Breadth-First Search BFS便是以Graph中任一個點開始，根據Edge List或是Adjacency Matrix來找出所有與該點連結的Node，先逐一Search過，然後再往外一層Search，也就是說根據與該點的深度來劃分，一層一層的Search。
7
Depth-First Search DFS先visit初始點的某一個child，然後接著再visit此child的child。而不是向BFS是先visit初始點的所有children。當我們一路visit到一個點已經沒有child可以visit之後，再往前回溯，待找到一個尚有其他小孩的Node，然後循著這一個路線再visit直到路的盡頭，依此不停的直到所有的點都被visited為止。
8
Minima Spanning Tree 所謂的Spanning Tree便是一個sub-graph，此sub-graph剛好將所有的Node連結起來，而且其中沒有cycle。
9
Shortest-path Problem
一個path是幾個edges所組成來連接Graph中的任兩點，而在一個Graph中，可以連結兩點的path極有可能不只一條，而Shortest-path指的就是最近的一條（或者說是weight最小的一條）。
10
Dijkstra’s Algorithm
11
Dijkstra’s Algorithm
12
Dijkstra’s Algorithm
13
Dijkstra’s Algorithm
14
Dijkstra’s Algorithm
15
Dijkstra’s Algorithm
16
Dijkstra’s Algorithm
Similar presentations
