2022-03-16-DataStructure-Week11-실습2

adj_matrix

• DFS와 BFS의 구현
• 명령어
  D: DFS
  B: BFS
  Q: Quit

자료구조 및 함수 구성

// Adjacency matrix for a graph
int adj[MAX_VERTICES][MAX_VERTICES];

• void build_simple_graph()
  샘플 그래프의 생성

• void insert_edge(int v, int w)
  vertex v 와 w 를 연결하는 edge 를 2 차원 배열에 표현
  
  
• void dfs(int v)
  v 에서 DFS 수행
  
  
• void bfs(int v)
  v 에서 BFS 수행
  
• void addq(Element e)
  새 노드 생성
  큐의 맨 뒤에 삽입
  
  
• Element deleteq()
  큐의 맨 앞 노드 삭제
  
  

• boolean is_queue_empty()

  실행 예

Source

• 실습2.h

#pragma once
#define MAX_VERTICES 100
#define boolean unsigned char
#define true 1
#define false 0

int adj[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];

void build_simple_graph();
void insert_edge(int v, int w);
void dfs(int v);
void bfs(int v);

typedef int Element;
typedef struct queue* queue_pointer;
typedef struct queue {
	Element item;
	queue_pointer link;
}queue;
queue_pointer front, rear;

void addq(Element e);
Element deleteq();
boolean is_queue_empty();

• 실습2.cpp

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<ctype.h>
#include"실습2.h"

void build_simple_graph() {
	for (int i = 0; i < MAX_VERTICES; i++)
		for (int j = 0; j < MAX_VERTICES; j++)
			adj[i][j] = 0;

	insert_edge(1, 2);
	insert_edge(2, 1);
	insert_edge(1, 3);
	insert_edge(3, 1);
	insert_edge(1, 4);
	insert_edge(4, 1);
	insert_edge(2, 5);
	insert_edge(5, 2);
	insert_edge(3, 5);
	insert_edge(5, 3);
	insert_edge(3, 5);
	insert_edge(5, 4);

	printf("\nGraph is built. V = 5, E = 6. \n\n");
}
void insert_edge(int v, int w) {
	adj[v][w] = 1;
	adj[w][v] = 1;
}
void dfs(int v) {
	printf("%d ", v);
	visited[v] = true;
	for (int i=1; i<=MAX_VERTICES; i++) {
		if (adj[v][i] && !visited[i])
			dfs(i);
	}
}

void bfs(int v) {
	queue_pointer w;
	printf("%d ", v);
	visited[v] = true;
	addq(v);
	while (!is_queue_empty()) {
		v = deleteq();
		for (int i = 1; i <= MAX_VERTICES; i++) {
			if (adj[v][i] && !visited[i]){
				printf("%d ", i);
				visited[i] = true;
				addq(i);
			}
		}
	}
}

void addq(Element e) {
	queue_pointer temp = (queue_pointer)malloc(sizeof(queue));
	temp->item = e;
	temp->link = NULL;

	if (is_queue_empty())
		front = rear = temp;

	rear->link = temp;
	rear = temp;
}
Element deleteq() {
	queue_pointer temp;
	Element item;

	if (is_queue_empty())
		return item;
	item = front->item;
	temp = front;

	front = front->link;
	free(temp);

	return item;
}
boolean is_queue_empty() {
	if (front == NULL)
		return true;
	else
		return false;
}

void main() {
	char c;
	int i, v;

	front = rear = NULL;
	build_simple_graph();

	while (1) {
		printf("\nCommand> ");
		c = getch();
		putch(c);
		c = toupper(c);

		switch (c) {
		case'D':
			printf("\n Start vertex: ");
			scanf("%d", &v);
			for (i = 0; i < MAX_VERTICES; i++)
				visited[i] = false;
			dfs(v);
			printf("\n");
			break;
		case'B':
			printf("\n Start vertex: ");
			scanf("%d", &v);
			for (i = 0; i < MAX_VERTICES; i++)
				visited[i] = false;
			bfs(v);
			printf("\n");
			break;
		case'Q':
			printf("\n");
			exit(1);
		default:
			break;
		}
	}
}