[자료구조] Graph.c

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include "LinkedList.h" // Graph 구조체 구현 시 필요 -> LinkedList.h LinkedList.c 모두 빌드에 추가
#include "Stack.h" // DFS 구현 시 필요 -> Stack.h Stack.c 모두 빌드에 추가해야함
#include "CircularQueue.h" // BFS 구현 시 필요

#define MAX_VERTEX 100

typedef struct graphType {
	int N;
	List* adjList_H; // List 배열을 가리키는 header 포인터
	int visited[MAX_VERTEX];
}Graph;

void GraphInit(Graph* gp, int nv) {
	gp->N = nv;
	gp->adjList_H = (List*)malloc(sizeof(List) * nv);

	for (int i = 0; i < nv; i++) {
		// ListInit(List* plist);
		// gp->adjList_H[i] == List type
		ListInit(&(gp->adjList_H[i]));
	}

	for (int i = 0; i < nv; i++) gp->visited[i] = 0;
}

void AddEdge(Graph* gp, int from, int to) {
	FrontInsert(&(gp->adjList_H[from]), to);
	FrontInsert(&(gp->adjList_H[to]), from); //무방향일때 추가
}

void visitedInit(Graph* gp) {
	for (int i = 0; i < gp->N; i++) gp->visited[i] = 0;
}


void DFS(Graph* gp, int startv) {
	visitedInit(gp);

	Stack stack;
	StackInit(&stack,100); // stack size 100
	
	Node* curNode;

	gp->visited[startv] = 1;
	printf("%d\n", startv);

	// stack이 다 비지 않을때까지
	while (startv!=-1) {
		curNode = (gp->adjList_H[startv].head)->next;

		// 방문할 노드가 있으면
		while (curNode != NULL) {
			// 아직 방문하지 않았으면
			if (gp->visited[curNode->data] == 0) {
				push(&stack, startv);
				//PrintStack(&stack);

				gp->visited[curNode->data] = 1;
				printf("%d\n", curNode->data);

				// 해당 리스트로 이동
				startv = curNode->data;
				curNode = (gp->adjList_H[startv].head)->next;
			}
			// 방문했으면
			else {
				curNode = curNode->next;
			}
		}
		startv = pop(&stack);
	}
}

void BFS(Graph* gp, int startv) {
	
	visitedInit(gp);

	CQueue cq;
	CQInit(&cq,100);

	Node* curNode;

	gp->visited[startv] = 1;

	printf("%d\n", startv);
	CQPush(&cq, startv);

	while (!CQIsEmpty(&cq)) {

		startv = CQFront(&cq);
		CQPop(&cq);

		curNode = (gp->adjList_H[startv]).head->next;

		// BFS 니까 끝까지 조사
		while (curNode != NULL) {
			// 방문을 안했으면
			if (gp->visited[curNode->data] == 0) {
				printf("%d\n", curNode->data);
				gp->visited[curNode->data] = 1;
				// 큐에 추가
				CQPush(&cq, curNode->data);
			}
			curNode = curNode->next;
		}
	}
}

int main() {
	Graph graph;
	GraphInit(&graph, 8);

	AddEdge(&graph, 1, 2);
	AddEdge(&graph, 2, 3);
	AddEdge(&graph, 3, 4);
	AddEdge(&graph, 4, 5);
	AddEdge(&graph, 5, 6);
	AddEdge(&graph, 4, 7);
	DFS(&graph, 1);
	printf("\n");
	BFS(&graph, 1);
	return 0;
}

---

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include "string.h"

// GRAPH + STACK + QUEUE

typedef int Sdata;
typedef int QData;
typedef int LData;

#define SIZE 100

// char 자료형이면 visited[char-'A'+1?]로 해야함

// STACK

typedef struct _Stack {
	Sdata* arr;
	int top; // -1
}Stack;

void StackInit(Stack* s, int N) {
	s->arr = (Sdata*)malloc(sizeof(Sdata) * N);
	s->top = -1;
}

// 최대 100 일때
void push(Stack* s, Sdata d) {
	if (s->top != SIZE) {
		s->top++;
		s->arr[s->top] = d;
	}
}

int pop(Stack* s) {
	int retData = -1;
	if (s->top != -1) {
		retData = s->arr[s->top];
		s->top--;
	}
	return retData;
}

void peek(Stack* s) {
	if (s->top != -1) {
		printf("%d\n", s->arr[s->top]);
	}
	else {
		printf("-1\n");
	}
}

int size(Stack* s) { return s->top + 1; }

int IsEmpty(Stack* s) { return s->top == -1; }

void PrintStack(Stack* s) {
	for (int i = 0; i < s->top; i++) {
		printf(" %d", s->arr[i]);
	}
	printf("\n");
}

// QUEUE
typedef int QData;

typedef struct _CircularQueue {
	QData* arr;
	int size;
	int front; // front에는 데이터 없음. 원형큐는 front 한 칸만 공백
	int rear;
}CQueue;

void CQInit(CQueue* qp, int size) {
	// calloc 가능
	qp->arr = (QData*)malloc(sizeof(QData) * size);
	memset(qp->arr, 0, size * sizeof(QData));

	qp->size = size;
	qp->front = qp->rear = 0;
}

int NextPosIdx(CQueue* qp, int pos) { return (pos + 1) % qp->size; }

int CQIsEmpty(CQueue* qp) {
	return qp->front == qp->rear ? 1 : 0;
}

int CQIsFull(CQueue* qp) {
	return NextPosIdx(qp, qp->rear) == qp->front ? 1 : 0;
}

void CQPrint(CQueue* qp) {
	for (int i = 0; i < qp->size; i++) {
		printf(" %d", qp->arr[i]);
	}
	printf("\n");
}

void CQPush(CQueue* qp, QData data) {
	if (!CQIsFull(qp)) {
		qp->rear = NextPosIdx(qp, qp->rear); // rear 한칸 이동 후 저장
		qp->arr[qp->rear] = data;
	}
	else {
		printf("overflow ");
		CQPrint(qp);
	}
}

void CQPop(CQueue* qp) {
	if (!CQIsEmpty(qp)) {
		qp->front = NextPosIdx(qp, qp->front); // front 한칸 이동
		qp->arr[qp->front] = 0;
		//printf("%d\n", qp->arr[qp->front]);
	}
	else {
		printf("underflow\n");
	}
}

QData CQFront(CQueue* qp) {
	if (!CQIsEmpty(qp)) return qp->arr[NextPosIdx(qp, qp->front)];
	else return -1;
}

QData CQBack(CQueue* qp) {
	if (!CQIsEmpty(qp)) return qp->arr[qp->rear];
	else return -1;
}

int CQSize(CQueue* qp) {
	return qp->rear >= qp->front ? qp->rear - qp->front : (qp->size - qp->front) + qp->rear;
}

// LINKED-LIST

typedef struct node {
	LData data;
	struct node* next;
}Node;

typedef struct linkedlist {
	Node* head;
	int cnt;
}List;

void ListInit(List* plist) {
	// DummyNode
	plist->head = (Node*)malloc(sizeof(Node));
	plist->head->next = NULL;
	plist->cnt = 0;
	//printf("List init complete\n");
}

//무조건 앞에 배치
void FrontInsert(List* plist, LData data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	// plist->head == DummyNode 임

	newNode->next = plist->head->next;
	plist->head->next = newNode;
}

// 무조건 끝에 배치
void BackInsert(List* plist, LData data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	Node* temp = plist->head; // 더미노드에서 시작

	while (temp->next != NULL) {
		temp = temp->next;
	}

	temp->next = newNode;
}

// 원하는곳에 추가
void ListInsert(List* plist, int idx, LData data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	Node* prev = plist->head;

	// idx-1번째를 찾아야함
	for (int i = 0; i < idx - 1; i++) {
		if (prev == NULL) { return; }
		prev = prev->next;
	}

	prev->next = newNode;
}

void ListDelete(List* plist, int idx) {
	Node* prev = plist->head;

	for (int i = 0; i < idx - 1; i++) {
		if (prev == NULL) return;
		prev = prev->next;
	}

	prev->next = prev->next->next;
	free(prev);
}

//GRAPH(LIST)

typedef struct graphType {
	int N;
	List* adjList_H; // List 배열을 가리키는 header 포인터
	int visited[SIZE];
}Graph;

void GraphInit(Graph* gp, int nv) {
	gp->N = nv;
	gp->adjList_H = (List*)malloc(sizeof(List) * nv);

	for (int i = 0; i < nv; i++) {
		// 리스트 배열의 각 리스트 초기화
		ListInit(&(gp->adjList_H[i]));
	}

	for (int i = 0; i < nv; i++) gp->visited[i] = 0;
}

void AddEdge(Graph* gp, int from, int to) {
	FrontInsert(&(gp->adjList_H[from]), to);
	FrontInsert(&(gp->adjList_H[to]), from); //무방향일때 추가
}

void visitedInit(Graph* gp) {
	for (int i = 0; i < gp->N; i++) gp->visited[i] = 0;
}

// 여긴 더미노드를 사용한 adjList를 사용했으므로
// adjList[v].head로 초반작업을 해줘야함

void DFS(Graph* gp, int startv) {
	// 방문 모두 0으로 초기화
	visitedInit(gp);

	Stack stack;
	StackInit(&stack, SIZE);

	Node* curNode;

	gp->visited[startv] = 1;
	printf("%d\n", startv);

	// stack이 다 비지 않을때까지
	while (startv != -1) {
		curNode = (gp->adjList_H[startv].head)->next;

		// 방문할 노드가 있으면
		while (curNode != NULL) {
			// 아직 방문하지 않았으면
			if (gp->visited[curNode->data] == 0) {
				// 기존에 탐색하던 리스트 번호를 스택에 넣어 저장해두고
				push(&stack, startv);
				// 해당 리스트로 이동
				startv = curNode->data;

				// 새로운 리스트 탐색 전에 방문처리 해주기
				gp->visited[curNode->data] = 1;
				printf("%d\n", curNode->data);

				curNode = (gp->adjList_H[startv].head)->next;
			}
			// 이미 방문을 한거면
			else {
				curNode = curNode->next;
			}
		}
		// 해당 리스트 노드 탐색이 다 끝났으면
		// stack에 넣어놨던 리스트 번호를 꺼내 탐색하기
		startv = pop(&stack);
	}
}

void BFS(Graph* gp, int startv) {

	visitedInit(gp);

	CQueue cq;
	CQInit(&cq, SIZE);

	Node* curNode;

	gp->visited[startv] = 1;

	printf("%d\n", startv);
	CQPush(&cq, startv);

	while (!CQIsEmpty(&cq)) {

		startv = CQFront(&cq);
		CQPop(&cq);

		curNode = (gp->adjList_H[startv]).head->next;

		// BFS 니까 한 리스트를 끝까지 조사
		// 중간에 방문안한 노드 만나도 그냥 큐에 집어넣기만함
		while (curNode != NULL) {
			// 방문을 안했으면
			if (gp->visited[curNode->data] == 0) {
				printf("%d\n", curNode->data);
				gp->visited[curNode->data] = 1;
				// 큐에 추가
				CQPush(&cq, curNode->data);
			}
			// 해당 리스트 계속 탐색
			curNode = curNode->next;
		}
	}
}

int main() {
	Graph graph;
	GraphInit(&graph, 8);

	AddEdge(&graph, 1, 2);
	AddEdge(&graph, 1, 3);
	AddEdge(&graph, 2, 4);
	AddEdge(&graph, 2, 5);
	AddEdge(&graph, 3, 5);
	AddEdge(&graph, 4, 6);
	AddEdge(&graph, 5, 6);
	AddEdge(&graph, 6, 7);
	
	DFS(&graph, 1);
	printf("\n");
	BFS(&graph, 1);
	return 0;
}