범위 우선 검색 c 언어 구현

오늘 오후 에 시간 이 있어 서 도 론 이 궁금 해서 알고리즘 서론 의 22 장의 도 론 기 초 를 보 여 주 었 습 니 다. 마지막 으로 그 강 한 연결 분량 을 보지 않 았 습 니 다. 무슨 소 용이 있 는 지 모 르 겠 습 니 다. 사용 할 때 보 세 요. 모든 것 은 취미 에 따라 가 겠 습 니 다.밤 에 두 시간 넘 게 광 도 를 우선 검색 하 는 부분 을 한 번 실현 해 보 니 기분 이 좋다.전체 과정 에서 데이터 구조 에 있어 저 는 실현 방면 의 원인 으로 공간 을 낭비 하지 않 고 이 넓 은 검색 을 실현 하려 고 노력 했 습 니 다.
    코드 를 직접 붙 이 고 나중에 코드 에 주석 을 달 아 보 세 요. 하지만 쓸데없는 말 을 많이 썼 습 니 다. 일부 개념 은 책 에 있 지만 자신 이 쓴 코드 는 가끔 잊 어 버 립 니 다.

/*************************************************************************
    > 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;
    }
}