그래프 (Graph)
- 노드와 그 노드를 연결하는 간선의 집합으로, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조
- 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트 2가지 방법이 있다.
인접 행렬
- 이차원 배열로 그래프의 연결 관계를 표현하는 방식으로, 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비가 심하다.
- 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 알 수 있으므로 효율성이 떨어진다.
인접 리스트
- 리스트로 그래프의 연결 관계를 표현하는 방식으로, 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다.
- 인접 행렬에 비해 특정한 두 노드의 연결 정보를 얻는 속도가 느리다.
n, m = map(int,input().split())
# 인접 행렬
a = [[False] * n for _ in range(n)]
# 인접 리스트
g = [[] for _ in range(n)]
for _ in range(m):
u, v = map(int,input().split())
# 인접 행렬 저장
a[u][v] = a[v][u] = True
# 인접 리스트 저장
g[u].append(v)
g[v].append(u)
이분 그래프
- 노드가 두 개의 집합으로 나뉜 그래프
- 이분 그래프의 간선은 같은 집합 내에 존재할 수 없고 항상 다른 집합 사이에서만 존재할 수 있다.
from collections import deque
t = int(input())
for _ in range(t):
v, e = map(int, input().split())
graph = [[] for _ in range(v + 1)]
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
bipart = [[] for _ in range(2)]
check = [False] * (v + 1)
q = deque()
q.append((1, 0))
check[1] = True
bipart[0].append(1)
flg = True
while q:
now, s = q.popleft()
for nxt in graph[now]:
# 같은 집합 안에 있으면 종료
if nxt in bipart[s]:
flg = False
break
if nxt not in bipart[1 - s] and check[nxt] == False:
bipart[1 - s].append(nxt)
q.append((nxt, 1 - s))
check[nxt] = True
if flg == False:
break
# 그래프가 분리되있는 경우
if not q:
for i in range(1, v + 1):
if check[i] == False:
bipart[0].append(i)
q.append((i, 0))
check[i] = True
break
if flg == False:
print("NO")
else:
print("YES")
그래프 VS 트리
그래프 | 트리 | |
정의 | 노드와 그 노드를 연결하는 간선의 집합 | 그래프의 한 종류로, 방향성이 있는 비순환 그래프 |
방향성 | 방향, 무방향 모두 가능 | 방향 그래프만 가능 |
사이클 | 순환, 비순환, 루프 모두 가능 | 비순환 그래프만 가능 |
루트 노드 | 루트 노드의 개념이 없음 | 한 개의 루트 노드만 존재 |
부모-자식 | 부모-자식 개념이 없음 | 루트 노드를 제외한 노드는 1개의 부모 노드만 가짐 |
모델 | 네트워크 모델 | 계층 모델 |
간선의 수 | 간선의 수에 제약이 없음 | N개의 노드를 가지는 트리는 항상 N-1개의 간선을 가짐 |
경로 | 임의의 두 노드 간의 경로는 유일 |
그래프 탐색
- 그래프 탐색이란 그래프의 각 정점을 방문하는 과정을 말하며, 크게 깊이 우선 탐색과 너비 우선 탐색 2가지 알고리즘이 있다.
BFS
- 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 점점으로 나아가며 탐색하는 방식
- 주로 큐로 구현하며 그래프의 최단 경로를 구하는 문제 등에 사용한다.
- 시간 복잡도는 O(V+E) (V는 노드의 수, E는 간선의 수)
from collections import deque
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9
q = deque()
q.append(1)
visited[1] = True
while q:
now = q.popleft()
print(now, end=" ")
for nxt in graph[now]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)
DFS
- 그래프 상에 존재하는 임의의 한 정점으로부터 나아갈 수 있는 정점이 존재할 때까지 계속 나아가다가, 더 이상 나아갈 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 탐색하는 방식
- 그래프에서 모든 노드를 방문하고자 할 때 더 선호되는 방법
- 주로 스택이나 재귀로 구현하며, 백트래킹을 통해 효율성을 높인다.
백트래킹
- 해결책에 대한 후보를 구축해 나가다가 가능성이 없다고 판단되면 즉시 후보를 포기하고 되돌아가 정답을 찾아가는 알고리즘
- 수많은 제약 조건을 충족하는 상태를 찾아내는 제약 충족 문제에 유용한다.
def dfs(x):
global visited
visited[x] = True
print(x, end=" ")
for i in dic[x]:
# 이전에 방문하지 않은 경우
if not visited[i]:
dfs(i)
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9
'Python > Algorithm' 카테고리의 다른 글
트리의 종류와 트리 순회 (0) | 2022.02.26 |
---|---|
최단 경로 알고리즘 (0) | 2022.02.25 |
해시 테이블 (0) | 2022.02.24 |
스택과 큐 (0) | 2022.02.23 |
배열과 연결리스트 (0) | 2022.02.22 |