자료구조 21.04.05. 수업내용
방문여부를 표시하는 방문테이블그래프의 탐색
ㄴ 정점들을 방문하여 목표 정점을 찾는것
ㄴ그래프 탐색은 그래프를 생성, 저장하는 것과 함께 그래프에서 가장 중요한 연산.
ㄴ노드를 방문하는 순서에 따라 깊이 우선탐색(Depth First Search) 과 너비 우선탐색(Breath First Search)이 있다.
깊이 우선탐색
ㄴ깊이우선탐색은 각 노드에서 형제 노드를 방문하기 전에 자식노드를 먼저 처리한다.
ㄴ자식노드 처리 순서는 먼저 생성한 자식노드순으로 처리한다.
그래프의 특수한 한 형태가 트리라고 했을 때, 이진트리의 전위순회, 중위순회, 후위순회는 깊이 우선순회 범주에 속하게 되며, 레벨순서순회는 너비 우선 순회에 속하게 된다. 깊이우선탐색은 엄격한 의미에서는 그래프의 모든 정점을 방문하면서 목표노드를 검색하는 연산.
깊이 우선 탐색은 크게 재귀호출을 사용하는 방법과 스택을 사용하여 비재귀호출방식으로 구현하는 방법이 있다.
그래프의 탐색이 트리의 순회와 다른 점은 그래프의 간선은 트리와 달리 부모-자식간의 링크 뿐만 아니라 여러 정점들이 무차별적으로 연결될 수 있다는 점이다. 따라서, *그래프의 탐색은 해당 정점을 이미 방문했는지를 체크하는 추가적인 작업이 포함되어야 한다. 보통 별도의 테이블을 만들어 방문 노드들을 추가하여 관리하거나 노드 클래스에 방문여부를 표시하는 속성을 추가하여 확인하는 방법 등이있다.
너비우선탐색은 트리의 레벨 순서 순회와 유사하게 각 레벨에 잇는 인접 노드들을 순차적으로 Queue에 넣은 후 이 Queue에서 노드를 꺼내 레벨 순서대로 노드를 방문하도록 구현한다. 방문한 노드들을 체크하는 방문테이블을 관리하면서 이미 방문하지 않은 노드만 출력하도록 한다.
너비 우선 탐색은 이렇게Queue를 통해 인접노드들 즉 형제노드들을 먼저 방문하게 된다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study801
{
public class Graph
{
public List<Node> nodes;
public Graph()
{
this.nodes = new List<Node>();
}
public void AddVertex(Node node)
{
this.nodes.Add(node);
}
public Node AddVertex(string data)
{
Node node = new Node(data);
this.nodes.Add(node);
return node;
}
public void AddEdge(Node from, Node to, int weight = 1)
{
from.neighbors.Add(to);
from.weights.Add(weight);
//양방향으로 만들 때
/*to.neighbors.Add(from);
to.weights.Add(weight);*/
}
public void DFS()
{
//방문 여부를 표시하는 방문 테이블 생성
var hash = new HashSet<Node>();
//각 노드를 꺼낸다
foreach (var node in this.nodes)
{
//방문여부 확인
if (!hash.Contains(node))
{
//재귀호출
this.DFSRecursive(node, hash);
}
}
}
private void DFSRecursive(Node node, HashSet<Node> hash)
{
//출력
Console.Write(" {0}", node.data);
//방문등록
hash.Add(node);
//인접노드 확인(Adjacent)
foreach (var adjNode in node.neighbors)
{
//방문하지 않았다면
if (!hash.Contains(node))
{
this.DFSRecursive(adjNode, hash);
}
}
}
private 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(vertex.data);
//방문 등록
hash.Add(vertex);
}
//방법 1
foreach (var adjNode in node.neighbors)
{
if (!hash.Contains(adjNode))
{
stack.Push(adjNode);
}
}
//방법2
var cnt = vertex.neighbors.Count;
//거꾸로 인덱스
for (int i = cnt - 1; i >= 0; i++)
{
if (!hash.Contains(vertex.neighbors[i]))
{
hash.Add(vertex.neighbors[i]);
}
}
}
}
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에 추가
hash.Add(vertex);
}
//vertex의 인접노드들을 확인
foreach(var adjNode in vertex.neighbors)
{
//방문하지 않았다면 Queue에 넣는다.
if (!hash.Contains(adjNode))
{
queue.Enqueue(adjNode);
}
}
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study801
{
public class Node
{
public string data;
public List<Node> neighbors; //인접노드들
public List<int> weights; //가중치
public Node(string data)
{
this.data = data;
this.neighbors = new List<Node>();
this.weights = new List<int>();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study801
{
public class App
{
//생성자
public App()
{
Console.WriteLine("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.DFS();
}
}
}