[자료구조] 그래프 - 인접 행렬 (C언어 구현)

그래프를 구현하는 방법에는 크게 두가지가 있다.

1. 순차 자료구조를 이용한 그래프의 구현 : 인접 행렬

2. 연결 자료구조를 이용한 그래프의 구현 : 인접 리스트

 

이번에는 인접행렬로 그래프를 구현해보겠다.

 

▶전체코드

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

#define MAX_VERTICES 5  // 최대 정점의 수 제한

// 그래프 구조체
typedef struct Graph {
    int numV;                                   //정점의 수 설정
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];  // 인접 행렬
} Graph;

// 그래프 초기화
void graphInit(Graph* g, int numV) {
    g->numV = numV;
    for (int i = 0; i < numV; i++) {
        for (int j = 0; j < numV; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// 간선 추가
void addEdge(Graph* g, int from, int to) {
    g->adjMatrix[from][to] = 1;  // 방향 그래프 일때 추가
    //g->adjMatrix[to][from] = 1;  // 무방향 그래프 일때 추가
}

// 그래프 출력
void printGraph(Graph* g) {
    for (int i = 0; i < g->numV; i++) {
        for (int j = 0; j < g->numV; j++) {
            printf("%d ", g->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    Graph g;
    graphInit(&g, MAX_VERTICES);

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 4);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 4);

    printGraph(&g);

    return 0;
}

 

 

▶코드 뜯어보기

▷그래프 구조체

typedef struct Graph {
	int numV;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

그래프 구조체를 만들어줬다. 

 

▷그래프 초기화

void GraphInit(Graph* g, int numV) {
	g->numV = numV;
    for(int i = 0; i<numV; i++) {
    	for(int j = 0; j<numVl j++){
        	g->adjMatrix[i][j] = 0; //모든 원소를 0으로 설정
        }
    }
}

현재 MAX_VERTICES = 5 이므로

만약 numV가 3이라면 이런 배열이 나올것이다.

 

 

 

▷간선 추가

void AddEdge(Graph* g, int from, int to) {
	g->adjMatrix[from][to] = 1;
    //g->adjMartix[to][from] = 1; 무방향 그래프일 때 추가
}

 

 

 

▷그래프 출력

// 그래프 출력
void printGraph(Graph* g) {
    for (int i = 0; i < g->numV; i++) {
        for (int j = 0; j < g->numV; j++) {
            printf("%d ", g->adjMatrix[i][j]);
        }
        printf("\n");
    }
}