160102P(토)

자료구조론 - Chapter 14

 

그래프(gragh)

다양한 모델이 적용할 수 있는 유연성 있는 자료구조

꼭지점(vertex) + 변(edge)

 

ex)

컴퓨터 네트워크

컴퓨터나 라우터 = vertex

잇는 선 = edge

 

전자 회로

회로의 접점 = vertex

전기 선 = edge

 

그래프의 유래

쾨니히스베르크 다리 문제

 

 

같은 다리를 2번 건너지 않으면서도 모든 다리를 건너는 방법

 

오일러 - 수학자

각 육지부분(A, B, C, D)을 하나의 vertex로, 다리(a, b, c, d, e, f, g)를 edge인 그래프로 표현

∴ 문제의 답을 찾는것이 불가능함을 증명

 

인접(adjacency)

두 꼭지점이 하나의 변으로 연결되어있는 경우 이 두 꼭지점을 인접 또는 이웃해 있다고 한다.

 

경로(path)

변들의 연결로서 두 꼭지점이 연결되어 있음을 나타낸다.

꼭지점의 나열로 표기

 

연결된 그래프(connected graph)

어떠한 그래프에서 그것을 끝점으로 하는 경로가 최소한 하나이상 존재하는 경우 연결되어 있다고 한다.

∴ 끊어지지 않은 그래프

 

방향있는 그래프(directed graph)

그래프의 각 변이 방향을 가지는 경우

 

Vertex 의 표현

class Vertex {

public String label;

public boolean visitFlag;

 

// 꼭지점의 고유번호

int id;                                

 

public Vertex(String l) {

label = l;

visitFlag = false;

id = -1;

}

 

public int getId() {

return id;

}

 

public void setId(int i) {

id = i;

}

 

public boolean isVisited() {

return visitFlag;

}

 

public void setVisited() {

visitFlag = true;

}

 

public void unsetVisited() {
    visitFlag = false;

}

}

 

Edge의 표현

1. 인접행렬(adjacency matrix)

행렬을 만들어서 사용하며 연결되어 있을 때는 1, 연결되어 있지 않은 경우에는 0

 

A    B    C

A    0     0    1

B    0     0    0

C    1     0    0

 

2. 인접리스트(adjacency list)

각 꼭지점은 자신의 연결리스트를 하나씩 가지게 된다.

여기에 자신이 연결된 꼭지점을 항목으로 삽입

 

방향없는 인접행렬 Graph

class Graph {

final int MAX = 50;

 

int adjMat[][];

 

// 그래프의 꼭지점들

Vertex vertice[];

 

// 현재 그래프에 연결된 꼭지점 수

int numOfVertice;

 

int isDirected;

 

public Graph() {

int i, j;

adjMat = new int[MAX][MAX];

vertice = new int[MAX];

 

numOfVertice = 0;

isDirected = 0;

 

 

// 인접행렬 0으로 초기화

for(i = 0; i < MAX; i++) {

for(j = 0; j < MAX; j++) {

adjMat[i][j] = 0;

}

}

}

 

public void addVertex(Vertex v) {

v.setId(numOfVertice);

vertice[numOfVertice] = v;

numOfVertice += 1;

}

 

public void addEdge(Vertex src, Vertex dst) {

adjMat[src.getId()][dst.getId()] = 1;

adjMat[dst.getId()][src.getId()] = 1;

}

}

 

그래프 탐색

그래프에서 원하는 값(Vertex)를 찾아내는 방법

그래프의 모든 꼭지점들을 하나씩 방문하여 값을 확인해야 하는데 꼭지점을 모두, 중복없이 탐색 할 수 있는가 에 대한 고민

 

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

스택을 이용하며 시작꼭지점을 방문했다고 표시한 뒤 스택에 주변 꼭지점을 push한다. 후에 꼭지점 하나를 pop하여 방문 여부를 표시하고 위와같은 과정을 계속 반복한다. 스택이 Empty되면 그래프를 모두 방문한 것

 

1. 스택에서 꼭지점을 하나 꺼내 온다. 스택에 아무것도 없으면 탐색을 종료한다.

2. 꺼내온 꼭지점으로 이동하고 방문했음을 표시

3. 현재 꼭지점에서 다른 꼭지점들을 찾아서 방문 표시가 없으면 스택에 넣는다.

4. 현재의 꼭지점에 연결 되어 있고 방문하지 않은 꼭지점들을 모두 스택에 넣고나면 단계 1로 돌아간다.

 

public void DFS(Vertex start) {

int i;

Stack S = new Stack();

S.insert(start);

Vertex current;

 

while(!S.isEmpty()) {

current = (Vertex) S.pop();

current = setVisited();

 

System.out.print(current.label + " ");

 

for(i = 0; i < numOfVertice; i++) {

if(adjMat[current.getId()][i] == 1 && !vertice[i].isVisited()) {

S.insert(vertice[i]);

}

}

}

System.out.println("\n");

}

 

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

큐를 이용하여 시작 꼭지점을 하나 선택하여 큐에 집어넣고 큐에서 꼭지점을 하나 뽑아 방문 했음을 표시하고 꼭지점과 연결된 다른 꼭지점 중에 방문하지 않은 꼭지점들을 큐에 넣고 다시 큐에서 꼭지점을 뽑아 앞의 과정 반복. 마찬가지로 큐가 Empty되면 그래프를 모두 방문한 것

 

1. 큐에서 꼭지점을 하나 꺼내온다. 큐에 아무것도 없으면 탐색을 종료한다.

2. 꺼내온 꼭지점으로 이동하고 방문 했음을 표시

3. 현재 꼭지점에 연결된 다른 꼭지점들을 찾아서 해당 꼭지점에 방문한 적이 없으면 큐에 집어넣는다.

4. 현재의 꼭지점에 연결되어있고 방문하지 않은 꼭지점들을 모두 큐에 넣고 나면 단계1로 돌아간다.

 

public void BFS(Vertex start) {

int i;

Queue Q = new Queue();

Q.insert(start);

Vertex current;

 

while(!Q.isEmpty()) {

current = (Vertex) Q.get();

current.setVisited();

 

System.out.print(current.label + " ");

 

for(i = 0; i < numOfVertice; i++) {

if(adjMat[current.getId()][i] == 1 && !vertice[i].isVisited()) {

Q.insert(vertice[i]);

}

}

}

System.out.print("\n");

}

 

위상정렬(topological sorting)

방향그래프(DAG)에서 각 꼭지점들을 연결하는 변들의 방향을 이용하여 그 방향의 순서대로 그래프를 정렬하는 방법

 

ex)

선수과목(prerequisite)

선수과목의 체계가 깨지지 않는 이상 자신이 원하는 순서로 과목을 수강할 수 있다.

 

1. 자신을 가리키는 변이없는 꼭지점을 찾는다.

DAG이므로 이는 보장된다

인접행렬의 경우 열이 모두 0인 꼭지점을 찾으면 된다.

 

2. 찾은 꼭지점을 출력하고 찾은 꼭지점과 그 꼭지점에서 출발하는 변들을 그래프에서 지운다.

3. 아직 그래프에 꼭지점이 남아있으면 단계1로 돌아가고, 남아잇지 않으면 위상정렬을 종료한다.

 

방향그래프의 인접행렬

행 - 변이 시작되는 곡지점

열 - 변이 가리키는 꼭지점

 

방향성을 고려한 인접행렬 그래프

class Graph {

final int MAX = 50;

 

int adjMat[][];

 

// 그래프의 꼭지점들

Vertex vertice[];

 

// 현재 그래프에 연결된 꼭지점 수

int numOfVertice;

 

int isDirected;

 

public Graph() {

int i, j;

adjMat = new int[MAX][MAX];

vertice = new int[MAX];

 

numOfVertice = 0;

isDirected = false;

 

 

// 인접행렬 0으로 초기화

for(i = 0; i < MAX; i++) {

for(j = 0; j < MAX; j++) {

adjMat[i][j] = 0;

}

}

}

 

public void setDirected() {

isDirected = true;

}

 

public void unsetDirected() {

isDirected = false;

}

 

public void addVertex(Vertex v) {

v.setId(numOfVertice);

vertice[numOfVertice] = v;

numOfVertice += 1;

}

 

public void addEdge(Vertex src, Vertex dst) {

adjMat[src.getId()][dst.getId()] = 1;

 

if(!isDirected()) {

adjMat[dst.getId()][src.getId()] = 1;

}

}

}

 

방향 그래프에서의 경로

같은 방향으로 연결된 꼭지점들의 집합

 

순환(cycle)

경로의 시작과 끝이 연결

 

DAG(Directed Acycle Graph)

방향 그래프 중에서 순환을 가지지 않는 그래프

위상정렬은 DAG를 기반으로 수행

 

각각의 꼭지점에서 DFS나 BFS의 탐색과정을 거쳐도 좋으나 Warshall의 알고리즘을 이용하면 꼭지점 집합을 쉽게 알아낼 수 있다.

∴ Warshall 알고리즘에 대해서 조사할 것

 

public Vertex pick() {

for(int i = 0; i < numOfVertice; i++) {

boolean flag = false;

 

if(vertice[i].isVisited()) {

continue;

}

 

for(int j = 0; j < numOfVertice; j++) {

if(!vertice[i].isVisited() && adjMat[j][i] != 0) {

flag = true;

}

}

 

if(flag == false) {

return vertice[i];

}

}

 

return null;

}

 

public void deleteVertex(Vertex v) {

int vertexId = v.getId();

 

v.setVisited();

 

for(int i = 0; i < numOfVertice; i++) {

adjMat[verticeId][i] = 0;

}

}

 

public void topoSorting() {

Vertex v;

 

v = pick();

 

while(v != null) {

System.out.print(v.label + " -> ");

 

deleteVertex(v);

 

v = pick();

}

 

System.out.print("done!");

}