범위 우선 검색 c 언어 구현
6776 단어 알고리즘 서론
코드 를 직접 붙 이 고 나중에 코드 에 주석 을 달 아 보 세 요. 하지만 쓸데없는 말 을 많이 썼 습 니 다. 일부 개념 은 책 에 있 지만 자신 이 쓴 코드 는 가끔 잊 어 버 립 니 다.
/*************************************************************************
> File Name: graph.c
> Author: jeff zhu
> Mail: [email protected]
> Created Time: 2016 09 04 18 58 08
************************************************************************/
#include
#include
#include
#define MAXSIZE 100 // 100,
#define WHITE 1 // , , , , 。
#define GRAY 2
#define BLACK 3
#define INFINITE INT_MAX //
typedef struct gra_ptr_node { // , ( , , )
struct gra_ptr_node *next;
struct graph_node *ptr;
}PTR_NODE;
typedef struct graph_node { // ,parent ,nect ,key ,d ,f //
struct graph_node *parent;
struct graph_node *next;
int key;
int d;
int f;
int color;
}NODE;
typedef struct graph { // ,length adj
PTR_NODE *adj[MAXSIZE];
int length;
}GRAPH;
typedef struct stack_of_granode { // BFS
NODE *arr_temp[MAXSIZE];
int start;
int end;
int length;
int count;
}NODEQUEUE;
NODE *arr_V[MAXSIZE]; // ,
void BFS (GRAPH *G , NODE *s) ;
void init_graph (GRAPH *G , int len) ;
NODE *create_and_init_node (int key) ;
void insert_to_adj (GRAPH *G , NODE *x , int key) ;
void init_queue (NODEQUEUE *Q , GRAPH *G) ;
void enqueue (NODEQUEUE *Q , NODE *x) ;
NODE *dequeue (NODEQUEUE *Q) ;
void BFS (GRAPH *G , NODE *s) ;
int main () {
int i;
int count = 0;
GRAPH G;
NODE *temp;
NODE *temp1;
PTR_NODE *ptr_temp;
NODEQUEUE Q; // BFS ,
init_queue (&Q , &G);
init_graph (&G , 8); //
temp = create_and_init_node (0); // , 《 》 22-3
arr_V[count++] = temp;
insert_to_adj (&G , temp , 1);
temp = create_and_init_node (1);
arr_V[count++] = temp;
insert_to_adj (&G , temp , 0);
insert_to_adj (&G , temp , 2);
temp = create_and_init_node (2);
temp1 = temp;
arr_V[count++] = temp;
insert_to_adj (&G , temp , 1);
insert_to_adj (&G , temp , 3);
temp = create_and_init_node (3);
arr_V[count++] = temp;
insert_to_adj (&G , temp , 2);
insert_to_adj (&G , temp , 4);
insert_to_adj (&G , temp , 5);
temp = create_and_init_node (4);
arr_V[count++] = temp;
insert_to_adj (&G , temp , 3);
insert_to_adj (&G , temp , 5);
insert_to_adj (&G , temp , 6);
insert_to_adj (&G , temp , 7);
temp = create_and_init_node (5);
arr_V[count++] = temp;
insert_to_adj (&G , temp , 3);
insert_to_adj (&G , temp , 4);
insert_to_adj (&G , temp , 6);
temp = create_and_init_node (6);
arr_V[count++] = temp;
insert_to_adj (&G , temp , 5);
insert_to_adj (&G , temp , 4);
insert_to_adj (&G , temp , 7);
temp = create_and_init_node (7);
arr_V[count++] = temp;
insert_to_adj (&G , temp , 6);
insert_to_adj (&G , temp , 4); //
for (i = 0 ; i < 8 ; i++) {
ptr_temp = G.adj[i];
while (ptr_temp != NULL) {
printf ("%d " , ptr_temp->ptr->key);
ptr_temp = ptr_temp->next;
}
printf ("
");
} // ,
printf ("
");
BFS (&G , temp1); // BFS
for (i = 0 ; i < count ; i++) {
printf ("%d " , arr_V[i]->d);
}
printf ("
");
}
void init_graph (GRAPH *G , int len) { //
int i;
G->length = len;
for (i = 0 ; i < len ; i++) {
G->adj[i] = NULL;
}
}
NODE *create_and_init_node (int key) { //
NODE *temp = (NODE *) malloc (sizeof (NODE));
temp->key = key;
temp->d = 0;
temp->f = 0;
temp->next = NULL;
temp->parent = NULL;
return temp;
}
void insert_to_adj (GRAPH *G , NODE *x , int key) { // 。
if (key >= G->length) {
printf ("the key is too big");
return;
}
PTR_NODE *temp;
temp = (PTR_NODE *) malloc (sizeof (PTR_NODE));
temp->next = G->adj[key];
temp->ptr = x;
G->adj[key] = temp;
}
void init_queue (NODEQUEUE *Q , GRAPH *G) { // BFS Q。
Q->start = 0;
Q->end = 0;
Q->length = G->length;
Q->count = 0;
}
void enqueue (NODEQUEUE *Q , NODE *x) { // x Q 。 ,Q->count 1。
if (((Q->end+1) % Q->length) == Q->start)
return;
else {
Q->arr_temp[Q->end] = x;
Q->end++;
if (Q->end == Q->length)
Q->end = 0;
Q->count++;
}
}
NODE *dequeue (NODEQUEUE *Q) { // Q->arr[Q->start], 。 ,Q->count 1。
NODE *temp;
if (Q->start == Q->end)
return;
else {
temp = Q->arr_temp[Q->start];
Q->start++;
if (Q->start == Q->length)
Q->start = 0;
Q->count--;
}
return temp;
}
void BFS (GRAPH *G , NODE *s) { // , , ,
int i;
NODEQUEUE Q;
init_queue (&Q , G);
NODE *temp;
PTR_NODE *ptr_temp;
for (i = 0 ; i < G->length ; i++) {
if (arr_V[i] != s) {
arr_V[i]->color = WHITE;
arr_V[i]->d = INFINITE;
arr_V[i]->parent = NULL;
}
}
s->color = GRAY;
s->parent = NULL;
s->d = 0;
enqueue (&Q , s);
while (Q.count != 0) {
temp = dequeue (&Q);
ptr_temp = G->adj[temp->key];
while (ptr_temp != NULL) {
if (ptr_temp->ptr->color == WHITE) {
ptr_temp->ptr->color = GRAY;
ptr_temp->ptr->d = temp->d + 1;
ptr_temp->ptr->parent = temp;
enqueue (&Q , ptr_temp->ptr);
}
ptr_temp = ptr_temp->next;
}
temp->color = BLACK;
}
}