[Data Structure]#簡略グラフィック
26701 ワード
グラフとは?
グラフィックは、オブジェクト間の関連付けを表すデータ構造です.(地下鉄路線図、流れ資源関係、死亡分析)
グラフィック用語
ツリーもグラフィックの一種なので、グラフィックにも似たような用語が使われています.
グラフィックの実装
隣接マトリクスと隣接リストを使用するグラフィックを表す方法は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;
}
Reference
この問題について([Data Structure]#簡略グラフィック), 我々は、より多くの情報をここで見つけました https://velog.io/@y1andyu/Data-Structure-그래프-간단-정리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol