[Data Structure]#簡略グラフィック


グラフとは?


グラフィックは、オブジェクト間の関連付けを表すデータ構造です.(地下鉄路線図、流れ資源関係、死亡分析)

グラフィック用語


ツリーもグラフィックの一種なので、グラフィックにも似たような用語が使われています.

グラフィックの実装


隣接マトリクスと隣接リストを使用するグラフィックを表す方法は2つあります.

隣接行列



隣接リスト



インプリメンテーション


隣接行列

#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;
}