묻고답하기
Graph class에서 함수 구현하기 질문입니다
2011.06.02 13:35
안녕하십니까.. 고수님들 도움부탁 드립니다..
c/c++ 언어에 대해 아직 개념도 파악 못하고 있습니다..
열공을 하고자 하는데. 한숨만 나오네요....많은 도움 부탁 드릴께요.. ㅠㅠ
제발 플리즈~
--문제--
아래에 첨부한 source code를 확인해 보면 Graph class에서 구현이 안된 함수가 다음과 같이 4개 있습니다.
void dfs (int i)
void bfs (int i)
void floyd (int val[][NO_NODE])
void topo_sort ()
이 4개의 함수를 구현해야 되는데요.. 잘 모르겠습니다. ㅠㅜ
제발 고수님들의 도움에 손길을 제게 부탁 드려요~
--소스--
#include <stdio.h>
#defineNO_NODE6// graph 안에 포함된 node의 개수
#defineINF999999// distance의 무한대 값, 즉 이 값을 갖는 link는 끊어진 link임
class cGraph// adjacent matrix로 구현한 digraph
{
public:
intdist[NO_NODE][NO_NODE];// dist[i][j]는 node i에서 node j로의 link의 distance를 의미
intvisited[NO_NODE];// 처리 결과를 저장할 array
voidset_dist (int val[][NO_NODE])// 2차원 array *val[]의 element val[i][j]를 dist[i][j]에 copy
{
for (int i = 0; i < NO_NODE; i++)
for (int j = 0; j < NO_NODE; j++)
dist[i][j] = val[i][j];
}
voidprint_dist (FILE *fp)
{
fprintf(fp,"[Dist]\n");
for (int i = 0; i < NO_NODE; i++)
{
for (int j = 0; j < NO_NODE; j++)
fprintf(fp,"\t%d",dist[i][j]);
fprintf(fp,"\n");
}
fprintf(fp,"\n");
}
voidprint_val (FILE *fp, int val[][NO_NODE])
{
fprintf(fp,"[Val]\n");
for (int i = 0; i < NO_NODE; i++)
{
for (int j = 0; j < NO_NODE; j++)
fprintf(fp,"\t%d",val[i][j]);
fprintf(fp,"\n");
}
fprintf(fp,"\n");
}
voidprint_visited (FILE *fp)
{
fprintf(fp,"[Visited]\n");
for (int i = 0; i < NO_NODE; i++)
fprintf(fp,"\t%d",visited[i]);
fprintf(fp,"\n\n");
}
voiddfs (int i)// to be implemented
{// node i로 부터 시작해서 깊이 우선 탐색을 하고, 방문한 node의 번호를 visited array에 차례로 기록
}
voidbfs (int i)// to be implemented
{// node i로 부터 시작해서 넓이 우선 탐색을 하고, 방문한 node의 번호를 visited array에 차례로 기록
}
voidfloyd (int val[][NO_NODE])// to be implemented
{// Floyd의 최단 경로 알고리즘을 적용해서 node i에서 node j로의 최단 경로의 disatnce를 val[i][j]에 기록
}
voidtopo_sort ()// to be implemented
{// topological sorting을 하면서 제거한 node의 번호를 visited array에 차례로 기록
}
};
voidmain ()
{
FILE*fp = fopen("log.txt","w");
cGraphgraph;
// test
intval[NO_NODE][NO_NODE] = {{0, INF, 10, 20, INF, INF},
{INF, 0, INF, 15, 30, INF},
{INF, INF, 0, INF, INF, 5},
{INF, INF, INF, 0, INF, 7},
{INF, INF, INF, INF, 0, 10},
{INF, INF, INF, INF, INF, 0}};
graph.set_dist(val);
graph.print_dist(fp);
graph.dfs(0);
graph.print_visited(fp);
graph.bfs(0);
graph.print_visited(fp);
graph.floyd(val);
graph.print_val(fp,val);
graph.topo_sort();
graph.print_visited(fp);
fclose(fp);
}
메일주소는 omylov2@nate.com