Graph에 대해 알아보도록 하겠습니다.

Graph란 node와 node를 연결하는 간선을 하나로 모아놓은 Data Structure를 말합니다.

  • 용어.
    Vertex(정점) : 노드(node)와 같습니다.
    Edge(간선) : 포인터와 같습니다.
    degree(차수) : 무방향 그래프에서 인접한 정점의 수
    in-degree(진입 차수) : 다른 정점에서 오는 간선의 개수
    out-degree(차출 차수) : 다른 정점으로 가는 간선의 개수

  • 특징
    네트워크 모델
    버텍스 사이에서 양쪽 방향으로 방향을 가질 수 있습니다.
    Root / Leaf / 부모 / 자식 등이 없습니다.

  • 종류
    무방향/방향 그래프 (Undirected/Directed Graph)
    무방향 그래프는 아래의 그림처럼 그래프에 화살표가 없습니다!
    그래서 각 간선은 양방향으로 갈 수 있습니다.
    반대로 방향 그래프는 아래 그림에서 한쪽으로 화살표가 추가됩니다.

Graph의 실제 사용 예시

지하철 노선도
최단 거리

Graph Data structure의 methods

addVertex()
addEdge()

Graph Data structure의 property

Graph 이미지

algorithm16-1 (1).png

Graph 구현 (이차원 배열을 사용 / 연결 리스트 사용)

pseudo code

- addVertex()
node객체를 생성자를 이용하여 만든다.

- addEdge()
연결할 node의 메모리 주소를 가리킨다.(양방향이든, 단방향이든)