on
[Data Structure] 그래프 표현 방법 2) 인접 리스트
[Data Structure] 그래프 표현 방법 2) 인접 리스트
728x90
그래프의 표현방법
인접 행렬 (Adjacency Matrix) : 2차원 배열 을 사용
(Adjacency Matrix) : 을 사용 인접 리스트 (Adjacency List) : 연결 리스트 를 사용
인접 리스트
각 연결 리스트들 의 노드는 인접 정점들을 저장
의 노드는 각 연결 리스트들은 헤더 노드를 보유 → 헤더 노드는 배열로 구성 → 배열의 인덱스를 이용해서 각 정점의 연결 리스트에 접근
그래프 인접리스트 구현
#define MAX_VERTEX 50 typedef struct graphnode { int vertex; // 각 노드의 정점 struct graphnode* link; // 정점들간에 연결해주는 link }graphnode; typedef struct graph { int n; // 정점의 개수 graphnode* list[MAX_VERTEX]; // 하나의 연결리스트 안에 존재하는 정점들의 배열 }graph;
- Example) 위의 그림을 예제로
graphnode : (1, link), (2, link), (3, link), (4, link), (5, link) 존재
graph (graphnode* list[MAX_VERTEX]) : 위의 예제의 연결리스트 5개를 각각 하나로 인식하고 배열에 추가
→ list[0] : 1→2→3→4→5→NULL
→ list[1] : 2→1→3→5→NULL
→ list[2] : 3→1→2→NULL
→ list[3] : 4→1→5→NULL
→ list[4] : 5→1→2→4→NULL
Vertex 삽입 연산
void insert_vertex(graph* g, int v) { if (is_full(g)) { fprintf(stderr, "그래프 정점의 개수가 MAX에 도달하였습니다
"); return; } else if (bool_vertex(g, v) == 0) { fprintf(stderr, "해당 정점은 이미 그래프에 존재합니다.
"); return; } graphnode* new_node = (graphnode*)malloc(sizeof(graphnode)); new_node->vertex = v; new_node->link = NULL; g->list[g->n++] = new_node; }
vertex를 insert하는 연산 = graph의 list포인터 배열에 vertex를 insert
new_node 동적 할당 → new_node의 vertex, link(NULL)에 정보를 insert하고 배열에 new_node를 그대로 추가
Edge 삽입 연산
int bool_vertex(graph* g, int v) { // 그래프에 정점 v가 존재하는지 판별 int flag = 1; for (int i = 0; i < g->n; i++) { if (g->list[i]->vertex == v) flag = 0; } if (flag == 0) return 0; // 존재 O else return 1; // 존재 X } void insert_edge(graph* g, int start, int end) { if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) { fprintf(stderr, "그래프에 해당 정점은 없습니다
"); return; } graphnode* new_node = (graphnode*)malloc(sizeof(graphnode)); new_node->vertex = end; new_node->link = g->list[start]->link; g->list[start]->link = new_node; }
편의상으로 edge를 insert할 때, 인접 리스트 맨 처음에 추가
그러면 new_node의 link는 원래 해당 리스트의 정점이 가리키던 노드를 가리켜야 한다
그리고 해당 리스트의 정점은 new_node를 가리켜야 한다
※ Example
#include #include // 인접 리스트 (무방향 그래프) #define MAX_VERTEX 50 typedef struct graphnode { int vertex; // 각 노드의 정점 struct graphnode* link; // 정점들간에 연결해주는 link }graphnode; typedef struct graph { int n; // 정점의 개수 graphnode* list[MAX_VERTEX]; // 하나의 연결리스트 안에 존재하는 정점들의 배열 }graph; graph* create() { // 그래프 동적 할당 return (graph*)malloc(sizeof(graph)); } int is_full(graph* g) { return g->n == MAX_VERTEX; } void init_graph(graph* g) { g->n = 0; for (int i = 0; i < MAX_VERTEX; i++) g->list[i] = NULL; } int bool_vertex(graph* g, int v) { // 그래프에 정점 v가 존재하는지 판별 int flag = 1; for (int i = 0; i < g->n; i++) { if (g->list[i]->vertex == v) flag = 0; } if (flag == 0) return 0; // 존재 O else return 1; // 존재 X } void insert_vertex(graph* g, int v) { if (is_full(g)) { fprintf(stderr, "그래프 정점의 개수가 MAX에 도달하였습니다
"); return; } else if (bool_vertex(g, v) == 0) { fprintf(stderr, "해당 정점은 이미 그래프에 존재합니다.
"); return; } graphnode* new_node = (graphnode*)malloc(sizeof(graphnode)); new_node->vertex = v; new_node->link = NULL; g->list[g->n++] = new_node; } void insert_edge(graph* g, int start, int end) { if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) { fprintf(stderr, "그래프에 해당 정점은 없습니다
"); return; } graphnode* new_node = (graphnode*)malloc(sizeof(graphnode)); new_node->vertex = end; new_node->link = g->list[start]->link; g->list[start]->link = new_node; } void print_list(graph* g) { graphnode* p; for (int i = 0; i < g->n; i++) { graphnode* p = g->list[i]; printf("정점 %d의 인접 리스트 : V", i); while (p != NULL) { printf("%d -> ", p->vertex); p = p->link; } printf(" NULL
"); } } int main(void) { graph* g1, * g2; g1 = create(); g2 = create(); init_graph(g1); init_graph(g2); printf("V : {0, 1, 2, 3}
"); printf("E : {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)
"); for (int i = 0; i < 4; i++) insert_vertex(g1, i); insert_edge(g1, 0, 1); insert_edge(g1, 1, 0); insert_edge(g1, 0, 2); insert_edge(g1, 2, 0); insert_edge(g1, 0, 3); insert_edge(g1, 3, 0); insert_edge(g1, 1, 2); insert_edge(g1, 2, 1); insert_edge(g1, 2, 3); insert_edge(g1, 3, 2); print_list(g1); printf("--------------------------------------------------
"); printf("V : {0, 1, 2, 3, 4}
"); printf("E : {(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)
"); for (int i = 0; i < 5; i++) insert_vertex(g2, i); insert_edge(g2, 0, 1); insert_edge(g2, 1, 0); insert_edge(g2, 0, 2); insert_edge(g2, 2, 0); insert_edge(g2, 0, 3); insert_edge(g2, 3, 0); insert_edge(g2, 1, 2); insert_edge(g2, 2, 1); insert_edge(g2, 1, 4); insert_edge(g2, 4, 1); insert_edge(g2, 2, 3); insert_edge(g2, 3, 2); insert_edge(g2, 3, 4); insert_edge(g2, 4, 3); print_list(g2); free(g1); free(g2); return 0; }
728x90
반응형
from http://cs-ssupport.tistory.com/193 by ccl(A) rewrite - 2021-12-22 17:00:38