[자료구조 - Graph 와 DFS] Graph와 DFS란?

[Algorithm] 깊이 우선 탐색

 

목차

1. DFS란?

 

2. 그래프란?

• 그래프의 특징

• 그래프의 종류

• 그래프 용어

 

 

1. DFS란?

• 깊이 우선 탐색(Depth-First-search)은 그래프 완전 탐색 기법중 하나

• 그래프의 시작 노드에서 출발하여 탐색할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 분기 쪽으로 이동하여 탐색을 수행하는 알고리즘

• 트리의 완전 탐색에 사용된다.

• 깊이 우선탐색 특징

  기능	특징	시간 복잡도 (노드 -V, 엣지 - E)
  그래프 완전 탐색	- 재귀 함수로 구현 - 스택 자료구조 이용	O(V+E)

• DFS는 사실상 재귀함수문제와 다름없다.

• 재귀 함수를 이용하므로 스택오버플로에 유의해야 한다.

• DFS를 이용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

• DFS는 한 번 방문한 노드를 다시 방문 하지 않아야 하므로 노드 방문 여부를 체크할 배열이 필요하다.

• 그래프의 인접 리스트로 표현할 수 있다.

 

• DFS의 동작방식
  1. 시작할 노드를 정한 후 사용할 자료구조(인접리스트) 초기화 하기
   

2. 스택에서 노드를 꺼낸 후 노드의 인접 노드를 다시 스택에 삽입 
3. 스택 자료구조에 값이 없을 때까지 반복하기
   • 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.

 

 

2. 그래프란?

• 단순히 노드와 노드를 연결하는 간선을 하나로 모아놓은 비선형 자료구조

• 연결된 객체 간의 관계를 표현하는 자료구조

• 방향 그래프와 무방향 그래프로 나눌 수 있다.

https://velog.io/@sohi_5/algorithmDFS

• 무방향 그래프
  • 두 정점을 연결하는 간선에 방향이 없는 그래프
  • 정점 Vi,Vj를 연결하는 간선을 (Vi,Vj)로 표현한다.
  • V(노드) = {A,B,C,D} , E(엣지) = {{A,B},{A,D},{B,D},{B,C},{C,D}}

 

 

• 완전 그래프
  • 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프
  • 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2
  방향 그래프의 최대 간선 수는 n(n-1)
  
  

 

 

• 부분 그래프
  • 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프

 

• 가중 그래프
  • 정점을 연결하는 간선에 가중치를 할당한 그래프
  • 가중치를 weight라고 한다.
  
  
  • 행렬에 1이 아닌 가중치값을 적을 수 있다.
    
    
    
    
    

 

유향 비순환 그래프

• 방향 그래프에서 사이클이 없는 그래프연결 그래프
  • 떨어져 있는 정점이 없는 그래프

• 
  그래프 용어
  • 차수(Degree) : 정점에 부속되어 있는 간선의 수
    • 진입 차수 : 정점을 머리로 하는 간선의 수
    • 진출차수 : 정점을 꼬리로 하는 간선의 수
  • 경로: 정점 Vi~ Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
    • 한 번 지나간 경로를 다시 거치는 것은 경로라고 하지 않는다.
    • 단순 경로 : 모두 다른 정점으로 구성된 경로
  • 경로 길이 : 경로를 구성하는 간선의 수
  • 사이클 :
    • 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
    • 트리는 cycle이 존재하지 않는다.(부모와 자식 관계이기 떄문)

 

• 그래프의 표현 방법(인접성을 표현하기)
  • 인접행렬(adjacency matrix)
    • 메모리 낭비가 심하다.
    • 에지의 개수 이외에는 모두 0으로 표현되지 않기 때문
  • 인접리스트(adjacency list)
    • 인접행렬보다 효율적
    • 존재하는 에지만 추가하면 된다.