너비 우선 탐색

C# 언어에서 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘을 구현하는 간단한 예제를 아래에 제공합니다. 이 예제에서는 인접 리스트를 사용하여 그래프를 표현하고 있습니다.

코드: BreadthFirstSearchExample.cs

namespace BreadthFirstSearchExample
{
    using System;
    using System.Collections.Generic;

    class Graph
    {
        private int numVertices; // 정점의 개수
        private List<int>[] adjList; // 인접 리스트를 사용한 그래프 표현

        // 생성자: 정점의 개수를 인자로 받아 초기화
        public Graph(int numVertices)
        {
            this.numVertices = numVertices;
            adjList = new List<int>[numVertices];
            for (int i = 0; i < numVertices; i++)
            {
                adjList[i] = new List<int>();
            }
        }

        // 간선 추가 메서드: 두 정점 u, v를 인자로 받아 간선을 추가
        public void AddEdge(int u, int v)
        {
            adjList[u].Add(v);
        }

        // 너비 우선 탐색 메서드: 시작 정점을 인자로 받아 실행
        public void BFS(int startVertex)
        {
            bool[] visited = new bool[numVertices]; // 방문한 정점을 기록하는 배열
            Queue<int> queue = new Queue<int>(); // 탐색할 정점을 저장하는 큐

            visited[startVertex] = true; // 시작 정점을 방문한 것으로 표시
            queue.Enqueue(startVertex); // 시작 정점을 큐에 삽입

            while (queue.Count > 0)
            {
                int currentVertex = queue.Dequeue(); // 큐에서 정점을 꺼냄
                Console.WriteLine("방문한 노드: " + currentVertex);

                // 인접한 정점들을 순회하며 방문하지 않은 정점을 큐에 삽입
                foreach (int adjacent in adjList[currentVertex])
                {
                    if (!visited[adjacent])
                    {
                        visited[adjacent] = true;
                        queue.Enqueue(adjacent);
                    }
                }
            }
        }
    }

    class BreadthFirstSearchExample
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph(6); // 6개의 정점을 가진 그래프 객체 생성

            // 간선 추가
            graph.AddEdge(0, 1);
            graph.AddEdge(0, 2);
            graph.AddEdge(1, 3);
            graph.AddEdge(1, 4);
            graph.AddEdge(2, 4);
            graph.AddEdge(2, 5);

            graph.BFS(0); // 시작 정점을 0으로 설정하고 너비 우선 탐색 실행
        }
    }
}

방문한 노드: 0
방문한 노드: 1
방문한 노드: 2
방문한 노드: 3
방문한 노드: 4
방문한 노드: 5

위 코드에서 Graph 클래스는 그래프를 표현하고, BFS 메서드를 사용하여 너비 우선 탐색을 수행합니다. 너비 우선 탐색은 시작 정점에서 가장 가까운 정점들부터 방문하는 방식으로 진행됩니다. 방문한 노드를 visited 배열에 표시하여 이미 방문한 노드를 다시 방문하지 않습니다. 큐(Queue)를 사용하여 탐색할 정점들을 저장하고, 큐에 정점이 없을 때까지 탐색을 반복합니다.

Main 메서드에서 그래프를 생성하고 간선을 추가한 뒤, 시작 노드를 지정하여 너비 우선 탐색을 수행합니다. 이 예제에서는 시작 정점을 0으로 설정하고 너비 우선 탐색을 실행합니다. 결과로 인접한 정점들이 가까운 순서대로 방문한 노드가 출력됩니다.

프로그램 소스 코드 실행 순서는 다음과 같습니다.

1. 프로그램이 실행되면 Main 메서드가 호출됩니다.
2. Main 메서드에서 Graph 객체를 생성하고, 정점의 개수 6으로 초기화합니다. 이 때, Graph 클래스의 생성자가 호출되며, 인접 리스트를 초기화합니다.
3. 그래프에 간선들을 추가하기 위해 AddEdge 메서드를 호출합니다. 이 메서드는 인자로 받은 두 정점 사이에 간선을 추가합니다.
4. graph.BFS(0)을 호출하여 너비 우선 탐색을 시작합니다. 시작 정점은 0으로 설정됩니다.
5. BFS 메서드에서 visited 배열과 queue를 초기화합니다. 시작 정점을 방문한 것으로 표시하고 큐에 추가합니다.
6. 큐에 정점이 남아있는 동안 다음 단계를 반복합니다:
   1. 큐에서 정점을 꺼냅니다.
   2. 꺼낸 정점을 출력합니다.
   3. 꺼낸 정점의 인접한 정점들을 순회합니다.
      1. 인접한 정점이 방문되지 않았다면, 방문한 것으로 표시하고 큐에 추가합니다.
7. 큐가 비어있으면 너비 우선 탐색이 완료됩니다. 이 예제에서는 인접한 정점들이 가까운 순서대로 방문하게 되며, 방문한 노드를 출력합니다. 실행 결과는 다음과 같습니다.

방문한 노드: 0
방문한 노드: 1
방문한 노드: 2
방문한 노드: 3
방문한 노드: 4
방문한 노드: 5

너비 우선 탐색이 완료되면 프로그램이 종료됩니다. 이 알고리즘은 그래프의 모든 정점을 방문하고, 각 정점의 인접한 정점들을 큐에 추가함으로써 너비 우선 탐색을 구현합니다. 이를 통해 그래프의 모든 정점을 너비 우선 방식으로 방문하게 됩니다.

C 언어에서 너비 우선 탐색 알고리즘을 구현하려면, 큐(Queue) 자료구조를 사용하여 노드를 방문할 수 있습니다. 다음은 간단한 예시입니다:

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 10

bool visited[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];
int queue[MAX_VERTICES];
int front = -1;
int rear = -1;

void enqueue(int vertex) 
{
    queue[++rear] = vertex;
}

int dequeue() 
{
    return queue[++front];
}

bool is_queue_empty() 
{
    return front == rear;
}

void bfs(int start_vertex, int num_vertices) 
{
    visited[start_vertex] = true;
    enqueue(start_vertex);

    while (!is_queue_empty()) 
    {
        int current_vertex = dequeue();
        printf("방문한 노드: %d\n", current_vertex);

        for (int i = 0; i < num_vertices; i++) 
        {
            if (graph[current_vertex][i] && !visited[i]) 
            {
                visited[i] = true;
                enqueue(i);
            }
        }
    }
}

int main(void) 
{
    int num_vertices = 6;
    // 간선 표현 (인접 행렬)
    int edges[6][6] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0}
    };

    // 그래프 초기화
    for (int i = 0; i < num_vertices; i++) 
    {
        for (int j = 0; j < num_vertices; j++) 
        {
            graph[i][j] = edges[i][j];
        }
    }

    // 모든 정점을 방문하지 않은 상태로 초기화
    for (int i = 0; i < num_vertices; i++) 
    {
        visited[i] = false;
    }

    // 시작 정점을 0으로 설정하고 너비 우선 탐색 실행
    bfs(0, num_vertices);

    return 0;
}

위 코드는 인접 행렬을 사용하여 그래프를 표현하고 있으며, 너비 우선 탐색 알고리즘을 사용하여 그래프의 노드를 방문합니다. 방문한 노드는 visited 배열에 표시되어 이미 방문한 노드를 다시 방문하지 않습니다. 큐(Queue)를 사용하여 방문할 노드를 저장하고, 인접한 노드들을 순차적으로 방문하며 큐에 넣습니다. 이렇게 너비 우선 탐색은 레벨 순서대로 그래프의 노드를 방문하게 됩니다.

내용 준비중입니다...

내용 준비중입니다...

내용 준비중입니다...

내용 준비중입니다...

내용 준비중입니다...

내용 준비중입니다...

내용 준비중입니다...