[Data Structure] # 그래프 간단 정리

그래프란?

그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조입니다.(지하철 노선도, 프로세스 자원 관계, 데드락 분석)

그래프 용어

트리도 그래프의 한 종류이기 때문에 그래프에서도 비슷한 용어가 사용됩니다.

그래프의 구현

그래프를 표현하는 방법은 크게 2가지인데, 인접행렬과 인접리스트를 활용하는 것입니다.

인접행렬(adjacency matrix)

인접리스트(adjacency list)

구현

인접행렬

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50

typedef struct GraphType {
  int n;
  int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

void init(GraphType *g) {
  int s, e;
  g->n = 0;

  for (s = 0; s < MAX_VERTICES; s++) {
    for (e= 0; e < MAX_VERTICES; e++) {
      g->adj_mat[s][e] = 0;
    }
  }
}

void insert_vertice(GraphType *g, int v) {
  if (((g->n) + 1) > MAX_VERTICES) {
    fprintf(stderr, "정점 초과");
    return;
  }
  g->n++;
}

void insert_edge(GraphType *g, int start, int end) {
  if (start >= g->n || end >= g->n) {
    fprintf(stderr, "정점 갯수 오류");
    return;
  }

  g->adj_mat[start][end] = 1;
  g->adj_mat[end][start] = 1;
}

void print_adj_mat(GraphType *g) {
  for (int i = 0; i < g->n; i++) {
    for (int j = 0; j <g->n; j++) {
      printf("%2d ", g->adj_mat[i][j]);
    }
    printf("\n");
  }
}

void main() {
  GraphType *g;
  g = (GraphType*)malloc(sizeof(GraphType));
  init(g);

  for (int i = 0; i<4; i++) {
    insert_vertice(g, i);
  }

  insert_edge(g, 0, 1);
  insert_edge(g, 0, 2);
  insert_edge(g, 0, 3);
  insert_edge(g, 1, 2);
  insert_edge(g, 2, 3);

  print_adj_mat(g);

  free(g);
}

인접리스트

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50

typedef struct GraphNode {
  int vertex;
  struct GraphNode* link;
} GraphNode;

typedef struct GraphType {
  int n;
  GraphNode* adj_list[MAX_VERTICES];
} GraphType;

void init(GraphType* g) {
  g->n = 0;
  for (int v = 0; v < MAX_VERTICES; v++) {
    g->adj_list[v] = NULL;
  }
}

void insert_vertex(GraphType* g, int v) {
  if ((g->n) + 1 > MAX_VERTICES) {
    fprintf(stderr, "그래프: 정점 개수 초과");
    return;
  }

  g->n++;
}

void insert_edge(GraphType* g, int u, int v) {
  GraphNode* node;
  
  if (u >= g->n || v >= g->n) {
    fprintf(stderr, "그래프: 정점 번호 오류");
    return;
  }

  node = (GraphNode*)malloc(sizeof(GraphNode));
  node->vertex = v;
  node->link = g->adj_list[u];
  g->adj_list[u] = node;
}

void print_adj_list(GraphType* g) {
  for (int i = 0; i < g->n; i++) {
    GraphNode* p = g->adj_list[i];
    printf("정점 %d의 인접리스트 => ", i);
    while(p != NULL) {
      printf("%d -> ", p->vertex);
      p = p->link;
    }
    printf("\n");
  }
}

void main() {
  GraphType *g;
  g = (GraphType*)malloc(sizeof(GraphType));
  init(g);

  for(int i = 0; i < 4; i++) {
    insert_vertex(g, i);
  }
  insert_edge(g, 0, 1);
  insert_edge(g, 1, 1);
  insert_edge(g, 0, 2);
  insert_edge(g, 2, 0);
  insert_edge(g, 0, 3);
  insert_edge(g, 3, 0);
  insert_edge(g, 1, 2);
  insert_edge(g, 2, 1);
  insert_edge(g, 2, 3);
  insert_edge(g, 3, 2);
  print_adj_list(g);

  free(g);

  return;
}