ㅠㅠ 지식인에도 올렸는데, 여기에도 도움을 요청합니다.
지식인 내공이 필요하신 분은 지식인 답글을 달아주셔도 감사하겠습니다.. 내공 100이에유..
내공 100겁니다!!!!!!! ㅠㅠ
인접리스트를 활용한 깊이우선, 너비우선 탐색 프로그램인데요..
똑같은 코드를 복사 붙여넣기하여 c파일을 2개 생성한 뒤
메인함수 마지막 부분에 깊이우선탐색이나 너비우선탐색 항목 1개만 넣어서 실행하면 잘 되는데
한 코드에 깊이우선탐색, 너비우선탐색의 결과를 같이 보려고 하면
어떤 것이 뒤에 있던 상관 없이 뒤에 있는 탐색의 결과가 0으로 나옵니다.
그러니까
1.c -> 동일코드~~~~ 너비우선탐색실행 -> 잘나옴
2.c -> 동일코드~~~~ 깊이우선탐색실행 -> 잘나옴
1.c -> 동일코드~~~~너비우선탐색실행 깊이우선탐색실행 -> 너비우선탐색잘나옴, 깊이우선탐색 0만 나옴
..왜 이런거죠? 그래프를 2개 만들어 복사한 후 각각의 함수에 다른 그래프를 적용시켜도 마찬가지입니다
제발도와주세요.. ㅠㅠ아무리 봐도 모르겠네요
아래는 코드입니다.. 내공 최대로 걸게요
#include
#include
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
int visited[MAX_VERTICES];
typedef int element;
typedef struct QueueNode {
element item;
struct QueueNode *link;
}QueueNode;
typedef struct {
QueueNode *front, *rear;
}QueueType;
typedef struct GraphNode {
int vertex;
struct GraphNode *link;
}GraphNode;
typedef struct GraphType {
int n; //정점의 개수
GraphNode *adj_list[MAX_VERTICES];
}GraphType;
//그래프 초기화
void graph_init(GraphType *g)
{
int v;
g->n = 0;
for (v = 0; v < MAX_VERTICES; v++)
{
g->adj_list[v] = NULL;
}
}
//정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
if (((g->n) + 1) > MAX_VERTICES)
{
fprintf(stderr, "그래프 : 정점의 개수 초과");
return;
}
g->n++;
}
//간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType *g, int u, int v)
{
GraphNode *node;
if (u >= g->n || v >= g->n)
{
fprintf(stderr, "그래프: 정점 번호 오류");
return;
}
node = (GraphNode *)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
}
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
int init(QueueType *q)
{
q->front = q->rear = NULL;
}
int is_empty(QueueType *q)
{
return (q->front == NULL);
}
void is_full(QueueType *q)
{
return 0;
}
void enqueue(QueueType *q, element item)
{
QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
if (temp == NULL)
error("메모리를 할당할 수 없습니다.");
else {
temp->item = item;
temp->link = NULL;
if (is_empty(q)) {
q->front = temp;
q->rear = temp;
}
else {
q->rear->link = temp;
q->rear = temp;
}
}
}
element dequeue(QueueType *q)
{
QueueNode *temp = q->front;
element item;
if (is_empty(q))
error("큐가 비어있습니다");
else {
item = temp->item;
q->front = q->front->link;
if (q->front == NULL)
q->rear = NULL;
free(temp);
return item;
}
}
void bfs_list(GraphType *g, int v)
{
GraphNode *w;
QueueType q;
init(&q);
visited[v] = TRUE;
printf("%d ", v);
enqueue(&q, v);
while (!is_empty(&q)) {
v = dequeue(&q);
for (w = g->adj_list[v]; w; w = w->link)
if (!visited[w->vertex]) {
visited[w->vertex] = TRUE;
printf("%d ", w->vertex);
enqueue(&q, w->vertex);
}
}
printf("성공");
}
void dfs_list(GraphType *g, int v)
{
GraphNode *w;
visited[v] = TRUE;
printf("%d ", v);
for (w = g->adj_list[v]; w; w = w->link)
{
if (!visited[w->vertex])
dfs_list(g, w->vertex);
}
}
int main()
{ /*
int i;
GraphType g;
graph_init(&g);
//인접리스트 생성
for (i = 0; i < 4; i++)
{
insert_vertex(&g, i);
}
insert_edge(&g, 0, 1);
insert_edge(&g, 1, 0);
insert_edge(&g, 0, 3);
insert_edge(&g, 3, 0);
insert_edge(&g, 1, 2);
insert_edge(&g, 2, 1);
insert_edge(&g, 1, 3);
insert_edge(&g, 3, 1);
insert_edge(&g, 2, 3);
insert_edge(&g, 3, 2);
bfs_list(&g, 0);
*/
int i;
int temp1, temp2;
char temp_c, temp_c2;
GraphType g;
graph_init(&g);
FILE *fp;
fp = fopen("data.txt", "r");
if (fp == NULL)
{
printf("파일 개방 실패");
return -1;
}
while (!feof(fp))
{
fscanf(fp, "%c", &temp_c);
switch (temp_c)
{
case 'v':
fscanf(fp, "%d", &temp1);
insert_vertex(&g, temp1);
break;
case 'e':
fscanf(fp, "%d %d", &temp1, &temp2);
insert_edge(&g, temp1, temp2);
break;
case '\n':
break;
}
fscanf(fp, "%c", &temp_c);
}
printf("너비 우선 탐색 : ");
bfs_list(&g, 0);
printf("\n");
printf("깊이 우선 탐색 : ");
dfs_list(&g, 0);
printf("\n");
}
data.txt 내용
v 0
v 1
v 2
v 3
e 0 1
e 1 0
e 0 3
e 3 0
e 1 2
e 2 1
e 1 3
e 3 1
e 2 3
e 3 2
결과 :
너비 우선 탐색 : 0 3 1 2
깊이 우선 탐색 : 0
글쓰기