연결리스트 - Graph

연결 리스트를 이용해서 그래프를 표현

배열로 포현하면 복잡도가 O(n^2)이 되는데, 연결 리스트로 표현하면 O(n)이 되서 효율적

[그래프]

위의 [그래프]를 각 Vertex 마다 Adjacent한 Vertex를 연결리스트로 표현한 그림은 밑에 그림이다.

간단하게 각 Vertex마다 Head Node를 만들고 연결 리스트로 Adjacent 한 Node를 연결하면 된다.

[Adjacent Vertex를 연결 리스트로 표현]

설계없이 그냥 막 짜서 더럽다.

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX 30
//A-B-C 인접 연결 Node

typedef struct Graph_Node
{
	//현재 Vertex
	char Vertex;
	
	//다음 Vertex
	struct Graph_Node* link;

}GraphNode, *PGraphNode;

// Vertex 생성 --> Vertex가 4개인 그래프면
// 각 Vertex 당 인접 정보를 알 수있어야 하기 때문에
typedef struct Graph_Vertex
{
	//해당 Graph에 몇개의 Vertex가 존재하는지
	char Num;
	//각 Vertex 마다 연결된 인접을 확인하기 위해서
	PGraphNode Vertex[MAX];
}Init_Vertex, *PInit_Vertex;

void Init_Graph(PInit_Vertex arg_Vertex);
PInit_Vertex Create_Graph()
{
	PInit_Vertex var_Vertex = (PInit_Vertex)malloc(sizeof(Init_Vertex));
	memset(var_Vertex, 0x00, sizeof(Init_Vertex));
	return var_Vertex;
}

//Inert adjan Vertex
// 각 Vertex마다 인접함 Vertex를 삽입한다.
// ARG1 = PInit_Vertex
// ARG2 = static_Vertex
// ARG3 = linked_Vertex
// 첫인자는 처음 초기화 한 각 Vertex의 배열을 소요한 구조체
//두번째는 연결 a->b, a->c에서 a를
//세번째는 위에서의 b,c를
void Inert_Adjan(PInit_Vertex arg_Head, char arg2_static_vertex, char arg3_adjan_vertex)
{
	int index = 0;
	PGraphNode new_Node = (PGraphNode)malloc(sizeof(GraphNode));
	PGraphNode tmp_Node = NULL;
	memset(new_Node, 0x00, sizeof(GraphNode));
	new_Node->Vertex = arg3_adjan_vertex;

	for (index = 0; index < arg_Head->Num; index++)
	{
		if (arg_Head->Vertex[index]->Vertex == arg2_static_vertex){
			tmp_Node = arg_Head->Vertex[index];
			break;
		}
	}
	while (tmp_Node->link != NULL){
		tmp_Node = tmp_Node->link;
	}
	tmp_Node->link = new_Node;

}


//Print Adan
void Print_Adjan(PInit_Vertex arg_Head)
{
	unsigned char count = 0;
	printf("Print Each Vertex Adjan List!\n");
	for (count = 0; count < arg_Head->Num; count++)
	{
		PGraphNode tmp_Node = arg_Head->Vertex[count];
		while ( tmp_Node ->link != NULL)
		{
			printf("%c ->", tmp_Node->Vertex);
			tmp_Node = tmp_Node->link;
		}
		printf("%c", tmp_Node->Vertex);
		printf("\n");
	}
}

int main()
{
	//Graph 생성
	int var_num = 0;
	PInit_Vertex ALL_Vertex = Create_Graph();

	//몇개의 Vertex인지 설정
	printf("Print Insert Vetex Number : ");
	scanf_s("%d", &(ALL_Vertex->Num));
	printf("\nGraph Vertex Numvber : %d\n", ALL_Vertex->Num);
	fflush(stdin);

	//Init_Graph 각 Vertex 생성함.
	Init_Graph(ALL_Vertex);


	Inert_Adjan(ALL_Vertex, 'A', 'B');
	Inert_Adjan(ALL_Vertex, 'A', 'C');

	Inert_Adjan(ALL_Vertex, 'B', 'A');
	Inert_Adjan(ALL_Vertex, 'B', 'D');

	Inert_Adjan(ALL_Vertex, 'C', 'A');
	Inert_Adjan(ALL_Vertex, 'C', 'D');

	Inert_Adjan(ALL_Vertex, 'D', 'B');
	Inert_Adjan(ALL_Vertex, 'D', 'C');

	Print_Adjan(ALL_Vertex);
	
	printf("End");
	getchar();
}

void Init_Graph(PInit_Vertex arg_Vertex)
{
	char vertex = 'A';
	char count = 0;
	for(; count <  (arg_Vertex->Num);count++)
	{
		//각 Vertex[Node]생성
		PGraphNode Node = (PGraphNode)malloc(sizeof(GraphNode));
		memset(Node, 0x00, sizeof(GraphNode));
		//Vertex에 A,B,C,D 이름 부여
		Node->Vertex = (char)(vertex+count);
		//각 그래프마다 연결
		arg_Vertex->Vertex[count] = Node;
	}
}

그래프를 만드는 Insert 함수를 입력함수로 바꾸면 된다. 

그냥 입력 값으로 넣었다.