Data structure & Algorithms study

그래프(Graphs) - 인접행렬(Adjacency Matrix)

adulty22 2024. 9. 9. 16:10

그래프(Graphs) 개요

그래프는 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 이루어진 자료구조이다. 그래프는 여러 문제를 모델링하는 데 유용하며, 특히 네트워크, 지도, 소셜 네트워크 등의 문제를 해결할 때 자주 사용된다.

그래프는 방향성(Directed)이 있을 수도 있고 없을 수도 있으며, 가중치(Weighted)가 있을 수도 있고 없을 수도 있다. 이 특징에 따라 그래프의 형태가 달라진다.

그래프를 표현하는 두 가지 주요 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)입니다. 이 중에서 인접 행렬에 대해 자세히 살펴보겠다.

 

인접 행렬 (Adjacency Matrix)

인접 행렬은 그래프를 표현하는 방법 중 하나로, 2차원 배열을 사용하여 노드 간의 연결 상태를 나타낸다.

  • 인접 행렬은 크기가 N x N인 이차원 배열로, 여기서 N은 그래프의 노드 개수이다.
  • 배열의 행과 열은 그래프의 노드를 나타내며, 행과 열이 교차하는 지점은 두 노드 사이에 간선이 있는지 여부를 나타낸다.
    • 0: 노드 사이에 간선이 없는 경우
    • 1 또는 가중치 값: 노드 사이에 간선이 있는 경우

인접 행렬의 예시

다음은 4개의 노드로 이루어진 무방향 그래프의 인접 행렬이다.

    0 -- 1
     \\  / \\
      2 -- 3

이 그래프의 인접 행렬은 다음과 같다:

  0 1 2 3
0 0 1 1 0
1 1 0 1 1
2 1 1 0 1
3 0 1 1 0

이 행렬에서:

  • (0, 1)의 값이 1이므로 0번 노드와 1번 노드 사이에 간선이 있다.
  • (0, 3)의 값이 0이므로 0번 노드와 3번 노드 사이에는 간선이 없다.

특징

  • 공간 복잡도: 인접 행렬은 항상 N x N 크기의 배열을 사용하므로 공간 복잡도는 O(N^2)이다. 간선이 적은 희소 그래프(Sparse Graph)에서는 비효율적일 수 있다.
  • 시간 복잡도: 간선이 있는지 여부를 확인하는 데 O(1)의 시간이 걸린다. 하지만, 모든 간선을 확인하려면 O(N^2)이 필요하다.
class AdjacencyMatrix:
    def __init__(self, num_vertices):
        # num_vertices는 그래프의 노드 개수를 의미하며, N x N 행렬을 초기화합니다.
        self.num_vertices = num_vertices
        self.matrix = [
            [0 for _ in range(self.num_vertices)] for _ in range(self.num_vertices)
        ]

    # 간선을 추가하는 함수 (무방향 그래프)
    def add_edge(self, u, v, weight=1):
        # u와 v 노드 간에 weight로 간선을 추가합니다.
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight

    # 간선을 제거하는 함수
    def remove_edge(self, u, v):
        # u와 v 노드 간의 간선을 제거합니다.
        self.matrix[u][v] = 0
        self.matrix[v][u] = 0

    # 특정 노드의 인접 노드 목록을 반환하는 함수
    def get_adjacent_nodes(self, u):
        # u 노드에 연결된 모든 노드들을 반환합니다.
        return [v for v in range(self.num_vertices) if self.matrix[u][v] != 0]

    # 그래프를 출력하는 함수
    def display(self):
        # 현재 인접 행렬을 보기 쉽게 출력합니다.
        for row in self.matrix:
            print(row)


# 그래프 생성 (4개의 노드)
am = AdjacencyMatrix(4)

# 간선 추가
am.add_edge(0, 1)
am.add_edge(0, 2)
am.add_edge(1, 2)
am.add_edge(1, 3)
am.add_edge(2, 3)

# 그래프 출력
am.display()
"""
[0, 1, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, 1, 1, 0]
"""
# 특정 노드의 인접 노드 출력
print("0번 노드와 인접한 노드들:", am.get_adjacent_nodes(0))
# 0번 노드와 인접한 노드들: [1, 2]
print("1번 노드와 인접한 노드들:", am.get_adjacent_nodes(1))
# 1번 노드와 인접한 노드들: [0, 2, 3]

코드 설명

  1. Graph 클래스: 그래프의 노드 개수만큼의 인접 행렬을 초기화하고, 이를 기반으로 간선 추가, 제거, 인접 노드 반환 등의 기능을 구현한다.
  2. add_edge 메서드: 두 노드 u와 v 사이에 간선을 추가합니다. 무방향 그래프이므로, self.adj_matrix[u][v]와 self.adj_matrix[v][u]를 동시에 설정한다.
  3. remove_edge 메서드: 두 노드 u와 v 사이의 간선을 제거한다.
  4. get_adjacent_nodes 메서드: 특정 노드에 연결된 노드들을 리스트로 반환한다.
  5. display 메서드: 현재 인접 행렬을 보기 쉽게 출력한다.

 

  • 인접 행렬은 그래프의 노드와 간선 정보를 2차원 배열로 저장하는 방식이다.
  • 간선이 있는지 여부를 빠르게 확인할 수 있지만, 공간 효율성이 떨어지는 경우도 있다.
  • 이 구현은 무방향 그래프를 기반으로 하고 있으며, 방향 그래프를 표현할 때는 간선을 단방향으로만 추가하면 된다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms

728x90