1. DFS(Depth-first search)?- 갈 수 있는 가장 깊은 곳까지 내려가는 알고리즘- Pre/In/Post - order순회- 재귀를 이용하여 구현 가능하다. - 다음과 같은 그래프를 3을 기준으로 DFS한다고 생각해보자. (인접노드일때 값이 작은것부터 탐색한다.)- (3 -> 1 -> 0 -> 2 -> 4 -> 5 -> 6) 이 될것이다. 2. Code 구현dfs_visit = list()def DFS(graph,start_node): dfs_visit.append(start_node) for each_node in graph[start_node]: if (each_node in dfs_visit) == False: DFS(graph,each_..
1. Graph?- 두 대상 사이 관계를 나타낼 수 있는 자료구조- 아래의 그림처럼 동그란 점들이 Node, 점끼리 이어진 선들이 edge가 됨.1.1. wark?- 두 Node을 잇는 edge가 존재하는 경우 둘을 인접한다고 정의한다.-- 인접한 꼭짓점을 따라 이동한 족적을 Walk라고 한다.- 시작점과 끝점이 동일한 경우 닫힌 walk라고 하며,- 다른경우 열린 walk라고 한다. 1.2. path- walk 가운데 중복된 꼭짓점이 존재하지 않는 것을 path라고한다.1.3. cycle- 닫힌 walk와 path의 조건을 모두 만족하는 경우 이를 cycle이라고 한다.ex) 위의 그림에선 A - B - D - A 가 된다. 2. Directed Graph- 엣지에 방향이 존재하는 경우 Directed..
1. Disjoint set(서로소 집합)- Disjoint set(Union Find)는 대표적인 그래프 알고리즘이다.- 여러개의 노드가 존재할 때 두 개의 노드를 선택헤서 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘/ - 해당 그래프를 표로 나타내면 다음과 같다.012345000144 - 이렇게 부모를 합칠 때 일반적으로 더 작은 값 쪽으로 합친다. 이를 합침(Union)이라고 한다. - 하지만 해당 graph에서 3과 0이 연결되어있는지 어떻게 파악할 수 있는지가 관건이 된다.- 0의 부모는 0 3의부모는 1이므로 '부모노드'만 보고는 한번에 파악이 불가능이다. --> 그렇기에 재귀함수를 이용하여 해결 가능하다.ex)3의 부모노드 -> 11의 부모노드 -> 00의 부모노드 =..
