NOJ数据结构020——基于图的广度优先搜索策略

 图的广度搜索，数据结构图和队列应用的完美结合，以下是代码

#include 
#include 
#define MAX_VEXTEX_NUM 100

//弧结点数据结构
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nestArc;
}ArcNode;

//图结点数据结构
typedef struct VexNode
{
    int value;
    ArcNode *firstArc;
}VexNode;

//图数据结构——邻接表
typedef struct
{
    int vexNum, arcNum;
    VexNode vertex[MAX_VEXTEX_NUM];
    int visited[MAX_VEXTEX_NUM];
}Graph, *AdjList;

//循环队列，用于广度搜索
typedef struct
{
    VexNode element[MAX_VEXTEX_NUM+1];
    int size;
    int front;
    int rear;
}SeqQueue;


//队列初始化
void initQueue(SeqQueue *q, int Qsize)
{
    q->front = 0;
    q->rear = 0;
    q->size = Qsize;
}

//元素x入队
int enterQueue(SeqQueue *q, VexNode x)
{
    if ((q->rear + 1) % q->size == q->front) return 0;
    q->element[q->rear] = x;
    q->rear = (q->rear + 1) % q->size;
    return 1;
}

//弹出元素x
int popQTop(SeqQueue *q, VexNode *x)
{
    if (q->front == q->rear) return 0;
    *x = q->element[q->front];
    q->front = (q->front + 1) % q->size;
    return 1;
}

//判断队列是否为空
int isQEmpty(SeqQueue q)
{
    if (q.front == q.rear) return 1;
    else return 0;
}


//根据结点的值val查在图中的编号
int locate(AdjList al, int val)
{
    for (int i=0; ivexNum; i++) {
        if (al->vertex[i].value == val)
            return i;
    }
    return -1;
}

//根据输入数据创建图
void crtGraph(AdjList *al)
{
    *al = (Graph *)malloc(sizeof(Graph));
    int n, m;
    scanf("%d%d", &n, &m);
    (*al)->vexNum = n;
    (*al)->arcNum = m;
    for (int i=0; i<(*al)->vexNum; i++) {
        scanf("%d", &((*al)->vertex[i].value));
        (*al)->vertex[i].firstArc = NULL;
    }

    int v1, v2, p;
    for (int j=0; j<(*al)->arcNum; j++) {
        scanf("%d%d", &v1, &v2);
        p = locate(*al, v1);
        ArcNode *newArc = (ArcNode *)malloc(sizeof(ArcNode));
        newArc->adjvex = locate(*al, v2);
        newArc->nestArc = (*al)->vertex[p].firstArc;    //头插法
        (*al)->vertex[p].firstArc = newArc;
    }

    for (int k=0; kvisited[k] = 0;
    }
}

//广度搜索，souce和dest是源点和目标在图中的编号，用locate算
int pathSearch_BFS(AdjList al, int source, int dest)
{
    if (source == dest) return 1;

    SeqQueue q;
    initQueue(&q, al->vexNum);
    enterQueue(&q, al->vertex[source]);
    al->visited[source] = 1;
    VexNode *v0;
    ArcNode *arc;
    while (!isQEmpty(q)) {
        popQTop(&q, v0);
        arc = v0->firstArc;
        while (arc) {
            if (!al->visited[arc->adjvex]) {
                if (arc->adjvex == dest) return 1;
                al->visited[arc->adjvex] = 1;
                enterQueue(&q, al->vertex[arc->adjvex]);
            }
            arc = arc->nestArc;
        } 
    }
    return 0;
}

//输出邻接表
void printGraph(AdjList al)
{
    for (int i=0; ivexNum; i++) {
        ArcNode *arc = al->vertex[i].firstArc;
        printf("%d", al->vertex[i].value);
        while (arc) {
            printf("->%d", al->vertex[arc->adjvex].value);
            arc = arc->nestArc;
        }
        printf("n");
    }
}

int main()
{
    AdjList al;
    crtGraph(&al);
    printGraph(al);
    int source, dest;
    scanf("%d%d", &source, &dest);
    if (pathSearch_BFS(al, locate(al, source), locate(al, dest)))
        printf("yesn");
    else
        printf("non");
}

命名大多采用驼峰法命名，应该都能看懂。加上最近忙于考试所以只在函数开头有注释。

加油！！！