�ݺ�ߣ

그래프와 그래프 알고리즘
(Graph & Graph Algorithm)
Wider planet Tech Talk
2015.10.22
조은우

그래프(Graph)란 무엇인가?
• 현상이나 사물들을 정점(Vertex)으로 표현하고,
정점들간에 관계를 간선(Edge)으로 표현한 것
• 도로 시스템
• 도시와 도시간의 항공편
• 트리(Tree)도 그래프의 한 종류

그래프 용어(1)
• 정점(Vertex)
: 정점, 꼭지점, 노드라고도 부르며, 그래프 알고리즘의 핵심
• 간선(Edge)
: 정점들 간의 관계를 나타냄.
간선이 방향을 가지면 유향 그래프(Directed Graph)
• 가중치(Weight)
: 한 정점에서 다른 정점으로 가는데 발생하는 비용
• 경로(Path)
: 간선으로 연결된 정점들을 순서대로 나열한 것
• 순환(Cycle)
: 유향 그래프에서 순환은 시작 정점과 마지막 정점이 같은 경로.
순환이 없는 그래프는 Acyclic graph.
유향그래프가 순환을 갖지 않으면 Directed acyclic graph

그래프 용어(2)
G = (V, E)
그래프 G는 N개의 정점의 집합 V와 간선들의 집합 E로 구성

코드로 추상화(ADT)한 그래프
• Graph 클래스: 비어있는 새 그래프 객체를 생성
• addVertex(vert): Vertex클래스의 인스턴스(vert)를 인자로
전달해서 그래프에 정점을 추가
• addEdge(fromVert, toVert, weight): 인접한 2개의 정점을
잇는 간선을 추가, 마지막 인자는 가중치(선택)
• getVertex(vertKey): vertKey 를 이름으로 갖는 정점을 찾음
• getVertices(): 그래프안에 있는 모든 정점들의 리스트를 반환

그래프의 표현
인접 행렬(Adjacency Matrix)
• 두개의 정점이 간선에 의해 서로
연결되어 있으면 인접하다
(adjacent)
• 정점v에서 정점w까지의 간선의 가
중치가 각 셀에 저장됨

그래프의 표현
인접 리스트(Adjacency List)
• 그래프의 모든 정점을 기준 리스트
로 유지하고, 각 정점들마다 인접
한 정점들을 리스트로 연결
• 인접행렬과 달리 존재하지 않는 간
선은 표현상에 나타나지 않음

인접 행렬(Adjacency Matrix)
장점
• 간단해서 이해하기 쉬우며, 간선의 존재여부를 즉각 알 수
있음
• 밀도가 아주 높은 그래프를 표현하기에 적합
단점
• 행렬을 준비하는 과정에서 정점의 개수(n)의 제곱만큼의 공
간과 시간이 필요함
• 밀도가 낮은 그래프는 빈 공간이 많이 생기기 때문에 적합
하지 않음

인접 리스트(Adjacency List)
장점
• 공간이 간선의 총 개수에 비례하는 양만큼만 필요하므로 낭비가 없음
• 밀도가 낮은 그래프를 표현하는데 적합
• 특정 정점을 기준으로 연결되어 있는 모든 간선을 쉽게 찾을 수 있음
단점
• 모든 정점에 간선이 존재하는 경우 리스트를 만드는데 많은 비용이
발생
• 정점들간에 간선의 유무를 확인하기 위해 리스트를 차례로 훓어야함

<?php
class Vertex
{
public function __construct($key)
{
$this->id = $key;
$this->connect_to = array();
}
public function addNeighbor($neighbor, $weight = 0)
{
$this->connect_to[$neighbor->getId()] = array('neighbor' => $neighbor, 'weight' =>
$weight);
}
public function getConnections()
{
return array_keys($this->connect_to);
}
public function getId()
{
return $this->id;
}
public function getWeight($neighbor)
{
return $this->connect_to[$neighbor->getId()]['weight'];
}
}
PHP 클래스로 정점의 인접 리스트 구현
4 5
3
6

단어 사다리 문제
(The Word Ladder Problem)
• ‘이상한 나라의 엘리스’의 작가 ‘루이스캐럴’
발명
• 시작 단어에서 도착 단어까지 한글자씩 바꿔
가면서 도달
• 각 단계마다 모두 의미가 있는 단어가 되어야
함

단어 사다리 그래프 만들기
• 각각의 단어들이 정점(Vertex)
• 무향 그래프(Undirected Graph)이며 가중치를 갖지 않음
• 한글자만 다른 두 단어는 서로 인접하여, 간선(Edge)으로 연결됨

단어 사다리 그래프 구현
1. 모든 정점들마다 다른 정점과 비교
• 단점: 비교하는 횟수는 단어 개수에 제곱
2. 단어의 한글자만 가린 라벨을 단 단어 버켓을 만들어 단어들
을 분류

단어 사다리 그래프 구현<?php
require_once('Graph.php');
function buildGraph($word_file)
{
$container = array();
$graph = new Graph();
$f = fopen($word_file, "r");
if ($f) {
while (($word = fgets($f)) !== false) {
$container = setBucketContainer(trim($word));
}
fclose($f);
} else {
throw new Exception('파일을 읽을 수 없습니다.');
}
$bucket_keys = array_keys($container);
foreach ($bucket_keys as $bucket) {
foreach ($container[$bucket] as $word1) {
foreach ($container[$bucket] as $word2) {
if ($word1 != $word2) {
$graph->addEdge($word1, $word2);
}
}
}
}
return $graph;
}

단어 사다리 그래프 구현(2)
function setBucketContainer($word)
{
$container = array();
$word_length = strlen($word);
for ($i = 0; $i < $word_length; $i++) {
$bucket = substr($word, 0, $i) . '_' . substr($word, $i + 1, ($word_length - 1) - $i);
if (array_key_exists($bucket, $container)) {
array_push($container[$bucket], $word);
} else {
$container[$bucket] = array($word);
}
}
return $container;
}

너비 우선 탐색
(Breath First Search)
• 탐색과정을 트리로 표현하면 이해하기 쉬움
• 루트(root)노드를 시작으로 같은 거리에 있는 자식 노드들을 탐색
• 부모 노드는 자식 노드들은 전임자(Predecessor)로 등록하고,
현재까지의 누적 거리를 저장

너비우선탐색(BFS) 구현function bfs($start_vertex)
{
$start_vertex->setDistance(0);
$start_vertex->setPredcessor(false);
$queue = array();
array_push($queue, $start_vertex);
while (count($queue) > 0) {
$current_vertext = array_shift($queue);
$neighbor = $current_vertext->getConnections();
foreach ($neighbor as $nbr_vertext) {
if ($nbr_vertext['neighbor']->getColor() == 'white') {
$nbr_vertext['neighbor']->setColor('gray');
$nbr_vertext['neighbor']->setDistance($current_vertext->getDistance() +
1);
$nbr_vertext['neighbor']->setPredecessor($current_vertext);
array_push($queue, $nbr_vertext['neighbor']);
}
}
$current_vertext->setColor('black');
}
}
bfs($word_radder->getVertex('fool'));

Github
$ git clone https://github.com/jonnung/word_ladder_graph

�ݺ�ߣ

그래프(Graph)와 그래프 알고리즘(단어사다리 문제 해결)

More Related Content

그래프(Graph)와 그래프 알고리즘(단어사다리 문제 해결)

Editor's Notes