알고리즘 ch7 Graph

Graph and Graph Traversals

 

    Graph

-   정점과 간선으로 이루어지며 트리와 달리 계층(부모-자식)이 존재하지 않는 자료구조

- 주로 G(V,E)로 표현한다. (V:정점, E:간선)

- Directed graph : 간선이 방향이 있는 그래프, Digraph라고도 한다.

 정점이 v와 w가 있고, v에서 w로 가는 간선이 있다면

 directed edge는 (v,w)로 표현한다. 혹은 v→w , 간단하게 vw라고도 한다.

v는 source 또는 start라고 부르고, w는 destination 또는 end라고 부른다.

(v,w) ≠ (w,v) : 방향간선이므로 둘은 다르다

- Undirected Graph : 간선이 방향이 없는 그래프

undirected graph는 자기 자신으로 가는 간선을 정의하지 않는다.

    정점이 v와 w가 있고, v에서 w로 가는 간선이 있다면

    undirected edge는 {v,w}로 표현한다. 혹은 v－w , 간단하게 vw or wv라고도 한다.

    vw는 정점 v, w와 incident 하다고 말하기도 한다.

+ incident와 adjacent 구별 

 임의의 두 노드가 하나의 간선으로 연결되어있을시

  incident : 정점과 간선 사이의 관계 뜻함, 간선이 정점에 incident(부속) 되었다고 한다.

  adjacent : 정점과 정점 사이의 관계 뜻함, 두 정점이 서로 adjacent(인접) 되었다고 한다.

- Weighted Graph : 무방향 혹은 방향 그래프에서 간선에 가중치 혹은 우선순위 정보가 있는 그래프

-  그래프 표현방법: 간선의 정보 저장박식에 따라 인접리스트, 인접행렬 표현으로 나뉨

G = (V,E) , n = |V|, m = |E|, V= {v1,v2,v3,...,vn}일때

①     인접리스트: 공간복잡도 O(V+E), 간선의 수가 적은 그래프에서 유리

즉, graph가 sparse하다 = edge수가 노드 수보다 적다 일 경우 리스트 사용이 유리

②     인접행렬: 공간복잡도 O(V*V), 두 정점간 연결 유무를 바로 알수 있고 간선 수 많은 그래프 유리

   즉, graph가 dense하다 = edge수가 노드 수보다 많다 일 경우 행렬 사용이 유리

그래프의 연산 중 V.incidentAdge() , V.isAdjacentTo() 연산 비교

incidentAdge() : 정점에 연결된 간선 정보가 필요할 때 사용, 

     행렬은 O(n) time 리스트는 O(degree(v)) time

isAdjacentTo() : 두 개의 정점이 연결되있는 확인할 때 사용, 

   행렬은 O(1) time 리스트는 O(min(degree(v),degree(w)) 

degree : 정점에 연결된 간선의 수

-      graph용어

(1)   Directed edge: 방향이 있는 간선, 간선이 순서가 있는 쌍으로 구성

(2)   Undirected edge: 방향이 없는 간선(양방향 간선)

(3)   Adjacent vertex: 인접한 정점. 간선 하나로 도달할 수 있는 정점.

(4)   Degree of a vertex: 정점에서 연결된 간선의 수

 방향그래프에서 한 노드의 degree는 incoming degree와 outgoing degree로 나뉜다.

incoming degree : 한 노드 기준으로 들어오는 간선 수

outgoing degree : 한 노드에서 나가는 간선 수

(5)   Edges incident on a vertex: 정점에서 연결된 간선들.

(6)   Subgraph : 임의의 그래프 G = (V,E)가 주어졌을 때 다음을 만족하는 G' = (V',E')을 G의 subgraph라고 한다.

  - V'은 V의 부분집합니다.

  - E'은 V'에 부속되어 있으며, E의 부분집합이다.

(7)   Complete graph : 모든 노드들이 간선으로 연결되어 있는 그래프, 즉 간선의 수가 최대인 그래프

방향그래프에서 edge 수 = n*(n-1)

무방향그래프에서 edge 수 = n*(n-1) /2

어차피 둘다 O(n^2)

(8)   Path : 인접한 노드들로 구성된 시퀀스(1개이상), Path의 length는 경로내 존재하는 edge의 수

(9)   Simple path: 같은 정점이나 간선을 다시 방문하지 않는 path

(10)  cycle: 한 노드에서 시작해서 해당 노드에서 끝나는 nonempty path

(11)  Simple cycle : 첫번째와 마지막 정점을 제외하고 정점이 겹치지 않는 경우

  같은 정점이나 간선을 방문하지 않는 cycle

(12)  Reachable : 정점간 이동이 가능하면 reachable하다고 한다.

v1-v2-v3 일 경우 v1과 v3는 reachable

(13)  Connected : undirected graph에서 모든 정점간이 reachable할 때

(14)  Strongly connected : directed graph에서 모든 정점 간이 reachable할 때

(15)  Acyclic : 그래프에 cycle이 없는 상태

(16)  Directed acyclic graph(DAG): 사이클 없는 digraph

(17)  Free tree = Undirected Tree : 모든 정점이 connected하고, acyclic하고, undirected하는 graph

(18)  Root tree : Free tree에서 특정 노드가 Root인 경우

(19)  Forest : 서로 독립인 트리들의 집합

(20)  Connected component : 그래프는 여러개의 부분 그래프로 구성될 수 있는데 서로 연결되어 있는 여러개의 고립된 부분 그래프 각각을 connected component라고 한다. = Connected Maximal Subgraph라고도 한다.

+ vertex와 edge 관계 (m은 edge개수, n은 vertex개수)

- Undirected graph가 connected 하다면 m ≥ n-1

- Undirected graph가 tree 라고 한다면 m = n-1

- Undirected graph가 forest라고 한다면 m ≤ n-1

- Traversing Graph (여기서 Digraph만을 이용해서 설명하겠다)

  : vertex의 상태를 undiscovered, discovered, finished

   edge의 상태를 unexplored, explored로 나눠서 표현

  ① DFS(Depth First Search) : Edge를 4개로 분류해서 부르기도 한다.

* tree edge : 다음에 방문하는 정점이 undiscovered일 경우

* back edge : ancestor 관계

* descendant edge : descendant 관계

* cross edge : ancestor, descendant 관계도 아닌 관계

  ② BFS(Bread First Search)

- SCC(Strongly Connected Components)

 : 위의 용어설명에서 Connected Component에 대해 설명했다.

  그럼 SCC란 무엇일까? 

   Digraph 즉 방향그래프의 connected component 내 노드 u에서 v로 향하는 경로path, 노드 v에서 u로 향하는 경로가 존재하면 해당 connected component를 SCC라고 한다.

  방향그래프에서 SCC는 Kosaraju's algorithm( 2번의 dfs 이용 )을 이용해서 구한다.

  과정 1. digraph G에서 임의의 정점부터 dfs 수행, 수행 속에서 먼저 끝나는 vertex를 stack에 push 하여 저장

dfs 수행후 아직 방문하지 않은 정점이 있을 경우 해당 정점부터 다시 dfs수행

모든 정점을 방문할 때까지 dfs 수행

  과정 2. G의 간선 방향을 모두 바꾼 Gt 즉 transpose graph를 만든다.

Gt그래프를 대상으로 dfs 수행, 시작 vertex는 stack에서 pop한 순서대로 수행

스택이 비어있을 때까지 dfs 진행.

이때 탐색되는 모든 정점을 SCC로 묶는다. (leader 즉 starting point가 같으면 같은 SCC)

만약 스택 top에 위치한 정점이 이미 방문한 곳이면 pop만한다.

  코사라주 알고리즘의 시간복잡도

  과정 1. dfs 수행 시간 // O(n+m) time (인접리스트로 구현시에, 인접행렬이면 각 열마다 O(n)시간 걸림)

  과정 2. Gt 만드는 시간 // O(n+m) time

dfs 수행 시간 // O(n+m) time

  ∴ O(n+m)

  코사라주 알고리즘의 공간복잡도

  인접리스트 이용시 ∴ O(n+m)