깊이우선탐색(Depth First Search) 를 이용하여 Pre, Post 및 Strongly Connected Component 계산하기

소개

알고리즘 코딩과제로 제출했던 것 입니다.
Visual Studio 2010 에서 C++로 제작하였습니다.
대표적 자료구조인 linked list와 stack 공간을 이용하였으며, Gobow함수를 구현했습니다.
학부수준에서는 높은 퀄리티라 생각되며 공부가 많이 되실 것 입니다.

-Strongly Connected Component

파일로부터 데이터를 입력받아서 그래프를 adjacency matrix의 형태로 저장한다.

– 파일의 구조
• n (vertex의 개수)
• Vertex list
• m (edge의 개수)
• Edge list (Source Destination)

– 입력 파일: digraph.txt

Graph.txt 파일로부터 그래프에 대한 정보를 읽어 들여서 adjacency matrix의 형태로 화면에 출력한다.

• Graph를 depth-first search하면서 pre와 post를 계산해서 출력한다.
• Graph로부터 strongly connected component를 계산해서 출력한다.
• Strongly connected component들의 그룹으로부터 만들어진 dag에서 source와 sink를 표시한다.

컴파일 실행환경

Microsoft Visual Studio 2010

본문내용

#include
#include
#include "DAGStack.h"
#include "LinkedList.h"
#include "Vertex.h"
#include "Stack.h"

using namespace std;

#define FILE_NAME "digraph.txt" //인풋파일이름

/*클래스 스택노드
클래스 스택
클래스 버택스
클래스 리스트노드
클래스 링키드 리스트
클래스 DAG 스택*/

//주요 자료구조는 linked list 밖에 없다. 행렬, pre post, source sink 모두 리스트를 가져와서 표현
LINKED_LIST *Adjacency_List; // 인접 리스트

VERTEX *Digraph;

STACK *S, *P;

DAG_STACK *DAGs;

int N;

int Cnt, SCC; // PRE&POST VISIT Counter

void Initialize(void)
{
int i, j, k, m;

char v1, v2;

// 초기화
Digraph = NULL;//Vertex
S = P = NULL;//STACK *S, *P;
DAGs = NULL;//DAG stack
Cnt = 0;
// 파일 입력
ifstream fin;

// dynamic allocation
fin.open(FILE_NAME);
fin >> N;
Digraph = new VERTEX[N];

Adjacency_List = new LINKED_LIST[N];// 생성

// vertex name insertion
for(i = 0; i < N ;i++)
{
fin >> Digraph[i].V;
}

fin >> m; //

//인접리스트 만드는거
for(i = 0; i < m ;i++)
{
fin >> v1 >> v2;
for(j = 0; j < N; j++)
{
if(Digraph[j].V == v1) break;
}
for(k = 0; k < N; k++)
{
if(Digraph[k].V == v2) break;
}
Adjacency_List[j].Insert(k);
}
fin.close();
}

void Adjacency_Matrix(void)
{
//printf("ADJ CALLn");
int i, j; // 인접리스트의 내용을 가져와서 null이 아닐때까지 하나하나 표시 i는 세로 j는 가로
LIST_NODE *p;
cout Data].Pre == -1)
{
DFS(p->Data); //재귀호출. 초기화했던 -1인 각 노드 인 것들을 모두 DFS하여 pre를 센다.
}
else if(Digraph[p->Data].SCC==-1)
{
int j; //Strongly Connected Component -1 인 것을 각 pop
do
{
j = P->Pop();
} while(Digraph[j].Pre > Digraph[p->Data].Pre);
P->Push(j);// pop 했던 것을 다른곳에 push
}
p = p->Next;
}
if(P->IsTop(i)) //top
{
int j; //SCC 변수 j = P->Pop();
DAG_STACK *Stack_Node;//DAG = new LINKED_LIST;
Stack_Node = new DAG_STACK;
do
{
j = S->Pop(); //STACK *S, *P;
Stack_Node->DAG->Insert(j);
Digraph[j].SCC = SCC;
} while(j != i);
Stack_Node->Next = DAGs;
DAGs = Stack_Node; //하나의 DAGs를 Stack_Node에 넣어놓고
SCC++; // SCC 증가시키고
j=P->Pop(); // pop
}
Digraph[i].Post = ++Cnt; //post counter // int Cnt, SCC; PRE&POST VISIT Counter
}

참고자료

· 없음