グラフアルゴリズム

1
# グラフの表現方法
2

3
# 隣接リスト
4
graph = {
5
    0: [1, 2],
6
    1: [0, 2, 3],
7
    2: [0, 1, 3],
8
    3: [1, 2]
9
}
10

11
# 隣接行列
12
import numpy as np
13
graph = np.array([
14
    [0, 1, 1, 0],
15
    [1, 0, 1, 1],
16
    [1, 1, 0, 1],
17
    [0, 1, 1, 0]
18
])

1
# 幅優先探索の実装
2
from collections import deque
3

4
def bfs(graph, start):
5
    visited = set()
6
    queue = deque([start])
7
    visited.add(start)
8

9
    while queue:
10
        vertex = queue.popleft()
11
        print(vertex)
12

13
        for neighbor in graph[vertex]:
14
            if neighbor not in visited:
15
                visited.add(neighbor)
16
                queue.append(neighbor)
17

18
# 使用例
19
graph = {
20
    0: [1, 2],
21
    1: [0, 2, 3],
22
    2: [0, 1, 3],
23
    3: [1, 2]
24
}
25
bfs(graph, 0)

1
# 深さ優先探索の実装
2
def dfs(graph, start, visited=None):
3
    if visited is None:
4
        visited = set()
5

6
    visited.add(start)
7
    print(start)
8

9
    for neighbor in graph[start]:
10
        if neighbor not in visited:
11
            dfs(graph, neighbor, visited)
12

13
# 使用例
14
graph = {
15
    0: [1, 2],
16
    1: [0, 2, 3],
17
    2: [0, 1, 3],
18
    3: [1, 2]
19
}
20
dfs(graph, 0)

1
# ダイクストラ法の実装
2
import heapq
3

4
def dijkstra(graph, start):
5
    distances = {vertex: float('infinity') for vertex in graph}
6
    distances[start] = 0
7
    priority_queue = [(0, start)]
8

9
    while priority_queue:
10
        current_distance, current_vertex = heapq.heappop(priority_queue)
11

12
        if current_distance > distances[current_vertex]:
13
            continue
14

15
        for neighbor, weight in graph[current_vertex].items():
16
            distance = current_distance + weight
17

18
            if distance < distances[neighbor]:
19
                distances[neighbor] = distance
20
                heapq.heappush(priority_queue, (distance, neighbor))
21

22
    return distances
23

24
# 使用例
25
graph = {
26
    0: {1: 4, 2: 1},
27
    1: {2: 2, 3: 5},
28
    2: {1: 1, 3: 8},
29
    3: {}
30
}
31
distances = dijkstra(graph, 0)
32
print(distances)

1
# グラフアルゴリズムの使用例
2

3
# ソーシャルネットワークの分析
4
social_network = {
5
    "Alice": ["Bob", "Charlie"],
6
    "Bob": ["Alice", "Charlie", "David"],
7
    "Charlie": ["Alice", "Bob", "David"],
8
    "David": ["Bob", "Charlie"]
9
}
10

11
# 幅優先探索で友達の友達を探す
12
def find_friends_of_friends(graph, person, depth=2):
13
    visited = set()
14
    queue = deque([(person, 0)])
15
    visited.add(person)
16
    friends_of_friends = []
17

18
    while queue:
19
        current, current_depth = queue.popleft()
20

21
        if current_depth == depth:
22
            continue
23

24
        for friend in graph[current]:
25
            if friend not in visited:
26
                visited.add(friend)
27
                queue.append((friend, current_depth + 1))
28
                if current_depth == 1:
29
                    friends_of_friends.append(friend)
30

31
    return friends_of_friends
32

33
friends_of_friends = find_friends_of_friends(social_network, "Alice")
34
print(f"Aliceの友達の友達: {friends_of_friends}")
35

36
# 経路探索
37
def find_shortest_path(graph, start, end):
38
    visited = set()
39
    queue = deque([(start, [start])])
40
    visited.add(start)
41

42
    while queue:
43
        vertex, path = queue.popleft()
44

45
        if vertex == end:
46
            return path
47

48
        for neighbor in graph[vertex]:
49
            if neighbor not in visited:
50
                visited.add(neighbor)
51
                queue.append((neighbor, path + [neighbor]))
52

53
    return None
54

55
shortest_path = find_shortest_path(social_network, "Alice", "David")
56
print(f"最短経路: {shortest_path}")