[자료구조] Graph - 그래프 탐색 방법

자료구조 07 - 2 / Graph 

---

탐색방법

 

너비 우선 탐색 (Breadth First Search: BFS)

 

최단경로, 임의의 한 정점에서 연결된 모든 정점으로 나가감, Tree의 LeveOrder Trabersal,

자료구조 Queue 사용(정점의 순서 기록)

시간복잡도 O(v+e) vertex 수 + edge 수 

 

깊이 우선 탐색 (Depth First Search: DFS) 

 

임의의 한 정점으로부터 연결된 한 정점으로만 나아간다, 연결된 정점이 없을때까지 방문하고 그 전 단계 정점으로 돌아서 다시 나아간다

자료구조 Stack 사용(방문했던 정점 기록)

시간 복잡도 O(v+e) vertex 수 + edge 수 

 

 

추가용어

완전 그래프(complete Graph) : 최대 간선 수를 가진 그래프, 모든 정점이 연결됨밀집 그래프(Dense Graph) : 간선의 수가 최대 간선의 수에 가까운 그래프희소 그래프(Sparse Graph) : 간선이 얼마 없는 그래프

 

구현

let graph = Graph()

let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")

graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeD)
graph.addEdge(nodeB, neighbor: nodeE)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeG)
graph.addEdge(nodeE, neighbor: nodeH)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeG)

BFS : Breath-First Search

// Swift 5
// https://github.com/raywenderlich/swift-algorithm-club/tree/master/Breadth-First%20Search
func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var queue = Queue<Node>()
  queue.enqueue(source)

  var nodesExplored = [source.label]
  source.visited = true

  while let node = queue.dequeue() {
    for edge in node.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        queue.enqueue(neighborNode)
        neighborNode.visited = true
        nodesExplored.append(neighborNode.label)
      }
    }
  }

  return nodesExplored
}

let nodesExplored = breadthFirstSearch(graph, source: nodeA)
print(nodesExplored)
// ["a", "b", "c", "d", "e", "f", "g", "h"]

DFS : Depth-First Search

 

// Swift 5
// https://github.com/raywenderlich/swift-algorithm-club/tree/master/Depth-First%20Search
func depthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var nodesExplored = [source.label]
  source.visited = true

  for edge in source.neighbors {
    if !edge.neighbor.visited {
      nodesExplored += depthFirstSearch(graph, source: edge.neighbor)
    }
  }
  return nodesExplored
}

let nodesExplored = depthFirstSearch(graph, source: nodeA)
print(nodesExplored)
// ["a", "b", "d", "e", "h", "f", "g", "c"]

추가적으로 생각해볼 내용

면접 예상질문

Q: BFS의 장점

A: 가중치 없는 그래프의 탐색에 유용 (Shortest Path)/ Minimum Spanning Tree 탐색시 유용

 

단점: 최단경로 보장 x

 

Q : DFS의 장점

A : 희소 그래프의 탐색에 유용, TopologicaSort 에 사용, 그래프의 edge 찾기등

 

단점: 인접 노드가 적은 경로로 깊이 빠지면 돌아오는데 오래걸림

 

Reference : raywenderlich.com github BFS DFS