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)
          void dfs(int x) { // implemented recursively
              check[x] = true;
              printf("%d ", x);
              for (int i=1; i<=n; i++) {
                  if (a[x][i] == 1 && check[i] == false) {
                      dfs(i);
                  }
              }
          }
      • implement of DFS with Adjacency List
      • time complexity = O(V + E)
          void dfs(int x) {
          	check[x] = true;
              printf("%d ", x);
          	for (int i=0; i<a[x].size(); i++) {
              	int y = a[x][i];
              	if (check[y] == false) {
                  	dfs(y); 
                  }
              }
          }
  • 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
      queue<int> q;
      check[1] = true; q.push(1);
      while(!q.empty()) {
      	int x = q.front(); q.pop();
      	printf("%d ", x);
      	for (int i=1; i<=n; i++) { // it's really similar to DFS, but DFS is implemented by recursive function
          	if (a[x][i] == 1 && check[i] == false) {
              	check[i] = true;
              	q.push(i);
              }
          }
        
      }
    • implemented of BFS with Adjacency List
      queue<int> q;
      check[1] = true; q.push(1);
      while (!q.empty()) {
      	int x = q.front(); q.pop();
      	printf("%d ", x);
      	for (int i=0; i<a[x].size(); i++) {
          	int y = a[x][i];
          	if (check[y] == false) {
              	check[y] = true; q.push(y);
              }
          }
      }

Problem implementing DFS and BFS

  • boj.kr/1260
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.StringTokenizer;

    public class Main {

        static boolean[] checkList;
        static int numOfVisitedVertices;
        static StringBuffer sb = new StringBuffer();

        public static void dfs(ArrayList<Integer>[] adjacentList, int startVertexNum, int numOfVertices){
            int currentVertexNum;
            for(int i=0; i<adjacentList[startVertexNum].size(); i++) {
                if(!checkList[adjacentList[startVertexNum].get(i)]) {
                    currentVertexNum = adjacentList[startVertexNum].get(i);
                    sb.append(currentVertexNum + " ");
                    checkList[currentVertexNum] = true;
                    numOfVisitedVertices++;
                    dfs(adjacentList, currentVertexNum, numOfVertices);
                }
            }
        }

        public static void bfs(ArrayList<Integer>[] adjacentList, int startVertexNum, int numOfVertices){

            LinkedList<Integer> queue = new LinkedList();
            queue.push(startVertexNum);

            while(!queue.isEmpty()){
                int currentVertexNum = queue.peekFirst();
                for(int i=0; i<adjacentList[currentVertexNum].size(); i++) {
                    int currentEdgeNum = adjacentList[currentVertexNum].get(i);
                    if(!checkList[currentEdgeNum]) {
                        queue.add(currentEdgeNum);
                        checkList[currentEdgeNum] = true;
                    }
                }

                sb.append(queue.poll() + " ");
            }
        }

        public static void main(String args[]) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());

            int numOfVertices = Integer.parseInt(st.nextToken());
            int numOfEdges = Integer.parseInt(st.nextToken());
            int startVertex = Integer.parseInt(st.nextToken());

            ArrayList<Integer>[] adjacentList = new ArrayList[numOfVertices + 1];

            for(int i=0; i<numOfEdges; i++){
                st = new StringTokenizer(br.readLine());

                int vNum = Integer.parseInt(st.nextToken());
                int eNum = Integer.parseInt(st.nextToken());

                if(adjacentList[vNum] == null) adjacentList[vNum] = new ArrayList();
                if(adjacentList[eNum] == null) adjacentList[eNum] = new ArrayList();

                adjacentList[vNum].add(eNum);
                adjacentList[eNum].add(vNum);
            }

            for(int i=1; i<=numOfVertices; i++)
                if(adjacentList[i] != null)
                    Collections.sort(adjacentList[i]);

            checkList = new boolean[numOfVertices + 1];
            checkList[startVertex] = true;
            numOfVisitedVertices = 1;
            sb.append(startVertex + " ");
            dfs(adjacentList, startVertex, numOfVertices);

            sb.append("\n");

            checkList = new boolean[numOfVertices + 1];
            checkList[startVertex] = true;
            bfs(adjacentList, startVertex, numOfVertices);

            System.out.print(sb);
        }
    }
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글