[서울대학교 논자시 준비] 알고리즘 : chapter 10 그래프 : dfs, bfs

1. dfs와 bfs의 시간 복잡도 dfs와 bfs 모두 인접리스트, 인접 행렬로 구현할 수 있다. N이 그래프의 노드의 수, E가 그래프의 간선의 수라고 하자. dfs와 bfs 모두 인접리스트로 그래프를 구현했을 때 O(N+E)의 시간 복잡도를 가지며 인접행렬로 구현했을 때 O(N^2)의 시간 복잡도를 갖는다. 2. bfs 소스코드 C++ BFS(G, s){ for each v ( s visited[v] = NO; } visited[s] = YES; enqueue(Q, s) while (Q!=0){ u

2023.08.26