Adjacency Matrix vs Adjacency List

1
2
3

  A — B
  |   |
  C — D

1
2
3

  A → B
  ↓   
  C → D

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class GraphMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 모든 값을 0으로 초기화한 2차원 배열 생성
        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
    
    def add_edge(self, v1, v2, weight=1):
        # 정점 v1에서 v2로 가는 간선 추가
        self.matrix[v1][v2] = weight
        
        # 무방향 그래프인 경우 양방향 연결
        # self.matrix[v2][v1] = weight
        
    def remove_edge(self, v1, v2):
        # 정점 v1에서 v2로 가는 간선 제거
        self.matrix[v1][v2] = 0
        
        # 무방향 그래프인 경우 양방향 연결 제거
        # self.matrix[v2][v1] = 0
        
    def print_graph(self):
        for row in self.matrix:
            print(row)

1
2
3

  A — B
  |   |
  C — D

1
2
3
4

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

1
2
3

  A → B
  ↓   
  C → D

1
2
3
4

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class GraphList:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 각 정점마다 빈 리스트 생성
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, v1, v2, weight=1):
        # 정점 v1에서 v2로 가는 간선 추가 (가중치 포함)
        self.adj_list[v1].append((v2, weight))
        
        # 무방향 그래프인 경우 양방향 연결
        # self.adj_list[v2].append((v1, weight))
        
    def remove_edge(self, v1, v2):
        # v1에서 v2로 가는 간선 제거
        self.adj_list[v1] = [(vertex, weight) for vertex, weight in self.adj_list[v1] if vertex != v2]
        
        # 무방향 그래프인 경우 v2에서 v1로 가는 간선도 제거
        # self.adj_list[v2] = [(vertex, weight) for vertex, weight in self.adj_list[v2] if vertex != v1]
        
    def print_graph(self):
        for i in range(self.num_vertices):
            print(f"정점 {i}:", end=" ")
            for j, weight in self.adj_list[i]:
                print(f"({j}, 가중치: {weight})", end=" ")
            print()