그래프(Graph)

그래프

  그래프란 사물을 정점(vertex)와 간선(Edge)으로 나타내기 위한 도구이다.

  그래프는 두가지 방식으로 구현할 수 있다.

  인접행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식

  인접리스트(Adjacency List) : 리스트를 사용하는 방식.

 

  노드를 정점 혹은 노드라고 부르고 그 노드들을 이어주는 선을 간선이라고 한다.

  위 그림에서 0, 1, 2는 노드 3, 7은 간선이다.

 

  인접행렬에서 그래프는 2차원 배열로 표현한다.

  표를 보면 0에서 0으로 이동하는것은 이동하지 않기 때문에 0인것이고

  0에서 1로 이동하는 것은 3, 2로 이동하는것은 7 이런 형태이다.

  즉, 이동하는 간선이 3, 7인 것이다.

  무한이라고 되어있는 경우는 간선이 없는 경우이다.

  1에서 2로 가는 경우나 2에서 1로 가는경우는 간선이 없기 때문에 무한이다.

  그래프는 이런 2차원 배열 형태로 만든다.

 

무방향 비가중치 그래프와 인접행렬

  모든 간선이 방향성을 가지지않는 그래프를 무방향 그래프라고 하고

  모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 한다.

  무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접행렬도 출력할 수 있다.

  방향성을 가지지 않고 연결만 되어있는 그래프도 무방향 그래프라고 한다.

 

예제코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int a[1001][1001];
int n, m;

int main(void){
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i < m; i++){
    int x, y;
    scanf("%d %d", &x, &y);
    a[x][y] = 1;
    a[y][x] = 1;
  }
  
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      printf("%d ", a[i][j]);
    }
    printf("\n");
  }
  system("pause");
}

  5 3

  1 2

  3 4

  4 5

  이렇게 입력하면

  0 1 0 0 0

  1 0 0 0 0

  0 0 0 1 0

  0 0 1 0 1

  0 0 0 1 0

  이렇게 출력된다.

 

  a[x][y] = 1

  a[y][x] = 1

  이 부분을 처리할 때 보면 x와 y는 입력값으로 처음에 1와 2이 들어간다.

  n은 정점, m은 간선으로 5와 3이 처음에 입력되고 x와 y는 그 다음 입력값부터 들어간다.

  a[1][2] = 1,  a[2][1] = 1 이 형태가 되는건데

  이차원 배열이므로 첫행 2번째 인덱스에 1, 두번째행 1번째 인덱스에 1이 들어간다.

  출력문에서 보면 a[1][2] = 1 이   0 1 0 0 0 으로 출력된것을 확인 할 수 있다.

  출력하는 반복문을 0부터가 아닌 1부터 시작했기 때문에 0번째 인덱스는 제외하고 1번 인덱스부터 출력이 되서

  보이는 숫자 그대로의 위치로 확인한다.

  4번행은 1이 두번들어가있는데 3 4로 한번 4 5로 한번 들어갔기 때문에 두개의 인덱스에 1이 들어간것이다.

 

방향 가중치 그래프와 인접리스트

  모든 간선이 방향을 갖는 그래프를 방향그래프라고 한다.

  모든 간선에 가중치가 있는 그래프를 가중치그래프라고한다.

  방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접리스트로 출력할 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//스택기반 연결리스트

typedef struct{
  int index;
  int distance;
  struct Node *next;
} Node;
//한개의 노드 정의
//어떤 인덱스로 어떠한 만큼의 가중치
//즉, 거리를 갖는지 정의할 수 있도록 한다.
//연결리스트니까 next로 다음 노드를 기록할 수 있도록 한다.

void addFront(Node *root, int index, int distance){
  Node *node = (Node*)malloc(sizeof(Node));
  node->index = index;
  node->distance = distance;
  node->next = root->next;
  root->next = node;
}
/*
  가장 앞단에 데이터를 추가한다.
  어떠한 노드에 어떠한 인덱스까지 가는 거리가 얼마인지를 넣어준다.
*/

void showAll(Node *root){
  Node *cur = root->next;
  
  while(cur != NULL){
    printf("%d(거리 : %d) ", cur->index, cur->distance);
    cur = cur->next;
  }
}

int main(void){
  int n, m;
  scanf("%d %d", &n, &m);
  Node **a = (Node**)malloc(sizeof(Node*) * (n + 1));
  
  for(int i = 1; i <= n; i++){
    a[i] = (Node*)malloc(sizeof(Node));
    a[i]->next = NULL;
  }
  
  for(int i = 0; i < m; i++){
    int x, y, distance;
    scanf("%d %d %d", &x, &y, &distance);
    addFront(a[x], y, distance);
  }
  
  for(int i = 1; i <= n; i++){
    printf("원소 [%d] : ", i);
    showAll(a[i]);
    printf("\n");
  }
  system("pause");
  return 0;
}
/*
  노드의 개수를 n, 간선의 개수를 m에 입력받는다.
  인접리스트로 구현할 때는 노드의 개수만큼 연결리스트가 필요하기 때문에
  노드의 개수에 +1을 더한만큼 동적할당을 해준다.
  여기서 출력문을 만들 때 0부터가 아닌 1부터 출력하도록 할것이기 때문이다.
  0부터 출력한다면 더하지 않아도 되는 부분이다.
  
  첫 반복문에서 각 노드를 동적할당으로 초기화
  next에는 NULL을 넣어서 root가 NULL값을 가리키도록 한다.
  
  두번째 반복문은 각 간선의 정보를 사용자로부터 입력받도록 한다.
  입력받은 값을 바로 리스트화 하기 위해 addFront로 보내 처리한다.
  
  마지막 반복문에서는 각 원소를 출력하고
  showAll에서 특정한 노드 정점에 연결되어있는 다른 정점을 출력하도록 한다.
*/

  5 4

  1 2 9

  1 3 8

  1 5 10

  3 4 8

  이렇게 입력해주면

 

  원소 [1] : 5(거리 : 10) 3(거리 : 8) 2(거리 : 9)

  원소 [2] :

  원소 [3] : 4(거리 : 8)

  원소 [4] :

  원소 [5] :

 

  이렇게 출력된다.

 

  5는 노드의 개수 4는 간선의 개수이다.

  1 2 9라는 것은 1이라는 노드와 2라는 노드의 거리가 9라는 것이다.

  1 2 9를 기준으로 보자면 입력받고나서 addFront(a[1], 2, 9) 형태로 넘어간다.

 

  그럼 addFront에서는 root에 a[1], index에 2, distance에 9가 들어가게되고

  새로 할당받은 node의 index는 2, distance는 9, next는 a[1]의 next니까 NULL root의 next는 node가 된다.

 

void addFront(Node *root, int index, int distance){//a[1], 2, 9
  Node *node = (Node*)malloc(sizeof(Node));
  node->index = index = 2;
  node->distance = distance = 9;
  node->next = root->next = NULL;
  root->next = node = index(2), distance(9);
}


void addFront(Node *root, int index, int distance){ //a[1], 3, 8
  Node *node = (Node*)malloc(sizeof(Node));
  node->index = index = 3;
  node->distance = distance = 8;
  node->next = root->next = node(index(2), distance(9));
  root->next = node = index(3), distance(8);
}

  그림으로 보면 다음과 같다.

 

 

  제일먼저 n의 크기를 갖도록 만들어주고

  addFront에서 node를 만들어 index과 distance를 정의한다.

  그리고 연결해주는 것이다.

 

 

  입력 순으로 이렇게 모두 연결된 뒤 출력하게 된다.

 

  인접행렬은 모든 정점들의 연결 여부를 저장하여 O(V^2)의 공간을 요구하므로 공간 효율성이 떨어지지만

  두 정점이 서로 연결되어 있는지 확인하기 위해 O(1)의 시간을 요구한다.

  인접리스트는 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하므로 공간 효율성이 우수하지만

  두 정점이 서로 연결되어있는지 확인하기 위해 O(V)의 시간을 요구한다.

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직