Adjacency Multilists

다음과 같이 사용자로부터 정보를 입력받아서 무방향그래프(undirected graph)를 Adjacency multilist로 구성하여 각 정점에 부속(속해있는)되는 간선을 출력하는 프로그램 을 작성하라.

 

<input.txt>

4	6
0	1
0	2
0	3
1	2
1	3
2	3

Example

입력파일의 첫 줄은 정점(vertex) 수와 간선(edge)의 수를 나타냄, 그래프의 정점은 0부터 시작됨

 

하나의 간선 (i, j)을 표현하는 방법

Example

정점과 간선의 수를 입력받음

 

그래프를 구성하는 간선을 하나씩 입력받으면서 adjacency multilist를 구성함(같은 간선이 두 번 입력되지 않음을 가정함)

 

각 정점에 대해 부속된 간선(edges incident to a vertex v)을 출력하기 (입력데이터 순서대로 출력, 헤더노드 정점이 먼저 오게 출력)

Result

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

enum {
	FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR
};

#define NAME(a) #a
#define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false)
#define CALLOC(type,data_num,ptr) do{if(!(ptr=(type*)calloc(data_num,sizeof(type)))){CATCH(MEMORY_ALLOCATION_ERROR);}}while(false)

typedef struct node* link;
typedef struct node {
	int num1;
	link num1_ptr;
	int num2;
	link num2_ptr;
} node;

link* graph;
node* edges;

void print_graph(void);

#define FILE_NAME "input.txt"

int vertex_num, edge_num;
int tmp_from, tmp_to;

int main(void)
{
	FILE* fp;fopen_s(&fp, FILE_NAME, "r");
	if (fp)
	{
		fscanf_s(fp, "%d %d", &vertex_num, &edge_num);
		CALLOC(link, vertex_num, graph);
		CALLOC(node, edge_num, edges);

		int i, j;
		for (i = 0;i < edge_num;i++)
		{
			fscanf_s(fp, "%d %d", &tmp_from, &tmp_to);
			edges[i].num1 = tmp_from; edges[i].num2 = tmp_to;

			for (j = 0;j < vertex_num;j++)
			{
				if(j==tmp_from&&!graph[j])
					graph[j] = &edges[i];

				if(j==tmp_to&&!graph[j])
					graph[j] = &edges[i];
			}

			for (j = 0;j < i;j++)
			{
				if (edges[j].num1 == tmp_from && !edges[j].num1_ptr)
					edges[j].num1_ptr = &edges[i];

				if (edges[j].num2 == tmp_from && !edges[j].num2_ptr)
					edges[j].num2_ptr = &edges[i];

				if (edges[j].num1 == tmp_to && !edges[j].num1_ptr)
					edges[j].num1_ptr = &edges[i];

				if (edges[j].num2 == tmp_to && !edges[j].num2_ptr)
					edges[j].num2_ptr = &edges[i];
			}
		}

		fclose(fp);
	}
	else CATCH(FILE_OPEN_ERROR);

	print_graph();

	return 0;
}

void print_graph(void)
{
	link tmp; int i;

	printf("< Print Input Node Seqence >\n");
	for (i = 0;i < vertex_num;i++)
	{
		printf("graph[%d] : ", i);
		for (tmp = graph[i];tmp;)
		{
			printf("(%d %d) ", tmp->num1, tmp->num2);
			tmp = (i == tmp->num1) ? tmp->num1_ptr : tmp->num2_ptr;
		}
		printf("\n");
	}
	printf("\n");

	printf("< Print Header Node First Seqence >\n");
	for (i = 0;i < vertex_num;i++)
	{
		printf("graph[%d] : ", i);
		for (tmp = graph[i];tmp;)
		{
			printf("(%d %d) ", i, ((i == tmp->num1) ? tmp->num2 : tmp->num1));
			tmp = (i == tmp->num1) ? tmp->num1_ptr : tmp->num2_ptr;
		}
		printf("\n");
	}
	printf("\n");
}