Algorithms 実践的アルゴリズ ム理論

実践的アルゴリズム理論 Theory of Advanced

Algorithms

グラフのデータ構造 担当：上原隆平

Theory of Advanced

Algorithms 実践的アルゴリズ ム理論

Data Structure of Graphs

Ryuhei Uehara

新宿

東京 池袋 上野

例: 講義の履修順序

グラフ (graph)

•

–

:

–

:

例: 路線図

• Vertices are joined by edges

– Directed graph: each edge has direction

– (Undirected) graph: each edge has no direction

Shinjuku

Tokyo Ikebukuro Ueno

Example: Order of classes

Graph

Example: Railmap

グラフ : 表記

u1

u2 u10

u3

u4

u9

u7 u5 u6

u8

東京 上野 新宿 池袋

•

: G = (V, E)

– V:

E:

•

: u, v, … ∈ V

•

: e = {u, v} ∈ E

a = (u, v) ∈ E

•

– w(u), w(e)

–

5

• Graph: G = (V, E)

– V: Vertex set

E: Edge set

• Vertices: u, v, … ∈ V

• Edges: e = {u, v} ∈ E (undirected) a = (u, v) ∈ E (directed)

• Vertices/edges can have weight

– w(u), w(e)

– Distance, price, time, etc.

Graph: Notation

u1

u2 u10

u3

u4

u9

u7 u5 u6

u8

Tokyo Ueno Ikebukuro

Shinjuku

6

グラフ : 基本的な用語 (1/2)

•

(path):

–

(simple path):

•

(cycle, closed path): v

v

•

(connected graph):

2

Graph: Basic terms (1/2)

• Path: Vertices joined by edges

– Simple path: never visits the same vertex twice

• cycle, closed path: path from v to v

• connected graph: Any pair of vertices is

joined by a path

グラフ : 基本的な用語 (2/2)

•

(forest):

•

(tree):

•

(planar graph):

•

(complete graph):

–

K

Graph: Basic terms (2/2)

• forest: acyclic graph (no cycle)

• tree: connected acyclic graph

• planar graph: It can be drawn on a plane without crossing of edges

• complete graph: graph s. t. all pairs are joined

– Complete graph K

is

a minimal non-planar graph

グラフアルゴリズムの計算量

•

n,

m ∈ O(n

)

–

: m ≦ n(n-1)/2 –

: m ≦ n(n-1)

•

m ∈ O(n)

•

n

m

Complexity of graph algorithms

• n vertices and m edges; m ∈ O(n

)

– undirected graph: m ≦ n(n-1)/2 – directed graph: m ≦ n(n-1)

• On a plane graph, m ∈ O(n)

• Computational complexity of a graph

algorithm is given by an expression of n,m

グラフの表現方法

•

•

1 2 3

4 4

2 3

4 2

頂点 隣接頂点のリスト

1 2

3

4

13

Representation of a graph

• Adjacency matrix

• Adjacency list

1 2 3

4 4

2 3

4 2

Vertices List of neighbors

1 2

3

4

14

1 2

3

4

グラフの表現方法 : 行列表現（隣接行列）

• (u, v) ∈ E ⇒ M[u, v] = 1

• (u, v) E ⇒ M[u, v] = 0

1 2

3

4

Representation of a graph:

Matrix representation (adj. matrix)

• (u, v) ∈ E ⇒ M[u, v] = 1

• (u, v) E ⇒ M[u, v] = 0

1 2 3

4 4

2 3

4 2

頂点 隣接頂点のリスト

グラフの表現方法 : リスト表現（隣接リスト）

1 2

3

4

• (u, v) ∈ E ⇔ v ∈ T(u)

– T(u)

u

•

:

• (u, v) ∈ E ⇔ v ∈ T(u)

– T(u) is the list of neighbors of u

• Example:

1 2 3

4 4

2 3

4 2

Vertices List of neighbors

Representation of a graph:

List representation (adj. list)

1 2

3

4

隣接行列 vs 隣接リスト

•

–

: Θ(n

)

–

: Θ(m log n)

•

: (u, v) ∈ E ?

–

: Θ(1)

–

: Θ(n)

• Memory

– Adj. matrix: Θ(n

) – Adj. list: Θ(m log n)

• Time for check if (u, v) ∈ E ?

– Adj. matrix: Θ(1) – Adj. list: Θ(n)

Adj. Matrix vs Adj. List