graph
tree
그래프의 한 종류로 DAG(Directed Acyclic Graphe) 방향성이 있는 비순환 그래프의 한 정류
Directed Graph 방향 그래프이다.
cycle 불가능하고, 자체 간선(self-loop) 불가능, 비순환그래프
하나의 루트 노드만이 존재하고 모든 자식 노드는 하나의 부모 노드만을 가진다.
부모-자식 관계는 top-bottom 과 bottom-top으로 이뤄진다
계층 모델이다.
DFS, BFS 안의 pre-, in-, post-order로 순회한다.
간선의 수는 노드가 N인 트리는 항상 n-1의 간선을 가진다.
경로는 임의의 두 노드 간의 경로로 유일하다.
예시 및 종류로는 이진 트리, 이진 탐색 트리, 균형트리, 이진힙 등이 있다.
=> 정리하자면 트리는 그래프 중에서 방향성이 있는 비순환 그래프이다.
출처 : https://developer-mac.tistory.com/64
루트 노드(Root Node) 혹은 다른 임의의 Node 에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
자기 자신을 호출하는 순환 알고리즘
형태
전위 순회(Pre-Order Traversals)을 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류임
이 알고리즘의 구현은, 그래프 탐색의 경우 '어떤 노드를 방문했었는지에 대한 여부를 반드시 검사' 해야 함
얻어진 해가 최단 경로가 된다는 보장이 없는데, 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버려, 이때 얻어진 해는 최적이 아닐 수 있음
왼쪽 그림이 DFS의 탐색 방법
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3
Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Output: DFS from vertex 2 : 2 0 1 3
출처 : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def DFSUtil(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
def DFS(self, v):
visited = set()
self.DFSUtil(v, visited)
if __name__ == "__main__":
g = Graph()
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,2)
g.addEdge(2,0)
g.addEdge(2,3)
g.addEdge(3,3)
print('following is Depth First Traversal (starting from vertex 2)')
g.DFS(2)
=> 즉, DFS는 '경로의 특징'을 저장해 둬야 하는 문제나
검색 대상 그래프가 클 때 사용함
[LeetCode]