[자료구조] 그래프 순회와 BFS(너비 우선 탐색) C#

BFS(Breadth First Search 너비 우선 탐색)

 

BFS는 다음에 접근할 정점을 예약하며 예약이 가장 오래된 녀석 부터 순회를 하는 방법으로 

Queue를 사용하여 사용한다. 

 

BFS는 대표적으로 최단거리 길찾기에서 사용한다. (가중치가 있다면 사용에 부적절하다.)

BFS는 가중치가 동일하다는 가정하에 진행하게 된다.

BFS(Breadth First Search 

전체 연결 그래프

2차 배열 사용

    class Program
    {
        static void Main(string[] args)
        {
            int[,] adj = new int[6, 6]
            {
                { 0, 1, 0, 1, 0, 0},
                { 1, 0, 1, 1, 0, 0},
                { 0, 1, 0, 0, 0, 0},
                { 1, 1, 0, 0, 1, 0},
                { 0, 0, 0, 1, 0, 1},
                { 0, 0, 0, 0, 1, 0},
            };

            BFS bfs = new BFS();
            bfs.Initurlize(adj);
            var resault = bfs.Search(0);

            foreach (var dic in resault)
            {
                foreach (var value in dic.Value)
                    Console.WriteLine($"{dic.Key} - {value}");
            }
        }
    }
    public class BFS
    {
        int[,] _graph;
        public void Initurlize(int[,] graph)
        {
            _graph = graph;
        }

        public Dictionary<string, int[]> Search(int start)
        {
            if (_graph == null)
                return null;

            int num = _graph.GetLength(0);//정점 총수

            Queue<int> queue = new Queue<int>();
            bool[] found = new bool[num];//경유 유무
            List<int> sequence = new List<int>();//경유 순서
            int[] parent = new int[num];//정점의 부모
            int[] distance = new int[num];//start정점과 각 정점사이거리

            queue.Enqueue(start);
            found[start] = true;
            parent[start] = start;
            distance[start] = 0;

            while (queue.Count > 0)
            {
                int now = queue.Dequeue();
                sequence.Add(now);

                for (int next = 0; next < num; next++)
                {
                    if (_graph[now, next] == 0)
                        continue;

                    if (found[next])
                        continue;

                    queue.Enqueue(next);
                    found[next] = true;
                    parent[next] = now;
                    distance[next] = distance[now] + 1;
                }
            }

            Dictionary<string, int[]> answer = new Dictionary<string, int[]>()
            {
                {"sequence",sequence.ToArray() },
                {"parent",parent },
                {"distance",distance },
            };

            return answer;
        }
    }

List 사용