그래프 정의

요즘은 인터넷에서도 버스와 지하철의 노선도를 확인할 수 있다. 뿐만 아니라 출발지와 목적지를 정하면, 그에 맞는 최적의 경로를 알 수도 있다. 이러한 프로그램의 구현에 사용되는 것이 바로 그래프 알고리즘이다.
그래프 알고리즘은 수학자 오일러에 의해 고안되었다. 오일러는 1736년도에 그 유명한 ‘쾨니히스베르크의 다리 문제’를 풀기 위해서 그래프 이론을 사용하였다고 한다.
그래프는 트리보다 복잡하다. 자식이 딸린 노드로 구성된다는 점에서는 트리와 같다. 하지만 트리와 달리 한 노드에 부모가 여럿 있을 수 있어서 루프가 만들어질 수 있다는 점이 다르다.
그리고 노드 자체가 아닌 노드 사이의 링크에도 값 또는 가중치가 있을 수 있다. 이렇게 다른 노드를 가리키는 기능 외에 별도의 정보를 담을 수 있는 링크를 에지^edge라고 부른다.

그래프 종류와 용어

에지에는 단방향 에지와 양방향 에지가 있으며, 단방향 에지가 들어 있는 그래프는 방향성 그래프^{directed graph}라고 부른다.
양방향 에지만 들어 있는 그래프는 무방향성 그래프^{undirected graph}라고 부른다.

무방향 그래프, 방향성 그래프

• 무방향 그래프(Undirected Graph)
  • 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
  • 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
    (A, B)는 (B, A) 동일 Ex) 양방향 통행 도로
• 방향 그래프(Directed Graph)
  • 간선에 방향성이 존재하는 그래프
  • A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.

  <A, B>는 <B, A>는 다름 Ex) 일방 통행
  
  

가중치 그래프

• 가중치 그래프(Weighted Graph)
  • 간선에 비용이나 가중치가 할당된 그래프
  • ‘네트워크(Network)’ 라고도 한다.
    Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등
    
    

연결 그래프 VS 비연결 그래프

• 연결 그래프(Connected Graph)
  • 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
    Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
• 비연결 그래프(Disconnected Graph)
  • 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
    
    

사이클 VS 비순환 그래프

• 사이클(Cycle)
  • 단순 경로의 시작 정점과 종료 정점이 동일한 경우
    • 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
• 비순환 그래프(Acyclic Graph)
  • 사이클이 없는 그래프
    
    

완전 그래프

• 완전 그래프(Complete Graph)
  • 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프
  • 정점 수: n이면 간선의 수: n * (n-1) / 2
    
    
    

그래프 구현방법

• 간선 리스트
  • 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아니고서야 많이 사용되지는 않는다.
• 인접 행렬 기반 그래프
  • 정점이 N개라면 NxN행렬을 만들어서 각각에 연결된 모든 간선들을 표시한다. 장점은 어떠한 두 정점이 연결되어 있는지를 확인한다 던지 할 경우 2차원 배열에서 탐색하기 때문에 인덱스로 상수시간 탐색이 가능하다는것. 단점은 간선의 수가 적던 많던 무조건 NxN의 공간을 사용하기 때문에 특히 정점에 비해 간선의 수가 적은 경우 매우 비효율적이라고 할 수 있다.
• 인접 리스트 기반 그래프
  • 가장 많이 사용되는 그래프 표현 방식 먼저 1차원 배열을 생성하고 배열의 요소로, 각 배열 인덱스가 사용하는 간선의 정보를 동적배열로 생성하여 저장한다.
    
    

참조

• 윤성우의 열혈 C 자료구조
• 프로그래밍 면접, 이렇게 준비한다.
• HeeJeong Kwon Blog
• wan088.log