내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.
1) 11장. 그래프(Graph)
Graph의 ADT
데이터: 정점의 집합과 간선의 집합
연산:
- creat(): 그래프를 생성한다.
- isEmpty(): 그래프가 비어있는지 확인한다.
- insertVertex(v): 그래프에 정점 v를 삽입한다.
- insertEdge(u, v): 그래프에 간선 (u, v)를 삽입한다.
- deleteVertex(v): 그래프의 정점 v를 삭제한다.
- deleteDdge(u, v): 그래프의 간선(u, v)를 삭제한다.
- adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반환.
인접행렬을 이용한 그래프 클래스의 구현
인접행렬은 정점이 n개 이면 n x n의 matrix에 정보를 표현하는 방식이다. 간단하게 class만 보이고 넘어가겠다.
#pragma once
#include <cstdio>
#include <iostream>
const int max_vixs = 256;
class AdjMatGraph {
protected:
int size;
char vertices[max_vixs];
int adj[max_vixs][max_vixs];
public:
explicit AdjMatGraph() { reset(); }
char getVertex(const int& i) const { return vertices[i]; }
int getEdge(const int& i, const int& j) const {
return adj[i][j];
}
void setEdge(const int& i, const int& j, const int& val) { adj[i][j] = val; }
bool isEmpty() { return size == 0; }
bool isFull() { return size == max_vixs; }
void reset() {
size = 0;
for (int i = 0; i < max_vixs; i++)
for (int j = 0; j < max_vixs; j++)
setEdge(i, j, 0);
}
void insertVertex(char name) {
if (!isFull()) vertices[size++] = name;
else printf("Error: 그래프 정점 개수 초과\n");
}
void insertEdge(const int& u, const int& v) {
setEdge(u, v, 1);
setEdge(v, u, 1);
}
void display(FILE* fp = stdout) {
fprintf(fp, "%d\n", size);
for (int i = 0; i < size; i++) {
fprintf(fp, "%c ", getVertex(i));
for (int j = 0; j < size; j++)
fprintf(fp, "%3d", getEdge(i, j));
fprintf(fp, "\n");
}
}
};
인접 리스트를 이용한 그래프의 표현
인접 리스트(adjacency list)는 그래프의 각 정점에 인접한 정점들을 linked_list로 표현하는 방식이다. 우선 코드를 먼저 확인후 내가 잘 이해하지 못했던 부분의 코드를 설명하면서 이해하겠다.
Node.h
#pragma once
#include <cstdio>
class Node {
protected:
int id;
Node* link;
public:
explicit Node(int i, Node* l = nullptr) : id(i), link(l) {}
~Node() {
if (link != nullptr) delete link;
}
int getId() { return id; }
Node* getLink() { return link; }
void setLink(Node* l) { link = l; }
};
AdjListGraph.h
#pragma once
#include "Node.h"
const int max_vtxs = 256;
class AdjListGraph {
int size;
char vertices[max_vtxs];
Node* adj[max_vtxs];
public:
AdjListGraph() : size(0) {}
~AdjListGraph() { reset(); }
void reset() {
for (int i = 0; i < size; i++)
if (adj[i] != nullptr) delete adj[i];
size = 0;
}
bool isEmpty() { return size == 0; }
bool isFull() { return size >= max_vtxs; }
char getVertex(const int& i) { return vertices[i]; }
void insertVertex(char val) {
if (!isFull()) {
vertices[size] = val;
adj[size++] = nullptr;
}
else printf("Error: 그래프 정점 개수 초고\n");
}
void insertEdge(const int& u, const int& v) {
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}
void display() {
printf("%d\n", size);
for (int i = 0; i < size; i++) {
printf("%c ", getVertex(i));
for (Node* v = adj[i]; v != nullptr; v = v->getLink())
printf(" %c", getVertex(v->getId()));
printf("\n");
}
}
Node* adjacent(const int& v) { return adj[v]; }
};
여기서 insertEdge()가 처음에 잘 이해되지 않았다. 나의 경우에는 인접리스트가 생성되면 꼬리를 물며 새로운 node가 추가될때마다 기존 linked_list의 꼬리node에서 새로운 node를 가리키는 형태를 생각하면서 코드를 계속 봤는데 말이안됬다. 우선 문제의 그 코드를 봐보자.
void insertEdge(const int& u, const int& v) {
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}u와 v를 연결하는 무방향 그래프이다. main에서 간선 삽입 코드와 같이 생각해보자.
main.cpp
#include "AdjLIstGraph.h"
int main()
{
AdjListGraph g;
for (int i = 0; i < 4; i++)
g.insertVertex('A' + i);
g.insertEdge(0, 1);
g.insertEdge(0, 3);
g.insertEdge(1, 2);
g.insertEdge(1, 3);
g.insertEdge(2, 3);
printf("인접 행렬로 표한한 그래프\n");
g.display();
return 0;
}insert(0, 1)에서 u가 0이고, v가 1이다.
따라서 new Node (1, adj[0]); 이 맨 처음 실행되는 코드이며 이때 adj[0]은 nullptr이다
따라서 adj[0] = new Node (1, adj[0]); 이 실행되면 다음과 같은 모습이 된다.
head second
| |
| |
+---+---+ +----+----+
| A | o-----> | B |NULL|
+---+---+ +----+----+ 문제는 다음 node가 추가될떄 second node 뒤에 이어서 연결되는 것 아닌!, head와 second 사이에 node가 추가된다는 점 이다.
g.insertEdge(0, 3); 을 생각해보자. u가 0이고, v가 3이다. 따라서 adj[0] = new Node (3, adj[0]); 이 된다. data가 3인 node의 주소가 adj[0]에 추가되고, 이 새로생긴 node는 기존에 adj[0]이 가리키던곳을 가리키게 된다. 다음 그림을 확인해 보자.
head third second
| | |
| | |
+---+---+ +----+----+ +-----+----+
| A | o ----->| D | o -----> | B |NULL|
+---+---+ +----+----+ +-----+----+ 이와 같은 원리로 코드를 실행시키면 결과는 다음과 같다.
DFS (depth first search)
이 방식은 stack을 이용한 미로 탐색과 유사하다. 미로를 탐색할때 한 방향으로 쭉 계속 이동하다 더이상 갈수없게 되면 다시 가장 가까운 갈림길로 돌아와 다른 방향을 탐색하는 방법이다. 알고리즘의 형태로 다음과 같이 나타낼 수 있다.
depthFirstSearch(v)
v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
if (u가 아직 방문되지 않았으면)
then depthFirstSearch(u)인접 행렬로 구현한 class
#pragma once
#include "AdjMatGraph.h"
class SrchAMGraph : public AdjMatGraph {
bool visited[max_vixs];
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;
printf("%c ", getVertex(v));
for (int w = 0; w < size; w++)
if (isLinked(v, w) && visited[w] == false)
DFS(w);
}
};인접 리스트로 구현한 class
#pragma once
#include "AdjListGraph.h"
class SrchALGraph : public AdjListGraph {
bool visited[max_vtxs];
public:
void resetVisited() {
for (int i = 0; i < size; i++)
visited[i] = false;
}
bool isLinked(int u, int v) {
for (Node* p = adj[u]; p != nullptr; p = p->getLink())
if (p->getId() == v) return true;
return false;
}
void DFS(const int& v) {
visited[v] = true;
printf("%c ", getVertex(v));
for (Node* p = adj[v]; p != nullptr; p = p->getLink())
if (visited[p->getId()] == false)
DFS(p->getId());
}
};BFS (breadth first search)
breadthFirstSearch(v)
v를 방문되었다고 표시;
큐 Q에 정점 v를 삽입;
while (not is_empty(Q)) do
Q에서 정점 W를 삭제;
for all u ∈ (w에 인접한 정점) do
if (u가 아직 방문되지 않았으면(
then u를 큐에 삽입;
u를 방문되었다고 표시;인접 행렬로 구현한 class. 교제에서는 직접 만든 원형 큐를 사용하는데 나는 그냥 STL의 queue를 상요하였다.
#pragma once
#include "AdjMatGraph.h"
#include <queue>
class SrchAMGraph : public AdjMatGraph {
bool visited[max_vixs];
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;
printf("%c ", getVertex(v));
for (int w = 0; w < size; w++)
if (isLinked(v, w) && visited[w] == false)
DFS(w);
}
void BFS(int v) {
visited[v] = true;
printf("%c ", getVertex(v));
std::queue<int> q;
while (!q.empty()) {
int v = q.front();
q.pop();
for(int w = 0; w < size; w++)
if (isLinked(v, w) && visited[v] == false) {
visited[w] = true;
printf("%c ", getVertex(w));
q.push(w);
}
}
}
};인접 리스트로 구현한 class
#pragma once
#include "AdjListGraph.h"
class SrchALGraph : public AdjListGraph {
bool visited[max_vtxs];
public:
void resetVisited() {
for (int i = 0; i < size; i++)
visited[i] = false;
}
bool isLinked(int u, int v) {
for (Node* p = adj[u]; p != nullptr; p = p->getLink())
if (p->getId() == v) return true;
return false;
}
void DFS(const int& v) {
visited[v] = true;
printf("%c ", getVertex(v));
for (Node* p = adj[v]; p != nullptr; p = p->getLink())
if (visited[p->getId()] == false)
DFS(p->getId());
}
void BFS(int v) {
visited[v] = true;
printf("%c ", getVertex(v));
std::queue<int> q;
q.push(v);
while (!q.empty()) {
int v = q.front();
q.pop();
for (Node* w = adj[v]; w != nullptr; w = w->getLink()){
int id = w->getId();
if (!visited[id]) {
visited[id] = true;
printf("%c ", getVertex(id));
q.push(id);
}
}
}
}
};
연결 성분 (connected component)
최대로 연결된 부분 그래프를 말한다. 다음 그림을 보자.
+---+---+ +----+----+
| A | o-----> | B |NULL|
+---+---+ +----+----+
+---+---+ +----+----+ +-----+----+
| 1 | o ----->| 2 | o -----> | 3 |NULL|
+---+---+ +----+----+ +-----+----+ A-B 와 1-2-3 으로 2개의 연결된 부분 그래프, 즉 2개의 연결 성분이 있다.
연결성분을 찾기 위해 DFS나 BFS를 사용한다. 먼저 그래프 상에서 임이의 정점을 선택해 탐색을 하면 시작정점과 연결된 모든 정점을 알수있다. 이후 아직 방문되지 않은 정점을 선택해 다시 탐색하면 그 정점에서 이어지는 연결성분을 또 찾을수있다. 이 과정을 모든 정점이 방문될때까지 반복하면 된다.
신장 트리 (spanning tree)
신장 트리란 그래프 내의 모든 정점을 포함하는 트리이다. 신장트리도 트리의 일종으로 모든 정점들이 연결되어 있고 사이클이 없어야한다. n개의 정점을 정확히 n-1 개의 간선으로 연결한다. 신장 트리는 DFS나 BFS 탐색 도중에 사용된 간선들만 모으면 만들 수 있다.
DFS 알고리즘을 변경하여 신장 트리 알고리즘을 나타내면 다음과 같다.
spanningTreeDFS(v)
v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
if (u가 아직 방문되지 않았으면)
then (v, u)를 신장 트리 간선이라고 표시;
spanningTreeByDFS(u);2) 나의 현황
◆ 지난번 열혈 자료구조를 공부하면서도 들었던 생각이 이번에도 똑같이 들고있다.
책을 보면서 한줄한줄 이해는 가며 그코드를 왜 작성했는지 흐름을 느끼며 공부하고있다.
문제는 이걸 책 없이 눈감고 싹 작성해봐 라고 한다면.. 음... 할수있으려나?... 향후 PS준비를 위해서 눈감고도 다 코드 나올만큼 이걸 암기하고 공부해야 하나? 라는 생각이 든다...
'CS > Data Structure (2021-1)' 카테고리의 다른 글
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 13장, 정렬 (0) | 2022.01.15 |
|---|---|
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 12장, 가중치 그래프 (0) | 2022.01.15 |
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 10장, 힙 (0) | 2022.01.15 |
| [자료구조] C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9-1 (0) | 2022.01.15 |
| C++로 쉽게 풀어쓴 자료구조 : 9장, 이진 탐색 트리 (0) | 2022.01.15 |
댓글