【Goで学ぶコンピューターサイエンス】グラフの基礎

グラフ

グラフは以下の要素で構成されます。

• 頂点（Vertex）
  • グラフの中のポイントで、ノードとも呼ばれる
• 辺（Edge）
  • 頂点間の接続のことで、関係性やリンクを表す

グラフは通常、$G = (V, E)$ と表されます。

• (V): 頂点の集合
• (E): 辺の集合

グラフの種類

1. 有向グラフ

各辺に方向があるグラフ。例えば、Xの「フォロー」関係は有向グラフで表現できます。

2. 無向グラフ

辺に方向がないグラフ。Facebookの「友達」関係のように双方向でつながっています。

3. 重み付きグラフ

各辺に重み（値）が割り当てられているグラフ。重みは距離、コスト、時間などを表します。

4. サイクルの有無

• 非巡回グラフ
  • サイクル（同じ頂点に戻るパス）が存在しないグラフ
• 巡回グラフ
  • サイクルが存在するグラフ

グラフの表現方法

1. 隣接リスト

各頂点に対して、その頂点に接続されている隣接頂点をリストで持つ形式。

A: B, C
B: A, D
C: A
D: B

2. 隣接行列

頂点を行と列に持ち、接続されていれば1、そうでなければ0を持つ2次元配列。

   A B C D
A [0 1 1 0]
B [1 0 0 1]
C [1 0 0 0]
D [0 1 0 0]

3. エッジリスト

辺をリストとして持つ形式。

[(A, B), (A, C), (B, D)]

グラフアルゴリズム

1. 幅優先探索 (Breadth-First Search, BFS)

レベル順にグラフを探索。

2. 深さ優先探索 (Depth-First Search, DFS)

一つの経路を深く進んでいき、戻ることを繰り返して探索。

3. 最短経路探索

• ダイクストラ法
  • 重み付きグラフの最短経路を求める
• ベルマンフォード法
  • 負の重みが存在する場合の最短経路

4. 最小全域木

• クラスカル法
• プリム法

無向グラフGoサンプルコード

package main

import "fmt"

// グラフ構造体
type Graph struct {
	adjacencyList map[string][]string
}

// グラフの作成
func NewGraph() *Graph {
	return &Graph{
		adjacencyList: make(map[string][]string),
	}
}

// 頂点の追加
func (g *Graph) AddVertex(vertex string) {
	if _, exists := g.adjacencyList[vertex]; !exists {
		g.adjacencyList[vertex] = []string{}
	}
}

// 辺の追加 (無向グラフ)
func (g *Graph) AddEdge(v1, v2 string) {
	g.adjacencyList[v1] = append(g.adjacencyList[v1], v2)
	g.adjacencyList[v2] = append(g.adjacencyList[v2], v1)
}

// グラフの表示
func (g *Graph) Display() {
	for vertex, edges := range g.adjacencyList {
		fmt.Printf("%s -> %v\n", vertex, edges)
	}
}

// メイン関数
func main() {
	graph := NewGraph()

	// 頂点を追加
	graph.AddVertex("A")
	graph.AddVertex("B")
	graph.AddVertex("C")
	graph.AddVertex("D")

	// 辺を追加
	graph.AddEdge("A", "B")
	graph.AddEdge("A", "C")
	graph.AddEdge("B", "D")

	// グラフを表示
	fmt.Println("グラフの構造:")
	graph.Display()
}

A -> [B C]
B -> [A D]
C -> [A]
D -> [B]