9. 그래프

인접 리스트 방식 그래프

#pragma once
#ifndef GRAPH_H
#define GRAPH_H

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

enum VisitedMode { Visited, NotVisited };

typedef int ElementType;

typedef struct tagVertex {
	ElementType Data;
	int Visited;
	int Index;

	struct tagVertex* Next;
	struct tagEdge* AdjacenyList;
} Vertex;

typedef struct tagEdge {
	int Weight;
	struct tagEdge* Next;
	Vertex* From;
	Vertex* Target;
} Edge;

typedef struct tagGraph {
	Vertex* Vertices;
	int VertexCount;
} Graph;

Graph* CreateGraph();
void DestroyGraph(Graph* G);

Vertex* CreateVertex(ElementType Data);
void DestroyVertex(Vertex* V);

Edge* CreateEdge(Vertex* From, Vertex* Target, int Weight);
void DestroyEdge(Edge* E);

void AddVertex(Graph* G, Vertex* V);
void AddEdge(Vertex* V, Edge E);
void PrintGraph(Graph* G);

#endif

#include "Graph.h"

Graph* CreateGraph() {
	Graph* graph = (Graph*)malloc(sizeof(Graph));

	graph->Vertices = NULL;
	graph->VertexCount = 0;
	
	return graph;
}

void DestroyGraph(Graph* G) {
	while (G->Vertices != NULL) {
		Vertex* Vertices = G->Vertices->Next;
		DestroyVertex(G->Vertices);
		G->Vertices = Vertices;
	}

	free(G);
}

Vertex* CreateVertex(ElementType Data) {
	Vertex* V = (Vertex*)malloc(sizeof(Vertex));

	V->Data = Data;
	V->Next = NULL;
	V->AdjacenyList = NULL;
	V->Visited = NotVisited;
	V->Index = -1;

	return V;
}

void DestroyVertex(Vertex* V) {
	while (V->AdjacenyList != NULL) {
		Edge* Edge = V->AdjacenyList->Next;

		DestroyEdge(V->AdjacenyList);

		V->AdjacenyList = Edge;
	}

	free(V);
}

Edge* CreateEdge(Vertex* From, Vertex* Target, int Weight) {
	Edge* E = (Edge*)malloc(sizeof(Edge));

	E->From = From;
	E->Target = Target;
	E->Next = NULL;
	E->Weight = Weight;

	return E;
}
void DestroyEdge(Edge* E) {
	free(E);
}

void AddVertex(Graph* G, Vertex* V) {
	Vertex* VertexList = G->Vertices;

	if (VertexList == NULL) {
		G->Vertices = V;
	}
	else {
		while(VertexList->Next != NULL)
			VertexList = VertexList->Next;

		VertexList->Next = V;
	}

	V->Index = G->VertexCount++;
}

void AddEdge(Vertex* V, Edge* E) {
	if (V->AdjacenyList == NULL) {
		V->AdjacenyList = E;
	}
	else {
		Edge* AdjacencyList = V->AdjacenyList;

		while (AdjacencyList->Next != NULL)
			AdjacencyList = AdjacencyList->Next;

		AdjacencyList->Next = E;
	}
}

void PrintGraph(Graph* G) {
	Vertex* V = NULL;
	Edge* E = NULL;

	if ((V = G->Vertices) == NULL)
		return;

	while (V != NULL) {
		printf("%c : ", V->Data);

		if ((E = V->AdjacenyList) == NULL) {
			V = V->Next;
			printf("\n");
			continue;
		}

		while (E != NULL) {
			printf("%c[%d] ", E->Target->Data, E->Weight);
			E = E->Next;
		}

		printf("\n");

		V = V->Next;
	}

	printf("\n");
}

int main() {
	/* 그래프 생성 */
	Graph* G = CreateGraph();

	/* 정점 생성 */
	Vertex* V1 = CreateVertex('1');
	Vertex* V2 = CreateVertex('2');
	Vertex* V3 = CreateVertex('3');
	Vertex* V4 = CreateVertex('4');
	Vertex* V5 = CreateVertex('5');

	/* 그래프에 정점을 추가 */
	AddVertex(G, V1);
	AddVertex(G, V2);
	AddVertex(G, V3);
	AddVertex(G, V4);
	AddVertex(G, V5);

	/* 정점과 정점을 간선으로 잇기 */
	AddEdge(V1, CreateEdge(V1, V2, 0));
	AddEdge(V1, CreateEdge(V1, V3, 0));
	AddEdge(V1, CreateEdge(V1, V4, 0));
	AddEdge(V1, CreateEdge(V1, V5, 0));

	AddEdge(V2, CreateEdge(V2, V1, 0));
	AddEdge(V2, CreateEdge(V2, V3, 0));
	AddEdge(V2, CreateEdge(V2, V5, 0));

	AddEdge(V3, CreateEdge(V3, V1, 0));
	AddEdge(V3, CreateEdge(V3, V2, 0));

	AddEdge(V4, CreateEdge(V1, V1, 0));
	AddEdge(V4, CreateEdge(V1, V5, 0));

	AddEdge(V5, CreateEdge(V5, V1, 0));
	AddEdge(V5, CreateEdge(V5, V2, 0));
	AddEdge(V5, CreateEdge(V5, V4, 0));

	PrintGraph(G);

	/* 그래프 소멸 */
	DestroyGraph(G);

	return 0;
}