그래프

• 그래프

  • 자료구조의 일종
  • 정점(node, vertex)
    • 주로 번호가 써있음
  • 간선(edge) : 정점 사이 연결
  • 그래프 G =(V,E)로 나타냄

• 그래프를 저장하는 방법

  • 인접 행렬
    • 정점 개수를 v라고 할때,
    • v 제곱 크기의 인차원 배열 이용
    • a[i][j]=1
      • i에서 j 로 가는 간선이 있으면
    • a[i][j]=0
      • i에서 j 로 가는 간선이 없으면
    • a[i][j] = w
      • i에서 j로의 간선 가중치가 w 이면
    • 없는 간선도 저장하기 때문에 자주 사용하지 않는 방법
    • 쉬운 문제 풀 때 주로 사용
  • 인접 리스트
    • 링크드 리스트를 이용해서 구현
    • a[i] = i와 연결된 정점이 링크드리스트 형태로 저장
    • a[1] : 2, 5
      • 1과 연결된 정점이 2, 5
    • 링크드 리스트는 구현하는데 시간이 오래걸림
      • 그래서, vector / arraylist로 함
    • 가중치가 있으면
      • 정점과 가중치를 같이 저장
      • a[1] : (2,2), (5,7)

• 그래프의 탐색

  • 목적 : 모든 정점을 한 번씩 방문

  • 깊이 우선 탐색 (DFS)

    • 최대한 깊숙히 많이 감
    • 스택 사용
    • 스택을 이용해서 갈수 있는 만큼 많이 가고
    • 갈 수 없으면 이전 정점으로 돌아감 (스택에서 pop해서)
    • check라는 배열이 필요함
      • 0 : 아직 방문 X
      • 1 : 방문 O
    • 갈 수 있는 정점이 여러개면
      • 번호가 작은 것부터
    • pop 계속하다가 스택이 비면 탐색 종료
    • 구현

    void dfs(int x){
    
    	//방문 했다고 체크
        check[x] = true;
        
        //a[x] : x와 연결된 정점들이 저장되어 있음
        for(int i=0; i<a[x].size; i++){
        
        	//x와 연결된 정점
            int y = a[x][i];
            
            //방문하지 않았으면 방문
            if(check[y] == false){
                dfs(y);
            }
        }
    }

    ​

  • 너비 우선 탐색 (BFS)

    • 최대한 넓게 가는 것
    • 큐 사용
    • 모든 가중치가 1이면 최단 거리 찾는 알고리즘
    • 큐를 이용해서 아직 방문하지 않았고, 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
    • 큐에 넣을 때 방문했다고 체크
    • check라는 배열이 필요함
      • 0 : 아직 방문 X
      • 1 : 방문 O
    • 구현

    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);
            }
        }
    }

    ​