[TIL] 그래프 종류와 표현 방식

그래프

연결되어 있는 객체 간의 관계를 표현하는 비선형 자료 구조

그래프의 정의

그래프 G 는 (V, E) 로 표시한다 << 이 표기법을 언제 사용하는건지 질문 받았었는데

추가로 알아보니, 코드에서는 E (간선의 집합)을 직접적으로 사용하지 않고, 코드에서는

주로 V (정점의 집합)과 그래프의 인접 리스트나 인접 행렬을 통해 간선을 간접적으로 표현한다고 한다

다시 정리하면, (V, E) 는 그래프에서 V 라는 이름의 정점들이 있고,

그 정점을 사이를 연결하는 E 라는 이름의 간선들이 있다는 것을 의미한다

따라서 (V, E) 표기는 그래프의 구조를 간단하고 명확하게 나타낼 수 있기 때문에

알고리즘을 설계하거나 설명할 때 주로 사용한다고 한다 

 

V - Vertex 정점, 여러 가지 특성을 가질 수 있는 객체, Node 

E - Edge 간선, 정점들 간의 관계, Link 

출처 https://www.notion.so/a7f03b96950c48189edbd9ab12e70a10

 

무방향 그래프에서 두 노드가 연결되어 있으면 두 노드는 인접하다고 표현 가능하다 

무방향 그래프와 가중치 그래프에서는 A 와 B 가, A 와 C 가 인접하다, B 와 C 는 인접하지 않다 

 

하지만 방향 그래프에서는 간선이 A 에서 B 쪽으로 방향을 갖고 있어서 A 가 B 로는 인접하고 B 에서 A 로는 인접하지 않다 

A, C 도 마찬가지로 C 에서 A 로 방향을 갖고 있으므로 C 에서 A 로 인접하고 A 에서 C 로는 인접하지 않다 

무방향 그래프, 방향 그래프, 가중치 그래프

 

그래프 구현

1. 인접 행렬

인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현한 것으로, 

2차원 리스트를 사용하여 인접 행렬을 구현할 수 있다

 

연결된 노드는 1, 연결되지 않은 노드는 0 으로 표시한다 

 

무방향 그래프와 가중치 그래프의 경우 대각선을 기준으로 대칭이지만 방향 그래프는 그렇지 않다 

또한 가중치 그래프의 경우 연결되어 있지 않은 경우 무한으로 표현한다 

	무방향 그래프			방향 그래프			가중치 그래프
연결 관계	A	B	C	A	B	C	A	B	C
A	0	1	1	0	1	0	0	5	2
B	1	0	0	0	0	0	5	0	INF
C	1	0	0	1	0	0	2	INF	0

(그래프를 깔끔하게 나누고 싶었는데 티스토리 그래프는 어떻게 편집하는지 잘 모르겠다)

+ 그래프를 행렬로 구현했을 때 어디가 기준이고 어디가 방향인지 헷갈렸는데, 관례적으로 | 가 기준, ㅡ 가 방향 (대상) 이라고 한다 

++ 연결되지 않은 노드들에 대해서 방향/ 무방향 그래프는 0 으로 표기하고, 가중치 그래프는 INF 로 표기하는 이유를 찾아봤다

가중치 그래프의 경우는 실제로 거리가 중요하기 때문에 연결되지 않은 상태를 무한대로 표시하지만

방향/ 무방향 그래프에서는 경로 존재 여부만 중요하기 때문에 0 으로 표기해도 충분하다고 한다 

 

인접 행렬 코드 구현

무방향 그래프

graph = [
   [0, 1, 1],
   [1, 0, 0],
   [1, 0, 0]
]

print(graph[0][1]) # 1 출력
print(graph[2][1]) # 0 출력

방향 그래프 

graph = [
   [0, 1, 0],
   [0, 0, 0],
   [1, 0, 0]
]

print(graph[0][2]) # 0 출력
print(graph[2][0]) # 1 출력

가중치 그래프

INF = 21470000000

graph = [
   [0, 5, 2],
   [5, 0, INF],
   [2, INF, 0]
]

print(graph[0][1]) # 5 출력
print(graph[1][2]) # 21470000000 출력

 

2. 인접 리스트

그래프에서 각 노드에 연결된 다른 노드들을 리스트로 표현하는 방식

각 노드마다 해당 노드와 연결된 노드들의 정보를 리스트나 배열로 저장해서

노드 간의 연결 관계를 효율적으로 표현하는 방법 

무방향 그래프

 

방향 그래프

가중치 그래프

인접 리스트 코드 구현 

무방향 그래프

# 인접 리스트 초기화
graph = [[] for _ in range(3)]

# A에서 B, C로의 연결
graph[0].append(1)  # A -> B
graph[0].append(2)  # A -> C

# B에서 A로의 연결
graph[1].append(0)  # B -> A

# C에서 A로의 연결
graph[2].append(0)  # C -> A

# graph[0] (A)에 연결된 모든 노드 출력
print("노드 A의 연결:")
for node in graph[0]:
    print("노드", node)
    
# 출력 결과
# [[1, 2], [0], [0]]

 

가중치 그래프

# 인덱스 A, B, C 를 각각 0, 1, 2 로 표기
graph = [[] for _ in range(3)]

# A 에서의 연결을 가중치를 포함하여 튜플로 저장
graph[0].append((1, 5))
graph[0].append((2, 2))

# B 에서 A 연결을 가중치 포함하여 튜플로 저장
graph[1]. append((0, 5))

# C 에서 A 연결을 가중치 포함하여 튜플로 저장
graph[2].append((0, 2))

# graph[0] (A) 에 연결된 모든 노드와 그 가중치를 출력 
# 노드 A 가 연결된 노드 B 와 C 의 정보를 출력
for i in range(len(graph[0])):
    print("노드", graph[0][i][0], ", 가중치", graph[0][i][1])
    
# 출력 결과
# 노드 1 , 가중치 5
# 노드 2 , 가중치 2

 

인접 행렬과 인접 리스트의 차이

	인접 행렬	인접 리스트
특징	모든 관계를 저장한다	연결된 노드에 대한 정보만 저장한다
장점	두 노드의 연결 정보를 빠르게 탐색할 수 있다	간선 개수에 비례하는 메모리만 차지한다
단점	그래프에 대한 정보가 커질수록 메모리 낭비가 심하다	두 노드에 대한 연결 정보를 얻는 속도가 느리다

 

 + 그래프 탐색 알고리즘은 DFS, BFS 가 있고 내일 공부할 예정 

 

참고한 블로그

https://c4u-rdav.tistory.com/19