그래프의 ADT에 대해서 알아보고 인접 행렬 방식으로 구현해보자

그래프의 ADT

• 객체 : 정점의 집합과 간선의 집합

• 연산

  	create_graph() :: 그래프를 생성한다.
  
  	init(g) :: 그래프 g를 초기화한다.
  
  	insert_vertex(g, v) :: 그래프 g에 정점 v를 삽입한다.
  
  	insert_edge(g, u, v) :: 그래프 g에 간선 (u,v)를 삽입한다.
  
  	delete_vertex(g, v) :: 그래프 g의 정점 v를 삭제한다.
  
  	delete_edge(g, u, v) :: 그래프 g의 간선 (u,v)를 삭제한다.
  
  	destroy_graph(g) :: 그래프 g를 제거한다.
  
  	is_empty(g) :: 그래프 g가 공백 상태인지 확인한다.
  
  	adjacent(v) :: 정점 v에 인접한 정점들의 리스트를 반환한다.

---

그래프의 구현

그래프는 행렬 or 리스트를 이용하여 두가지 방법으로 표현할 수 있다.

1. 인접 행렬 방법 (adjacent matrix)

   • 간선 $(i,\;j)$가 존재한다면, $M[i][j] \;=\; 1$ 로 표시한다.

   • 따라서 정점이 N개 존재하는 그래프를 표현하려면 $N^2$크기의 행렬이 필요하다.
     
     

2. 인접 리스트 방법 (adjacent list)

   • 각 정점을 하나의 노드로 표현하고, 이를 연결리스트로 구현한다.

인접 행렬 방법

간선 $(i,\;j)$가 존재한다면, $M[i][j]\;=\;1$ 로 표시한다.
따라서 정점이 N개 존재하는 그래프를 표현하려면 $N^2\;$크기의 행렬이 필요하다.

---

코드 설명

전체코드는 설명 아래에 있습니다.

1. 인접행렬 구조체

1. GraphType 구조체에 인접행렬과 그래프의 정보를 저장할 예정

2. 그래프의 정점은 0부터 n-1번 까지 순서대로 할당한다.

3. 따라서 정점의 개수가 n일때 실제로 정점의 번호는 0 ~ n-1 가 된다.

2. 구조체 그래프 초기화 함수

초기화 시 그래프에 저장된 정점이 존재하지 않는다 (1).
따라서 모든 정점 사이의 연결이 존재하지 않는다 (2, 3).

1. 정점이 존재하지 않는다 : g->n = 0

2. 전체 정점에 대하여 : i 와 j는 0부터 MAX-1까지

3. i번 정점과 연결된 j번 정점 없음 : M[i][j] = 0

3. 그래프에 정점 삽입 함수

1. 그래프에 정점을 삽입할 수 있는지 확인해야 한다.

2. 최대 정점의 수는 MAX개 이므로 정점 번호의 최댓값은 MAX-1이다.

3. 삽입할 수 없다면 오류 출력

4. 삽입할 수 있다면 정점의 개수를 늘린다.
   Q: 뭔가 허전한데요? A: 이미 전체 그래프를 초기화 해두었기 때문에 정점의 개수만 늘리면 됨

4. 그래프에 간선 삽입 함수

1. 그래프에 간선을 삽입할 수 있는지 확인해야 한다.

2. 출발하는 정점 번호와 도착하는 정점 번호가 가능한 범위 내에 있는지 확인한다.

3. 오류가 없다면 출발->도착 하는 행렬과 도착->출발하는 행렬의 값을 1로 바꾼다.
   구현할 떄 무방향 그래프를 전제로 했기 때문에 이렇게 만들었다. 만약 방향 그래프라면 출발->도착하는 행렬의 값만 바꾸면 된다.

5. 정점 v의 인접 정점을 출력

1. 존재하지 않는 노드 번호를 입력하면 오류 출력

2. 정점이 존재한다면 해당 정점 번호의 열을 확인하여 1이면 노드의 번호 출력

---

전체 코드

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


#define MAX 50 //그래프 노드의 최대 개수

//그래프의 정보를 저장하는 구조체
typedef struct GraphType {
	int n; //정점 개수 => n-1은 정점의 최대 번호와 같음
	int M[MAX][MAX];//간선 정보 저장. 행 : 노드, 열 : 간선으로 연결된 노드
}GraphType;


//그래프 초기화
void init(GraphType* g) {
	g->n = 0;
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			g->M[i][j] = 0;
		}
	}
}


//그래프 g에 정점 v를 삽입
void insert_vertex(GraphType* g, int v) {
	if ((g->n) == MAX) {//이미 그래프가 꽉 칬다면 오류출력
		fprintf(stderr, "ERROR:정점의 개수 초과");
		exit(1);
	}
	//그래프에 정점을 추가할 수 있다면 정점의 개수를 하나 늘린다.
	g->n++;
}

//그래프 g에 간선 (start,end)삽입
void insert_edge(GraphType* g, int start, int end) {
	if (start >= n || end >= n) {//정의되지 않은 정점을 입력한 경우 오류 출력
		fprintf(stderr, "ERROR:정점의 번호 오류");
		exit(1);
	}
	//오류 없음
	g->M[start][end] = 1; //start 노드에서 end 노드로 연결됨
	g->M[end][start] = 1; //end 노드에서 start 노드로 연결됨
}

//정점 v에 인접한 정점들의 리스트를 반환한다.
void print_adjacent(GraphType* g, int v) {
	
	//잘못된 노드번호 v를 입력했다면 오류 출력
	if (v>=g->n) {
		fprintf(stderr, "ERROR:잘못된 정점번호");
		exit(1);
	}

	for (int i = 0; i < g->n; i++) {
		if (g->M[v][i] == 1)//인접한 노드이면
			printf("%d ", i);//노드의 번호 출력
	}
}



void main() {
	GraphType* g;
	//GraphType*크기의 메모리 공간을 확보하고 공간의 주소를 g에 저장
	g = (GraphType*)malloc(sizeof(GraphType));

	//공간만 할당되어있던 g를 초기화하여 사용하기 용이한 상태로 변경함
	init(g); 

	for (int i = 0; i < 4; i++) {
		//정점을 0~3번까지 삽입. 실제로 코드상에서는 g->n을 4까지 늘린것.
		insert_vertex(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);
	
	//2번 정점과 연결된 인접 노드를 출력
	print_adjacent(g, 2);

	//동적할당 free
	free(g);
}