151225P(금)

자료구조론 - Chapter 15

 

가중치 그래프(weighted graph)

그래프의 변에 가중치(weight)를 부여한 그래프

 

가중치(weight)

한 꼭지점에서 다른 꼭지점 사이를 이동하기 위해 소요되는 비용(cost)

두 꼭지점 사이의 거리와 같이 변이 내포할 수 있는 수치

 

구현하기 위해서는 인접 행렬과 인접 리스트 사용 가능

인접 행렬이 구현하기 더 쉽다.

 

 

연결되지 않았음을 표시하기 위해

∞를 사용한다.

 

그래프에 변 추가

public void addEdge(Vertex src, Vertex dst) {

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

 

// 방향그래프가 아니므로 반대쪽도 연결

if(!isDirected) {

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

}

}

 

getId() : 꼭지점(Vertex)의 번호 반환

isDirected : 방향없는 그래프 0, 방향 그래프 1

 

 

class AdjListItem {

Vertex vertexItem;

int weight;

AdjListItem next;

 

public AdjListItem(AdjListItem prev, Vertex v, int w) {

next = null;

vertextItem = v;

weight = w;

 

if(prev != null) {

prev.setNext(this);

}

}

 

public void setNext(AdjListItem item) {

next = item;

}

}

 

최소 신장 트리(minimum spaning tree)

1. 가중치를 이용한 최소 신장 트리

2. 가중치가 없는 그래프의 최소 신장 트리

 

그래프의 부분집합의 개념

모든 꼭지점을 연결 할 수 있도록 원래 그래프 중에서 가중치가 최소인 변만을 선택하여 구성한 그래프

E(최소 변의 개수) = V(꼭지점의 총 개수) - 1

그래프의 탐색 과정과 비슷(BFS, DFS)

 

DFS

하나의 꼭지점에서 연결된 다른 꼭지점을 찾는 과정을 반복적으로 수행하다가 모든 꼭지점을 방문하게 되면 지금까지 지나온 변들이 모든 꼭지점을 연결하는 최소 개수의 변들이 된다.

따라서 최소 신장 트리를 구성 할 수 있다.

 

가중치가 없는 그래프에서 DFS를 기반으로 하는 최소신장 트리

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 siVisited() {

return visitFlag;

}

 

public void setVisited() {

visitFlag = true;

}

 

public void unsetVisited() {

visitFlag = false;

}

}

 

class Graph {

fanal int MAX = 50;

 

int adjMat[][];

Vertex vertice[];

public int numOfVertice;

 

boolean isDirected;

 

public Graph() {

int i, j;

adjMat = new int[MAX][MAX];

vertice = new Vertex[Max];

 

numOfVertice = 0;

isDirected = false;

 

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

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

adjMat[i][j] = 0;

}

}

}

 

public Vertex getVertex(int i) {

return vertice[i];

}

 

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;

}

}

 

public void setDirected() {

isDirected = true;

}

 

public void unsetDirected() {

isDirected = false;

}

 

public void MST(Vertex start) {

int i;

Stack S = new Stack();

 

S.insert(start);

Vertex current;

 

start.setVisited();

 

while(!S.isEmpty) {

current = (Vertex)S.pop();

 

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

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

S.insert(vertice[i]);

vertice[i].setVisited();

 

System.out.println(current.label + "-" + vertice[i].label);

}

}

}

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

}

}

 

가중치 그래프의 최소 신장 트리

최소 개수의 변으로 모든 꼭지점을 연결 + 가중치의 합이 최소

 

1. 시작 꼭지점을 집합에 넣는다.

2. 집합에 포함된 꼭지점들과 포함되지 않은 꼭지점들을 연결하는 변들 중에서 가장 낮은 가중치를 가지는 변을 선택한다.

3. 선택된 변을 최소 신장 트리에 넣고 연결된 꼭지점을 집합에 추가한다.

4. 집합에 포함되지 않은 꼭지점이 남아있으면 단계 2로 가고, 남아있지 않으면 종료한다.

 

가장 낮은 가중치를 가지는 변의 search는 우선순위 큐로 해결(단계2)

큐에 넣기 위해서는 인접행렬 형태의 변을 하나의 객체로 만든다.

 

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 siVisited() {

return visitFlag;

}

 

public void setVisited() {

visitFlag = true;

}

 

public void unsetVisited() {

visitFlag = false;

}

}

 

class Edge {

public int weight;

public Vertex src;

public Vertex dst;

 

// true == 방향없는 그래프

// false == 방향 그래프

public boolean duplex = true;

 

Edge(Vertex s, Vertex d, int w) {

src = s;

dst = d;

weight = w;

}

}

 

class PriorityQueue {

Edge data[];

final int MAX = 100;

int front;

int rear;

 

public PriorityQueue() {

data = new Edge[MAX];

front = 0;

rear = 0;

}

 

public void insert(Edge e) {

for(int i = front; i < rear; i++) {

if(data[i].src.getId() == e.src.getId()) && data[i].dst.getId() == e.dst.getId()) {

return;

}

 

if(e.duplex && data[i].dst.getId() == e.src.getId() && data[i].src.getId() == e.dst.getId()) {

return;

}

}

 

data[rear] = e;

 

for(int i = front; i < rear; i++) {

if(e.weight > data[i].weight) {

shift(i);

data[i] = e;

 

break;

}

}

 

if(rear < MAX) {

rear += 1;

}

}

 

public void shift(int k) {

for(int i = rear; i > k; i--) {

data[i] = data[i - 1];

}

}

 

public Edge getMax() {

if(front < MAX) {

front += 1;

}

 

return data[front - 1];

}

 

public Edge getMIN() {

rear -= 1;

 

return data[rear];

}

 

public boolean isEmpty() {

if(front == rear) {

return true;

}

}

 

 

else

return false;

}

 

class Graph {

final int MAX = 50;

 

// 연결없음(∞)

final int INFINITY = 60000;

 

int adjMat[][];

Vertex vertice[];

 

// 시작 꼭지점까지의 거리

int distance[];

 

public int numOfVertice;

 

boolean isDirected;

 

public Graph() {

adjMat = new int[MAX][MAX];

vertice = new Vertex[MAX];

distance = new int[MAX];

 

numOfVertice = 0;

isDirected = false;

 

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

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

adjMat[i][j] = INFINITY;

}

}

 

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

distance[i] = INFINITY;

}

}

 

public Vertex getVertex(int i) {

return vertice[i];

}

 

public void addVertex(Vertex V) {

V.setId(numOfVertice);

vertice[numOfVertice] = V;

numOfVertice += 1;

}

 

public void addEdge(Vertex src, Vertex dst, int w) {

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

 

if(!isDirected) {

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

}

}

 

public void setDirected() {

isDirected = true;

}

 

public void unsetDirected() {

isDirected = false;

}

 

public void MSTW(Vertex start) {

Vertex V;

PriorityQueue PQ = new PriorityQueue();

 

v = start;

int count = 1;

 

while(count < numOfVertice) {

v.setVisited();

 

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

int w = adjMat[v.getId()][i];

 

//  변을 Edge객체로 변환하여 우선순위 큐에 넣는다.

if(w < INFINITY && !vertice[i].isVisited()) {

Edge tmp = new Edge(v, vertice[i], w) {

PQ.insert(tmp);

}

}

 

Edge e;

 

do {

e = PQ.getMIN();

v = e.dst;

} while(v.isVisited());

 

count += 1;

 

System.out.println(e.src.label + " - " + e.est.label);

}

}

}

 

최단 경로 탐색(shortest path search)

가중치 있는 방향 그래프가 일반적

변과 꼭지점 수가 많아지게 되면 경우의 수도 기하급수적으로 늘어나기 때문에 체계적인 방법 필요

 

다익스트라(Dijkstra)

하나의 꼭지점에서 그래프의 다른 모든 꼭지점까지의 최단 경로를 찾아내는 알고리즘

MSTW와 비슷하지만 해당 꼭지점까지의 거리를 기준으로 집합에 추가

최단경로 유추를 위하여 시작 꼭지점에서 자기까지의 최단 경로에서 자기 바로 전의 꼭지점이 무엇인지 기록

그래프 전체적으로 시작 꼭지점에서 각 꼭지점까지의 총 거리가 얼마인가 하는 정보 유지

 

1. 현재 선택된 꼭지점을 '고정'으로 표시한다.

2. 선택된 꼭지점에 연결된 변들을 통하여 다른꼭지점들까지 연결되는 더 짧은 경로가 있는지를 확인하고, 더 짧은 경로가 있다면 꼭지점의 '거리정보'를 갱신한다.

3. 각 꼭지점까지의 거리를 확인하여 '고정'으로 표시 되지 않은 꼭지점 중 거리가 가장 짧은 꼭지점을 선택한다.

4. 모든 꼭지점이 '고정'으로 표시되었으면 탐색을 중지하고 아니면 단계1로 돌아간다.

 

Class Vertex {

public String label;

public boolean fix;

int id;

 

public Vertex prev;

 

public Vertex(String l) {

label = l;

fix = false;

id = -1;

prev = null;

}

 

public int getId() {

return id;

}

 

public void setId(int i) {

id = i;

}

 

public boolean isFixed() {

return fix;

}

 

public void setFixed() {

fix = true;

}

 

public void unsetFixed() {

fix = false;

}

}

 

class Graph {

final int MAX = 50;

final int INFINITY = 60000;

 

int adjMat[][];

Vertex vertice[];

int distance[];

 

public int numOfVertice;

 

boolean isDirected;

 

public Graph() {

adjMat = new int[MAX][MAX];

vertice = new Vertex[MAX];

distance = new int[MAX];

 

numOfVertice = 0;

isDirected = false;

 

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

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

adjMat[i][j] = INFINITY;

}

}

 

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

distance[i] = INFINITY;

}

}

 

public Vertex getVertex(int i) {

return vertice[i];

}

 

public void addVertex(Vertex V) {

V.setId(numOfVertice);

vertice[numOfVertice] = V;

numOfVertice += 1;

}

 

public void addEdge(Vertex src, Vertex dst, int w) {

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

 

if(!isDirected) {

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

}

}

 

public void setDirected() {

isDirected = true;

}

 

public void unsetDirected() {

isDirected = false;

}

 

public Vertex getMinVertex() {

Vertex v = null;

int tmpDistance = INFINITY;

 

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

if(!vertice[i].isFixed() && distance[i] < tmpDistance) {

tmpDistance = distance[i];

v = vertice[i];

}

}

 

return v;

}

 

public void updateDistance(Vertex v) {

int tmpDistance;

 

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

if(adMat[v.getId()][i] < INFINITY) {

tmpDistance = distance[v.getId()] + adjMat[v.getId()][i];

 

if(tmpDistance < distance[i]) {

distance[i] = tmpDistance;

vertice[i].prev = v;

}

}

}

}

 

public void SPF(Vertex start) {

Vertex v;

distance[start.getId()] = 0;

 

v = start;

 

do {

v.setFixed();

updateDistance(v);

v = getMinVertex();

} while(v != null);

 

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

String result[] = new String[numOfVertice];

 

int count = 0;

v = vertice[i];

 

while(v != null) {

result[count] = v.label;

count++;

v = v.prev;

}

 

System.out.print(vertice[i].label + " : ");

 

for(int j = count - 1; j >= 0; j--) {

System.out.print(result[j]);

 

if(j > 0) {

System.out.print(" -> ");

}

}

System.out.println();

}

}

}

 

그래프 탐색의 복잡도

꼭지점의 개수 V

변의 개수 E

 

인접 행렬 O(V^2)

인접 리스트 O(V + E)

 

V에 비하여 E가 월등히 많다면 둘다 성능 향상은 그닥

V에 비하여 E가 적으면 인접리스트가 유리

 

NP complete(Non-deterministic Polynomial : 비다항식)

문제를 구성하는 변수의 변화에 의해 급격하게 복잡도가 올라가거나 수행의 횟수가 증가하는 문제

문제 변수의 변화에 따른 계산 시간이 다항식적으로 증가하지 않는다.

 

ex) 여행하는 세일즈맨 - O(N!)

도시의 개수에 따라 최단거리가 n * (n-1) * ... * 2 * 1 즉 factorial로 나타난다.