[운영체제]1-1. 실습과제 : C 프로그램 컴파일 및 실행

운영체제 수업 과제를 위한 소스코드 입니다.

20214110 안세준

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
#define MAX_NODES 50

// 방문 체크 배열
int visited_matrix[MAX_NODES];
int visited_list[MAX_NODES];

// 인접 행렬 기반 그래프 구조체
typedef struct {
    int num_nodes;
    int adjacency[MAX_NODES][MAX_NODES];
} MatrixGraph;

// 큐 구조체
typedef struct {
    int front, rear;
    int data[MAX_SIZE];
} Queue;

// 연결 리스트 기반 그래프 구조체
typedef struct GraphNode {
    int vertex;
    struct GraphNode *next;
} GraphNode;

typedef struct {
    int num_nodes;
    GraphNode *adj_list[MAX_NODES];
} ListGraph;

// 인접 행렬 그래프 초기화
void init_matrix_graph(MatrixGraph *g) {
    g->num_nodes = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        for (int j = 0; j < MAX_NODES; j++) {
            g->adjacency[i][j] = 0;
        }
    }
}

// 연결 리스트 그래프 초기화
void init_list_graph(ListGraph *g) {
    g->num_nodes = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        g->adj_list[i] = NULL;
    }
}

// 정점 추가
void add_vertex(MatrixGraph *g) {
    if (g->num_nodes >= MAX_NODES) {
        fprintf(stderr, "정점 초과 오류\n");
        return;
    }
    g->num_nodes++;
}

void add_vertex_list(ListGraph *g) {
    if (g->num_nodes >= MAX_NODES) {
        fprintf(stderr, "정점 초과 오류\n");
        return;
    }
    g->num_nodes++;
}

// 간선 추가
void add_edge(MatrixGraph *g, int src, int dest) {
    g->adjacency[src][dest] = 1;
    g->adjacency[dest][src] = 1;
}

void add_edge_list(ListGraph *g, int src, int dest) {
    GraphNode *node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = dest;
    node->next = g->adj_list[src];
    g->adj_list[src] = node;
}

// 큐 초기화
void init_queue(Queue *q) {
    q->front = q->rear = -1;
}

int is_empty(Queue *q) {
    return q->front == q->rear;
}

int is_full(Queue *q) {
    return q->rear == MAX_SIZE - 1;
}

void enqueue(Queue *q, int item) {
    if (!is_full(q)) {
        q->data[++(q->rear)] = item;
    }
}

int dequeue(Queue *q) {
    if (!is_empty(q)) {
        return q->data[++(q->front)];
    }
    return -1;
}

// BFS 탐색 (인접 행렬)
void bfs_matrix(MatrixGraph *g, int start) {
    Queue q;
    init_queue(&q);
    visited_matrix[start] = 1;
    printf("%d 방문 -> ", start + 1);
    enqueue(&q, start);

    while (!is_empty(&q)) {
        int v = dequeue(&q);
        for (int i = 0; i < g->num_nodes; i++) {
            if (g->adjacency[v][i] && !visited_matrix[i]) {
                visited_matrix[i] = 1;
                printf("%d 방문 -> ", i + 1);
                enqueue(&q, i);
            }
        }
    }
}

// BFS 탐색 (연결 리스트)
void bfs_list(ListGraph *g, int start) {
    Queue q;
    init_queue(&q);
    visited_list[start] = 1;
    printf("%d 방문 -> ", start + 1);
    enqueue(&q, start);

    while (!is_empty(&q)) {
        int v = dequeue(&q);
        for (GraphNode *node = g->adj_list[v]; node; node = node->next) {
            if (!visited_list[node->vertex]) {
                visited_list[node->vertex] = 1;
                printf("%d 방문 -> ", node->vertex + 1);
                enqueue(&q, node->vertex);
            }
        }
    }
}

int main(void) {
    MatrixGraph *g = (MatrixGraph*)malloc(sizeof(MatrixGraph));
    ListGraph *l = (ListGraph*)malloc(sizeof(ListGraph));
    
    int edges[][2] = {{1, 3}, {1, 2}, {2, 8}, {8, 7}, {8, 6}, {6, 7}, {3, 5}, {3, 4}, {4, 5}};
    
    init_matrix_graph(g);
    init_list_graph(l);

    for (int i = 0; i < 8; i++) {
        add_vertex(g);
        add_vertex_list(l);
    }
    
    for (int i = 0; i < 9; i++) {
        add_edge(g, edges[i][0] - 1, edges[i][1] - 1);
        add_edge_list(l, edges[i][0] - 1, edges[i][1] - 1);
    }

    printf("BFS 탐색 (인접 행렬) : \n");
    bfs_matrix(g, 0);
    printf("\n");
    
    printf("BFS 탐색 (연결 리스트) : \n");
    bfs_list(l, 0);
    printf("\n");
    
    free(g);
    free(l);
    return 0;
}