목차
- 인접리스트
- 인접행렬
인접리스트
# 입력
n,m,s=map(int,input().split()) #n-노드갯수, m-입력갯수, s-시작정점
adj_list=[[] for _ in range(n+1)]
for _ in range(m):
a,b=map(int,input().split())
adj_list[a].append(b)
adj_list[b].append(a)
#####################################################
visited=[None]*(n+1)
# DFS 함수 정의
def dfs(v):
adj_list[v].sort() #노드번호가 작은순부터 탐색할경우
# 현재 노드를 방문 처리
visited[v] = True
print(v)
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in adj_list[v]:
if not visited[i]:
dfs(i)
print('[DFS 방문순서]')
dfs(s)
인접행렬
# 입력
n, m, s = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
matrix[f][t] = matrix[t][f] = 1
################################################
def dfs(v):
visited[v] = True
print(v)
for i in range(len(matrix[v])):
if matrix[v][i] == 1 and not visited[i]:
dfs(i)
dfs(s)
'Computer Science > 알고리즘 템플릿' 카테고리의 다른 글
다익스트라 Dijkstra (1) | 2023.12.07 |
---|---|
BFS (1) | 2023.12.07 |