그래프와 그 순회 알고리즘

이 섹션에서는 그래프 데이터 구조가 무엇인지, 그리고 이 구조의 탐색 알고리즘을 살펴보겠습니다.

그래프는 하나의 비선형 데이터 구조입니다. 그것은 일부 노드와 연결된 가장자리로 구성됩니다. 가장자리는 방향성이 있거나 방향이 없을 수 있습니다. 이 그래프는 G(V, E)로 나타낼 수 있습니다. 다음 그래프는 G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A )})

그래프에는 두 가지 유형의 탐색 알고리즘이 있습니다. 이를 너비 우선 탐색과 깊이 우선 탐색이라고 합니다.

BFS(Breadth First Search)

BFS(Breadth First Search) 탐색은 주어진 그래프의 모든 노드를 방문하는 데 사용되는 알고리즘입니다. 이 탐색 알고리즘에서는 하나의 노드를 선택한 다음 모든 인접 노드를 하나씩 방문합니다. 인접한 꼭짓점을 모두 완료한 후 더 이동하여 다른 꼭짓점을 확인하고 인접 꼭짓점을 다시 확인합니다.

알고리즘

bfs(vertices, start)
Input: The list of vertices, and the start vertex.
Output: Traverse all of the nodes, if the graph is connected.
Begin
   define an empty queue que
   at first mark all nodes status as unvisited
   add the start vertex into the que
   while que is not empty, do
      delete item from que and set to u
      display the vertex u
      for all vertices 1 adjacent with u, do
         if vertices[i] is unvisited, then
            mark vertices[i] as temporarily visited
            add v into the queue
         mark
      done
      mark u as completely visited
   done
End

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘입니다. 이 알고리즘에서는 하나의 시작 정점이 주어지며, 인접 정점이 발견되면 그 인접 정점으로 먼저 이동하고 같은 방식으로 순회를 시도합니다.

알고리즘

dfs(vertices, start)
Input: The list of all vertices, and the start node.
Output: Traverse all nodes in the graph.
Begin
   initially make the state to unvisited for all nodes
   push start into the stack
   while stack is not empty, do
      pop element from stack and set to u
      display the node u
      if u is not visited, then
         mark u as visited
         for all nodes i connected to u, do
            if ith vertex is unvisited, then
               push ith vertex into the stack
               mark ith vertex as visited
         done
   done
End