[알고리즘 - 기초] Python 인접 리스트 구현하기 ( feat. 유향 | 무향 )

 

 

🏃🏻 들어가며

DFS / BFS 구현 과정에서 데이터를 입력 받아 정리할때 사용하는 인접 리스트와 인접 행렬 방식이 있으며,

이번 글에서는 그중에서도 인접 리스트에 대해서 정리해 보았습니다.

 

이번글에서는 아래의 3가지 내용을 소개하고자 합니다.

첫번째로는 인접 리스트 구현 ( 유향  ) 

두번째로는 인접 리스트 구현 ( 무향 ) 

세번째로는 실제 PS 에서 사용하는 방식

 

---

 

✅  인접 리스트 구현하기

정점과 간선으로 이루어져 있는 그래프 구조의 데이터를 

1) 유향 ( 방향성이 있는 간선 ) 인접 리스트 구현하기

1-1) 유향 ( 방향성이 있는 간선 ) 인접 리스트

 

1-2) 실행 결과

 

1-3) 인접 리스트 구현

class DirectedGraph:
    def init(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, source, destination):
        if source in self.adjacency_list and destination in self.adjacency_list:
            self.adjacency_list[source].append(destination)

    def print_graph(self):
        for vertex in self.adjacency_list:
            print(f"{vertex}: {self.adjacency_list[vertex]}")

# 예시 사용
graph = DirectedGraph()

graph.add_vertex(1)
graph.add_vertex(2)
graph.add_vertex(3)
graph.add_vertex(4)
graph.add_vertex(5)

graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

graph.print_graph()

 

---

 

2) 무향 ( 방향성이 없는 간선 ) 인접 리스트 구현하기

2-1) 무향 ( 방향성이 없는 간선 ) 인접 리스트

2-2) 실행 결과

 

2-3) 인접 리스트 구현

class UndirectedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.adjacency_list and vertex2 in self.adjacency_list:
            self.adjacency_list[vertex1].append(vertex2)
            self.adjacency_list[vertex2].append(vertex1)

    def print_graph(self):
        for vertex in self.adjacency_list:
            print(f"{vertex}: {self.adjacency_list[vertex]}")

# 예시 사용
graph = UndirectedGraph()

graph.add_vertex(1)
graph.add_vertex(2)
graph.add_vertex(3)
graph.add_vertex(4)
graph.add_vertex(5)

graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

graph.print_graph()

 

---

✅  PS 에서 풀이를 할때 사용하는 방식

 

 

데이터 예시

V (정점 갯수)                   |  5

E (간선 갯수)                   |  7

edges (시작점, 끝점)    |  [(1,2), (1,4), (2,3), (2,4), (3,4), (3,5), (4,5)]

 

# 1 ~ V 까지 리스트를 사용하기 위해 V + 1 을 하여 빈 배열 리스트를 생성
AL = [[] for _ in range(V+1)]

# 주어진 edge 의 갯수 만큼 순회하며 s(시작점) , e(끝점) 데이터를 배열에 입력
for s,e in edges:
	AL[s].append(e)
    # AL[e].append(s) // 무향 그래프인 경우 사용
    
for x in AL:
	print(x)