/*
Elementary Graph Operations, 기본적인 그래프 연산들(DFS, BFS, Components, DfnLow)
*/
#include <iostream>
#include <queue> //BFS 위해
using namespace std;
class Chain;
class ChainIterator;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int num) :data(num)
{
link = NULL;
}
friend Chain;
friend ChainIterator;
};
class Chain
{
private:
ChainNode *first;
public:
Chain()
{
first = NULL;
}
void Insert(int num)
{
ChainNode *newNode = new ChainNode(num);
newNode->link = first;
first = newNode;
}
void Delete(int num)
{
ChainNode *prev = NULL; //이전 위치 저장
ChainNode *current = first; //처음을 가리키고
while (current->data != num && current != NULL) //current가 존재하고 num 전일 때까지
{
prev = current; //원래 현재 위치를 저장
current = current->link;
}
if (current)
{
if (prev)
prev->link = current->link; //prev 다음을 current 다음과 연결
else
first = first->link; //처음에 있던 요소가 없어진 것이기 때문에 first의 위치를 옮긴다
delete current;
}
}
friend class ChainIterator;
friend ostream &operator<<(ostream &os, Chain &cn);
};
class ChainIterator
{
private:
ChainNode *current;
Chain &chain;
public:
ChainIterator(Chain &temp) :chain(temp)
{
current = temp.first;
}
int *First()
{
if (current)
return ¤t->data;
else
return NULL;
}
int *Next()
{
current = current->link;
return ¤t->data;
}
bool exist()
{
if (current)
return true;
else
return false;
}
bool linkExist()
{
if (current->link)
return true;
else
return false;
}
friend ostream &operator<<(ostream &os, Chain &cn);
};
ostream &operator<<(ostream &os, Chain &cn)
{
ChainIterator ci(cn);
if (!ci.exist())
return os;
os << *ci.First() << endl;
while (ci.linkExist())
os << *ci.Next() << endl;
return os;
}
class LinkedGraph
{
private:
Chain *firstNode;
int n; //정점의 개수
int num; //DfnLow와 Biconnected 함수에서 포함하라고 한 멤버변수
int *low; //DfnLow와 Biconnected 함수에서 포함하라고 한 멤버변수
int *dfn; //DfnLow와 Biconnected 함수에서 포함하라고 한 멤버변수
bool *visited;
public:
LinkedGraph(int v = 0) :n(v)
{
firstNode = new Chain[n];
}
~LinkedGraph()
{
delete[]firstNode;
}
void Initialize() //그래프를 미리 그려놓는다(6.17 그림을 참고)
{
firstNode[0].Insert(1);
firstNode[1].Insert(0);
firstNode[0].Insert(2);
firstNode[2].Insert(0);
firstNode[1].Insert(3);
firstNode[3].Insert(1);
firstNode[1].Insert(4);
firstNode[4].Insert(1);
firstNode[2].Insert(5);
firstNode[5].Insert(2);
firstNode[2].Insert(6);
firstNode[6].Insert(2);
firstNode[3].Insert(7);
firstNode[7].Insert(3);
firstNode[4].Insert(7);
firstNode[7].Insert(4);
firstNode[5].Insert(7);
firstNode[7].Insert(5);
firstNode[6].Insert(7);
firstNode[7].Insert(6);
}
void DFS() //Depth First Search
{
visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false; //초기화
DFS(0);
delete[]visited;
}
void DFS(const int v)
{
//한 정점으로부터 도달할 수 있는 모든 정점을 방문한다(이미 방문한 정점은 X)
visited[v] = true;
cout << v << " ";
ChainIterator ci(firstNode[v]);
if (!ci.exist())
return; //존재하지 않다면 break
int temp = *ci.First();
while (1)
{
if (!visited[temp])
DFS(temp);
if (ci.linkExist()) //다음 정점이 존재한다면
temp = *ci.Next();
else
return;
}
}
void BFS(int v)
{
visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;
queue<int> q;
q.push(v); //v를 push
visited[v] = true;
while (!q.empty())
{
v = q.front();
cout << v << " ";
ChainIterator ci(firstNode[v]);
q.pop();
int temp = *ci.First();
while (1)
{
if (!visited[temp]) //방문하지 않았다면 queue에 push
{
visited[temp] = true;
q.push(temp);
}
if (ci.linkExist())
temp = *ci.Next();
else
break;
}
}
delete[]visited;
}
void Components() //정점 출력
{
visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;
for (int i = 0; i < n; i++)
if (!visited[i])
{
cout << "정점들: ";
DFS(i);
cout << endl;
}
delete[]visited;
}
void DfnLow(const int x) //x 정점으로부터 DFS 실시
{
num = 1;
dfn = new int[n];
low = new int[n];
for (int i = 0; i < n; i++)
dfn[i] = low[i] = 0;
DfnLow(x, -1);
delete[]dfn;
delete[]low;
}
void DfnLow(const int u, const int v)
{
//u 정점으로부터 DFS를 실시하며 dfn과 low를 계산한다
//v는 u의 부모이다
dfn[u] = low[u] = num++;
ChainIterator ci(firstNode[u]);
if (!ci.exist())
return; //존재하지 않는다면
int temp = *ci.First();
while (1)
{
if (dfn[temp] == 0)
{
DfnLow(temp, u);
if (low[temp] < low[u])
low[u] = low[temp];
}
else
{
if (temp != v)
{
if (dfn[temp] < low[u])
low[u] = dfn[temp];
}
}
if (ci.linkExist())
temp = *ci.Next();
else
return;
}
}
void Biconnected()
{
int num = 1;
dfn = new int[n];
low = new int[n];
for (int i = 0; i < n; i++)
dfn[i] = low[i] = 0;
DfnLow(0, -1);
delete[]dfn;
delete[]low;
}
};
int main(void)
{
LinkedGraph lg(8);
lg.Initialize();
cout << "DFS 결과: ";
lg.DFS();
cout << endl;
lg.Components();
cout << "BFS 결과: ";
lg.BFS(0);
cout << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, http://sarah950716.tistory.com/13, http://119.201.123.184/30stair/articulation/articulation.php?pname=articulation
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*BFS 수정 완료!
*http://119.201.123.184/30stair/articulation/articulation.php?pname=articulation 여기서 dfn 개념을 확인했습니다
*코드대로 Biconnected와 DfnLow를 작성하기는 했지만 여전히 어떻게 돌아가는지 잘 모르겠습니다.
*좀 더 공부하고 나중에 작성해보도록 하겠습니다.(Prim, Kruskal은 수도코드도 없던데 어떻게 해야할지 모르겠습니다)
*책의 내용은 점점 간략해지는데 난이도는 점점 어려워지고 있습니다... 어떻게 해야하지