def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited
def dfs2(graph, start_node):
## deque 패키지 불러오기
from collections import deque
visited = []
need_visited = deque()
##시작 노드 설정해주기
need_visited.append(start_node)
## 방문이 필요한 리스트가 아직 존재한다면
while need_visited:
## 시작 노드를 지정하고
node = need_visited.pop()
##만약 방문한 리스트에 없다면
if node not in visited:
## 방문 리스트에 노드를 추가
visited.append(node)
## 인접 노드들을 방문 예정 리스트에 추가
need_visited.extend(graph[node])
return visited
vector<vector<int>> adjacent; //인접 행렬로 구현된 그래프 들어감
vector<bool> visited; // 그래프의 정점만큼의 크기로 생성
void DFS(int now)
{
visited[now] = true;
int N = adjacent.size();
for (int i = 0; i < N; i++)
{
if (adjacent[now][i] == 0)
continue;
if (!visited[i])
DFS(i);
}
}
DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로
n*O(n)이므로 O(n^2)의 시간복잡도를 가지게 된다.따라서 O(n^2)의 시간복잡도를 가지게 된다.
vector<vector<int>> adjacent; //인접 리스트로 구현된 그래프 들어감
vector<bool> visited; // 그래프의 정점만큼의 크기로 생성
void DFS(int now)
{
visited[now] = true;
for (int i = 0; i < adjacent[now].size(); i++)
{
int next = adjacent[now][i];
if (!visited[next])
DFS(next);
}
}
DFS가 총 N번 호출되긴 하지만 인접행렬과 달리 인접 리스트로 구현하게 되면 DFS하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되므로 예측이 불가능 하다. 하지만 DFS가 다 끝난 후를 생각하면, 모든 정점을 한번씩 다 방문하고, 모든 간선을 한번씩 모두 검사했다고 할 수 있으므로 O(n+e)의 시간이 걸렸다고 할 수 있다.
따라서 시간복잡도는 O(n+e)이다.
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://velog.io/@cha-suyeon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-%EA%B3%BC-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS
https://currygamedev.tistory.com/10
https://data-marketing-bk.tistory.com/44