1. 그래프 순회
스패닝 트리 (Spanning Tree)
- 정의: 그래프의 모든 정점을 포함하고 사이클이 없는 부분 그래프.
- 구성: 깊이 우선 탐색(DFS)을 사용하여 스패닝 트리를 구성.
- DFS로 연결된 그래프의 정점을 순회하면서 n-1개의 간선으로 스패닝 트리를 정의함.
// DFS를 사용한 스패닝 트리 생성 예제 코드
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
bool visited[MAX];
int graph[MAX][MAX];
int n; // 정점의 개수
void dfs(int v) {
visited[v] = true;
printf("%d ", v);
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
dfs(i);
}
}
}
int main() {
n = 6; // 정점의 수
// 그래프 인접 행렬
int graph[MAX][MAX] = {
{0, 1, 1, 0, 0, 0},
{1, 0, 1, 1, 0, 0},
{1, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 1},
{0, 0, 1, 1, 0, 1},
{0, 0, 0, 1, 1, 0}
};
for (int i = 0; i < n; i++) visited[i] = false;
printf("DFS Spanning Tree starting from vertex 0:\n");
dfs(0);
printf("\n");
return 0;
}
2. BFS (너비 우선 탐색)
- 정의: 시작 정점에서 인접한 정점들을 우선으로 방문하는 방법.
- 구현: FIFO 큐를 사용하여 구현.
- 시간 복잡도:
- 인접 행렬 사용 시: O(n^2)
- 인접 리스트 사용 시: O(n+e) (e는 간선의 수)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100
typedef struct {
int items[MAX];
int front;
int rear;
} Queue;
void initQueue(Queue* q) {
q->front = -1;
q->rear = -1;
}
bool isEmpty(Queue* q) {
return q->front == -1;
}
bool isFull(Queue* q) {
return q->rear == MAX - 1;
}
void enqueue(Queue* q, int value) {
if (isFull(q)) return;
if (isEmpty(q)) q->front = 0;
q->items[++q->rear] = value;
}
int dequeue(Queue* q) {
int item;
if (isEmpty(q)) return -1;
item = q->items[q->front];
if (q->front >= q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
return item;
}
void bfs(int graph[MAX][MAX], int start, int n) {
Queue q;
initQueue(&q);
bool visited[MAX] = { false };
printf("BFS Traversal starting from node %d:\n", start);
visited[start] = true;
enqueue(&q, start);
while (!isEmpty(&q)) {
int currentNode = dequeue(&q);
printf("%d ", currentNode);
for (int i = 0; i < n; i++) {
if (graph[currentNode][i] == 1 && !visited[i]) {
visited[i] = true;
enqueue(&q, i);
}
}
}
printf("\n");
}
int main() {
int n = 6; // 정점의 개수
int graph[MAX][MAX] = {
{0, 1, 1, 0, 0, 0},
{1, 0, 1, 1, 0, 0},
{1, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 1},
{0, 0, 1, 1, 0, 1},
{0, 0, 0, 1, 1, 0}
};
bfs(graph, 0, n);
return 0;
}
3. 최소 비용 스패닝 트리 (Minimum Cost Spanning Tree)
크루스칼 알고리즘 (Kruskal's Algorithm)
- 정의: 모든 간선의 가중치 합이 최소인 스패닝 트리를 찾는 알고리즘.
- 구현: 간선을 가중치 순으로 정렬하고, 사이클이 생기지 않도록 선택.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int u, v, w;
} Edge;
Edge edges[MAX];
int parent[MAX];
int find(int i) {
while (parent[i] != i)
i = parent[i];
return i;
}
void unionSets(int i, int j) {
int a = find(i);
int b = find(j);
parent[a] = b;
}
int cmp(const void* a, const void* b) {
Edge* edgeA = (Edge*)a;
Edge* edgeB = (Edge*)b;
return edgeA->w - edgeB->w;
}
void kruskal(int n, int e) {
int i, cost = 0;
for (i = 0; i < n; i++)
parent[i] = i;
qsort(edges, e, sizeof(Edge), cmp);
printf("Edges in MST:\n");
for (i = 0; i < e; i++) {
int u = edges[i].u;
int v = edges[i].v;
int w = edges[i].w;
if (find(u) != find(v)) {
printf("(%d, %d) -> %d\n", u, v, w);
cost += w;
unionSets(u, v);
}
}
printf("Minimum cost: %d\n", cost);
}
int main() {
int n = 6; // 정점의 수
int e = 9; // 간선의 수
Edge inputEdges[] = {
{0, 1, 4}, {0, 2, 4}, {1, 2, 2}, {1, 0, 4},
{2, 0, 4}, {2, 1, 2}, {2, 3, 3}, {2, 5, 2},
{2, 4, 4}, {3, 2, 3}, {3, 4, 3}, {4, 2, 4},
{4, 3, 3}, {5, 2, 2}, {5, 4, 3}
};
for (int i = 0; i < e; i++)
edges[i] = inputEdges[i];
kruskal(n, e);
return 0;
}
프림 알고리즘 (Prim's Algorithm)
- 정의: 정점을 하나씩 추가하면서 최소 비용 스패닝 트리를 구성하는 알고리즘.
- 구현: 최소 간선을 선택하여 트리를 확장.
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
#define INF 9999999
void prim(int graph[MAX][MAX], int n) {
int selected[MAX] = { false };
int no_edge = 0;
selected[0] = true;
printf("Edge : Weight\n");
while (no_edge < n - 1) {
int min = INF;
int x = 0;
int y = 0;
for (int i = 0; i < n; i++) {
if (selected[i]) {
for (int j = 0; j < n; j++) {
if (!selected[j] && graph[i][j]) {
if (min > graph[i][j]) {
min = graph[i][j];
x = i;
y = j;
}
}
}
}
}
printf("%d - %d : %d\n", x, y, graph[x][y]);
selected[y] = true;
no_edge++;
}
}
int main() {
int n = 5; // 정점의 수
int graph[MAX][MAX] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
prim(graph, n);
return 0;
}
Comments 0