본문으로 건너뛰기

그래프

그래프는 유한한 정점, 노드 또는 점의 집합으로 구성됩니다. 방향이 없는 그래프의 경우 순서가 지정되지 않는 쌍의 정점으로, 방향이 있는 그래프의 경우는 순서가 지정된 쌍의 정점으로 구성됩니다.


용어설명​

  • Vertex: 노드
  • Edge: 노드 간의 연결
  • Weighted/Unweighted: 노드 간 거리에 할당된 값
  • Directed/Undirected: 노드 간 거리에 할당된 방향

사용처​

  • 소셜 네트워크
  • 위치, 지도
  • 라우팅 알고리즘
  • 시각적 계층
  • 파일시스템 최적화
  • 어느곳이든!

저장하는 방식​

Adjacency List (인접리스트)

  • Vertex 추가: O(1)
  • Edge 추가: O(1)
  • Vertex 삭제: O(V + E)
  • Edge 삭제: O(E)
  • 검색: O(V + E)
  • 공간복잡도: O(V + E)

Adjacency Matrix (인접행렬)

  • Vertex 추가: O(V^2)

  • Edge 추가: O(1)

  • Vertex 삭제: O(V^2)

  • Edge 삭제: O(1)

  • 검색: O(1)

  • 공간복잡도: O(V^2)

  • 인접리스트가 행렬보다 공간을 덜 차지 한다.

  • 인접리스트가 행렬보다 모든 간선을 순회할 때 빠르다.

  • 인접행렬이 리스트보다 특정 간선을 찾는데 더 빠르다.


DFS (깊이우선순회)​

(Recursive)

  1. 시작 노드를 하나 받는다.
  2. 종료 결과를 저장(마지막에 반환할)하는 리스트를 생성한다.
  3. 방문한 정점을 저장할 객체를 생성한다.
  4. 정접을 인자로 받는 helper 함수를 생성한다.
    1. 정점이 비어있으면 반환한다.
    2. 인자로 받은 정점을 방문 객체에 저장하고, 결과 리스트에 저장한다.
    3. 그 정점의 인접리스트에 있는 모든 값에 대해서 반복한다.
    4. 그 값들 중 방문되지 않는게 있다면, 그 정점으로 helper 함수를 재귀적으로 호출한다.
  5. 시작 정점으로 helper 함수를 실행한다.
  6. 결과 리스트를 반환한다.

(Interative)

  1. 시작 노드를 하나 받는다.
  2. 정점을 추적하도록 돕는 스택을 생성한다.
  3. 최종 결과를 저장하는 리스트를 생성한다.
  4. 방문한 노드를 저장할 객체를 생성한다.
  5. 시작 노드를 스택에 넣고 방문한 것으로 체크한다.
  6. 스택 안에 값이 있다면 아래를 반복한다.
    1. 스택에서 노드를 하나 꺼낸다.
    2. 방문하지 않은 노드라면 방문한 것으로 체크하고, 결과 리스트에 추가한다. 그리고 이웃 노드들을 스택에 넣는다.
  7. 결과를 반환한다.

BFS (넓이우선순회)​

  1. 시작 노드를 하나 받는다.
  2. 큐를 생성하고 시작 노드를 넣는다.
  3. 방문한 노드를 저장할 배열을 만든다.
  4. 방문한 노드를 저장할 객체를 만든다.
  5. 큐에 아무것도 없을 때까지 반복한다.
    1. 큐에서 노드하나를 꺼내서 방문한 노드 배열에 넣는다.
    2. 방문한 노드의 인접리스트의 각 노드에 대해서 반복한다.
      1. 해당 노드가 방문한 노드가 아니라면, 그 노드를 방문한 것으로 체크하고 큐에 넣는다..
  6. 루프가 종료되면 방문한 배열을 반환한다.