■ 너비 우선 탐색을 사용해 최단 경로 구하기

----------------------------------------------------------------------------------------------------


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

    }

}

 

 

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

    }

}

 

 

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

    }

}

 

----------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker
TAG