14. Graph Basics

Graph

그래프란?

정점(V, vertex)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

= 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조

 

용어

• 정점(Vertex, V): 꼭짓점 (node라고도 부름)
• ex) 위 그래프에서 정점은 총 7개 0,1,2,3,4,5,6 이 있다.
• 간선(Edge, E): 꼭짓점 간의 관계, 꼭짓점을 연결하는 선 (link, branch라고도 부름)
• ex) 위 그래프에선 간선이 총 6개 [(0-1) ,(1-2), (1-3), (2-5), (2-6), (3-4)] 있다.
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• ex) 위 그래프에선 정점 1의 인접 정점은 정점 0, 2, 3이 있다.
• 정점의 차수(degree): 하나의 정점에 인접한 정점의 수
• ex) 위 그래프에서 정점 1의 degree는 3 이다. (정점 0, 2, 3)

 

• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• ex) 위 그래프에서 0부터 5까지 가는 경로 길이는 [(0-1), (1-3), (3-5)]를 거쳐가므로 3이다.
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• ex) 위 그래프에서 i != j 일때, 정점 i에서 정점 j까지 가는 최단 경로는 모두 단순경로이다.
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
• cf> 정점 i에서 다시 정점 i로 돌아올 수 있는 경로가 있을 때, cyclic 그래프라고 한다.

 

 

 

종류

• Acyclic vs Cyclic

ACyclic: Cycle을 하나도 포함하고 있는 않은 그래프

 

Cyclic: Cycle을 하나라도 포함하고 있는 그래프

 

• Undirected vs Directed

Undirected: 방향성이 없어 양방통행이 가능한 그래프

 

Directed: 방향성이 있어 일방통행만 가능한 그래프

 

 

• Unconnected vs Connected

Unconnected: 어느 정점 i에서 정점 j로의 경로가 하나도 없는 그래프

 

Connected: 어떤 정점에서 시작하더라도 다른 모든 정점으로 가는 경로가 모두 있는 그래프

 

• Complete

Complete: 모든 정점이 연결되어 있는 그래프.

V개의 정점이 있다면, E = V(V-1) / 2

 

• Sparse vs Dense

o Sparse: E < V² 인 그래프

o Dense: E >= V²인 그래프

기준이 대충 이렇다는 거고, 눈으로 보기에 빽빽해 보이면 Dense임. 아무튼 Dense임

 

• Weighted

o Weighted: 간선마다 가중치가 다른 그래프

o Unweighted: 모든 간선이 가중치가 같은 그래프

 

그래프의 표현

// graph.h
// a structure to represent an adjacency list node

typedef struct GNode *pGNode;
typedef struct GNode {
  int item;
  pGNode next; 
} GNode;

// a structure to represent a graph.
// a graph is an array of adjacency lists.
// size of will be V (number of vertices in graph)
typedef struct Graph *pGraph; 
typedef struct Graph {
  int V; // number of vertices in the graph 
  int E; // number of edges in the graph 
  pGNode adj; // an array of adjacency lists
} Graph;


pGNode newGNode(int item) {
  pGNode node = (pGNode)malloc(sizeof(GNode)); assert(node != NULL);
  node->item = item;
  node->next = NULL;
  return node;
}


pGraph newGraph(int V) {
  pGraph g = (pGraph) malloc(sizeof(Graph)); 
  assert(g != NULL) ;
  g->V = V;
  g->E = 0;
  
// create an array of adjacency list. size of array will be V 
  
  g->adj = (pGNode)malloc(V * sizeof(GNode)); 
  assert(g->adj != NULL);
  
// initialize each adjacency list as empty by making head as NULL;

 for (int i = 0; i < V; i++) {
  	g->adj[i].next = NULL; 
  	g->adj[i].item = i
 }
  return g; 

}


// add an edge to an undirected graph
 void addEdgeUniDirection(pGraph g, int v, int w) {
   // add an edge from v to w.
   // A new node is added to the adjacency list of v.
   // The node is added at the beginning
   
   pGNode node = newGNode(w);
   node->next = g->adj[v].next;
   g->adj[v].next = node;
 }

// add an edge to an undirected graph
void addEdge (pGraph g, int v, int w) {
  addEdgeUniDirection(g, v, w);
  addEdgeUnidirection(g, w, v);
}

 

 

 

1. 인접 리스트 (Adjacency List)

 

설계

우선 모든 정점에 대한 인접 리스트를 만든다. (여기선 A, B, C, D)

그리고 차례로 각 정점의 인접 정점을 차례로 저장한다. (가중치가 있다면, 가중치도 함께 저장할 수 있다.)

// 인접 리스트
A: (B,3), (D,1)
B: (A,3), (C,4), (D,2)
C: (B,4), (D,2)
D: (A,1), (B,2), (C,2)

cf> 무방향 그래프(Undirected Graph)에서 (a, b) 간선은 두 번 저장된다.

 

구현

자료 구조는 보통 linked list를 사용하지만, vector를 사용해도 무방

#include <iostream>
#include <vector>
#include <utility>
using namespace std;


int main() {
    int E, weight, V1, V2;
    vector< <pair <int, int> > adj;
    
    // E = edge의 수, V1, V2는 정점1, 2
 		cin >> E;
    for (int i = 0; i < E; i++) {
        cin >> V1 >> V2 >> weight;
        adj[V1].push_back(make_pair(V2, weight));
        adj[V2].push_back(make_pair(V1, weight));
  }
}

 

인접리스트의 장단점

• 장점
  • 실제 연결된 노드만 저장한다. 즉, 모든 vector원소 갯수의 합은 간선의 갯수이다.
  • 전체 정점 탐색시 시간복잡도는 O(E), 공간복잡도는 O(V+E)V개의 리스트에 실제 간선만큼의 원소가 들어있으므로 V+E
  • why? 전체 간선의 갯수(E)만 저장했으므로,
• 단점
  • 어떤 두 정점이 연결되어있나 확인하려면 인접리스트 한개를 모두 검사해야하므로 느리다.
  • 시간복잡도: O(V)

 

2. 인접 행렬 (Adjacency Matrix)

 

구현 설계

우선 모든 N개의 정점에 관하여 NxN의 행렬을 만든다.

그리고 정점 i번과 정점 j번이 연결되어 있다면 1 (가중치 그래프일 경우 Edge의 가중치), 연결되어 있지 않다면 0

cf> 무방향 그래프(Undirected Graph)에서 (i, i)를 기준으로 인접행렬은 대칭이다.

 

구현

자료구조는 2차원 배열을 사용한다.

#include <iostream>

using namespace std;

int main() {
    int E, weight, V1, V2;
    int adj_mat[100][100]
    
    // E = edge의 수, V1, V2는 정점1, 2
 	cin >> E;
    for (int i=0; i < E; i++) {
        cin >> V1 >> V2 >> weight;
        adj[V1][V2] = weight;
        adj[V2][V1] = weight;
  }
}

 

인접 행렬의 장단점

• 장점
  • 직관적이고 구현이 빠르다.
  • O(1)의 시간복잡도로 두 정점 V1, V2의 연결유무를 알 수 있다.
  • adj[V1][V2] > 0 이면 V1, V2는 연결되어있다.
• 단점
  • 어떤 정점에 연결된 모든 정점을 검색 할 때의 시간복잡도: O(V)
  why? adj[i][1] ~ adj[i][V]를 모두 탐색해야함
• 따라서 모든 정점에 대해 연결 유무를 탐색하려면 시간복잡도 O(V*V) = O(V²)

 

3. 인접행렬과 인접리스트의 결론

위 두 표현법의 장단점을 살펴본 결과 어느 것이 항상 좋다고는 말할 수 없다.

그렇다면 언제 무엇을 사용해야 할까?

	인접 행렬	인접 리스트
특정 정점 한 쌍의 연결 확인 시간복잡도	O(1)	O(V)
모든 정점에 대해 연결 확인 시간복잡도	O(V2)	O(E)
그래프를 저장하는데 사용되는 공간복잡도	O(V2)	O(V+E)

• E(간선의 수)가 V²에 비해 훨씬 적은 그래프일 경우(Sparse Graph): 인접 리스트
• E(간선의 수)가 V²에 비례하는 그래프일 경우(Dense Graph): 인접 행렬

 

Why?

E = V²라고 가정하면 (Dense Graph의 경우)

	인접 행렬	인접 리스트
특정 정점들의 연결 확인	O(1)	O(V)
정점 전체의 연결 확인	O(V2)	O(V2)
공간복잡도	O(V2)	O(V+V2)

가 되므로 인접 행렬이 더 효율적이기 때문이다.

반대로 E < V²이 된다면 인접 리스트가 더 효율적일 것이다.

 

 

Graph processing problems

Path. Is there a path between s and t ?

Shortest path. What is the shortest path between s and t ?

Cycle. Is there a cycle in the graph?

Euler tour. Is there a cycle that uses each edge exactly once?

Hamilton tour. Is there a cycle that uses each vertex exactly once.

Connectivity. Is there a way to connect all of the vertices?

MST. What is the best way to connect all of the vertices?

Biconnectivity. Is there a vertex whose removal disconnects the graph?

Planarity. Can you draw the graph in the plane with no crossing edges

Graph isomorphism. Do two adjacency lists represent the same graph?