[자료구조] STL의 vector를 사용해서 인접 리스트를 구현 with Python

🔍 STL 이란?

STL은 C++ 표준 라이브러리(Standard Template Library)의 약자이다.

파이썬에서는 STL을 직접 사용하는 것이 아니기 때문에 파이썬에서 STL을 불러올 필요가 없다.

🔍 vector란?

vector는 sequence container 이다. vector에 인접 리스트의 정점들을 저장할 것이다.

또한 정점의 번호를 마치 vector의 index인것처럼 사용한다.

👉 이런 ‘vector’ 클래스와 동일한 기능을 하는 내장 모듈인 ‘list’를 사용할 수 있다.

C++의 STL에서 제공되는 ‘vector’ 클래스와 같은 인접 리스트를 파이썬에서 구현하려면, 파이썬의 내장 자료구조인 리스트(List)를 사용할 수 있다. 리스트는 동적으로 크기가 조정되는 배열과 같은 역할을 한다.

💻 파이썬에서 무향 그래프를 인접 리스트로 구현하는 간단한 예제

class Graph:
		# num_vertices 개수의 정점을 가진 무향 그래프의 인접 리스트를 초기화
		def __init__(self, num_vertices):
				self.num_vertices = num_vertices
				self.adj_list = [[] for _ in range(num_vertices)]

		# 두 정점의 인덱스를 인수로 받아 해당 정점들을 서로의 인접 리스트에 추가
		def add_edge(self, src, dest):
				self.adj_list[src].append(dest)
				self.adj_list[dest].append(src)

		# 그래프의 인접 리스트를 출력
		def print_graph(self):
				for vertex in range(self.num_vertices):
						print(f"Adjacency list of vertex {vertex}: ")
						for neighbor in self.adj_list[vertex]:
								print(f" -> {neighbor}", end="")
						print()

🔸 무향 그래프를 인접 리스트로 사용하는 예시

# 그래프 객체 생성
graph = Graph(5)

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

# 그래프 출력
graph.print_graph()

✅ 결과

Adjacency list of vertex 0:
 -> 1 -> 4
Adjacency list of vertex 1:
 -> 0 -> 2 -> 3 -> 4
Adjacency list of vertex 2:
 -> 1 -> 3
Adjacency list of vertex 3:
 -> 1 -> 2 -> 4
Adjacency list of vertex 4:
 -> 0 -> 1 -> 3

💻 파이썬에서 유향 그래프를 인접 리스트로 구현하는 간단한 예제

class Graph:
		# num_vertices 개수의 정점을 가진 유향 그래프의 인접 리스트를 초기화
		def __init__(self, num_vertices):
				self.num_vertices = num_vertices
				self.adj_list = [[] for _ in range(num_vertices)]
		
		# 간선의 출발 정점 src와 도착 정점 dest를 인수로 받아, 출발 정점의 인접 리스트에 도착 정점을 추가
		def add_edge(self, src, dest):
				self.adj_list[src].append(dest)

		# 그래프의 인접 리스트를 출력
		def print_graph(self):
				for vertex in range(self.num_vertices):
						print(f"Adjacency list of vertex {vertex}: ")
						for neighbor in self.adj_list[vertex]:
								print(f" -> {neighbor}", end="")
						print()

🔸 유향 그래프를 인접 리스트로 사용하는 예시

# 그래프 객체 생성
graph = Graph(5)

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

# 그래프 출력
graph.print_graph()

✅ 결과

Adjacency list of vertex 0:
 -> 1 -> 4
Adjacency list of vertex 1:
 -> 2 -> 3
Adjacency list of vertex 2:

Adjacency list of vertex 3:
 -> 4
Adjacency list of vertex 4:
 -> 1