ツリーとグラフ

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文書の構造
チェス：対戦相手の取りうる手
検索と並べ替えアルゴリズム

グラフ

ノードのあるグラフの画像。

以下の要素の集合：
- ノード/頂点（vertice）
- リンク/エッジ（edge）
ツリーはグラフの一種

グラフ - 種類

有向グラフ：
- エッジに特定の方向がある

有向グラフの画像。

グラフ - 種類

無向グラフ：
- エッジに方向がない
- 関係は双方向

無向グラフの画像。

グラフ - 種類

重み付きグラフ：
- エッジに数値がついている
- 有向にも無向にもなりえる

都市名とそれらの間の距離が示された無向グラフの図。

グラフとツリーの違い

ツリー

サイクルを持てない
すべてのノードがつながっている必要がある

ノードのあるツリーの画像

グラフ

サイクルを持てる
つながっていないノードがある場合がある

ノードのあるグラフの画像。

グラフとツリーの違い

ツリー

サイクルを持てない
すべてのノードがつながっている必要がある

ノードのあるツリーの画像。

グラフ

サイクルを持てる
つながっていないノードがある場合がある

ノードを含むグラフの画像。どこにも接続されていないノードがあります。

グラフ - 実際の用途

SNSにおけるユーザー関係
- 友達
- フォロー
- いいね
- など
場所と距離
- 最適なルート
グラフデータベース
検索と並べ替えアルゴリズム

グラフ - 作成方法

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で学ぶデータ構造とアルゴリズム