0405 그래프의 탐색 ★★★★

깊이 우선 탐색 Depth First Search
너비 우선 탐색 Breath First Search


그래프는 트리와 다르게 여러 정점들이 무차별적으로 연결될 수 있으므로,
그래프의 탐색은 해당 정점을 이미 방문했는지를 체크하는 추가작업이 포함된다.
별도의 방문 테이블을 만들어 방문 노드들을 추가하거나,
클래스 방문 여부를 표시하는 속성을 추가한다.


깊이 우선 탐색 DFS
자식, 그 자식의 자식 등 계속 이동하여 깊은 노드부터 처리하는 방식
형제 노드를 방문하기 전 자식부터
모든 노드를 방문하면서 목표 노드를 검색하는 연산
재귀호출과 스택을 사용한 비재귀 호출


너비 우선 탐색 BFS
형제 노드부터 처리하는 방식
각 노드에서 자식 노드를 방문하기 전에 형제 노드를 먼저 방문한다.
모든 노드를 방문하는 연산

이진트리의 전위순회, 중위 순회, 후위 순회는 깊이 우선 순회
레벨 순서 순회는 너비 우선 순회

DFS 재귀함수로 구현

public class Graph
    {
        public List<Node> nodes;
        public Graph() 
        {
            this.nodes=new List<Node>();
        }
        //vertex 추가
        public void AddVertex(Node node) 
        {
            this.nodes.Add(node);
        }
        //method overloading
        public Node AddVertex(string data) 
        {
            var node = new Node(data);
            this.nodes.Add(node);
            return node;
        }
        //edge 추가
        public void AddEdge(Node from, Node to, int weight = 1) 
        {
            from.neighbors.Add(to);
            from.weight.Add(weight);
            to.neighbors.Add(from);
            to.weight.Add(weight);
        }
        public void DFS() 
        {
            //방문 여부를 표시하는 방문 테이블 해시셋 생성
            var hash = new HashSet<Node>();
            foreach (var node in this.nodes) 
            {
                //방문여부 확인
                if (!hash.Contains(node)) 
                {
                    //재귀호출
                    this.DFSRecursive(node, hash);
                }
            }
        }
        public void DFSRecursive(Node node, HashSet<Node> hash) 
        {
            Console.WriteLine("{0}", node.data);
            //방문 등록
            hash.Add(node);
            //인접노드 확인
            foreach (var adjNode in node.neighbors) 
            {
                if (!hash.Contains(adjNode)) 
                {
                    this.DFSRecursive(adjNode, hash);
                }
            }
        }
    }

public class Node
    {
        public string data;
        public List<Node> neighbors;
        public List<int> weight;
        public Node(string data)
        { 
            this.data = data;
            this.neighbors = new List<Node>();
            this.weight = new List<int>();
        }
    }

public class App
    {
        public App() 
        {
            Graph g = new Graph();
            var A = g.AddVertex("A");
            var B = g.AddVertex("B");
            var C = g.AddVertex("C");
            var D = g.AddVertex("D");
            var E = g.AddVertex("E");
            var F = g.AddVertex("F");
            var G = g.AddVertex("G");

            g.AddEdge(A, B);
            g.AddEdge(A, D);
            g.AddEdge(A, E);
            g.AddEdge(A, C);
            g.AddEdge(E, F);
            g.AddEdge(E, G);
            g.AddEdge(F, G);

            g.DFS();

        }
    }

 

 

 

DFS 스택으로 구현

public class Graph
    {
        public List<Node> nodes;
        public Graph() 
        {
            this.nodes=new List<Node>();
        }
        //vertex 추가
        public void AddVertex(Node node) 
        {
            this.nodes.Add(node);
        }
        //method overloading
        public Node AddVertex(string data) 
        {
            var node = new Node(data);
            this.nodes.Add(node);
            return node;
        }
        //edge 추가
        public void AddEdge(Node from, Node to, int weight = 1) 
        {
            from.neighbors.Add(to);
            from.weight.Add(weight);
            to.neighbors.Add(from);
            to.weight.Add(weight);
        }
        
        public void DFSIterative() 
        {
            //방문 여부를 넣어두는 테이블 생성
            var hash = new HashSet<Node>();
            //각 노드를 순회
            foreach (var node in this.nodes) 
            {
                if (!hash.Contains(node)) 
                {
                    this.DFSUsingStack(node, hash);
                }
            }
        }
        private void DFSUsingStack(Node node, HashSet<Node> hash)
        {
            //스택생성 
            var stack = new Stack<Node>();
            //노드 추가 
            stack.Push(node);

            while (stack.Count > 0)
            {

                //스택에서 꺼내고 
                var vertex = stack.Pop();

                //방문여부 확인하고 
                if (!hash.Contains(vertex))
                {
                    //출력 
                    Console.WriteLine("{0}", vertex.data);
                    //방문 등록 
                    hash.Add(vertex);
                }

                /*
                //방법 1
                foreach (var adjNode in vertex.neighbors)
                {
                    if (!hash.Contains(adjNode))
                    {
                        stack.Push(adjNode);
                    }
                }
                */

                //방법 2 
                var cnt = vertex.neighbors.Count;
                //꺼꾸로 인덱스  
                for (int i = cnt; i < cnt; i++)
                {
                    if (!hash.Contains(vertex.neighbors[i]))
                    {
                        stack.Push(vertex.neighbors[i]);
                    }
                }

            }
        }
    }

public class App
    {
        public App() 
        {
            Graph g = new Graph();
            var A = g.AddVertex("A");
            var B = g.AddVertex("B");
            var C = g.AddVertex("C");
            var D = g.AddVertex("D");
            var E = g.AddVertex("E");
            var F = g.AddVertex("F");
            var G = g.AddVertex("G");

            g.AddEdge(A, B);
            g.AddEdge(A, D);
            g.AddEdge(A, E);
            g.AddEdge(B, C);
            g.AddEdge(E, F);
            g.AddEdge(E, G);
            g.AddEdge(F, G);

            g.DFSIterative();

        }
    }

 

 

너비 우선 탐색 구현

public class Graph
    {
        public List<Node> nodes;
        public Graph()
        {
            this.nodes = new List<Node>();
        }
        //vertex 추가
        public void AddVertex(Node node)
        {
            this.nodes.Add(node);
        }
        //method overloading
        public Node AddVertex(string data)
        {
            var node = new Node(data);
            this.nodes.Add(node);
            return node;
        }
        //edge 추가
        public void AddEdge(Node from, Node to, int weight = 1)
        {
            from.neighbors.Add(to);
            from.weight.Add(weight);
            to.neighbors.Add(from);
            to.weight.Add(weight);
        }
        public void BFS() 
        {
            //테이블을 만든다
            var hash = new HashSet<Node>();
            //노드 순회
            foreach (var node in this.nodes) 
            {
                //방문하지 않은 노드라면
                if (!hash.Contains(node)) 
                {
                    //인접노드들을 queue에 넣고 꺼내서 방문되지 않는 노드를 출력
                    this.BFSImpl(node, hash);
                }
            }
        }
        private void BFSImpl(Node node, HashSet<Node> hash) 
        {
            //큐를 만든다
            var queue = new Queue<Node>();
            //큐에 넣는다.
            queue.Enqueue(node);
            //큐에 요소가 있다면 반복
            while (queue.Count > 0) 
            {
                //뺀다
                var vertex = queue.Dequeue();
                //방문 여부 체크
                if (!hash.Contains(vertex))
                {
                    Console.WriteLine("{0}", vertex.data);
                    //해시에 추가
                    hash.Add(vertex);
                }
                //vertex의 인접노드들을 확인한다
                foreach (var adjNode in vertex.neighbors) 
                {
                    if (!hash.Contains(adjNode)) 
                    {
                        queue.Enqueue(adjNode);
                    }
                }
                //방문하지 않은 노드를 큐에 넣는다
            }
            
        }
    }

public class App
    {
        public App() 
        {
            Graph g = new Graph();
            var A = g.AddVertex("A");
            var B = g.AddVertex("B");
            var C = g.AddVertex("C");
            var D = g.AddVertex("D");
            var E = g.AddVertex("E");
            var F = g.AddVertex("F");
            var G = g.AddVertex("G");

            g.AddEdge(A, B);
            g.AddEdge(A, D);
            g.AddEdge(A, E);
            g.AddEdge(B, C);
            g.AddEdge(E, F);
            g.AddEdge(E, G);
            g.AddEdge(F, G);

            g.BFS();

        }
    }