그래프 : Graph (1)

그래프 : Graph

• 자료구조로서 그래프 = 정점(Vertex) + 간선(Edge)
• 용어 정리
  • 간선(Edge) → (무방향 / 방향) + 가중치
    • 무방향(=양방향)
    • 방향 : 화살표 끝에 방향을 나타냄
    • 가중치
  • 정점의 차수(Degree)
    • deg(x) := 정점 x에 연결된 간선의 수
    • 모든 정점 차수의 합 = 간선 개수의 2배
      • 간선이 1 증가하면 차수의 합은 2 증가 한다.
• 그래프를 저장하는 방법

  	인접 행렬	인접 리스트
  A와 B를 잇는 간선 존재 여부	O(1)	O(min(deg(A),deg(B)))
  A와 연결된 모든 정점 확인	O(V)	O(deg(A))
  공간 복잡도	O(V^2)	O(E)

  • 인접 행렬 (Adjacency Matrix)
    • 2차원 행렬로 표현
    • O(V^2)만큼 공간 필요 → 구현하기 쉽지만 메모리 이슈가 있다
    • ex) A에서 B로 이동 가능? 가중치 얼마? → adj(A,B) 값 리턴 → O(1)
    • ex) 정점 A에서 갈 수 있는 정점들은? → O(V)
  • 인접 리스트 (Adjacency List)
    • A 정점에서 갈 수 있는 정점들을 인접 리스트에 담는다.
    • ArrayList<ArrayList> adj;
    • 총 O(E) 만큼의 공간 필요 = 모든 정점의 차수의 합과 동일
    • ex) A에서 B로 이동 가능? 가중치 얼마? → adj(A)에서 B 확인 → O(min(deg(A),deg(B))) <<양방향성 그래프일 경우>> → adj(A)에서 B 확인 → O(deg(A)) <<방향성 그래프일 경우>>
      
• 그래프에서의 탐색(Search)
  • 깊이 우선 탐색(Depth First Search)
    • 구현

      // x를 갈 수 있다는 걸 알고 방문한 상태
      static void dfs(int x){                   // -> 모든 정점이 x로 한번씩만 O(V) 
      		// x 방문
      		visit[x] = true;
      		
      		// x에서 갈 수 있는 곳들을 모두 방문
      		for(int y : x에서 갈 수 있는 점 들){       // -> 인접행렬 O(V) || 인접리스트 O(deg(x))
      				if(visit[y])     // visit[y]가 true면 이 y는 무시
      					continue;
      
      				// 아직 안가본 y라면 가보자
      				dfs(y);
      		}
      }

      • 인접 행렬 → O(V^2)
      • 인접 리스트 → O(deg(1) + deg(2) + … + deg(V)) = O(E)
• 너비 우선 탐색(Breath First Search)
  • 구현

    // start에서 시작해 갈 수 있는 정점 모두 탐색
    static void bfs(int start){
    		Queue<Integer> que = new LinkedList<>();
    		
    		//start는 방문 가능, que에 add
    			visit[start] = true;    // !!! start를 갈 수 있다고 표시
    		que.add(start);
    		while(!que.isEmpty()){  // 더 확인할 점이 없다면 정지
    				int x = que.poll(); // -> 모든 정점이 한번만 등장
    
    				for(int y : x에서 갈 수 있는 점들){
    						if(visit[y]) continue;   // x에서 y를 갈 수는 있지만 이미 탐색한 점이면 무시
    
    						// y를 갈 수 있으니까 que 추가하고 visit 추가
    						que.add(y);
    						visit[y] = true;
    				}
    		}
    }

  • 1️⃣ visit[]=true
    2️⃣ que.add()
    3️⃣ while(que is not empty)
    4️⃣ que.poll()
    5️⃣ y가 x에서 갈 수 있는 점들 순회하면서
    6️⃣ visit[] true 면 무시, 아니면 visit[]=true ,que.add()
  • Queue가 들고있는 자료의 의미
    • 방문 가능한 정점들을 찾을 때, queue에 해당 정점을 넣는다.
    • Queue에 정점이 남아있다면, 아직 방문 가능한 점이 남아있다. 탐색중이다.
    • Queue가 비어있다면, 시작점에서 갈 수 있는 모든 점들을 다 찾았다. || 탐색이 끝났다.
  • 탐색(Search) : 시작점에서 갈 수 있는 정점들은? 몇번의 이동은 모름 가중치가 적용되지 않을 때, BFS의 부가 효과를 이용한다면, 최소 이동 횟수도 계산 가능 → 갈 수 있냐만 하는게 아니라 몇개 필요하냐까지 해주는 BFS
    • dist[i] : S에서 i까지 갈 때 필요한 최소 간선 갯수, 불가하면 -1
    • “최소”, ”가장 빠른”