Algorithm Study #6 (Graph Search)

jakeseo_me·2019년 3월 14일
1

java algorithm study

목록 보기
17/18

Search of Graph

  • There are two kinds of way to search graph
    - DFS and BFS
    - DFS
    - Depth First Search Algorithm
    - Search graph as deeply and many as it can
    - It uses Stack
    - BFS
    - Breadth First Search Algorithm
    - Search graph as broadly as it can
    - It uses Queue
    - When all edges' weight is 1
    - it becomes the algorithm for getting shortest distance
  • Purpose of graph search (DFS, BFS)
    - To visit all vertices once
  • Algorithm of DFS
    - by using stack, it goes as much as it can
    • when there is no way to go, it goes back to a previous vertex
      - example)
      • first, to check if this vertex is already visited
        • it's good to make array for remembering the vertex number it visited.
          - i ........... 1 2 3 4 5 6
          • check[i] 1 0 0 0 0 0
            • it is a first state. start point is 1 and it is not moving yet
              • when all of check array's value have value of 1, this algorithm will be over.

                - when graph's state is like this, it can move any direction (2 or 5).
                - but in this case, we will make this go to smaller number first.

                - so it went to number 2
          • and array will be like
            - i ........... 1 2 3 4 5 6
            - check[i] 1 1 0 0 0 0
            - vertex of this point : 2
          • order : 1 2
          • stack : 1 2

            - vertex of this point : 3
            - i ........... 1 2 3 4 5 6
            - check[i] 1 1 1 0 0 0
          • order : 1 2 3
          • stack : 1 2 3

            - vertex of this point : 4
            - i ........... 1 2 3 4 5 6
            - check[i] 1 1 1 1 0 0
          • order : 1 2 3 4
          • stack : 1 2 3 4

            - vertex of this point : 5
            - i ........... 1 2 3 4 5 6
            - check[i] 1 1 1 1 1 0
          • order : 1 2 3 4 5
          • stack : 1 2 3 4 5
          • in this case, it has to go back to go to vertex 6
            • by using stack, it can trace the number of vertices it has stopped by at
              • after popping stack it will go to vertex number 4

                - vertex of this point : 5
                - i ........... 1 2 3 4 5 6
                - check[i] 1 1 1 1 1 0
          • order : 1 2 3 4 5 6
          • stack : 1 2 3 4 6
            - it's all over now
            • once it over, people can know it's over but
              • stack goes popping one by one
              • after stack : 1 2 3 4
                - it can know that there is no vertex to go.
                - it is judged by checking if array 'check[i]'s value is 1 or 0
                - only if the value is 0, we can go to that number of vertex
                • it should pop the stack out
              • after stack : 1 2 3
              • after stack : 1 2
              • after stack : 1
              • after stack : empty
                - implement of DFS with Adjecency Matrix
    • time complexity = V * O(V) -> O(V^2)
    • implement of DFS with Adjacency List
    • time complexity = O(V + E)
  • Algorithm of BFS
    - by using queue, it puts all the vertices which it can go to into queue
    • when it puts vertices into queue, it should check that number of vertex is in queue

      - vertex of this point : 1
      - i ........... 1 2 3 4 5 6
      - check[i] 1 0 0 0 0 0
      - order : 1
      - queue : 1

      - vertex of this point : 1
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 0 0 1 0
      - order : 1 2 5
      - queue : 1 2 5

      - vertex of this point : 2
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 0 0 1 0
      - order : 1 2 5
      - queue : 2 5
      - in this case, it can't go to 5 because 5 has been already checked at this point.
      - so it saves only vertex number 3

      - vertex of this point : 2
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 0 1 0
      - order : 1 2 5 3
      - queue : 2 5 3

      - vertex of this point : 5
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 0 1 0
      - order : 1 2 5 3
      - queue : 5 3

      - vertex of this point : 5
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 1 1 0
      - order : 1 2 5 3 4
      - queue : 5 3 4

      - vertex of this point : 3
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 1 1 0
      - order : 1 2 5 3 4
      - queue : 3 4

      - vertex of this point : 4
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 1 1 0
      - order : 1 2 5 3 4
      - queue : 4

      - vertex of this point : 4
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 1 1 1
      - order : 1 2 5 3 4 6
      - queue : 4 6

      - vertex of this point : 6
      - i ........... 1 2 3 4 5 6
      - check[i] 1 1 1 1 1 1
      - order : 1 2 5 3 4 6
      - queue : 6
      - implement of BFS with Adjacency Matrix

Problem implementing DFS and BFS

  • boj.kr/1260
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.

0개의 댓글