[C / 자료구조] 10주차 과제 - DFS

list.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct node {
    element val;
    struct node* next;
} node_t;

node_t* get_tail(node_t* head);
node_t* insert_tail(node_t* head, element n);
void print_list(int n, node_t* head);
void free_list(node_t* head);

 

dfs.c

#include <stdio.h> 
#include "list.h"
#define MAX_V 50
#define TRUE 1
#define FALSE 0

/*
typedef struct graph_t {
	int V; // No. of vertices
	node_t* adj[MAX_V];
} graph_t;
*/

typedef struct graph_t {
	int V; // No. of vertices 
	node_t** adj;   // 여기를 node_t* adj[MAX_V];로 배열선언해도됨
} graph_t;


// ADT
void init_graph(graph_t* g, int V);
void add_edge(graph_t* g, int v, int w);
node_t* insert_tail(node_t* head, element n);
void componet_of(graph_t* g, int start);
void print_graph(graph_t* g);
void free_list(node_t* head);
void free_graph(g);

void init_graph(graph_t* g, int V)
{
	g->V = V;
	g->adj = (node_t**)malloc(sizeof(node_t*) * V);  // 배열선언시 불필요
	for (int i = 0; i < V; i++)
		g->adj[i] = NULL;
}

void add_edge(graph_t* g, int v, int w)
{
	g->adj[v] = insert_tail(g->adj[v], w);
	g->adj[w] = insert_tail(g->adj[w], v);
}


int main(void)
{
	srand(time(NULL));
	graph_t* g = (graph_t*)malloc(sizeof(graph_t));
	int size;
	printf("노드 개수:");
	scanf_s("%d", &size);
	// 노드 개수로 그래프를 초기화한다
	init_graph(g, size);
	for (int i = 0; i < size; i++) {
		for (int j = i + 1; j < size; j++) {
			// 20% 확률로 에지를 랜덤하게 생성
			if (rand() % 5 == 0)
				add_edge(g, i, j);
		}
	}
	print_graph(g);
	printf("\n초기화 확인 노드 %d \n", g->adj[1]->next->val);
	
	int n;
	while (1) {
		printf("노드 번호:");
		scanf_s("%d", &n);
		if (n < 0 || n >= g->V)
			break;
		printf("%d번 노드가 속한 컴포넌트: ", n);
		componet_of(g, n);
	}
	free_graph(g);
	printf("\n초기화 확인 노드 %d \n", g->adj[1]->next->val);
	
	return 0;
}

// 과제 코드
void print_list(int n, node_t* head) {
	node_t* tmp = head;
	printf("[node %d] ", n);
	for (; tmp; tmp = tmp->next) {
		printf("%d ", tmp->val);
	}
	printf("\n");
}

void print_graph(graph_t* g) {
	for (int i = 0; i < g->V; i++)
		print_list(i, g->adj[i]);
	// 번호를 넘기로 i 노드의 연결리스트를 출력하게 함
}

node_t* insert_tail(node_t* head, element n) {
	node_t* tmp = head;
	node_t* res = (node_t*)malloc(sizeof(node_t));
	res->val = n;
	res->next = NULL;
	if (head == NULL) {
		return res;
	}
	while (tmp->next != NULL) {
		tmp = tmp->next;
	}
	tmp->next = res;
	return head;
}

int visited[MAX_V] = { 0 };

void dfs(graph_t* g, int v) {
	node_t* w;
	visited[v] = TRUE;
	printf("%d ", v);
	for (w = g->adj[v]; w; w = w->next) {
		if (!visited[w->val]) {
			dfs(g, w->val);
		}
	}
}

void componet_of(graph_t* g, int start) {
	for (int i = 0; i < MAX_V; i++) {
		visited[i] = 0;
	}
	dfs(g, start);
	printf("\n");
}

void free_list(node_t* head) {
	while (head != NULL) {
		node_t* removed = head;
		head = head->next;
		free(removed);
	}
}

void free_graph(graph_t* g) {
	for (int i = 0; i < g->V; i++) {
		free_list(g->adj[i]);
	}
	free(g);
}

 

 

카카오 코테에 데였나

과제가 왜 이렇게 쉬워졌지