그래프
vertex라고 불리는 node들의 집합 V와 edge의 집합 E로 이루어진 (V,E)
Directed Edge : 순서가 정해진 정점의 쌍
Undirected Edge : 순서가 정해지지 않은 정점의 쌍
Directed Graph : 모든 Edge들이 Directed Edge인 경우
Undirected Graph : 모든 Edge들이 Undirected Edge인 경우
adjacent : 어떤 edge가 두 vertex를 이으면 그 vertex들은 서로 adjacent합니다.
tree : 사이클이 없는 그래프는 tree라고 합니다.
self loop : self loop는 vertex자신을 연결하는 edge입니다.
parallel : 두 edge들은 그들이 같은 vertex 쌍을 연결하면 parallel이라고 합니다.
degree : ****vetex의 degree는 그 점에 연결되 edge의 수 입니다.
path : path는 인접한 vertex들의 sequence입니다.
cycle : 첫번째 점과 마지막 점이 같은 경로입니다.
DAG(Directed Acyclic Graph) : 방향 그래프에 사이클이 없는 경우를 말한다.
Forest : tree들의 disjoint set
Spanning Tree : 그래프의 모든 정점을 포함한 하나의 트리
Bipartile Graph : 정점들이 두 집합으로 나누어지고 모든 간선들이 한 집합의 정점들과 다른 집합의 정점들을 연결하는 그래프
Weighted Graph : weight이 각 간선에 할당
Complete Graph : 모든 간선이 존재하는 그래프
Sparce Graph : edge가 상대적으로 적은 graph
Dense Graph : edge가 상대적으로 많은 graph
Network : 방향 가중치 그래프
-
그래프의 표현 : 인접행렬
크기가 VxV인 행렬 Adj를 사용
정점 u로부터 v까지의 간선이 있을 때, Adj[u,v]의 값은 1이 되고, 그렇지 않으면 0
-
그래프 탐색
-
Depth First Search (깊이 우선 탐색)
내부적으로 스택을 사용
막다른 곳으로부터 돌아오는 과정을 백트래킹이라고 부릅니다.
-
그래프의 주어진 정점 u에서 시작
-
u부터 다른 정점으로 향하며 간선들을 검사
-
만약 그 간선이 이미 방문한 정점에 연결되어 있다면 현재의 정점 u로 돌아옴
-
방문하지 않은 정점에 연결되어 있다면, 그 정점으로 이동하여 그 정점부터 다시 처리를 시작
-
이 과정을 막다른 곳에 다다를 때까지 반복
-
백트래킹이 시작되는데, 이는 최초 백트래킹을 시작한 정점에 닿을 때 종료
-
-
Breadth First Search (너비 우선 탐색)
-