Graph

Graph

Graph

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

Vertex(정점) : 위치를 의미하며 그래프에서의 하나의 점을 의미함. (=Node)

Edge(간선) : Vertex를 연결한 선을 의미 (=Link, Branch)

in-degree(진입차수) / out-degree(진출차수) : 한 정점에 진입하고 진출하는 간선이 몇 개인지를 표현

Adjacent Vertex (인접 정점) : Edge로 직접 연결된 Node

Undirected Graph (무방향 그래프) : 간선에 방향이 없는 그래프이며 양방향으로 이동 가능 A와 B가 연결되어 있는 경우 (A, B) 또는 (B, A)로 표기

(무방향 그래프) : 간선에 방향이 없는 그래프이며 양방향으로 이동 가능 Directed Graph (방향 그래프) : 간선에 방향이 있는 그래프이며, 한 방향으로만 이동 가능 A → B일 경우 로 표기

(방향 그래프) : 간선에 방향이 있는 그래프이며, 한 방향으로만 이동 가능 Network / Weight Graph (가중치 그래프) : 간선에 비용 또는

/ (가중치 그래프) : 간선에 비용 또는 Conntected Graph (연결 그래프) : 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우

(연결 그래프) : 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우 Disconnected Graph (비연결 그래프) : 무방향 그래프에서 특정 노드에 대해 항상 경로가 존재하지 않는 경우

(비연결 그래프) : 무방향 그래프에서 특정 노드에 대해 항상 경로가 존재하지 않는 경우 Cycle (사이클) : 단순 경로가의 시작 노드와 종료 노드가 동일한 경우

(사이클) : 단순 경로가의 시작 노드와 종료 노드가 동일한 경우 Ancycle Graph (비순환 그래프) : 사이클이 없는 그래프

(비순환 그래프) : 사이클이 없는 그래프 Complete Grpah (완전 그래프) : 그래프의 모든 노드가 서로 연결 되어 있는 그래프

(완전 그래프) : 그래프의 모든 노드가 서로 연결 되어 있는 그래프 Breadth First Search (BFS, 너비 우선 탐색) : 정점들과 같은 레벨에 있는 노드(형제노드)들을 먼저 탐색하는 방식 시간복잡도 : O(n) = O(V+E) // V : 노드 수, E : 간선 수 두개의 Queue를 이용해서 구현 가능

(BFS, 너비 우선 탐색) : 정점들과 같은 레벨에 있는 노드(형제노드)들을 먼저 탐색하는 방식 Depth First Search (DFS, 깊이 우선 탐색) : 정점의 자식들을 먼저 탐색하는 방식 시간복잡도 : O(n) = O(V+E) // V : 노드 수, E : 간선 수 한 개의 Queue와 한 개의 Stack을 이용해서 구현 가능

(DFS, 깊이 우선 탐색) : 정점의 자식들을 먼저 탐색하는 방식

from http://min-gi.tistory.com/12 by ccl(A) rewrite - 2021-12-02 06:27:18