[C#/COMMON] 깊이 우선 탐색하기 (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
    }
}

 

728x90

 

▶ 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
    }
}

 

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()
        {
            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
    }
}