[알고리즘] 그래프 2 - 그래프의 구현(인접 행렬)

목차

 

순차 자료구조를 이용한 그래프의 구현 (인접행렬)

그래프에서는 두 정점을 연결한 간선의 상태를 행렬로 저장하기 위해서 정점 수에 대한 정방 행렬을 사용한다.

---

잠깐!. 정확히 알고 가자.

1. 행렬 (Matrix):

• 행렬은 숫자들을 직사각형 모양으로 배열한 것이다 다.
• $m$ X $n$행렬은 $m$개의 행과 $n$개의 열을 가지며, 각 원소는 $[a_{ij}]$로 표기한다.
• 예를 들어, 다음은 2x3 행렬의 예: 
  \[\begin {bmatrix}1&2&3\\4&5&6\\\end {bmatrix}\]

2. 정방 행렬 (Square Matrix):

• 정방 행렬은 행과 열의 개수가 같은 행렬을 말한다.
• $m$ X $n$ 행렬은 $n$개의 행과 $n$개의 열을 가지며, 정방 행렬이라고 부른다.
• 대각선 상의 원소를 제외한 모든 원소가 0인 행렬을 영행렬(Zero Matrix)이라고 한다.
• 예를 들어, 다음은 3x3 정방 행렬의 예:
  \[\begin {bmatrix}1&2&3\\4&5&6\\7&8&9\\\end {bmatrix}\]​

3. 행렬의 기본 용어:

• 행 (Row): 행렬에서 가로로 늘어선 요소들의 모음.
• 열 (Column): 행렬에서 세로로 늘어선 요소들의 모음.
• 전치 행렬 (Transpose): 행렬의 행과 열을 바꾼 것.
• 역행렬 (Inverse Matrix): 주어진 행렬과 곱했을 때 단위행렬이 되는 행렬.

4. 행렬 연산:

• 덧셈과 뺄셈: 같은 크기의 두 행렬의 각 원소끼리 더하거나 빼기.
• 스칼라 곱셈: 행렬의 모든 원소에 스칼라 값을 곱함.
• 행렬 곱셈: 두 행렬을 곱하는 연산. 주의할 점은 행렬 곱셈은 교환법칙이 성립하지 않는다.

---

두 정점이 인접해 있으면 그 행과 열에 1을 대입, 인접해 있지 않다면 그 행과 열에 0을 대입하여 2차원 배열을 이용하여 구현한다.

그래프의 인접행렬로의 표현.

코드 구현 부

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

#define MAX_VERTEX 30

typedef struct graphType{
    int n; // 그래프 정점의 개수
    int adjMatrix[MAX_VERTEX][MAX_VERTEX]; // 그래프에 대한 30x30의 2차원 배열
}graphType;

// 공백 그래프를 생성하는 연산
void createGraph(graphType* g) {
	int i, j;
	g->n = 0; // 정점 개수를 0으로 초기화
	for (i = 0; i < MAX_VERTEX; i++) {
		for (j = 0; j < MAX_VERTEX; j++)
			g->adjMatrix[i][j] = 0;	// 그래프 g에 대한 2차원 배열의 값을 0으로 초기화
	}
}

// 그래프 g에 정점 v를 삽입하는 연산
void insertVertex(graphType* g, int v) {
	if (((g->n) + 1) > MAX_VERTEX) {
		printf("\n 그래프 정점의 개수를 초과하였습니다!");
		return;
	}
	g->n++; // 그래프 정점의 개수 n을 하나 증가
}

// 그래프 g에 간선 (u, v)를 삽입하는 연산
void insertEdge(graphType* g, int u, int v) {
	// 간선 (u, v)를 삽입하기 위해 정점 u와 v가 그래프에 존재하는지 확인
	if (u >= g->n || v >= g->n) {
		printf("\n 그래프에 없는 정점입니다!");
		return;
	}
	g->adjMatrix[u][v] = 1;// 삽입한 간선에 대한 2차원 배열의 원소 값을 1로 설정
}

// 그래프 g의 2차원 배열 값을 순서대로 출력하는 연산
void print_adjMatrix(graphType* g) {
	int i, j;
	for (i = 0; i < (g->n); i++) {
		printf("\n\t\t");
		for (j = 0; j < (g->n); j++)
			printf("%2d", g->adjMatrix[i][j]);
	}
}

int main(void) {
	int i;
	graphType* SelfTest = (graphType*)malloc(sizeof(graphType));

	//G1 구성 : 정점 u에 대한 간선 (u,v)의 삽입순서는 v가 큰 것부터.
	createGraph(SelfTest);
	for(int i = 0; i < 7; i++)
		insertVertex(SelfTest, i);
	insertEdge(SelfTest, 0, 1);
	insertEdge(SelfTest, 0, 2);
	insertEdge(SelfTest, 1, 0);
	insertEdge(SelfTest, 1, 3);
	insertEdge(SelfTest, 1, 4);
	insertEdge(SelfTest, 2, 0);
	insertEdge(SelfTest, 2, 4);
	insertEdge(SelfTest, 3, 1);
	insertEdge(SelfTest, 3, 6);
	insertEdge(SelfTest, 4, 1);
	insertEdge(SelfTest, 4, 2);
	insertEdge(SelfTest, 4, 6);
	insertEdge(SelfTest, 5, 6);
	insertEdge(SelfTest, 6, 3);
	insertEdge(SelfTest, 6, 4);
	insertEdge(SelfTest, 6, 5);
	//--- 완성된 인접 행렬 출력
	printf("\n SelfTest의 인접 행렬");
	print_adjMatrix(SelfTest);

	getchar();  return 0;
}
------------------------------------------
                 0 1 1 0 0 0 0
                 1 0 0 1 1 0 0
                 1 0 0 0 1 0 0
                 0 1 0 0 0 0 1
                 0 1 1 0 0 0 1
                 0 0 0 0 0 0 1
                 0 0 0 1 1 1 0