Graph에 대하여

GRAPH란?

그래프 알고리즘은 수학자 ‘오일러’에 의해 고안되었다고 한다.

수학 문제를 풀다가 한번쯤 마주쳤을 법한 문제인 ‘쾨니히스베르크의 다리 문제’를 풀기 위해 그래프 이론을 사용했다고 한다.

문제 : 모든 다리를 한 번씩만 건너서 처음 출발했던 장소로 돌아올 수 있는가?

그래프에는 정점 과 간선 이 있다.

정점 은 Node, Vertex라고 불리고

간선 은 Edge라고 불린다.

‘정점’은 연결의 대상이 되는 개체 또는 위치 를 의미하고

‘간선’은 정점 간의 관계 를 나타낸다.

---

GRAPH의 종류

그래프는 방향 그래프, 무방향 그래프 가 있다.

• 방향 그래프(Directed Graph) : 간선에 방향이 있다. digraph라고도 한다.

  

• 무방향 그래프(Undirected Graph) : 간선에 방향이 없다. 양방향 그래프(Bidirection Graph)라고도 함.

  • 1-3인 경우, 1->3과 3->1로 저장해야 한다.

    

그리고 방향/무방향 그래프 는 간선의 연결 형태에 따라 완전 그래프 로 구분이 된다.

• 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프

  

  

• 추가

  • 두 정점 사이에 간선이 여러 개일 수도 있다.

    

  • 간선의 양 끝점이 같을 수도 있다.(루프)

    

간선에 가중치 정보를 제공하여 그래프를 구성 할 수도 있다.

가중치가 없는 경우에는 가중치가 ‘1’이라고 생각하면 된다.

가중치 는

• 한 정점에서 다른 정점으로 이동하는데 소요되는 시간, 소모 비용, 거리 등이 될 수 있다.

---

Graph에서 사용하는 용어

1. 경로

   1. 한 정점(시작점)에서 다른 정점(도착점)으로 가는 연속된 간선들.

   2. 최단 경로 가 중요하다.

      

      • 정점 1에서 5까지 가는 경로
        • 1 -> 2 -> 3 -> 4 -> 5
        • 1 -> 2 -> 4 -> 5
        • 1 -> 3 -> 4 -> 5
        • 1 -> 3 -> 5
        • 1 -> 4 -> 5

   3. 단순 경로

      • 같은 정점을 두 번 이상 방문하지 않는 경로다.
2. 사이클

   1. 시작점과 도착점이 같은 경로

      

      • 정점 3에서 다시 3으로 돌아오는 경로 * 3 -> 4 -> 1 -> 2 -> 3 * 3 -> 4 -> 1 -> 3

   2. 단순 사이클

      • 같은 정점을 두 번 이상 방문하지 않는 사이클이다.

3. 차수

   1. 정점과 연결되어 있는 간선의 개수를 나타낸다.

      

      • 정점 3의 차수 : 4
      • 정점 5의 차수 : 2

   2. 방향 그래프의 경우

      • In-degree(들어오는)와 Out-degree(나가는)로 나누어서 계산.

        

        • 4의 In-degree : 3
        • 4의 Out-degree : 1

---

그래프의 표현

그래프는 인접 행렬(adjacent matrix) 혹은 인접 리스트(adjacent list) 를 이용해서 표현 할 수 있다.

인접 행렬

​ 정점의 개수를 V라고 했을 때, V×V 크기의 이차원 배열을 이용한다.

​

	1	2	3	4	5
1	0	1	1	1	0
2	1	0	1	0	0
3	1	1	0	1	1
4	1	0	1	0	1
5	0	0	1	1	0

​ 이처럼 정점을 연결하는 간선이 있는 경우에는 1 , 없는 경우에는 0 으로 나타낸다.

#### * 가중치 그래프인 경우

​

	1	2	3	4	5
1	0	1	6	3	0
2	1	0	5	0	0
3	6	5	0	4	2
4	3	0	4	0	3
5	0	0	2	3	0

​ v 정점에서 x 정점의 가중치를 넣어주면 된다.

인접 리스트

​ 정점 V와 연결된 정점들을 리스트로 표현한다.

​

​ A[1] 2 3 4

​ A[2] 1 3

​ A[3] 1 2 4 5

​ A[4] 1 3 5

​ A[5] 3 4

	* 이때, 저장된 정점의 순서는 중요하지 않다.
	* 리스트의 크기는 동적으로 변경할 수 있어야 하므로 C++의 vector나 JAVA의 ArrayList가 구현에 용이하다.

* 가중치 그래프인 경우

​

​ A[1] (2,1) (3,6) (4,3)

​ A[2] (1,1) (3,5)

​ A[3] (1,6) (2,5) (4,4) (5,2)

​ A[4] (1,3) (3,4) (5,3)

​ A[5] (3,2) (4,3)

* 위와 같이 (연결된 정점, 가중치)의 쌍을 리스트에 포함하면 된다.

인접 행렬과 인접 리스트의 비교

• 공간 복잡도
  • 인접 행렬 : O(V^2)
    • 인접 행렬은 정점의 개수(V)×정점의 개수(V) 크기의 행렬이니까.
  • 인접 리스트 : O(E)
    • 간선만 저장하면 된다. 즉, 간선의 개수 만큼

인접 리스트가 일반적으로 공간이 적게 들텐데…그러면 인접 행렬은 언제 쓰는 거지?

1. 정점 u, v를 잇는 간선의 존재 여부를 찾을 때
   • A[u] [v]가 0인지 아닌지만 확인하면 된다. O(1)이 된다.
   • 하지만, 리스트에서는 A[u]를 모두 찾아서 v가 있는지 확인해야 한다.
2. 방향 그래프에서 u->v의 반대 방향이 있는지 찾을 때
   • A[v] [u]가 0인지 아닌지만 확인하면 된다. O(1)이 된다.
   • 하지만, 리스트에서는 A[v]를 모두 찾아서 u가 있는지 확인해야 한다.
3. 완전 그래프인 경우
   • 완전 그래프에서 간선의 개수는
     • E = V(V-1)/2가 된다.
     • 따라서, 이때는 인접 행렬이 더 편하다.

추가적인 표현 방법

​ 만약, 역량 평가 시험장에서 library를 쓰지 못하게 하거나, c만 써야하는 경우!

​ 나는 C++, JAVA 잘 몰라요~하는 경우!

​ 정말로 linked list를 구현해야 하는 경우!

​ 이럴 때는 어떻게 하느냐!

1. 간선에 대한 정보를 모두 저장 한다.

​ E[0] = 1 2

​ E[1] = 1 3

​ E[2] = 1 4

​ E[3] = 2 1

​ E[4] = 2 3

​ E[5] = 3 1

​ E[6] = 3 2

​ E[7] = 3 4

​ E[8] = 3 5

​ E[9] = 4 1

​ E[10] = 4 3

​ E[11] = 4 5

​ E[12] = 5 3

​ E[13] = 5 4

1. 간선의 앞 정점을 기준으로 개수를 센다.

   i	0	1	2	3	4	5
   count[i]	0	3	2	4	3	2

2. 숫자를 누적한다.

   i	0	1	2	3	4	5
   count[i]	0	3	3+2	3+2+4	3+2+4+3	3+2+4+3+2

   i	0	1	2	3	4	5
   count[i]	0	3	5	9	12	14

   • 이렇게 하면 정점 n에 저장된 간선들은 E[count[n-1]]~E[count[n]-1]에 있음을 쉽게 알 수 있다.
     • 정점 1과 관련된 간선들은 E[0]~E[2]
     • 정점 3과 관련된 간선들은 E[5]~E[8]

---

아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

---