[Unity C#] BFS(Breadth First Search Algorithm) : 너비 우선 탐색

개념

하나의 정점으로부터 시작하여 인접한 노드를 모두 방문하고 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘 

과정

장점

장점으로는, 출발노드에서 목표노드까지의 최단 길이 경로를 보장합니다. (물론 모든 간선의 가중치가 동일할 경우입니다.)

단점

단점으로는, 최악의 경우 모든 노드에 대한 정보를 위한 공간을 요구한다는 것입니다. 따라서 최대 저장공간을 크게 잡아야 합니다. 또한 목표노드가 깊은 단계에 있을 경우 오랜 시간이 소요됩니다.

시간복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

소스코드 - 인접리스트

public class BreadthFirstSearch_Source : MonoBehaviour
{
    void Start()
    {
        int n = 5; // 정점의 개수
        int m = 5; // 간선의 개수
        int v = 3; // 시작 정점


        ArrayList[] alist = new ArrayList[n + 1];
        bool[] c = new bool[n + 1];

        for (int i = 1; i < n + 1; i++)
        {
            alist[i] = new ArrayList();
        }

        //간선의 개수 5개 input으로하면 for문으로 m까지
        //양방향 그래프        
        alist[5].Add(4);
        alist[4].Add(5);

        alist[5].Add(2);
        alist[2].Add(5);

        alist[1].Add(2);
        alist[2].Add(1);

        alist[3].Add(4);
        alist[4].Add(3);

        alist[3].Add(1);
        alist[1].Add(3);

        for (int i = 1; i < n + 1; i++)
        {
            alist[i].Sort(); // 작은 값부터 먼저 방문하도록 정렬
        }

        bfs(alist,c,v);
    }

    // BFS 인접리스트
    void bfs(ArrayList[] a, bool[] c, int v)
    {
        Queue<int> q = new Queue<int>(); // queue만들기 

        q.Enqueue(v); // 시작정점 방문했으므로 노드 추가 
        c[v] = true; // 시작정점 방문했으므로 true 

        while (q.Count > 0) // q가 0이 되지 않았으면 반복 
        {
            v = q.Dequeue(); // 선입선출
            Debug.Log(v + " "); // out되는 데이터를 출력 

            foreach (int vv in a[v]) // 해당 배열에 리스트를 훑어보면서  
            {

                if (!c[vv])// 아직 방문하지 않은 노드가 있다면 
                {
                    q.Enqueue(vv); // 싹다 Enqueue에 추가한다, DFS에서는 재귀를 써서 깊이탐색을하는데
                    c[vv] = true;  // BFS에서는 그냥 추가를 해서 너비탐색을 함
                }

            }
        }
    }
    // 3(true)
    // 1(true) 4(true)
    // 4(true) 2(true 1)
    // 2(true 1) 5(true 4)
    // 5(true 4)
    // (종료)
    //
    // Log : 3
    // Log : 3 1
    // Log : 3 1 4
    // Log : 3 1 4 2
    // Log : 3 1 4 2 5
}

소스코드 - 인접행렬

void bfs_Matrix(int[,] arr, bool[] c , int v)
    {
        Queue<int> q = new Queue<int>();
        int n = arr.GetLength(0) - 1;

        //1.시작 정점 방문
        q.Enqueue(v);
        //2.시작 정점 방문 check
        c[v] = true;

        //3.q에 아무것도 없을 때까지 반복
        while(q.Count > 0)
        {
            v = q.Dequeue(); // 8.선출과 동시에 값 출력
            Debug.Log(v + " ");

            //4.각 인덱스에 대한 인접 행렬 살펴보기
            for(int i = 1; i <= n; i++)
            {
                //5.인접 행렬을 아직 방문을 하지 않았고, 서로 연결된 정점이라면
                if (arr[v,i] == 1 && !c[i])
                {
                    //6.방문한다
                    q.Enqueue(i);
                    //7.방문 체크한다 
                    c[i] = true;
                }
            }
        }
    }