[알고리즘] 인접 행렬을 통한 인접리스트 구현, DFS(1)

---

✏️그래프 형태

구현할 그래프는 다음과 같다.

가중치가 없는 무향그래프 이다.

---

 

✏️인접행렬(Adjacenty Matrix) -> 인접리스트(Adjacenty List) 구현

위 그래프의 인접행렬은 다음과 같다.
각 정점별로 간선이 있으면 1, 없으면 0 으로 표현한다.

#define N 9

int matrix[N][N] = {
	{0,1,0,0,0,0,0,0,0},
	{1,0,1,1,0,0,0,0,0},
	{0,1,0,1,1,0,0,0,0},
	{0,1,1,0,1,1,0,0,0},
	{0,0,1,1,0,0,0,0,0},
	{0,0,0,1,0,0,1,1,0},
	{0,0,0,0,0,1,0,1,1},
	{0,0,0,0,0,1,1,0,0},
	{0,0,0,0,0,0,1,0,0},
};

인접리스트를 위한 구조체 선언 및 초기화.

#include <stdio.h>
#include <malloc.h>

#define N 9
#define FALSE 0
#define TRUE 1

typedef struct list_node { //구조체 선언
	int vertex;
	struct list_node* link;
}NODE;

NODE* graph[N]; //정점의 개수 1번~9번 (포인터 변수로 선언)

int matrix[N][N] = {
	{0,1,0,0,0,0,0,0,0},
	{1,0,1,1,0,0,0,0,0},
	{0,1,0,1,1,0,0,0,0},
	{0,1,1,0,1,1,0,0,0},
	{0,0,1,1,0,0,0,0,0},
	{0,0,0,1,0,0,1,1,0},
	{0,0,0,0,0,1,0,1,1},
	{0,0,0,0,0,1,1,0,0},
	{0,0,0,0,0,0,1,0,0},
};

int main()
{
	int i;
	for (i = 0; i < N; i++) { //각 정점 NULL로 초기화
		graph[i] = NULL;
	}

	create_adj_list(); //연결리스트 생성
}

create_adj_list 작성

void create_adj_list() {
	NODE* temp;
	for (int i = 0; i < N; i++) {
		for (int  j = N - 1; j >= 0; j--) {
			if (matrix[i][j] != 0) {
				temp = (NODE*)malloc(sizeof(NODE));
				temp->vertex = j;
				temp->link = graph[i];
				graph[i] = temp;
			}
		}
	}
}

인접행렬에서 각 정점(i)별로 간선이 있다면 리스트에 붙인다는 함수다.

리스트가 만들어지는 과정을 이해해 보자.

 

*인접한 행렬이 있을 때 if문으로 들어간다.

i = 0, j = 1일때.

i = 1, j = 3 일때.

i = 1, j = 2 일때.

i = 1, j = 0 일때.

모든 정점(i = 0~8) 을 돌면인접 리스트가 만들어진다.

---

✏️전체 코드 및 샐행 결과

#include <stdio.h>
#include <malloc.h>

#define N 9
#define FALSE 0
#define TRUE 1

typedef struct list_node {
	int vertex;
	struct list_node* link;
}NODE;

NODE* graph[N];

int matrix[N][N] = { //인접 행렬로 그래프 표현.
	{0,1,0,0,0,0,0,0,0},
	{1,0,1,1,0,0,0,0,0},
	{0,1,0,1,1,0,0,0,0},
	{0,1,1,0,1,1,0,0,0},
	{0,0,1,1,0,0,0,0,0},
	{0,0,0,1,0,0,1,1,0},
	{0,0,0,0,0,1,0,1,1},
	{0,0,0,0,0,1,1,0,0},
	{0,0,0,0,0,0,1,0,0},
};

void create() {
	NODE* temp;
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= 0; j--) {
			if (matrix[i][j] != 0) {
				temp = (NODE*)malloc(sizeof(NODE));
				temp->vertex = j;
				temp->link = graph[i];
				graph[i] = temp;
			}
		}
	}
}

int main()
{
	int i;
	NODE* temp;
	for (i = 0; i < N; i++) { //각 정점 NULL로 초기화
		graph[i] = NULL;
	}

	create_adj_list(); //연결리스트 생성

	for (i = 0; i < N; i++) {  //연결리스트로 잘 만들어졌는지 확인해보기위함.
		printf("%d-th node ", i);
		temp = graph[i];
		while (temp)
		{
			printf("%d ", temp->vertex);
			temp = temp->link;
		}
		printf("\n");
	}
}