주의점 : 일반적인 코딩테스트에 나오는 그래프는 단순 그래프(정점 사이의 Edge는 한개이며, 루프가 존재하지 않는다 ) 라는 정의가 있어야만 단순 그래프 형식으로 생각해야 된다!
1-4) 표현법
행렬
편의상 단순 그래프, 즉 두 정점 사이의 간선이 1개 이하인 그래프라고 할 때 연결된 두 정점에는 1을, 연결되지 않은 두 정점에는 0
무방향 그래프시 대칭 형태
두 점이 연결되어 있는지를 O(1)
공간복잡도 O(V²)
Node와 연결된 Node를 확인 O(V)
효율 = 두점의 연결 여부 확인 / E가 V² 에 가까울수록
리스트
인접 행렬과 비교했을 때 정점이 많고 간선은 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식
두 점이 연결되어 있는지를 O( min(deg(u) , deg(v) )
공간 복잡도 O(V+E)
Node와 연결된 Node를 확인 O( deg(V) )
2. DFS
STACK 혹은 재귀로 구현 가능 ( 재귀로 구현 시와 STACK이랑 구현 시 결과 값이 다를 수 있으니 주의 )
BOJ 1260 - DFS
import sys
from collections import deque
input = sys.stdin.readline
dfs_answer = []
def dfs ( graph , visited , start ) :
dfs_answer.append(start)
visited[start] = 1
if start in graph :
graph[start].sort()
for data in graph[start] :
if visited[data] :
continue
dfs ( graph , visited , data )
return dfs_answer
def solution( ) :
n , m , start = map ( int , input().split() )
graph = dict()
for _ in range( m ) :
u , v = map ( int ,input().split() )
if u in graph :
graph[u].append( v )
else :
graph[u] = [v]
if v in graph :
graph[v].append( u )
else :
graph[v] = [u]
#DFS
print ( ' '.join ( str(x) for x in dfs ( graph , [False]* ( n + 1 ) , start ) ) )
3. BFS
Queue를 이용하여 구현 가능
BOJ 1260 - BFS
import sys
from collections import deque
input = sys.stdin.readline
def bfs ( graph , start , visited) :
answer = []
queue = deque()
queue.append( start )
visited[start] = True
while ( queue ) :
temp = queue.popleft()
answer.append( temp )
if temp in graph :
for data in graph[temp] :
if visited[data] :
continue
visited[data] = True
queue.append(data)
return answer
def solution( ) :
n , m , start = map ( int , input().split() )
graph = dict()
for _ in range( m ) :
u , v = map ( int ,input().split() )
if u in graph :
graph[u].append( v )
else :
graph[u] = [v]
if v in graph :
graph[v].append( u )
else :
graph[v] = [u]
#VFS
print ( ' '.join ( str(x) for x in bfs ( graph , start , [False]* ( n + 1 ) ) ) )
solution()
