c로 쓴 자료구조론 연습문제 6장(그래프)

소개글

c로 쓴 자료구조론 연습문제 6장(그래프)에 대한 보고서 자료입니다.

본문내용

;
printf("\n");
}
}
else if(w != v)
low[u] = low[u] < dfn[w] ? low[u] : dfn[w];
}
}
/*stack operation for bicon method*/
void adds(stack_pointer *top, int v1, int v2) {
stack_pointer temp = (stack_pointer)malloc(sizeof(stack));
if(IS_FULL(temp)) {
fprintf(stderr, "The memory is full\n");
exit(1);
}
temp->vertex1 = v1;
temp->vertex2 = v2;
temp->link = *top;
*top = temp;/*새로 추가된 node를 top*/
}
void deletes(stack_pointer *top, int *v1, int *v2) {
stack_pointer temp = *top;
if(IS_EMPTY(temp)) {
fprintf(stderr, "The memory is empty\n");
exit(1);
}
*v1 = temp->vertex1;
*v2 = temp->vertex2;
*top = temp->link;/*top의 node를 제거하고 새로운 top 설정*/
free(temp);
}
/*determine bridge*/
void bridge(int u, int v){
node_pointer ptr;
int w;
dfn[u] = low[u] = num++;
for(ptr = graph[u]; ptr; ptr = ptr->link) {
w = ptr->vertex;
if(dfn[w] < 0) {
bridge(w, u);
low[u] = low[u] < low[w] ? low[u] : low[w];
if(low[w] > dfn[u])
printf("<%d, %d> ", u, w);
}
else if(w != v)
low[u] = low[u] < dfn[w] ? low[u] : dfn[w];
}
}
/*연결 그래프의 간선들을 이중결합 요소로 분할*/
void dfnlow(int u, int v) {
node_pointer ptr;
int w;
dfn[u] = low[u] = num++;
for(ptr = graph[u]; ptr; ptr = ptr->link) {
w = ptr->vertex;
if(dfn[w] < 0) {/*w는 방문이 안된 정점*/
if(v == -1)/*루트가 둘이상의 자식을 가지는지 검사*/
child++;
dfnlow(w, u);
/*자식의 low중 최소값*/
low[u] = low[u] < low[w] ? low[u] : low[w];
/*root이면서 child가 둘이상이거나 root가 아니면서
low(w) >=dfn(u)를 만족하면 단절점*/
if (((u == root) && (child > 1)) || ((u != root) && (dfn[u] <= low[w])))
articulation_point[u] = TRUE;
}
else if(w != v)
low[u] = low[u] < dfn[w] ? low[u] : dfn[w];
}
}
void connected(int n) {
/*그래프의 연결 요소 결정*/
int i;
for (i = 0; i if(!visited[i]) {
dfs(i);
printf("\n");
}
}
/*깊이 우선 탐색*/
void dfs(int v) {
node_pointer w;
visited[v] = TRUE;
printf("%3d", v);
for(w = graph[v]; w; w = w->link)
if(!visited[w->vertex])
dfs(w->vertex);
}
/*너비 우선 탐색*/
void bfs(int v) {
node_pointer w;
queue_pointer front, rear;
front = rear = NULL;/*initialize queue*/
printf("%3d", v);
visited[v] = TRUE;
addq(&front, &rear, v);
while(front) {
v = deleteq(&front);
for(w = graph[v]; w; w = w->link)
if(!visited[w->vertex]) {
printf("%3d", w->vertex);
addq(&front, &rear, w->vertex);
visited[w->vertex] = TRUE;
}
}
}
void addq(queue_pointer *front, queue_pointer *rear, int item) {
/*큐의 rear에 원소를 삽입*/
queue_pointer temp = (queue_pointer) malloc(sizeof(queue));
if(IS_FULL(temp)) {
fprintf(stderr, "The memory is full\n");
exit(1);
}
temp->vertex = item;
temp->link = NULL;
if(*front)
(*rear)->link = temp;
else
*front = temp;
*rear = temp;
}
int deleteq(queue_pointer *front) {
queue_pointer temp = *front;
int item;
if(IS_EMPTY(*front)) {
fprintf(stderr, "The queue is empty\n");
exit(1);
}
item = temp->vertex;
*front = temp->link;
free(temp);
return item;
}
/*그래프를 출력하는 함수*/
void print_graph(node_pointer *graph) {
int i;
node_pointer ptr;
for(i = 0; i ptr = graph[i];
printf("Head[%d] : ", i);
for(;ptr;ptr = ptr->link) {
if(!(ptr->vertex == -1)) {
printf("%4d", ptr->vertex);
}
}
printf("\n");
}
}

키워드

c로쓴자료구조론,   데이터구조,   6장,   그래프,   연습문제,   c언어