[자료구조] 그래프

시나브로·2021년 6월 22일
0

자료구조

목록 보기
5/6
post-thumbnail



개요



  • 차수(degree) : 정점에 연결된 간선의 수
  • 정점(vertex)
  • 간선(edge)



정의


  • 그래프 G : 2개의 집합 V와 E로 구성
    • V : 공집합이 아닌 정점(vertex)의 유한집합
    • E : 간선(edge)이라고 하는 정점 쌍들의 집합


  • 무방향 그래프
    • 간선을 나타내는 정점의 쌍에 순서 없음


  • 방향 그래프
    • 방향을 가지는 정점의 쌍<u, v>로 표시
      (u는 꼬리(tail), v는 머리(head))
    • <u,v>와 <v,u>는 서로 다른 간선



제한 사항


  • 자기 간선(self edge) 또는 자기 루프(self loop)가 없음

  • 동일 간선의 중복 없음 / 다중 그래프는 예외

  • 완전 그래프 : n개의 정점과 n(n-1)/2개의 간선을 가진 그래프



용어


  • 정점 u로부터 정점 v까지의 경로(path)
    • 그래프 G에서 (u,i1), (i1,i2), (i2,i3),... (ik,v)를 E(G)에 속한 간선들이라 할 때, 정점열 u, i1, i2, i3 .... v를 말함
  • 경로의 길이(length)
    • 경로상에 있는 간선의 수
  • 단순 경로(simple length)
    • 경로상에서 처음과 마지막을 제외한 모든 정점들이 서로 다름
  • 단순 방향 경로(simple directed path)
  • 사이클(cycle)
    • 처음과 마지막 정점이 같은 단순 경로

인접 리스트(Adjaceny Lists)


  • 인접행렬의 n행들을 n개의 체인으로 표현
  • n개의 정점, e개의 간선의 무방향 그래프
    • n개의 헤드노드, 2e개의 리스트 노드가 필요
  • 방향 그래프 : e개의 리스트 노드
  • 연결 리스트 노드의 순차적 저장 : 배열 node[]
    • node[i] = 정점 i에 대한 리스트 시작 지점
    • node[n] = n + 2e + 1
    • 정점 i와 인접한 정점
      • node[i], .... node[i+1]-1에 저장
  • 역인접리스트
    • 리스트가 표현하는 정점에 인접한 각 정점에 대해 하나의 노드

Ex)





인접다중리스트(Adjacency Multilists)


  • 간선(u,v)는 두 개의 엔트리로 표현
    : u를 위한 리스트, v를 위한 리스트에 나타남
  • 새로운 노드 구조




가중치 간선(Weighted Edges)


  • 그래프의 간선에 가중치 부여
  • 인접행렬 : 행렬 엔트리에 a[i][j]의 가중치 정보 저장
  • 인접리스트 : 노드 구조에 weight 필드를 추가
  • 네트워크 : 가중치 간선을 가진 그래프



그래프 기본 연산


  1. 출발 정점 v를 방문
  2. v에 인접하고 방문하지 않은 한 정점 w를 선택
  3. w를 시작점으로 다시 깊이 우선 탐색 시작
  4. 모든 인접 정점을 방문한 정점 u에 도달하면, 최근에 방문한 정점 중 아직 방문을 안한 정점 w와 인접하고 있는 정점으로 되돌아감
  5. 정점 w로부터 다시 깊이 우선 탐색 시작
  6. 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료

Ex)


DFS 분석

  • 탐색을 끝내는 시간 O(e)
  • v에 인접한 모든 정점을 찾는데 O(n)의 시간
  • 총 시간 O(n2)



  • 시작 정점 v를 방문
  • v에 인접한 모든 정점들을 방문
  • 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문

Ex)


BFS 분석

  • 전체 시간 O(n2)
  • 인접 리스트 표현 : 전체 비용 O(e)



연결요소


방문하지 않은 정점 v에 대해 DFS 또는 BFS를 반복 호출로 구함

  • 인접리스트로 표현 : 모든 연결요소들 생성 시간은 O(n+e)
  • 인접행렬로 표현 : O(n2)



최단경로와 이행적 폐쇄


단일 시발점/모든 종점 : 음이 아닌 간선 비용

  • 문제: 시발 정점 v에서부터 G의 모든 다른 정점까지의 최단경로를 구하는 것




참조

  • 고려대학교 김상곤 교수님 강의 중
profile
Be More!

0개의 댓글