그래프의 간단한 DFS & BFS 탐색 프로그램

소개글

인접리스트로 구현된 그래프의 깊이 우선 탐색과 너비 우선 탐색을 수행하는 간단한 프로그램입니다.

컴파일 실행환경

Visual c++ 6.0 Console mode에서 무리없이 컴파일됩니다.

본문내용

typedef struct queue *queue_pointer;
typedef struct queue{
int vertex;
queue_pointer link;
} queue; //큐 구조체의 정의.
typedef struct node *node_pointer;
typedef struct node{
int vertex; //정점의 숫자.
int weight; //가중치 값.
node_pointer link;
} node;
node_pointer pGRAPH; //pGRAPH:그래프의 인접 리스트 헤드 노드의 대표 주소를 할당받게 될 구조체 포인터 변수.
int *pnVISITED; //정점 방문을 기록하기 위한 공간을 가리키는 포인터 변수.

void dfs(int v); //그래프의 정점 v에서 시작하는 깊이 우선 탐색 함수.
void bfs(int v); //그래프의 정점 v에서 시작하는 너비 우선 탐색 함수.
int deleteq(queue_pointer *front); //동적 큐의 delete함수.
void addq(queue_pointer *front,queue_pointer *rear, int vertex); //동적 큐의 add함수.
void free_space(node_pointer pGRAPH, int *pnVISITED, int nVERTEX);//프로그램 종료 직전 동적 할당된 메모리를 시스템에 반납.

int main(void){
node_pointer w; //pGRAPH:그래프의 인접 리스트 헤드 노드의 대표 주소를 할당받게 될 이중 구조체 포인터 변수.
int nVERTEX,nStart_v; //nVERTEX:정점의 개수를 담는 변수. nStart_v:시작 정점을 담을 변수.
int nTAIL,nHEAD,nWEIGHT; //그래프 정보 입력시 사용되는 변수.
int i=0,j=0;
int nSELECT; //탐색 방법을 결정하기 위한 변수.

참고 자료

없음