그래프 - 그래프의 개념과 구현

그래프 - 그래프의 개념과 구현

​

• 사물을 정점(vertex)와 간선(edge)으로 나타내기 위한 도구
• 두 가지 방식으로 구현
  • 인접행렬(adjacency matrix) : 2차원 배열을 사용하는 방식
  • 인접리스트(adjacency list): 리스트를 사용하는 방식
    ​
    ​
    ​

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

• 무방향 그래프: 모든 간선이 방향성을 가지지 않는 그래프

• 비가중치 그래프: 모든 간선에 가중치가 없는 그래프

• 무방향 비가중치 그래프가 주어졌을 때, 연결된 상황을 인접행렬로 출력할 수 있음

• 모든 정점의 연결 여부를 저장해 O(V^2)의 공간을 요구(공간 효율성 떨어짐)

• 두 정점이 서로 연결돼 있는지 확인하는 데 O(1)의 시간을 요구
  ​

  #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 l = 1 ; j <= n ; j++)
      {
        printf("%d ", a[i][j]);
      }
      printf("\n");
    }
    system("pause");
  }

  ​
  ​
  ​

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

• 방향 그래프: 모든 간선이 방향을 가지는 그래프

• 가중치 그래프: 모든 간선에 가중치가 있는 그래프

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

• 연결된 간선의 정보만 저장해 O(E)의 공간을 요구(공간 효율성 우수)

• 두 정점이 서로 연결돼 있는지 확인하는데 O(V)의 시간을 요구
  ​

  #include <stdlib.h>
  #include <stdio.h>
  ​
  typedef struct {
    int index;
    int distance;
    struct Node *next;
  } Note;
  ​
  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)
    {
      prinitf("%d(거리:%d) ", cur->index, cur->distance);
      cur = cur->next;
    }
  }