(알고리즘 설계와 분석)리스트에 기반한 그래프의 bfs

<<헤더파일>>

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

#define NONE      -1

void errorExit(const char *s);

typedef struct _SLL {
int i;
struct _SLL *p;
} SLL;

class SLList2 {
private:
SLL *SLL_pool;
public:
SLList2(void) {
SLL_pool = NULL;
}
~SLList2(void) {
}
unsigned long SLL_cnt;
unsigned long UsedMemoryForSLLs;

SLL *allocSLL(void);
void freeSLL(SLL *p);
void freeSLL_pool(void);
};

//class sllStack :public SLList {
class sllStack2 {
private:
SLL *ST;
public:
sllStack2(void) {
ST = NULL;
}
~sllStack2(void) {
}
void  push(SLL *p);
SLL  *pop(void);
SLL  *top(void);
bool  empty(void);  // true is the stack is empty
};

typedef struct vertex {
int   name; // may have more information
bool   flag;
sllStack2  S;    // adjacent list as a stack
} vertex;

typedef struct edge {
int    name;  // may have more information
int    cost;
bool   flag;
int    vf, vr;
} edge;

// Graph_adj_list_tree_check.cpp

int  Tree_Check_adj_list(int Vnum, vertex *V, int Enum, edge *E);

// Graph_adj_list_data_in.cpp

void Read_Graph_adj_list(int Vnum, vertex *V, int Enum, edge *E);
void Free_Graph_adj_list(int Vnum, vertex *V);

// BFS spanning tree generation
int BFS_Tree_adj_list(
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)
);

 

<<메인>>

#include "Graph_adj_list.h"

extern SLList2 pool;
extern unsigned long UsedMemoryForArray;

int main ( void ) {
int Vnum, Enum, src;
vertex *V;
edge   *E;
int    Tree_cost; // BFS_tree cost
int    Tnum;      // # of test cases
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_list(Vnum, V, Enum, E);
// Do BFS
start = clock(); // start timer

Tree_cost = BFS_Tree_adj_list(src, Vnum, V, Enum, E);

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

        if (Tree_Check_adj_list(Vnum, V, Enum, E ) == 0) { // check if spanning tree
if ( t != 0 ) printf("\n");
printf("**T%d (BFS) (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 (BFS) (V = %d, E = %d, time = %.3f sec) Tree Cost = %d", 
t+1, Vnum, Enum, cmpt, Tree_cost);
}

Free_Graph_adj_list(Vnum, V); // free adj list
if (pool.SLL_cnt != 0) {
printf("ERROR: SLL_cnt must be zero.");
exit(-1);
}
fflush(stdout);
    delete[] V; // free Vertex Array V
delete[] E;   // free Edge Array E
}
  printf("\nTotal memory used = %d", 
pool.UsedMemoryForSLLs + UsedMemoryForArray);
pool.freeSLL_pool( ); // return ptr_Ls in the pool to the system memory

return 0;
}

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

 

<<bfs체크>>

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

#define PARENT_OF_ROOT  -100
#define UNVISITED_IN_TREE_CHECK -1

int Tree_Check_adj_list(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++ ) {  // count the tree edge
if ( E[i].flag == true ) {
++u;
// printf("now u %d\n", u);
}
}
// printf("%d %d\n", u, Vnum);
if ( u != (Vnum-1) ) {
return 0; // it is not a spanning tree
}
visited = new int[Vnum];
for (int i=0; i < Vnum; i++ )
visited[i] = UNVISITED_IN_TREE_CHECK;
u = 0;
visited[u] = PARENT_OF_ROOT;
  do {
// check adjacent list at v0 and set Costi_Ni
for ( SLL *p = (V[u].S).top(); p != NULL; p = p->p ) {
ep = p->i;
if ( E[ep].flag == false ) {
continue;  // not a tree edge
}
w = E[ep].vf;
if ( u == E[ep].vf ) {
w = E[ep].vr;
}
if ( visited[w] == UNVISITED_IN_TREE_CHECK ) {
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();
}
return 0;
}
}
if ( q.empty() ) {
for (int i = 0; i < Vnum; i++) {
if (visited[i] == UNVISITED_IN_TREE_CHECK)
return 0; // the graph is not connected
}
return 1;
}
u = q.front();
q.pop();
} while ( 1 );
}

 

<<bfs 및 리스트 생성>>

#include "Graph_adj_list.h"
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>

extern void errorExit(const char *s);

SLList2 pool;
unsigned long UsedMemoryForArray = 0;


void Read_Graph_adj_list(int Vnum, vertex *V, int Enum, edge *E) {
// 파일에서 그래프 정보를 읽어 V와 E 배열을 구성한다.
// V[ ].name과 E[ ].name은 설정할 필요가 없으나 편의상 각 배열에서의
//   index를 저장한다. Vnum은 정점개수, Enum은 간선개수.
// V[ ].S는 adjacent list header로 스택 헤더로도 사용된다.
// 따라서 edge (i,j)를 읽으면 V[i].S에 edge index k를 push하고
//  마찬가지로 V[j].S에 k를 push한다.
// V[].flag과 E[].flag은 반드시 false로 설정해야 한다.

// V는 vertex 구조체 배열, E는 edge 구조체의 배열
/*
typedef struct vertex {
int   name; // may have more information
bool   flag;
sllStack2  S;    // adjacent list as a stack
} vertex;

typedef struct edge {
int    name;  // may have more information
int    cost;
bool   flag;
int    vf, vr;
} edge;*/

for (int i = 0; i < Vnum; i++) {
vertex v;
v.name = i;
v.flag = false;
V[i] = v;
// printf("%d\n", V[i].name);
}

int src=0; int dest=0; int cost=0;
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;

SLL* p; 
p = pool.allocSLL(); p->i = idx; p->p = NULL;
V[src].S.Push(push(p);
p = pool.allocSLL(); p->i = idx; p->p = NULL;
V[dest].S.push(p);

}

}

void Free_Graph_adj_list(int Vnum, vertex *V) {
// V 배열의 adjacency list의 원소를 pop()을 사용하여
// 모두  pool로 되돌려 준다
int k;

// ***이 함수를 작성한다
for (int idx = 0; idx < Vnum; idx++) {
while (!(V[idx].S.empty())) {
SLL* p = V[idx].S.pop();
// if (p == NULL)
// continue;
pool.freeSLL(p);
}
}
}

SLL* sllStack2::pop(void) {
// remove and return p at the top of ST

// ***이 함수를 작성했다
SLL* p = ST;
if (ST->p == NULL) {
ST = NULL;
// printf("Ok");
}
else {
// printf("No\n");
ST = ST->p;
}

return p;
}

int BFS_Tree_adj_list(
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)
) {
// BFS를 사용하여 BFS tree에 속하는 에지의 flag을 true로 설정한다.
// BFS 시작 vertex는 입력 파일에서 지정된다(src).
// V[]의 adjacent list 탐색은 .top() 멤버 함수를 사용하여
//  adj list 헤더를 얻고 이를 따라가며 인접 vertex를 탐색한다.
// BFS tree에 속한 에지의 cost 함을 return 한다
//   (not unique but 모든 각 edge cost가 1이면 unique)
// -- 함수의 모든 parameter가 사용될 필요는 없다.
// -- BFS를 위한 queue가 필요하면 STL의 queue를 사용해도 좋다
int ret = 0;
std::queue<int> que;

que.push(src);
V[src].flag = true;
int now;
int next;

SLL* Vtemp;
int* size = new int[Vnum];
memset(size, 0, Vnum*sizeof(int));
//사이즈 구하기
for (int sz = 0; sz < Vnum; sz++) {
Vtemp = V[sz].S.top();
for (; Vtemp !=NULL; ) {
size[sz]++; 
Vtemp = Vtemp->p;
}
}
// for (int sz = 0; sz < Enum; sz++) {
//  E[sz].flag = 0;
// }
int fff=0;
while (que.size() != 0) {
now=que.front();
que.pop();
//edge2 입성
Vtemp = V[now].S.top();
// printf("size %d\n", size[now]);
for (int j=0; j<size[now] ;j++) {
// printf("지금 중심이 된 점의 top %d \n", V[now].S.top()->i);
if(E[Vtemp->i].flag != true) {


if (V[E[Vtemp->i].vf].flag != true) {
next = V[E[Vtemp->i]..name;
E[Vtemp->i].flag = true;
// printf("con %d %d ",now, V[E[Vtemp->i].vf].name);
// printf("\nflag %d %d\n", Vtemp->i, E[Vtemp->i]);
// printf("%d\n", Vtemp->i);
Vtemp = Vtemp->p;
fff++;

}
else if (V[E[Vtemp->i].vr].flag != true) {
next = V[E[Vtemp->i].vr].name;
E[Vtemp->i].flag = true;
// printf("con %d %d ",now, V[E[Vtemp->i].vr].name);
// printf("\nflag %d %d\n", Vtemp->i, E[Vtemp->i]);
// printf("%d\n", Vtemp->i);
Vtemp = Vtemp->p;
fff++;

// printf("ret %d\n", ret);
}
else {
Vtemp = Vtemp->p;
// printf("3-------%d %d %d\n", Vtemp->i,
// E[Vtemp->i].name, now);
}
}
else {
//printf("4--------%d %d %d\n", Vtemp->i,
// E[Vtemp->i].name, now);
Vtemp = Vtemp->p;
// if (Vtemp == NULL) {
// printf("4!!\n");
// break;
// } 

continue;

}
// printf("next %d now %d\n", next, now);

if (!V[next].flag) {
V[next].flag = true;
ret++;
que.push(next);
// printf("ret %d %d\n", ret, V[next].name);
}

}
}
for (int sz = 0; sz < Enum; sz++) {
if (E[sz].flag != 1) E[sz].flag = 0;
// printf(" %d ", E[sz].flag);
}
return ret;
}

// stack member fuctions
void sllStack2::push(SLL *p) {
// insert p to the top of stack ST
p->p = ST;
ST = p;
}

SLL *sllStack2::top(void) {
// return p at the top of ST
return ST;
}

bool sllStack2::empty(void) {
// return true if empty
if (ST == NULL)
return true;
else
return false;
}

// SLList2 member functions
SLL *SLList2::allocSLL(void) { // allocate an SLL element
SLL *p;

// ***이 함수를 작성했다
if (SLL_pool == NULL) {
p = (SLL*)malloc(sizeof(SLL));
if (p == NULL)
errorExit("메모리 할당 에러(allocSLL)");
UsedMemoryForSLLs += sizeof(SLL);
p->i = NONE;
}
else {
p = SLL_pool; //pool- 스택 그자체. 즉, 첫번째요소
SLL_pool = p->p; //p:새로 생성한 노드. 이를 첫번째로 하고, 
}
p->p = NULL;
++SLL_cnt;

return(p);
}

void SLList2::freeSLL(SLL *p) { // free *p (move it to SLL_pool

// ***이 함수를 작성했다
if (p->i == NONE) {
errorExit("이건 이미 freed(freeSLL)");
}

p->i = NONE;
p->p = SLL_pool; //p->p 포인터가 헤더를 향하게 한다
SLL_pool = p; //이제 p는 pool의 첫번째 요소가 됨
--SLL_cnt;
}

void SLList2::freeSLL_pool(void) { // clear SLL_pool
SLL *p = SLL_pool;

// ***이 함수를 작성했다
while (p != NULL) {
SLL_pool = p->p;
free(p);
UsedMemoryForSLLs -= sizeof(SLL);
p = SLL_pool;
}

if (SLL_cnt != 0) {
errorExit("Non-zero SLL_cnt after cleanup.");
}
}