[Graphs] 개념 공부

<출처: leetcodes-interview-crash-course-data-structures-and-algorithms>

 

자 오늘은 새롭지만 트리와 비슷한 개념을 가진친구 Graphs를 공부해보자.

 

leetcode!

주목해야할만한 개념으로는 그전에 배웠던 Trees 의 상위범주라는것. 트리는 그래프에 많은 제한을 걸어서 특정 룰을 만든것에 지나지 않는다고한다. 

---

Terminology

• Edge of a node  -Direct 혹은 undirect 가 있으며 전자는 한방향(A->B)으로 이동가능한것이며 후자는 양방향(A<->B)으로 이동가능 (Tip binaray tree에서는 위에서 아래로 내려올수밖에없는 direct 구조)
• Connected component - 연결된 노드의 그룹 
• Neighbors - 말그래도 붙어있는 노드들을 지칭.(parent 와 child 라는 말로 많이씀)
• Indegree , Outdegree - 전자의 말은 한노드에 parent를 가리키는노드로 보통 1 indegree가 있으며(root node 제외) 밑에 달린 child 노드이 갯수를 나타낼때는 Outdegree로 말한다. 0 outdegree라면 그것은 leaf (끝에 매달림).
• cycle , acylic - 순환하는  그래프 모양과 그반대 말을 뜻한다. 

---

어떤식으로 문제가 나오나?

linked list에서는 head가 주어지고 binary tree에서는 root가 주어졌다면 그래프 문제에서는 오직 그래프가 주어진다.  binary tree는 root -> left , root->right 처럼 정해져서 쉬운데 graph는 이와 다르게 child가 2개 이상일 수 있어 모든 경우를 고려해야한다!  (아 해쉬맵이 여기서 나오는데 이해가 잘안되네.  거대한 티스토리 개발자들의 어깨에 올라타자. )

 

<그래프의 구현 방법은 크게 2가지가 있다  <출처:https://hongcoding.tistory.com/78>  감사합니다 잘쓰겠습니다. >

 

1. 인접 행렬방식

• 인접행렬 방식
  
  인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.
  노드들 간에 직접 연결이 되어있으면 1을, 아니면 0을 넣어서 행렬을 완성시킨 것이다.
  
  
• 인접행렬의 장점
  • 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다.
  • 인접리스트에 비해 구현이 쉽다.
• 인접행렬의 단점
  • 모든 정점에 대해 간선 정보를 대입해야 하므로 $O(n^2)$ 의 시간복잡도가 소요된다.
  • 무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다

 

2. 인접리스트 방식

• 인접리스트는 그래프의 노드를 리스트로 표현한 것이다.
  
  주로 정점의 리스트 배열을 만들어 관계를 설정하며 노드들 간에 직접 연결이 되어있으면 해당 노드의 인덱스에 그 노드를 삽입해주면 된다.
  
  즉, 1에는 2와 3이 직접 연결되어 있기 때문에 배열의 1번째 칸에 2와 3을 넣어준다. (여기서 hash 느낌이군)

  

• 인접리스트의 장점
  1. 정점들의 연결 정보를 탐색할 때 O(n) 시간이면 가능하다. -> hash의 특성 예를 들어 2번에서 4번노드를 찾기위해서 1 ,3 을 거쳐야하기때문에 
  2. 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.
• 인접리스트의 단점
  1. 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. (O(E) 시간 소요. E는 간선의 개수)
  2. 구현이 비교적 어렵다.

---

그래프 모양 (꽤나 다른곳에서 많이다루네)

 

• 완전 그래프(Complete graph)
  그래프의 모든 정점이 서로 연결되어 있는 그래프이다. (인접 연결)
  
  

• 신장트리(Spanning Tree)

여러가지 경우의수가 존재함 (빨강이들).

모든노드가 연결되어있으나 트리의 속성을 만족하는 그래프 -> 사이클이 존재하면 안됨.