그래프 기초

https://m.blog.naver.com/PostView.nhn?blogId=babobigi&logNo=220479341235&proxyReferer=https%3A%2F%2Fwww.google.com%2F

그래프 자료구조는 정점(Node, Vertex)과 정점간의 관계인 간선(Edge)으로 나타낼 수 있다.

        G = (V, E)

 

경로(Path)는 정점 a에서 b로 이동할 때의 다양한 방법을 나타낸다. 위의 그래프에서 1에서 4로 이동할 경우,

        1->3->4

        1->2->3->4

 

가 존재한다.

 

실생활에서의 예를 들면 서울에서 부산까지 갈 때, 대구를 거쳐서 가는지, 울산을 거쳐서 가는지에 따라 경로가 달라지겠다.

 

https://manducku.tistory.com/21

사이클(Cycle)은 a 정점에서 시작해서 같은 a 정점으로 돌아올 때의 경로이다. 위의 그래프에서 1에서 1로 돌아올 경우,

        1->2->4->3

이다.

 

또, 아래와 같을 때,

 

정점간 간선이 여러 개일 경우에는 다중 간선 그래프라 부른다.

 

 

그래프에서는 간선의 가중치(weight)라는 것이 존재할 수 있는데, 가중치가 있을 경우 가중치를 포함하여 그래프를 배열에 저장하게 된다. 간선의 가중치가 다 같을 때에는 가중치를 1로 놓을 수 있다.

 

실생활 가중치의 예로는 도로의 길이, 또는 이동하는데 소요되는 시간이 될 수가 있겠다.

 

 

차수

 

차수(Degree)는 어느 한 정점과 연결되는 간선의 갯수이다.

간선에 방향이 있을 경우, 정점으로 들어가는 간선의 개수를 in-degree라고 하고

정점에서 나오는 간선의 개수를 out-degree라 한다.

 

 

 

인접 행렬

 

 

정점과 간선을 컴퓨터에 저장할 때는 인접 행렬(Adjacency-matrix)를 이용할 수 있다.

 

정점의 개수가 V일 때, VxV 크기의 2차원 배열을 이용한다.

        A[i][j] = 1 (i->j로의 간선이 존재할 때), 0 (존재하지 않을 때)

 

ex)

     1  2  3  4  5  6

1   0  1  0  0  1  0

2   1  0  1  1  1  0

3   0  1  0  1  0  0

4   0  1  1  0  1  1

5   1  1  0  1  0  0

6   0  0  0  1  0  0

 

양방향 그래프에서는 인접 행렬이 항상 대칭행렬로 나온다. A[i][j] = A[j][i].

 

간선에 가중치가 존재할 때에는 1과 0 대신 가중치를 넣어 저장할 수 있다.

 

ex) 가중치 저장 예.

     1  2  3  4  5  6

1   0  2  0  0  7  0

2   2  0  1  4  2  0

3   0  1  0  1  0  0                   양방향 그래프의 경우, A[i][j] = A[j][i] = w

4   0  4  1  0  5  3

5   7  2  0  5  0  0

6   0  0  0  3  0  0

 

 

하지만 인접 행렬로 저장하면, 간선의 갯수와는 상관없이 항상 VxV의 공간을 확보해야 한다.

그래서 사용하는 것이 인접 리스트이다.

 

 

인접 리스트

 

 

인접 리스트는 vector와 같이 길이를 변경할 수 있는 배열을 사용한다.

가중치가 있을 때 pair를 사용하여 구현하면 편리하다.

 

ex) 정점에 따른 간선과 가중치 저장

a[1] (2,1) (5,3)

a[2] (1,3) (3,1) (4,5) (5,2)

a[3] (2,3) (4,2)

 

//source code

vector<pair<int,int>> a[n];

int n, m;

cin>>n>>m;

for(int i=0; i<m; i++){

    int u,v,w;

    scanf(&u,&v,&w);

    a[u].push_back(make_pair(v,w)); a[v].push_back(make_pair(u,w));  // 양방향 간선일 경우

}

 

 

간선 리스트

 

간선 리스트만을 저장하는 방법도 있다. 이 경우엔,

 

    E[0] = 1 2

    E[1] = 1 5

    E[2] = 2 1

    E[3] = 2 3

    E[4] = 2 4

    E[5] = 2 5

 

이런 식으로 간선들만을 배열에 저장한다.

또 정점당 간선 갯수를 저장하는 방법은,

 

   for(int i=0; i<n; i++){

       cnt[E[i][0]]++; }                       이고,

 

   for(int i=1; i<=n; i++){

       cnt[i] = cnt[i-1] + cnt[i]; }         로 누적 간선갯수를 저장하면

 

 

정점 i의 간선들은 E[cnt[i-1]] 부터 E[cnt[i]-1] 가 된다.