[C#/COMMON] 너비 우선 탐색을 사용해 최단 경로 구하기

TestProject.zip

다운로드

▶ Graph.cs

using System;
using System.Collections.Generic;

namespace TestProject
{
    /// <summary>
    /// 그래프
    /// </summary>
    /// <typeparam name="T">항목 타입</typeparam>
    public class Graph<T>
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 이웃 딕셔너리 - AdjacencyDictionary

        /// <summary>
        /// 이웃 딕셔너리
        /// </summary>
        public Dictionary<T, HashSet<T>> AdjacencyDictionary { get; } = new Dictionary<T, HashSet<T>>();

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - Graph()

        /// <summary>
        /// 생성자
        /// </summary>
        public Graph()
        {
        }

        #endregion
        #region 생성자 - Graph(vertexEnumerable, edgeEnumerable)

        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="vertexEnumerable">정점 열거형</param>
        /// <param name="edgeEnumerable">엣지 열거형</param>
        public Graph(IEnumerable<T> vertexEnumerable, IEnumerable<Tuple<T,T>> edgeEnumerable)
        {
            foreach(T vertex in vertexEnumerable)
            {
                AddVertex(vertex);
            }

            foreach(Tuple<T, T> edge in edgeEnumerable)
            {
                AddEdge(edge);
            }
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 정점 추가하기 - AddVertex(vertex)

        /// <summary>
        /// 정점 추가하기
        /// </summary>
        /// <param name="vertex">정점</param>
        public void AddVertex(T vertex)
        {
            AdjacencyDictionary[vertex] = new HashSet<T>();
        }

        #endregion
        #region 엣지 추가하기 - AddEdge(edge)

        /// <summary>
        /// 엣지 추가하기
        /// </summary>
        /// <param name="edge">엣지</param>
        public void AddEdge(Tuple<T,T> edge)
        {
            if(AdjacencyDictionary.ContainsKey(edge.Item1) && AdjacencyDictionary.ContainsKey(edge.Item2))
            {
                AdjacencyDictionary[edge.Item1].Add(edge.Item2);
                AdjacencyDictionary[edge.Item2].Add(edge.Item1);
            }
        }

        #endregion
    }
}

 

728x90

 

▶ GraphHelper.cs

using System;
using System.Collections.Generic;

namespace TestProject
{
    /// <summary>
    /// 그래프 헬퍼
    /// </summary>
    public static class GraphHelper
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Static
        //////////////////////////////////////////////////////////////////////////////// Public

        #region 최단 경로 함수 구하기 - GetShortestPathFunction<T>(graph, startItem)

        /// <summary>
        /// 최단 경로 함수 구하기
        /// </summary>
        /// <typeparam name="T">항목 타입</typeparam>
        /// <param name="graph">그래프</param>
        /// <param name="startItem">시작 항목</param>
        /// <returns>최단 경로 함수</returns>
        public static Func<T, IEnumerable<T>> GetShortestPathFunction<T>(Graph<T> graph, T startItem)
        {
            Dictionary<T, T> previousDictionary = new Dictionary<T, T>();
        
            Queue<T> queue = new Queue<T>();

            queue.Enqueue(startItem);

            while(queue.Count > 0)
            {
                T vertex = queue.Dequeue();

                foreach(T neighborVertex in graph.AdjacencyDictionary[vertex])
                {
                    if(previousDictionary.ContainsKey(neighborVertex))
                    {
                        continue;
                    }
            
                    previousDictionary[neighborVertex] = vertex;

                    queue.Enqueue(neighborVertex);
                }
            }

            Func<T, IEnumerable<T>> shortestPathFunc = vertex => {

                List<T> path = new List<T>{};

                T currentVertex = vertex;

                while(!currentVertex.Equals(startItem))
                {
                    path.Add(currentVertex);

                    currentVertex = previousDictionary[currentVertex];
                };

                path.Add(startItem);

                path.Reverse();

                return path;
            };

            return shortestPathFunc;
        }

        #endregion
    }
}

 

300x250

 

▶ Program.cs

using System;
using System.Collections.Generic;

namespace TestProject
{
    /// <summary>
    /// 프로그램
    /// </summary>
    class Program
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Static
        //////////////////////////////////////////////////////////////////////////////// Private

        #region 프로그램 시작하기 - Main()

        /// <summary>
        /// 프로그램 시작하기
        /// </summary>
        private static void Main()
        {
            Console.Title = "너비 우선 탐색을 사용해 최단 경로 구하기";

            List<Student> vertexList = Student.GetList(10);

            List<Tuple<Student, Student>> edgeList = new List<Tuple<Student, Student>>
            {
                Tuple.Create(vertexList[0], vertexList[1]),
                Tuple.Create(vertexList[0], vertexList[2]),
                Tuple.Create(vertexList[1], vertexList[3]),
                Tuple.Create(vertexList[2], vertexList[4]),
                Tuple.Create(vertexList[2], vertexList[5]),
                Tuple.Create(vertexList[3], vertexList[6]),
                Tuple.Create(vertexList[4], vertexList[6]),
                Tuple.Create(vertexList[4], vertexList[7]),
                Tuple.Create(vertexList[4], vertexList[5]),
                Tuple.Create(vertexList[7], vertexList[8]),
                Tuple.Create(vertexList[8], vertexList[9])                
            };

            Graph<Student> graph = new Graph<Student>(vertexList, edgeList);

            Student startVertex = vertexList[0];

            Func<Student, IEnumerable<Student>> shortestPathFunc = GraphHelper.GetShortestPathFunction<Student>(graph, startVertex);

            foreach(Student vertex in vertexList)
            {
                Console.WriteLine("학번 : {0}, 성명 : {1}", vertex.ID, vertex.Name);

                IEnumerable<Student> visitEnumerable = shortestPathFunc(vertex);

                foreach(Student visitVertex in visitEnumerable)
                {
                    Console.WriteLine("    학번 : {0}, 성명 : {1}", visitVertex.ID, visitVertex.Name);
                }

                Console.WriteLine();
            }
        }

        #endregion
    }
}