알고리즘 [그래프 기초]

🔎 그래프

그래프란 v(정점),e(간선)이 쌍을 이루는 데이터구조형태이다.

• v: 정점이라 불리는 노드의 집합
• e: 간선이라 불리는 정점쌍들의 집합

정점과 간선은 원소, 즉 정보를 저장

간선에 따른 그래프 유형

• 방향간선
  • 정점들의 순서쌍(u,v)
  • u: 시점(origin)
  • v: 종점(destination)
  • 예: 항공편(flight)
• 방향 그래프
  • 모든 간선이 방향간선인 그래프(항공편망)
• 무방향간선
  • 정점들의 무순쌍(u,v)
• 무방향 그래프
  • 무방향간선으로 이루어진 그래프(항로망)

용어

• 끝점: 정점U와 V는 a의 양끝점
• 부착간선: 간선 a,d,b는 v에 부착한다.
• 인접정점: U와V는 인접하다
• 차수 : x의 차수는 5다
• 병렬 간선: h,i는 병렬 간선
• 루프: j는 루프다.
• 경로(path): 정점과 간선의 교대열, 정점으로 시작하여 정점으로 끝나며 각 간선은 그 양끝점으로 시작하고 끝낸다.
  • 단순경로: 모든 정점과 간선이 유일한 경로
  • 비단순경로: 단순경로 반대개념
• 싸이클: 정점과 간선이 교대하는 원형열, 각 간선은 그 양끝점으로 시작하고 끝난다.
  • 단순싸이클: 모든 정점과 간선이 유일한 싸이클
  • 비단순싸이클: 단순싸이클의 반대개념

속성

• 각 간선은 두 번 세어진다
• 루프와 병렬 간선이 없는 무방향그래프의 상한은 n(n-1)/2 여기서 n은 정점수

부그래프

‘부’가 붙는다는 건 부분 집합을 의미한다.

그래프에서 일부만 취하거나 전체를 취한 그래프를 부그래프라고 부른다.

신장이란 모든 정점을 취한다는 뜻

• 신장부그래프: 모든 정점을 가지고 일부간선을 취한 그래프

연결성

• 모든 정점쌍에 대해 경로가 존재하면 “그래프가 연결되었다”라고 말한다.
• 그래프의 연결요소 -> 두개의 연결요소로 구성된 비연결그래프

밀집도

희소와 밀집

싸이클

• 자유트리: T는 연결되어 있으며 T에 싸이클이 존재하지 않다면 트리로 볼 수 있다.
• 숲: 싸이클이 없는 무방향 그래프
• 숲의 연결요소는 트리들이다.

신장

• 연결그래프의 신장트리: 신장부그래프에서 트리인것
• 신장트리는 그래프가 트리가 아닌한 유일하지 않다.
• 그래프의 신장숲: 신장 부그래프 가운데 숲인 것

그래프ADT 메서드

• 일반메서드
  • integer numVertices(): 그래프내에 모든 정점의 개수 리턴
  • integer numEdges(): 그래프내에 총 간선의 수를 리턴
  • iterator vertices(): 그래프내에 모든 정점을 리턴
  • iterator edges(): 그래프내에 총 간선을 리턴
• 접근메서드
  • vertex aVertex(): 아무 정점을 리턴(거의 정점의 맨앞을 리턴)
• 질의메서드
  • boolean isDirected(e): 이 간선이 방향간선인지 판단
• 반복메서드
  • iterator directedEdges(): 모든 방향간선리턴
  • iterator unDirectedEdges(): 모든 무방향간선리턴
• 갱신메서드
  • vertex insertVertex(o): 새로운 정점 추가
  • removeVertex(v): 정점삭제 명령
  • removeEdge(e): 간선삭제 명령

무방향그래프ADT 메서드

• 접근메서드
  • integer deg(v): 정점 v의 차수를 반환
  • vertex opposite(v,e): 해당 정점과 간선을 입력시 가르키는 방향의 정점 리턴
• 질의메서드
  • boolean areAdjacent(v,w): 정점두개가 인접한지 판단
• 반복메서드
  • iterator endVertices(e): 해당 간선의 양끝점을 리턴
  • iterator adjacentVertices(v): v에 인접한 정점을 리턴
  • iterator incidentEdges(v): v에 부착된 간선을 리턴
• 갱신메서드
  • edge insertEdge(v,w,o): 정점 v에서 w로 항목 o를 저장한 무방향간선을 삽입하고 반환

방향그래프ADT 메서드

• 접근메서드
  • vertex origin(e): 해당 간선의 출발지점 리턴
  • vertex destination(e): 해당 간선의 도착지점 리턴
  • integer inDegree(v): 해당 정점으로 들어오는 간선의 개수
  • integer outDegree(v): 해당 정점에서 나가는 간선의 개수
• 반복메서드
  • iterator inlncidentEdges(v): 해당 정점으로 들어오는 간선들 리턴
  • iterator outlncidentEdges(v): 해당 정점에서 나가는 간선들 리턴
  • iterator inAdjacentVertices(v):
  • iterator outAdjacentVertices(v):
• 갱신메서드
  • edge insertDirectedEdge(v,w,o): 정점 v에서 w로 항목 o를 저장한 방향간선을 삽입하고 반환
  • makeUndirected(e): 간선e를 무방향으로 전환
  • reverseDirection(e): 방향간선 e를 역행

그래프 구현

간선리스트 구조

• 정점리스트: 정점 노드들에 대한 포인터의 리스트
• 간선리스트: 간선 노드들에 대한 포인터의 리스트
• 정점 노드: 원소
• 간선 노드: 원소, 시작노드, 종점 노드

인접리스트 구조

간선리스트 구조 + α

• 각 정점에 대한 부착리스트존재
• 부착리스트: 각 정점의 부착간선들을 간선 노드에 대한 참조들의 리스트로 표시

인접행렬 구조

간선리스트 구조 + α

• 정점 개체에 대한 확장 -> 정점에 해당하는 정수 키
• 인접행렬 존재
  • m*n의 배열
  • 인접정점 쌍에 대응하는 간선노드들에 대한 참조
  • 비인접정점 쌍에 대한 null정보