딥러닝 공부방

이분 그래프 판별(bipartite graph distinction) 무방향 그래프의 이분 그래프를 판별하는 방법은 1) dfs, 2) bfs 두 가지 방법이 존재합니다. dfs 작동 원리 (1) 정점을 방문하면서 각 정점으 1, -1 두 그룹으로 번갈아 지정합니다. (2) 이미 방문했던 정점을 발견할 시에, 현재 정점과의 그룹을 비교하여 동일한 그룹인 경우 False를 반환합니다. bfs 작동 원리 (1) 동일한 level에 존재하는 정점을 같은 그룹으로 지정합니다. (2) 이미 방문한 정점인 경우, 현재 정점과의 그룹과 비교하여 동일한 그룹이면 False를 반환합니다. dfs 코드 # bipartite graph distinction # 1) dfs # 정점을 방문하면서 각 정점을 1, -1 그룹으로..

그래프 순회(Graph Traversals) 그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말합니다. 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversals)는 크게 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search)의 2가지 알고리즘이 있습니다. DFS가 일반적으로 BFS에 비해 더 널리 쓰입니다. DFS는 주로 스택으로 구현하거나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보입니다. 반면 BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용됩니다. 그래프 순회 알고리즘인 DFS와 BFS를 파이썬으로 구현해보도록 하겠습니다. 그래프를 우선 정의합니다. 그래..