[알고리즘]Depth First Search(깊이 우선 탐색) 구현 (Pre, Post 및 Strongly Connected Component 계산)

소개글

[알고리즘]Depth First Search(깊이 우선 탐색) 구현 (Pre, Post 및 Strongly Connected Component 계산)에 대한 보고서 자료입니다.

목차

[Debug]
digraph2011.exe
digraph2011.ilk
digraph2011.pdb

[digraph2011]
　DAGStack.h
　digraph.txt
　digraph1.cpp
　digraph2011.vcxproj
　digraph2011.vcxproj.filters
　digraph2011.vcxproj.user
　LinkedList.h
　ListNode.h
　Stack.h
　StackNode.h
　Vertex.h

　[Debug]
　　cl.command.1.tlog
　　CL.read.1.tlog
　　CL.write.1.tlog
　　digraph1.obj
　　digraph2011.exe.embed.manifest
　　digraph2011.exe.embed.manifest.res
　　digraph2011.exe.intermediate.manifest
　　digraph2011.lastbuildstate
　　digraph2011.log
　　digraph2011_manifest.rc
　　link.command.1.tlog
　　link.read.1.tlog
　　link.write.1.tlog
　　link-cvtres.read.1.tlog
　　link-cvtres.write.1.tlog
　　mt.command.1.tlog
　　mt.read.1.tlog
　　mt.write.1.tlog
　　rc.command.1.tlog
　　rc.read.1.tlog
　　rc.write.1.tlog
　　vc100.idb
　　vc100.pdb

digraph2011.sln
digraph2011.suo

본문내용

#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 CALL\n");
int i, j; // 인접리스트의 내용을 가져와서 null이 아닐때까지 하나하나 표시 i는 세로 j는 가로
LIST_NODE *p;
cout << "- Adjacency Matrix" << endl;
for(i = 0; i < N; i++)
{
j = 0;
p = Adjacency_List[i].Node; //인접리스트가 담긴 노드 이용
while(p != NULL)
{
for(;j < p->Data; j++)
{
cout << "0 ";
}
cout << "1 ";//p node 가 null이 아니면 1출력
j++;
p = p->Next;//리스트 한발짝 진전
};
for(;j < N; j++) //1 뒤의 0 표현
{
cout << "0 ";
}
cout << endl;
}
cout << endl;
}

int int_min(int x,int y)
{
return ((x }

void DFS(int i)
{
//printf("DFS CALL\n");
LIST_NODE *p; //p = Node->Next; Node->Next = p->Next;
Digraph[i].Pre = ++Cnt; // digraph의 순서 pre counter

S->Push(i); P->Push(i); //Stack 에 함수 각각 call하여 넣음.
p = Adjacency_List[i].Node;//인접리스트의 각 노드를 p에 넣음
while(p != NULL) // p가 null이 아닐때까지 계속 반복
{
if(Digraph[p->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
}

void SCC_Gabow(void) //SCC 가보우 함수정의
{
//printf("GABOW CALL\n");
int i;
S = new STACK; //S,P Stack
P = new STACK;
for(i = 0; i < N; i++) // N 정점 개수
{
if(Digraph[i].Pre == -1) DFS(i); // DFS로 Pre Post 확정
}
//여기서 DFS가 완전 끝남 그 값을 갖고
cout << "- Pre & Post" << endl;
cout << "Vertex Pre Post" << endl;
for(i = 0; i < N; i++) // vertex 수만큼
{
cout << Digraph[i].V << " " << Digraph[i].Pre << " " << Digraph[i].Post << endl; // vertex pre post
}
cout << endl;
//
cout << "- Strongly Connected Components" << endl; //SCC
DAG_STACK *DAG_p;
LIST_NODE *List_p;
DAG_p = DAGs;// DAG_p 에는 SCC가 list형태로 저장되어있음. 한 컴포넌트가 하

키워드

DFS,   Depth,   깊이우선탐색,   Pre,   Post,   Strongly Connected Component,   Search,   BFS