木構造とグラフ

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

木構造 - 定義

ノードを持つ木の図。

ノード基盤のデータ構造
各ノードは複数ノードへのリンクを持てる

木構造 - 用語

ノードを持つ木の図。根ノードが黄色。

木構造 - 用語

ノードを持つ木の図。根ノードが黄色。親ノードが橙色。

木構造 - 用語

ノードを持つ木の図。根ノードが黄色。親ノードが橙色で、その子が緑色。

木構造 - 用語

ノードを持つ木の図。

木構造 - 用語

階層レベル付きの木の図。

木構造 - 二分木

二分木の図。

各ノードは次のいずれか:
- 子が0
- 子が1
- 子が2

木構造 - 二分木の実装

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

ノードを持つ木の図。

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

木構造 - 実例

階層関係の保存
- コンピュータのファイルシステム
- HTML文書の構造
チェス: 相手の可能な手
探索・ソートアルゴリズム

グラフ

ノードを持つグラフの図。

次で構成:
- ノード/頂点
- リンク/辺
木はグラフの一種

グラフ - 種類

有向グラフ:
- 辺に向きがある

有向グラフの図。

グラフ - 種類

無向グラフ:
- 辺に向きがない
- 関係は相互

無向グラフの図。

グラフ - 種類

重み付きグラフ:
- 辺に数値の重み
- 有向/無向どちらも可

都市名と距離を示す無向グラフの図。

グラフ vs. 木構造

木構造

サイクルなし
すべてのノードが連結

ノードを持つ木の図。

グラフ

サイクル可
非連結ノードがあり得る

ノードを持つグラフの図。

グラフ vs. 木構造

木構造

サイクルなし
すべてのノードが連結

ノードを持つ木の図。

グラフ

サイクル可
非連結ノードがあり得る

ノードを持つグラフの図。1つのノードが他と未接続。

グラフ - 実世界の用途

ソーシャルネットワークのユーザー関係
- 友達
- フォロー
- いいね
- など
地点と距離
- 経路最適化
グラフデータベース
探索・ソートアルゴリズム

グラフ - 実装

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

有向グラフの図。

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}

練習してみましょう！

Pythonで学ぶデータ構造とアルゴリズム