c언어 dfs bfs 코드

#include <stdio.h>

#include <stdlib.h>

void makeList(int vertex1, int vertex2);

void showList();

void bfs(int startVertex);

void dfs(int startVertex);

void enqueue(int num);

int dequeue();

typedef struct node* nodePointer;

struct node{

int vertex;

nodePointer next;

}node;

nodePointer* arr;

int N, M, V, V1, V2;

int* queue; int front = 0, end = 0;

int* check_bfs, *check_dfs;

int main(){

FILE *fp = fopen("input1.txt", "rt");

fscanf(fp, "%d %d %d", &N, &M, &V);

arr = (nodePointer*)malloc(sizeof(nodePointer)+(N + 1));

check_bfs = (int*)malloc(sizeof(int)*(N + 1));

for (int i = 0; i <= N; i++){

arr[i] = NULL;

check_bfs[i] = 0; //dfs에서 방문한 노드를 체크하기 위하여

}

check_dfs = (int*)malloc(sizeof(int)*(N + 1));

for (int i = 0; i <= N; i++){

arr[i] = NULL;

check_dfs[i] = 0; //dfs에서 방문한 노드를 체크하기 위하여

}

while (!feof(fp)){

fscanf(fp, "%d %d", &V1, &V2);

makeList(V1, V2);

}

printf("bfs 탐색 %d : ", V);

bfs(V); printf("\n");

printf("dfs 탐색 %d : ", V);

dfs(V); printf("\n");

showList();

return 0;

}

void makeList(int vertex1, int vertex2)

{

nodePointer node1;

nodePointer node2, pre;

nodePointer temp;

node1 = (nodePointer) malloc(sizeof(node));

node2 = (nodePointer) malloc(sizeof(node));

node1->vertex = vertex1; node1->next = NULL;

node2->vertex = vertex2; node2->next = NULL;

if (!arr[vertex1])

arr[vertex1] = node2;

else{

for (temp = arr[vertex1]; temp; pre = temp, temp = temp->next);

temp = node2;

pre->next = temp;

}

if (!arr[vertex2])

arr[vertex2] = node1;

else{

for (temp = arr[vertex2]; temp; pre = temp, temp = temp->next);

temp = node1;

pre->next = node1;

}

}

void showList(){

for (int i = 1; i <= N; i++){

printf("%d : ", i);

for (nodePointer temp = arr[i]; temp; temp = temp->next){

printf(" %d", temp->vertex);

}

printf("\n");

}

}

void bfs(int startVertex)

{

int number = 0;

queue = (int*)malloc(sizeof(int)*(N+1));

for (int i = 0; i <= N; i++)

queue[i] = 0;

check_bfs[startVertex] = -1;

//큐에 시작값 삽입

enqueue(startVertex);

printf("%d,", startVertex);

//큐에 저장된 값이 사라질때 까지

while (number=dequeue())

{

//반복문 : 큐에서 뺄 값이 없을때까지 실행

for (nodePointer temp = arr[number]; temp ; temp = temp->next)

{

if (check_bfs[temp->vertex] != -1){

enqueue(temp->vertex);

check_bfs[temp->vertex] = -1;

printf(" %d,", temp->vertex);

}

/*if (check[temp->vertex] != -1){

dfs(temp->vertex);

}*/

}

}

}

void dfs(int startVertex){

check_dfs[startVertex] = -1;

printf(" %d", startVertex);

//for 해당 노드에서 연결되어 있는 노드들 탐색

for (nodePointer temp = arr[startVertex]; temp; temp = temp->next)

{

//탐색된 노드 중에서 방문안한 노드만 실행

if (check_dfs[temp->vertex] != -1){

dfs(temp->vertex);

}

}

}

void enqueue(int num){

queue[end++] = num;

}

int dequeue(){

return queue[front++];

}