7.Data Structures: Graphs 學習筆記

學習資料來源: Master the Coding Interview: Data Structures + Algorithms

【Data Structures: Graphs】

優點: 呈現關係

缺點: 難以縮放

特性: Linked lists are type of tree, trees are type of graph.

類型

• Directed(one way) vs Undirected graphs

• Weighted(have information in the edges) vs Unweighted graphs

• cyclic(from one node back to original node) vs Acyclic graphs

類型範例:

【Graph Data】

以 Edge lists 呈現

const graph1 = [[0, 2], [2, 3], [2, 1], [1, 3]];

以 Adjacent lists 呈現 (index = >node, value => node neighbors)

const graph2 = [[2], [2, 3], [0, 1, 3], [1, 2]];

以 Adjacent Matrix 呈現 (1 = >connection, 0 => no connection)

const graph3 = {
 0: [0, 0, 1, 0],
 1: [0, 1, 1, 0],
 2: [1, 1, 0, 1],
 3: [0, 1, 1, 0],
};

【用JS實作 Graph】

以Adjacent lists為例

回到筆記列表，文章中的內容如果有誤，歡迎提醒告知，謝謝!