자료 구조 - 그래프

6 minute read

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

그래프(graph)

요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조
그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다.
정점은 노드(node)라고도 불리며 간선은 링크(link)라고도 불린다.

그래프의 종류

무방향 그래프(undirected graph)
- 간선에 방향이 표시되지 않은 그래프 즉, 하나의 간선은 양방향으로 갈수 있는 길을 의미한다.
방향 그래프(directed graph)
- 간선에 방향성이 존재하는 그래프. 한쪽 방향으로만 갈 수 있음을 의미한다.
가중치 그래프(weighted graph)
- 간선에 비용이나 가중치가 할당된 그래프. 네트워크(network)라고도 한다.
부분 그래프(subgraph)
- 그래프를 구성하는 정점의 집합과 간선의 집합의 부분 집합으로 이루어진 그래프.

그래프의 용어

인접 정점(adjacent vertex)
- 간선에 의해 직접 연결된 정점
정점의 차수(degree)
- 해당 정점에 연결된 간선의 수. 무방향 그래프에서는 정점에 인접한 정점의 수가 되겠죠.
- 방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(in-degree)라고 하고, 외부로 향하는 간선의 수를 진출 차수(out-degree)라고 한다.
경로(path)
- 간선을 따라 갈 수 있는 길을 말하며, 정점의 나열로 표시된다.
경로의 길이
- 경로를 구성하는데 사용된 간선의 수
단순 경로(simple path)와 사이클(cycle)
- 경로 중에서 반복되는 간선이 없는 경로를 단순 경로라고 한다.
- 단순 경로의 시작 정점과 종료 정점이 같다면 해당 경로를 사이클이라고 한다.
연결 그래프(connected graph)
- 모든 정점들 사이에 경로가 존재하는 그래프
- 반대는 비연결 그래프
트리(Tree)
- 사이클을 가지지 않는 연결 그래프
완전 그래프(complete grpah)
- 모든 정점 간에 간선이 존재하는 그래프

그래프의 추상 자료형

데이터: 정점의 집합과 간선의 집합
연산:
 - create(): 그래프를 생성
 - isEmpty(): 그래프가 공백 상태인지 확인
 - insertVertex(v): 그래프에 정점 v를 삽입
 - insertEdge(u,v): 그래프에 간선 (u,v)를 삽입
 - deleteVertex(v): 그래프의 정점 v를 삭제
 - deleteEdge(u,v): 그래프의 간선 (u,v)를 삭제
 - adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반환

정점이 삭제되면 그와 연결된 모든 간선도 함께 삭제되어야 하는 것에 유의해야 한다.

그래프의 표현

배열을 사용하는 인접행렬과 연결 리스트를 사용하는 인접 리스트 두 방식이 있다.

인접 행렬(adjacentcy matrix) 이용

정점의 개수가 n 이라면 $n*n$의 2차원 배열을 이용한다.

간선 (i, j)가 존재한다면, M[i][j] = 1,

그러지 않으면 M[i][j] = 0

무방향 그래프의 경우, 배열의 상위 삼각이나 하위 삼각만 저장하여 메모리 절약할 수도 있다. 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 $n^2$번의 조사가 필요해서, 시간 복잡도는 $O(n^2)$이다.

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

데이터 필드: 먼저 데이터 필드에는 그래프의 크기(정점의 개수) 정보와 인접 행렬 정보가 있어야 한다. size는 그래프의 크기를 나타내고, 이차원 배열 adj는 인접 행렬을 표현한다. vertices는 정점의 정보를 나타낸다.
멤버 함수(메소드): 삭제 연산은 매개변수로 int를 받아 v번째 정점을 제거한다. insertEdge(), deleteEdge(), adjacent() 연산도 정점의 인덱스를 매개변수로 전달한다.

#include <cstdio>
#define MAX_VTXS 256

class AdjMatGraph {
protected:
  int size; // 정점의 크기
  char vcertices[MAX_VTXS]; // 정점의 이름
  int adj[MAX_VTXS][MAX_VTXS]; // 인접 행렬
public:
  AdjMatGraph() { reset(); } // 그래프 초기화
  char getVertex(int i) { return vertices[i]; } // 특정 인덱스의 정점 반환
  int getEdge(int i, int j) { return adj[i][j]; }
  void setEdge(int i, int j, int val) { adj[i][j] = val; }

  bool isEmpty() { return size==0; }
  bool isFull() { return size==MAX_VTXS; }

  void reset() {
    size = 0;
    for(int i=0; i<MAX_VTXS; i++) {
      for(int j=0; j<MAX_VTXS; j++) {
        setEdge[i][j] = 0;
      }
    }
  }

  // 
  void insertVertex( char name ) {
    if( !isFull() ) {
      vertices[size++] = name;
    } else {
      printf("The graph is full");
    }
  } 

  // 무방향 그래프의 경우이다.
  // 방향, 가중치 그래프에서는 수정해주기
  void insertEdge(int u, int v) {
    setEdge(u, v, 1);
    setEdge(v, u, 1);
  }

  void display() { ... }
};

인접 리스트(adjacency list)를 이용한 그래프의 표현

인접 리스트는 그래프의 각 정점에 인접한 정점들을 연결 리스트로 표현하는 방법이다.
연결 리스트의 노드들은 인접 정점 정보를 저장하는데, 그래프는 이러한 각 인접 리스트에 대한 헤더 포인터를 배열로 갖는다.
따라서 정점의 번호만 알면 각 정점의 연결 리스트에 쉽게 접근할 수 있다.
n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로,
$O(n+e)$의 연산이 요구된다.
즉, 간선의 개수가 적은 그래프일수록 효율적이겠죠

인접 리스트를 이용한 그래프 클래스의 구현

인접 리스트 노드

class AdjacencyListNode
{
private:
	int data = -1;
	AdjacencyListNode* link = nullptr;
public:
	AdjacencyListNode(int value = -1, AdjacencyListNode* nextNode = nullptr) : 
			data(value), link(nextNode) {}
	~AdjacencyListNode();

	AdjacencyListNode* getLink() { return link; }
	void setLink(AdjacencyListNode* node);
	void display() { printf("%4d", data); }
	int getData() { return data; }
};

void AdjacencyListNode::setLink(AdjacencyListNode* node)
{
	if(link == nullptr) {
		link = node;
	} else {
		link->setLink(node);
	}
}

인접리스트 그래프

class AdjListGraph
{
private:
	AdjacencyListNode* graph[MAX_GRAPH_SIZE];
	int size = 0;
public:
	AdjListGraph() { size = 0; }
	~AdjListGraph() {}
	bool isEmpty() { return size == 0; }
	bool isFull() { return size == MAX_GRAPH_SIZE; }
	void insertVertex(int vertexData);
	void insertEdge(int u, int v);
	void display();
};

void AdjListGraph::insertVertex(int vertexData)
{
	if(isFull()) {
		printf("graph is full");
		return;
	}
	AdjacencyListNode* node = new AdjacencyListNode(vertexData);
	graph[size++] = node;
}

void AdjListGraph::insertEdge(int u, int v)
{
	for(int i=0; i<size; ++i) {
		if(graph[i]->getData() == u) {
			AdjacencyListNode* node = new AdjacencyListNode(v);
			graph[i]->setLink(node);
			break;
		}
	}
}

그래프의 탐색

하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다.
깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다.

깊이 우선 탐색(DFS, depth first search)

아직 방문하지 않은 인접 정점으로 탐색을 진행나가되,
현재 정점에서 더 이상 방문하지 않은 인접 정점이 없다면 가장 마지막에 만났던 정점으로 되돌아간다.

깊이 우선 탐색의 구현

방문 여부를 기록하기 위해 bool타입의 원소를 담는 visited 배열을 사용한다.

인접 행렬을 이용한 그래프의 너비 우선 탐색

// 앞서 만들었던 인접 행렬 그래프를 상속한다.
#include "AdjMatGraph.h"

class SrchAMGraph : public AdjMatGraph
{
  bool visited[MAX_VTXS]; // 정점의 방문 정보를 담는 배열
public:
  void resetVisited() {
    for(int i=0; i<size; i++) {
      visited[i] = false;
    }
  }

  // 두 정점이 인접해 있는 지 여부를 반환한다.
  bool isLinked(int u, int v) { return getEdge(u,v) != 0; }

  // 깊이 탐색 함수
  void DFS(int v) {
    visited[v] = true; // 방문.

    for(int w=0; w<size; w++) {
      if(isLinked(v, w) && visited[w] == false) {
        visited[w] = true;
        DFS(w); 
      }
    }
  }
};

연결 리스트를 이용한 그래프의 깊이 우선 탐색 (!해보기!)

너비 우선 탐색(BFS, breadth first search)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
큐가 사용되며, 큐가 공백이 될때까지 반복한다.

너비 우선 탐색의 구현

인접 행렬을 이용한 그래프의 너비 우선 탐색

// 마찬가지로 인접 행렬을 이용한 그래프를 상속한다
#include "AdjListGraph.h"
// 4장에서 만든 원형 배열을 이용한 큐를 상속한다.
#include "CircularQueue.h"

class SrchAMGraph : public AdjMatGraph{
  bool visited[MAX_VTXS];
public:
  void resetVisited() {
    for(int i=0; i<size; i++) {
      visited[i] = false;
    }
  }

  // 두 정점이 인접해 있는 지 여부를 반환한다.
  bool isLinked(int u, int v) { return getEdge(u,v) != 0; }

  void BFS(int v) {
    visited[v] = true;

    CircularQueue que;
    que.enqueue(v);

    while(!que.empty()) {
      int v = que.deque();
      for(int w=0; w<size; w++) {
        if (isLinked(v, w) && visited[w] == false) {
          visited[w] = true;
          que.enqueue(w);
        }
      }
    }
  }
};

인접 리스트를 이용한 그래프의 너비 우선 탐색 (!해보기!)

연결 성분

연결 성분(connected component)이란 최대로 연결된 부분 그래프를 말한다.
각 부분 그래프를 다른 색깔(다른 int)로 색을 칠하며 찾아가면 된다.

인접 배열을 이용한 그래프의 연결 성분 탐색

// 이전의 인접 배열을 이용한 그래프의 깊이 우선 탐색을 상속한다
#include "SrchAMGraph.h"

class connectedComponentGraph : public SrchAMGraph {
  int label[MAX_VTXS]; // 정점의 색깔 필드 추가
public:
  void labelDFS(int v, int color) {
    visited[v] = true;
    label[v] = color;
    for (int w=0; w<size; w++) {
      if(isLinked(v, w) && visitied[w] == false) {
        labelDFS(w, color);
      }
    }
  }

  void findConnectedComponent() {
    int count = 0;
    for(int i=0; i<size; i++) {
      if(visited[i] == true) {
        labelDFS(i, ++count);
      }
    }
  }
};

신장 트리

신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리다.
트리이므로 사이클은 없어야 한다.
그러면 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다.
신장 트리는 여러개일 수 있다.
DFS나 BFS로 탐색하고 그 과정에서 사용된 간선들만 모으면 신장 트리를 만들 수 있다 !!

위상 정렬

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬(topological sort)이라고 한다.

진입 차수가 0인 정점을 선택하고,
선택된 정점과 여기에 연결된 모든 간선을 삭제한다.
삭제되는 간선과 연결된 남아 있는 정점들의 진입 차수를 변경한다.
반복하여 모든 정점이 삭제되면 알고리즘이 종료된다.
전체 과정에서 정점이 삭제되는 순서가 위상 순서(topological order)가 된다.

진입 차수 0인 정점이 여러 개 존재하면 어느 정점을 선택하여도 무방하다.
따라서 위상 정렬 결과는 여럿일 수 있다.
사이클이 있다면 모든 과목이 선수 과목을 가지므로 위상 정렬이 불가능하다.

Chocobubble

자료 구조 - 그래프

그래프(graph)

그래프의 종류

그래프의 용어

그래프의 추상 자료형

그래프의 표현

인접 행렬(adjacentcy matrix) 이용

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

인접 리스트(adjacency list)를 이용한 그래프의 표현

인접 리스트를 이용한 그래프 클래스의 구현

그래프의 탐색

깊이 우선 탐색(DFS, depth first search)

깊이 우선 탐색의 구현

인접 행렬을 이용한 그래프의 너비 우선 탐색

연결 리스트를 이용한 그래프의 깊이 우선 탐색 (!해보기!)

너비 우선 탐색(BFS, breadth first search)

너비 우선 탐색의 구현

인접 행렬을 이용한 그래프의 너비 우선 탐색

인접 리스트를 이용한 그래프의 너비 우선 탐색 (!해보기!)

연결 성분

인접 배열을 이용한 그래프의 연결 성분 탐색

신장 트리

위상 정렬

구현 (!해보기!)

Leave a comment

You may also enjoy

[Graphics] ImGUI

[Graphics] DirectX 개요

[Graphics] 수학

[Graphics] DirectXMath & glm