[C] 인접리스트로 그래프 구현

// 그래프를 인접리스트로 표현하기
#include "stdio.h"
#include "stdlib.h "
#define MAX_VERTEX 30
 
// 인접리스트의 노드 구조
typedef struct graphNode {
    int vertex;  // 정점을 나타내는 데이터 필드
    graphNode *link;  // 다음 인접 정점을 연결하는 링크필드
}graphNode;
 
// 그래프를 인접리스트로 표현하기 위한 구조체
typedef struct graphType {
    int n;  //정점 개수
    graphNode *adjList_Arr[MAX_VERTEX];
}graphType;
 
// 공백그래프를 생성하는 연산
void CreateGraph(graphType *ptr) {
    int v;
    ptr->n = 0;
    for (v = 0; v < MAX_VERTEX; v++) {
        ptr -> adjList_Arr[v] = NULL;  // 헤드포인터 널로 초기화
    }
}
 
// 그래프에 정점 v를 삽입하는 연산
void InsertVertex(graphType *ptr, int v) {
    if (((ptr -> n) + 1)  > MAX_VERTEX)  printf("n 그래프 정점의 개수를 초과했습니다!");
    ptr -> n++; // 정점의 개수 n을 하나씩 증가
}
 
// 그래프에 간선(u, v)를 삽입하는 연산
void InsertEdge(graphType *ptr, int u, int v) {
    graphNode *node = (graphNode*)malloc(sizeof(graphNode));
    if (u >= ptr->n || v >= ptr->n)  printf("n 그래프에 없는 정점입니다!");
    node -> vertex = v;
    node -> link = ptr -> adjList_Arr[u];  // 삽입한 간선에 대한 노드를 리스트의 첫번째 노드로 연결
        ptr -> adjList_Arr[u] = node;
}
 
void Print_AdjList(graphType *GType_ptr) {
    graphNode *GNode_ptr;
    for (int i = 0; i < GType_ptr -> n; i++) {
        printf("\n\t\t정점 %c의 인접리스트 ", i + 65);
        GNode_ptr = GType_ptr -> adjList_Arr[i];
        while (GNode_ptr) {
            printf("%c ", GNode_ptr -> vertex + 65);
            GNode_ptr = GNode_ptr -> link;
        }
    }
}
 
int main() {
    graphType *G1, *G2, *G3, *G4;
    G1 = (graphType*)malloc(sizeof(graphType));
    G2 = (graphType*)malloc(sizeof(graphType));
    G3 = (graphType*)malloc(sizeof(graphType));
    G4 = (graphType*)malloc(sizeof(graphType));
 
    CreateGraph(G1);
    CreateGraph(G2);
    CreateGraph(G3);
    CreateGraph(G4);
 
    // G1그래프
    for (int i = 0; i < 4; i++) {
        InsertVertex(G1, i);
    }
 
    InsertEdge(G1, 0, 1); InsertEdge(G1, 0, 3); // A
    InsertEdge(G1, 1, 0); InsertEdge(G1, 1, 2); InsertEdge(G1, 1, 3); // B
    InsertEdge(G1, 2, 1); InsertEdge(G1, 2, 3); // C
    InsertEdge(G1, 3, 0); InsertEdge(G1, 3, 1); InsertEdge(G1, 3, 2); // D
 
    printf("G1의 인접리스트"); Print_AdjList(G1); printf("\n\n");
 
    // G2 그래프
    for (int i = 0; i < 3; i++) {
        InsertVertex(G2, i);
    }
 
    InsertEdge(G2, 0, 2); InsertEdge(G2, 0, 1); // A
    InsertEdge(G2, 1, 2); InsertEdge(G2, 1, 0); // B
    InsertEdge(G2, 2, 1); InsertEdge(G2, 2, 0); // C
 
    printf("G2의 인접리스트"); Print_AdjList(G2); printf("\n\n");
 
    // G3 그래프
    for (int i = 0; i < 4; i++) {
        InsertVertex(G3, i);
    }
 
    InsertEdge(G3, 0, 3); InsertEdge(G3, 0, 1); // A
    InsertEdge(G3, 1, 3); InsertEdge(G3, 1, 2); // B
    InsertEdge(G3, 2, 3);  // C
 
    printf("G3의 인접리스트"); Print_AdjList(G3); printf("\n\n");
 
    // G4 그래프
    for (int i = 0; i < 3; i++) {
        InsertVertex(G4, i);
    }
 
    InsertEdge(G4, 0, 2); InsertEdge(G4, 0, 1); // A
    InsertEdge(G4, 1, 2); InsertEdge(G4, 1, 0); // B
 
    printf("G4의 인접리스트"); Print_AdjList(G4); printf("\n\n");
}