(알고리즘 설계와 분석)배열에 기반한 그래프의 dfs

<헤더파일>

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NONE -1

typedef struct _edge {
int  name;
int  vf, vr;  // e = (vf, vr) where vf, vr are vertex array indices
int  cost;    // edge cost
bool flag;    // true if in an SP, false otherwise 
int  fp, rp;  // adj list ptr of forward and reverse (-1 if none)
} edge;

typedef struct _vertex {
int  name;
bool flag;
int  f_hd, r_hd; // adj list header(-1 if none)
} vertex;

 

<<메인 함수>>

#include "Graph_adj_array.h"
#include <queue>

int Tree_Check_adj_array(int Vnum, vertex V[], int Enum, edge E[]);
void Read_Graph_adj_array(int Vnum, vertex V[], int Enum, edge E[]);
int DFS_Tree_adj_array(int src, int Vnum, vertex *V, int Enum, edge *E);

unsigned long usedMemoryForArray;
void errorExit(const char *s);

int main ( void ) {
int    Vnum, Enum, src;
vertex *V;
edge   *E;
int    Tnum; // # of test cases
int    Tree_cost; // DFS_tree cost
int    Memsize_for_array;
clock_t start, finish;
double cmpt;

scanf_s("%d", &Tnum);

for (int t = 0; t < Tnum; t++ ) {
scanf_s("%d %d %d", &Vnum, &Enum, &src);
V = new vertex [Vnum];
E = new edge [Enum];
if ( V == NULL || E == NULL ) {
errorExit("Memory Allocation Error");
}
Memsize_for_array = Vnum * sizeof(vertex) + Enum * sizeof(edge);
if (usedMemoryForArray < (unsigned long)Memsize_for_array ) {
usedMemoryForArray = Memsize_for_array;
}
Read_Graph_adj_array(Vnum, V, Enum, E);
// Do DFS
start = clock();

//     for ( int i = 0; i < Vnum; i++ ) {
//   V[i].flag = false;  // clear flag
//     }
//     for ( int i = 0; i < Enum; i++ ) {
//   E[i].flag = false;  // clear flag
//     }
Tree_cost = DFS_Tree_adj_array (src, Vnum, V, Enum, E);

finish = clock();
cmpt = ((double)(finish - start)) / (double)CLK_TCK;

        if (Tree_Check_adj_array(Vnum, V, Enum, E) == 0) { // check if spanning tree
if (t != 0) printf("\n");
printf("**T%d (DFS) (V = %d, E = %d, time = %.3f sec) ERROR: NOT A TREE!!", 
t+1, Vnum, Enum, cmpt);
}
else {
if ( t != 0 ) printf("\n");
printf("**T%d (DFS) (V = %d, E = %d, time = %.3f sec) Tree Cost = %d", 
t+1, Vnum, Enum, cmpt, Tree_cost);
}
delete V; delete E;
}
printf("\nTotal memory used = %d", usedMemoryForArray);
return 0;
}

void errorExit(const char *s) {
printf("%s\n", s);
exit(-1);
}

 

<<DFS 체크 함수>>

#include "Graph_adj_array.h"
//#include "Graph_adj_array_extern.h"
//#include "Graph_adj_array_function.h"
#include <queue>

#define PARENT_OF_ROOT  -100

int Tree_Check_adj_array(int Vnum, vertex V[], int Enum, edge E[]) {
int u = 0, ep, w;
int *visited;
std::queue<int> q;
for ( int i = 0; i < Enum; i++ ) {
if ( E[i].flag == true ) {
++u;
}
}
if ( u != (Vnum-1) ) {
return 0; // it is not a spanning tree
}
visited = new int[Vnum];  // allocate parent array
for (int i=0; i < Vnum; i++ )
visited[i] = NONE;
u = 0;
visited[u] = PARENT_OF_ROOT;
  do {
// check adjacent list at v0 and set Costi_Ni
for ( ep = V[u].f_hd; ep != NONE; ep = E[ep].fp ) { // forward
if ( E[ep].flag == false ) {
continue;
}
w = E[ep].vr;
if ( visited[w] == NONE ) {
visited[w] = u;
q.push(w);
}
else if ( visited[u] != w ) { // w is visited and w is not the parent of v,
  // implies that G has a cycle
while ( !q.empty() ) {
q.pop();
}
delete [] visited; 
return 0;
}
}
for ( ep = V[u].r_hd; ep != NONE; ep = E[ep].rp ) { // backward
if ( E[ep].flag == false ) {
continue;
}
w = E[ep].vf;
if ( visited[w] == NONE ) {
visited[w] = u;
q.push(w);
}
else if ( visited[u] != w ) { // w is visited and w is not the parent of v,
  // implies that G has a cycle
while ( !q.empty() ) {
q.pop();
}
delete [] visited; 
return 0;
}
}
if ( q.empty() ) {
for (int i=0; i < Vnum; i++ )
if (visited[i] == NONE) {
delete [] visited; 
return 0; // the graph is not connected
}
delete [] visited; 
return 1;
}
u = q.front();
q.pop();
} while ( 1 );
}

 

<<그래프 생성 및 DFS 시행 함수>>

#include "Graph_adj_array.h"
int arr[100];

void Read_Graph_adj_array (int Vnum, vertex V[], int Enum, edge E[]) {
// read graph information
// V와 E의 name field는 각각 자신의 인덱스를 저장한다
// V[].flag과 E[].flag은 반드시 false로 설정해야 한다.

for (int i = 0; i < Vnum; i++) {
vertex v;
v.name = i;
v.flag = false;
v.f_hd = -1;  v.r_hd = -1;
V[i] = v;
}

int src = 0; int dest = 0; int cost = 0;
int next = -2;
for (int idx = 0; idx < Enum; idx++) {
scanf_s("%d", &src);
scanf_s("%d", &dest);
scanf_s("%d", &cost);

E[idx].vf = src; E[idx].vr = dest; E[idx].cost = 1;
E[idx].flag = false;  E[idx].name = idx;
E[idx].fp = -1; E[idx].rp = -1;

E[idx].fp = V[src].f_hd;
V[src].f_hd = idx;

E[idx].rp = V[dest].r_hd;
V[dest].r_hd = idx;
}
// for (int i = 0; i < Vnum; i++)
// printf("%d %d\n", V[i].f_hd, V[i].r_hd);
// for (int i = 0; i < Enum; i++) {
// printf("%d %d %d %d\n", E[i].fp, E[i].vf, E[i].vr, E[i].rp);
// }
}

int dfs1(int ret, int eg, int Vnum, vertex* V,
int Enum, edge* E, int first);
int dfs2(int ret, int eg, int Vnum, vertex* V,
int Enum, edge* E, int second);

//인자: 정점의 fhd
int dfs1(int ret, int eg, int Vnum, vertex* V,
int Enum, edge* E, int first) {
//해당 에지가 -1이면, 패스
//또는 이미 방문한 거라면 패스
if (eg == -1) {
// ret--;
// printf("-1 exit %d decreased\n", ret);
return ret;
}
if (E[eg].flag == true) {
// printf("ture exit\n");
// ret--;
return ret;
}

while (eg != -1) {
//만일 이번에 해당 간선의 왼쪽의 정점을 방문한 것이라면
if (V[E[eg].vf].flag != true) {
V[E[eg].vf].flag = true;
E[eg].flag = true;
ret++;

// printf("result is %d now\n", ret);
// printf("Used %d edge\n", E[eg]);
// printf("visited %d\n", V[E[eg].vf].name);
arr[V[E[eg].vf].name] = 0;
//다음은 그 정점의 왼쪽과 오른쪽을 방문해
ret = dfs1(ret, V[E[eg].vf].f_hd, Vnum, V, Enum, E, first);
ret = dfs2(ret, V[E[eg].vf].r_hd, Vnum, V, Enum, E, first);
}
//해당 간선의 오른쪽의 정점을 방문한 것이라면
else if (V[E[eg].vr].flag != true) {
V[E[eg].vr].flag = true;
E[eg].flag = true;
ret++;

// printf("result is %d now\n", ret);
// printf("Used %d edge\n", E[eg]);
// printf("I visited %d\n", V[E[eg].vr].name);
arr[V[E[eg].vr].name] = 0;
// printf("edge %d %d\n", V[E[eg].vr].f_hd, V[E[eg].vr].r_hd);
ret = dfs1(ret, V[E[eg].vr].f_hd, Vnum, V, Enum, E, first);

ret = dfs2(ret, V[E[eg].vr].r_hd, Vnum, V, Enum, E, first);
}
//해당 간선의 모두를 방문했다면
else {
// if (eg == first)
// break;
// printf("%d edge can't visit any vertex\nand return %d\n", E[eg], ret);
// printf("now edge %d\n", eg);
eg = E[eg].fp;
// printf("now edge %d\n", eg);
// return ret;
continue;
}
//이번 간선에 연결된 fp rp를 찾아나설 차례
eg = E[eg].fp;
}

// printf("return %d\n", ret);
return ret;
}

//인자: 정점의 rhd
int dfs2(int ret, int eg, int Vnum, vertex* V,
int Enum, edge* E, int second) {
//해당 에지가 -1이면, 패스
//또는 이미 방문한 거라면 패스
if (eg == -1) {
// ret--;
// printf("-1 exit %d decreased\n", ret);
return ret;
}
if (E[eg].flag == true) {
// printf("ture exit\n");
// ret--;
return ret;
}

while (eg != -1) {
//만일 이번에 해당 간선의 왼쪽의 정점을 방문한 것이라면
if (V[E[eg].vf].flag != true) {
V[E[eg].vf].flag = true;
E[eg].flag = true;
ret++;

// printf("result is %d now\n", ret);
// printf("Used %d edge\n", E[eg]);
// printf("visited %d\n", V[E[eg].vf].name);
arr[V[E[eg].vf].name] = 0;
//다음은 그 정점의 왼쪽과 오른쪽을 방문해
ret = dfs1(ret, V[E[eg].vf].f_hd, Vnum, V, Enum, E, second);
ret = dfs2(ret, V[E[eg].vf].r_hd, Vnum, V, Enum, E, second);
}
//해당 간선의 오른쪽의 정점을 방문한 것이라면
else if (V[E[eg].vr].flag != true) {
V[E[eg].vr].flag = true;
E[eg].flag = true;
ret++;

// printf("result is %d now\n", ret);
// printf("Used %d edge\n", E[eg]);
// printf("I visited %d\n", V[E[eg].vr].name);
arr[V[E[eg].vr].name] = 0;
ret = dfs1(ret, V[E[eg].vr].f_hd, Vnum, V, Enum, E, second);
ret = dfs2(ret, V[E[eg].vr].r_hd, Vnum, V, Enum, E, second);
}
//해당 간선의 모두를 방문했다면
else {
eg = E[eg].fp;
continue;
}

//이번 간선에 연결된 fp rp를 찾아나설 차례
eg = E[eg].rp;
}
// printf("return %d\n", ret);
return ret;
}

int DFS_Tree_adj_array(
int     src,   // source node index
int     Vnum,  // number of vertices
vertex *V,     // vertex structure array (starting index 0)
int     Enum,  // number of edges
edge   *E     // edge structure array (starting index 0) 
) {  
// DFS를 사용하여 DFS tree에 속하는 에지의 flag을 true로 설정한다.
// DFS 시작 vertex는 입력 파일에서 지정된다(src).
// DFS tree에 속한 에지의 cost 함을 return 한다(모든 각 edge cost가 1이면 unique)
// recursive 함수로 작성해도 무방하다.

int ret = 0;  int ret2 = 0;
int* pt = &ret; int* st = &ret2;
int left = V[src].f_hd; int right = V[src].r_hd;
V[src].flag = true;

int first = left;  //the first used edge
int second = right;

ret += dfs1(*pt, left, Vnum, V, Enum, E, first);
*st = ret2;
ret2 += dfs2(*st, right, Vnum, V, Enum, E, second);
ret = ret + ret2;
arr[src] = 0;

return ret;
}