그래프_Graph

그래프(Graph)

그래프의 정의와 특징

• 정의
  • 그래프는 정점(vertex)와 그 정점을 연결하는 간선(Edge)으로 구성된다. 이러한 정점과 간선의 집합으로 이루어진 자료구조를 그래프라고 한다.

그래프 용어

• 정점(Vertex) : 노드(Node) 라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
• 간선(Edge) : 링크(Link) 라고도 하며 정점간의 관계를 나타낸다.
• 인접정점(Adjacent Vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다.
• 차수(Degree) : 정점에 연결된 간선의 수, 무방향 그래프에서 하나의 간선은 두개의 정점에 인접하기에 간선 수에 2배를 해주면 된다. 방향 그래프의 경우 외부에서 오는 간선의 수를 진입차수(in-degree)라고 하며, 외부로 향하는 간선의 수를 진출차수(out-degree)라고 한다.
• 경로(Path) : 간선을 따라 갈 수 있는 길, 정점을 나열하여 표시한다.
• 경로의 길이(Length) : 경로를 구성하는데 사용된 간선의 수
• 단순 경로(Simple Path) - 경로 중에서 반복되는 간선이 없는 경로
• 사이클(Cycle) : 시작 정점과 종료 정점이 같은 단순경로

특징

1. 방향성 : 그래프는 방향성이 있을 수도 있고, 없을 수도 있습니다. 방향성이 있는 그래프를 유향 그래프(Directed Graph), 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.
2. 가중치 : 간선에 가중치가 할당 되어 있을 수 있다. 이를 가중그래프(Weighted Graph)라고 한다. 네트워크(Network)라고 불리기도 한다.
3. 루프와 다중간선 : 그래프에는 자기자신으로 돌아오는 루프나 두 정점 사이에 여러 간선이 있을 수 있다.
4. 연결성 : 모든 정점이 어떤 경로로든 연결되어 있으면 연결그래프(Connected Graph)라고 한다.
5. 모든 정점간에 간선이 존재하는 그래프를 완전그래프(Complete Graph)라고한다. 정점이 N이면 간선의 수는 N*(N-1)/2

• ‘arc’는 그래프 이론에서 주로 ‘간선(edge)’와 같은 의미로 사용되며, 보통 유향그래프(Directed Graph)에서 간선을 지칭할 때 사용된다. 즉, 유향 그래프에서는 시작 정점에서 끝 정점까지 방향성이 있는 연결선을 ‘arc’라고 부른다.
  • 간선 : 방향성이 없다.
  • Arc : 방향성이 있다. ‘A-B’ Arc와 ‘B-A’ Arc는 다르게 취급한다.

그래프 구현 - 인접행렬(Adjacency Matrix)

• 컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)을 사용하는 방법과 연결리스트(LinkedList)를 사용하는 방법이 있다.

인접행렬을 이용한 그래프 구현

• 그래프의 정점을 2차원 배열로 만든 것.
  • 정점의 개수가 n이라면 n*n 형태의 2차원 배열이 인접행렬로 사용된다.
  • 인접행렬에서 행과 열은 정점을 의미하며, 각각의 원소들은 정점간의 간선을 나타낸다.
• 무 방향 그래프는 대칭적 구조를 가진다.(두 개의 정점에서 간선이 동시에 연결되어 있기 때문이다.)
• 가중치 그래프 는 행렬에서 0과 1이 아니라 각 간선의 가중치 값이 저장된다. (이 경우 가중치가 0인 것과 간선이 없는것이 구별 되어야 한다.)
• 장점
  • 2차원 배열에 모든 정점들이 간선 정보가 있기 때문에, 두 정점을 연결하는 간선을 조회시키는 O(1) 시간복잡도로 가능하다.
  • 정점(i)의 차수를 구할때는 다음과 같이 인접행렬의 i번째 행을 모두 더하면 되므로 O(n)시간 복잡도를 가진다.
  • 구현이 비교적 간단하다.
• 단점
  • 간선의 수와 무관하게 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
  • 그래프의 모든 간선의 수를 알기 위해서는 인접행렬 전체를 확인 해야하므로 O(n²) 시간이 소요된다.

그래프 구현 -인접리스트(Adjacency List)

• 각 정점에 인접한 정점들은 연결리스트(Linked List)로 표현하는 방법
• 정점의 개수만큼 인접리스트가 존재하고, 각각의 인접리스트에는 인접한 정점 정보가 저장 되는것이다. 그래프는 각 인접리스트에 대한 헤드 포인터를 배열로 갖는다.
• 무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드를 추가해야한다.
• 장점
  • 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다. 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 시간이 소요된다.
• 단점
  • 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접리스트를 탐색해야하므로 정점 차수만큼의 시간이 필요하다. O(degee(v))
  • 구현이 비교적 어렵다.