배열을 이용한 그래프 자료구조 구현하기

06 Nov 2023

javascript

그래프는 정점들과 정점들을 연결하는 간선들로 이루어진 자료구조입니다. 이번에는 배열을 이용하여 그래프 자료구조를 구현해 보겠습니다.

그래프 클래스 구현하기

class Graph:
    def __init__(self, V):
        self.V = V
        self.adj_list = [[] for _ in range(V)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def print_graph(self):
        for i in range(self.V):
            print("정점", i, "에 연결된 정점들:")
            for v in self.adj_list[i]:
                print(v, end=" ")
            print()

그래프 객체 생성 및 사용 예시

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.print_graph()

출력 예시

정점 0 에 연결된 정점들:
1 4 
정점 1 에 연결된 정점들:
0 2 3 4 
정점 2 에 연결된 정점들:
1 3 
정점 3 에 연결된 정점들:
1 2 4 
정점 4 에 연결된 정점들:
0 1 3 

결론

배열을 이용하여 그래프 자료구조를 구현하는 방법을 살펴보았습니다. 이러한 구현은 간단하고 직관적이며, 그래프의 연결 상태를 효율적으로 저장하고 조회할 수 있습니다.