범위 우선 검색 c 언어 구현

6776 단어 알고리즘 서론
오늘 오후 에 시간 이 있어 서 도 론 이 궁금 해서 알고리즘 서론 의 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; } }

좋은 웹페이지 즐겨찾기