图的广度优先遍历

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<stdbool.h>
#define MaxSize 20
typedef struct Node{
    char vex;
    int location;
    struct Node * next; 
}MapNode; 
int node_num;
int visited[MaxSize];

//创建用于广度优先遍历的队列
typedef struct QNode
{
    char data;
    struct QNode *qnext;
}QNode,*PQNode;


typedef struct Queue{
        PQNode front;
        PQNode rear;
}Queue,*PQueue;

PQueue initQueue(){
        PQueue pqueue = (PQueue)malloc(sizeof(Queue));
        PQNode pqnode = (PQNode)malloc(sizeof(QNode));
        if(pqnode==NULL){
                printf("队列头空间申请失败\n");
                exit(-1);
        }
        pqueue->front = pqueue->rear = pqnode;
        pqnode->qnext = NULL;
        return pqueue;
}

void enQueue(PQueue pqueue,char data){
        PQNode pqnode = (PQNode)malloc(sizeof(PQNode));
        if(pqnode==NULL){
                printf("队列结点申请失败");
        }
    pqnode->data = data;
    pqnode->qnext = NULL;
    pqueue->rear->qnext = pqnode;
    pqueue->rear = pqnode;
}

bool isEmpty(PQueue pqueue){
    if(pqueue->front == pqueue->rear){
        return true;
    }
    return false;
}

char deQueue(PQueue pqueue){
    if(isEmpty(pqueue)){
        printf("队列为空\n");
        exit(-1);
    }
    PQNode pqnode = pqueue->front->qnext;
    pqueue->front->qnext = pqnode->qnext;
    if(pqnode==pqueue->rear){
        pqueue->rear = pqueue->front;
    }
    char data = pqnode->data;
    free(pqnode);
    return data;
}

void createMap(MapNode **p ){
    char ch;
    int i=0;
    MapNode * q,* new_node;
    (*p) = (MapNode *)malloc(sizeof(MapNode)*MaxSize);
    printf("请输入图的节点:\n");
    scanf("%c",&ch);
    while(ch!='\n'){
        (*p)[i].vex = ch;
        (*p)[i].next = NULL;
        (*p)[i].location = i;
        i++;
        scanf("%c",&ch);
    }
    node_num = i;

    for(i=0;i<node_num;i++){
        q = (*p)+i;
        printf("请输入%c的邻接节点:\n",q->vex);
        scanf("%c",&ch);
        while(ch!='\n'){
             new_node = (MapNode *)malloc(sizeof(MapNode));
            new_node->vex = ch;
            new_node->next = NULL;
            q->next = new_node;
            q = new_node;
            scanf("%c",&ch);
        }
    }
}

int get_index(MapNode *p,char v){
    int i;
    for(i=0;i<node_num;i++){
        if(p[i].vex ==v){
            return i;
        }
    }
    return -1;

}

void depth(MapNode *p,int i){
    MapNode *q;
    q = p+i;
    printf("%c ",q->vex);
    visited[i] = 1;
    q= q->next;
    while(q){
        int index = get_index(p,q->vex);
        if(visited[index]==0){
            depth(p,index);
        }
        q = q->next;
    }
}


void print_depth(MapNode *p){
    int i;
    for(i=0;i<node_num;i++){
        visited[i] = 0; 
    }
    printf("图的深度遍历:\n");
    for(i=0;i<node_num;i++){
        if(visited[i]==0){
            depth(p,i);
        }
    }
}


void print_beef(MapNode *p){
    int i;
    MapNode *q;
    char v;
    MapNode *new_node,*node;
    int index;
    for(i=0;i<node_num;i++){
        visited[i] = 0;
    }
    printf("图的广度遍历:\n");
    PQueue pqueue = initQueue();
    for(i=0;i<node_num;i++){
        if(visited[i]==0){
            visited[i] = 1;
            q = p+i;
            printf("%c ",q->vex);
            enQueue(pqueue,i);
            while(!isEmpty(pqueue)){
                v = deQueue(pqueue);
                //index = get_index(p,v);
                new_node = p+v;
                for(node=new_node->next;node!=NULL;node=node->next){
                    index = get_index(p,node->vex); 
                    if(visited[index]==0){
                        printf("%c ",node->vex);
                        visited[index] = 1;
                        enQueue(pqueue,index);
                    }
                }           
            }
        }
    }
}

void print(MapNode *p){
    printf("图的邻接表:\n");
    int i;
    MapNode *q;
    for(i=0;i<node_num;i++){
        printf("%c:",p[i].vex);
        q = p[i].next;
        while(q){
            printf("%c->",q->vex);
            q = q->next;
        }
        printf("\n");
    }
}

int main(){
    MapNode *p;
    createMap(&p);
    print(p);
    print_beef(p);
    return 0;
}

如下图显示

image.png