■ 깊이 우선 탐색하기 (Depth-First Search)

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


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.Collections.Generic;

 

namespace TestProject

{

    /// <summary>

    /// 그래프 헬퍼

    /// </summary>

    public static class GraphHelper

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Static

        //////////////////////////////////////////////////////////////////////////////// Public

 

        #region 깊이 우선 탐색하기 - DepthFirstSearch<T>(graph, startItem)

 

        /// <summary>

        /// 깊이 우선 탐색하기

        /// </summary>

        /// <typeparam name="T">항목 타입</typeparam>

        /// <param name="graph">그래프</param>

        /// <param name="startItem">시작 항목</param>

        /// <returns>깊이-우선 탐색 결과</returns>

        public static HashSet<T> DepthFirstSearch<T>(Graph<T> graph, T startItem)

        {

            HashSet<T> visitedVertexHashSet = new HashSet<T>();

 

            if(!graph.AdjacencyDictionary.ContainsKey(startItem))

            {

                return visitedVertexHashSet;

            }

                

            Stack<T> stack = new Stack<T>();

 

            stack.Push(startItem);

 

            while(stack.Count > 0)

            {

                T vertex = stack.Pop();

 

                if(visitedVertexHashSet.Contains(vertex))

                {

                    continue;

                }

 

                visitedVertexHashSet.Add(vertex);

 

                foreach(T neighborVertex in graph.AdjacencyDictionary[vertex])

                {

                    if(!visitedVertexHashSet.Contains(neighborVertex))

                    {

                        stack.Push(neighborVertex);

                    }

                }

            }

 

            return visitedVertexHashSet;

        }

 

        #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()

        {

            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);

 

            HashSet<Student> vertexHashSet = GraphHelper.DepthFirstSearch<Student>(graph, vertexList[0]);

 

            foreach(Student vertex in vertexHashSet)

            {

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

            }

        }

 

        #endregion

    }

}

 

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

Posted by 사용자 icodebroker
TAG

댓글을 달아 주세요