我的 BFS C 代码给出了错误的（绝对是胡说八道）输出

Question

这里实现的BFS算法在Cormen中有提到。但是，由于某些原因，此代码会产生无效输出，即使对于微不足道的图形也是如此。直到创建邻接列表为止的一切工作正常。

完整代码如下：

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#define size 5

struct node *nodelist = NULL;

struct node
{
    int nodeid;
    int parentid;
    int sourcedist;
    char *color;
};

struct graph *adjlist = NULL;

struct graph
{
    struct listnode *list;
    int count;
};

struct listnode
{
    int nodeid;
    struct listnode *next;
};

struct listnode *createnode(int id)
{
    struct listnode *newnode = (struct listnode *)malloc(sizeof(struct listnode));
    (*newnode).nodeid = id;
    (*newnode).next = NULL;
    return newnode;
}

int addtoadjlist(int u, int v)
{
    struct listnode *newnode = createnode(v);
    if((*(adjlist + u)).list == NULL)
    {
        (*(adjlist + u)).list  = newnode;
        (*(adjlist + u)).count++;
    }
    else
    {
        (*newnode).next = (*(adjlist + u)).list;
        (*(adjlist + u)).list = newnode;
        (*(adjlist + u)).count++;
    }
}

int disp(int totalnodes)
{
    int degreesum = 0, i;
    struct listnode *currentnode = NULL;
    for(i = 0; i < totalnodes; i++)
    {
        currentnode = (*(adjlist + i)).list;
        printf("\n node %d -> ",i);
        while(currentnode != NULL)
        {
            printf("%d -> ",(*currentnode).nodeid);
            currentnode = (*currentnode).next;
        }
        printf("NULL | Degree: %d",(*(adjlist + i)).count);
        degreesum += (*(adjlist + i)).count;
    }
    return degreesum/2;
}

int dispnodeinfo(int totalnodes)
{
    int i;
    for(i = 0; i < totalnodes; i++)
    {
        printf("\n node %d: parent %d| distance from source %d| color %c",(*(nodelist + i)).nodeid,(*(nodelist + i)).sourcedist,(*(nodelist + i)).color);   
    }
}

int *BFSQf;
int *BFSQr;

int ENQ(int x)
{
    if(BFSQr == NULL)
    {
        BFSQr = BFSQf;
        *BFSQf = x;
    }
    else
    {
        BFSQr++;
        *BFSQr = x;
    }
    return 0;
}

int DEQ()
{
    int temp;
    if(BFSQr == NULL)
        return -1;
    else if(BFSQr == BFSQf)
    {
        BFSQr = NULL;
        return *BFSQf;
    }
    else
    {
        temp = *BFSQr;
        BFSQr--;
        return temp;
    }
}

int bfs(int s)
{
    (*(nodelist + s)).color = "G";
    (*(nodelist + s)).sourcedist = 0;
    BFSQr = NULL;               //Empty the Queue;
    ENQ(s);
    while(BFSQr != NULL)
    {
        int u = DEQ();
        struct listnode *currentnode = (*(adjlist + u)).list;
        while(currentnode != NULL)
        {
            int nodeid = (*currentnode).nodeid;
            if((*(nodelist + nodeid)).color == "W")
            {
                (*(nodelist + nodeid)).color = "G";
                (*(nodelist + nodeid)).sourcedist = (*(nodelist + u)).sourcedist + 1;
                (*(nodelist + nodeid)).parentid = u;
                ENQ(nodeid);
            }
            currentnode = (*currentnode).next;
        }
        (*(nodelist + u)).color = "B";
    }
}

int main(void)
{
    int totalnodes, choice = 0, u, v, i, s;

    printf("\n Enter the number of nodes in the graph: ");
    scanf("%d",&totalnodes);

    nodelist = (struct node *)malloc(totalnodes*sizeof(struct node));
    for(i = 0; i < totalnodes; i++)
    {
        (*(nodelist + i)).nodeid = i;
        (*(nodelist + i)).parentid = INT_MIN;
        (*(nodelist + i)).sourcedist = INT_MAX;
        (*(nodelist + i)).color = "W";
    }

    adjlist = (struct garph *)malloc(totalnodes*sizeof(struct graph));
    for(i = 0; i < totalnodes; i++)
    {
        (*(adjlist + i)).list = NULL;
        (*(adjlist + i)).count = 0;
    }

    while(choice != 3)
    {
        printf("\n\n 1.) Add Edges. \n 2.) Display \n 3.) Exit. \n Enter your choice: ");
        scanf("%d",&choice);

        switch(choice)
        {
            case 1:
                    printf("\n Enter source and destination vertices for the edge (starting 0): ");
                    scanf("%d %d",&u,&v);
                    addtoadjlist(u,v);
                    //addtoadjlist(v,u);
                    break;
            case 2:
                    disp(totalnodes);
                    //printf("\n Total edges = %d ",disp(totalnodes));     only for non directed graphs.
                    break;
            case 3:
                    break;
            default:
                    printf("\n Invalid input.");
        }
    }

    BFSQf = (int *)malloc(totalnodes*sizeof(int));
    BFSQr = NULL;               // Queue Empty.

    printf("\n Enter source node to apply BFS: ");
    scanf("%d",&s);
    bfs(s);
    dispnodeinfo(totalnodes);

    return 0;
}

对于输入：6 1 0 1 1 0 3 1 1 4 1 4 3 1 3 1 1 2 4 1 2 5 1 5 5 2 3 3

我得到的邻接表是：

 node 0 -> 3 -> 1 -> NULL | Degree: 2
 node 1 -> 4 -> NULL | Degree: 1
 node 2 -> 5 -> 4 -> NULL | Degree: 2
 node 3 -> 1 -> NULL | Degree: 1
 node 4 -> 3 -> NULL | Degree: 1
 node 5 -> 5 -> NULL | Degree: 1

这是正确的。但是产生的输出是：

 node 0: parent 2147483647| distance from source 984096070| color 
 node 1: parent 1| distance from source 984096072| color 
 node 2: parent 2147483647| distance from source 984096070| color 
 node 3: parent 0| distance from source 984096072| color 
 node 4: parent 2| distance from source 984096072| color 
 node 5: parent 2147483647| distance from source 984096070| color

仅正确分配了节点ID，其余均为假值。我确实在 main() 中的初始分配之后立即调用了 displaynodeinfo()，如下所示：

   int main(void)
   {
     ....

    nodelist = (struct node *)malloc(totalnodes*sizeof(struct node));
    for(i = 0; i < totalnodes; i++)
    {
        (*(nodelist + i)).nodeid = i;
        (*(nodelist + i)).parentid = INT_MIN;
        (*(nodelist + i)).sourcedist = INT_MAX;
        (*(nodelist + i)).color = "W";
    }
    displaynodeinfo(totalnodes);
    .....
   }

在这里我仍然为 nodeids 进行了虚假分配。怎么了？请帮忙。

Answer 1

您的代码有几处错误。对于初学者，启用所有编译器警告并查看它们。在这种情况下，其中一些实际上是真正的错误。下面是对每个警告的快速解释（使用 GCC 编译时）。

因此，在尝试调试代码的运行时问题之前，请先确认您的代码没有警告。

<source>: In function 'dispnodeinfo':
<source>:78:62: warning: format '%d' expects argument of type 'int', but argument 4 has type 'char *' [-Wformat=]
         printf("\n node %d: parent %d| distance from source %d| color %c",(*(nodelist + i)).nodeid,(*(nodelist + i)).sourcedist,(*(nodelist + i)).color);
                                                             ~^                                                                  ~~~~~~~~~~~~~~~~~~~~~~~
                                                             %s

<source>:78:72: warning: format '%c' expects a matching 'int' argument [-Wformat=]
         printf("\n node %d: parent %d| distance from source %d| color %c",(*(nodelist + i)).nodeid,(*(nodelist + i)).sourcedist,(*(nodelist + i)).color);
                                                                       ~^

前两个警告已经暗示了为什么您会在输出中看到 "bogus values"。不仅格式字符串类型不匹配，而且您还缺少一个参数。

<source>: In function 'bfs':
<source>:131:45: warning: comparison with string literal results in unspecified behavior [-Waddress]
             if((*(nodelist + nodeid)).color == "W")
                                             ^~

这让您知道将指针与字符串文字进行比较不会达到您的预期。事实上，您应该在结构中使用 char，而不是 char *；然后在整个代码中使用单个字符文字而不是字符串文字（'G' 与 "G"）。

<source>: In function 'main':
<source>:160:13: warning: assignment from incompatible pointer type [-Wincompatible-pointer-types]
     adjlist = (struct garph *)malloc(totalnodes*sizeof(struct graph));
             ^

在这里，编译器会警告您类型名称 (struct garph) 中的拼写错误。

<source>: In function 'addtoadjlist':
<source>:52:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

<source>: In function 'dispnodeinfo':
<source>:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

<source>: In function 'bfs':
<source>:142:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

其余三个警告是关于您声明为 returning int 而不是 void 的函数，因为它们没有 return 任何东西。

我的 BFS C 代码给出了错误的（绝对是胡说八道）输出

My C code of BFS gives incorrect (absolute nonsense) output

c

algorithm

graph-algorithm