N—E—E 2021-10-28 11:50 采纳率: 59.5%
浏览 35
已结题

这个用邻接表写的BFS哪里错了?

输入的图是:
0 4
0 5
0 1
0 2
2 3
1 3
5 6
权重都是1
输出中3号节点没有被访问而且报错了

#include "Gragh-link.h"
#include "Queue.h"
#include "stdbool.h"

Gragh Initialize(int VerNum){
    Gragh G = (Gragh)malloc(sizeof(struct LGragh));
    G->Nv = VerNum;
    G->Ne = 0;
    for (int i = 0;i < G->Nv-1;i++)
    {
        G->NodeList[i].First = NULL;
    }
    return G;
}
void InsertEdge(Gragh G,Edge E)
{
    PtrToAdjNode NewNode0 = (PtrToAdjNode)malloc(sizeof(struct AdjNode));
    NewNode0->Weight = E->Weight;
    NewNode0->VAdj = E->V2;
    //下面开始插入,插到表头后面
    NewNode0->Next = G->NodeList[E->V1].First;
    G->NodeList[E->V1].First = NewNode0;
    //若为无向图,还要执行以下代码
    PtrToAdjNode NewNode1 = (PtrToAdjNode)malloc(sizeof(struct AdjNode));
    NewNode1->Weight = E->Weight;
    NewNode1->VAdj = E->V1;

    NewNode1->Next = G->NodeList[E->V2].First;
    G->NodeList[E->V2].First = NewNode1;

}
Gragh BuildGragh(){
    int Nv,Ne;
    Edge E;
    do
    {
        printf("Please enter a number less than 100:");
        scanf("%d",&Nv);
    } while (Nv >= 100);
    Gragh G = Initialize(Nv);

    printf("Input the number of edges:");
    scanf("%d",&Ne);
    G->Ne = Ne;
    if (G->Ne != 0)
    {
        E = (Edge)malloc(sizeof(struct ENode));
        printf("please add edges for your gragh.format:Vec1 Vec2 Weight.\n");
        for (int i = 0;i < G->Ne;i++)
        {
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
            InsertEdge(G,E);
        }
        
    }
    /*以下是可选的数据录入*/
    //printf("Please add data for each vertex.");
    //for (int i = 0;i < G->Nv;i++)
    //{
    //    scanf("%s",G->NodeList[i].data[i]);
    //} 
    return G;       
}

PtrToQ queue_init()
{
    PtrToQ q = (PtrToQ)malloc(sizeof(struct queue));
    q->front = q->rear = 0;
    return q;
}
 
 
 
int queue_empty(PtrToQ q)
{
    return q->front == q->rear;
}
 
 
int queue_en(PtrToQ q, datatype e)
{
    /* 队满 */
    if (q -> rear == MAX_QUEUE_SIZE)
        return false;
 
    /* 入队 */
    q -> sp_queue_array[q -> rear] = e;
    q -> rear += 1;
    return true;
 
}
 
 
datatype queue_de(PtrToQ q)
{
    /* 队空 */
    if(queue_empty(q))
        return false;
 
    /* 出队 */
    datatype element = q->sp_queue_array[q->front];
    q->front += 1;
    return element;
}
 
 
void queue_clear(PtrToQ q)
{
    q -> front = q -> rear = 0;
}
 
 
int queue_len(PtrToQ q)
{
    return (q->rear - q->front);
}
 
 
void queue_traverse(PtrToQ q, void (*visit)(PtrToQ q))
{
    visit(q);
}
 
void visit(PtrToQ q)
{
    /* 队空 */
    if (q->front == q->rear)
        printf("队列为空\n");
 
    int temp = q->front;
    while(temp != q->rear)
    {
        printf("%d ",q->sp_queue_array[temp]);
        temp += 1;
    }
    printf("\n");
}





bool visited[MaxVerNum];
void visiting(Vertex V);

int main(){
    for (int i = 0;i < MaxVerNum;i++)
    visited[i] = false;
    Gragh G = BuildGragh();
    BFS(G,0,visiting);
    system("pause");
    return 0;
}


void BFS(Gragh G,Vertex V, void (*visiting)(Vertex));
void visiting(Vertex V){
    printf("visiting vertex %d now.",V);
}
void BFS(Gragh G,Vertex V, void (*visiting)(Vertex)){
    PtrToAdjNode S,W;
    PtrToQ Q = queue_init();
    
    queue_en(Q,V);
    while (!queue_empty(Q))
    {
        V = queue_de(Q);
        visiting(V);
        visited[V] = true;
        S = G->NodeList[V].First;
        while (S)
        {
            if (!visited[S->VAdj])
                queue_en(Q,S->VAdj);
            S = S->Next;
        }

    }

}

img

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 11月5日
    • 创建了问题 10月28日

    悬赏问题

    • ¥15 关于#python#的问题:求帮写python代码
    • ¥20 MATLAB画图图形出现上下震荡的线条
    • ¥15 LiBeAs的带隙等于0.997eV,计算阴离子的N和P
    • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
    • ¥15 来真人,不要ai!matlab有关常微分方程的问题求解决,
    • ¥15 perl MISA分析p3_in脚本出错
    • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
    • ¥15 ubuntu虚拟机打包apk错误
    • ¥199 rust编程架构设计的方案 有偿
    • ¥15 回答4f系统的像差计算