基于Cormen的C语言BFS代码输出异常问题求助

Hey there, let's work through those weird output issues with your BFS code! I notice your code snippet cuts off mid-definition, but even from what's provided, I can point out some common pitfalls that are likely causing the nonsensical results. Let's break them down:

1. Problem with String-Based Color Tracking #

Your struct node uses a char *color field, which is a risky choice here. If you're assigning string literals (like "WHITE") without proper memory management, or leaving the pointer uninitialized, you're inviting undefined behavior—this could easily lead to garbage values or crashes.

Fix: Swap the string pointer for an enum instead. It's faster, safer, and eliminates memory headaches:

typedef enum { WHITE, GRAY, BLACK } Color;

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

2. Uninitialized Struct Pointers #

You've declared struct node *nodelist = NULL; and struct graph *adjlist = NULL;, but if you don't allocate memory for these before using them, any access will trigger undefined behavior. For example, nodelist needs to be an array of nodes matching your graph's size:

Fix: Initialize your node list with proper memory allocation and default values:

nodelist = malloc(size * sizeof(struct node));
if (nodelist == NULL) {
    perror("Failed to allocate memory for node list");
    exit(EXIT_FAILURE);
}

// Set default values for each node
for (int i = 0; i < size; i++) {
    nodelist[i].nodeid = i;
    nodelist[i].parentid = -1; // Use -1 to represent no parent
    nodelist[i].sourcedist = INT_MAX;
    nodelist[i].color = WHITE;
}

3. Potential Queue Implementation Flaws #

BFS lives or dies by a correctly implemented queue. If your queue has bugs—like trying to dequeue from an empty queue, overflowing a fixed-size queue, or mismanaging pointers—it'll completely break the traversal order and produce garbage output.

Example Safe Queue Structure (Linked List Version):

struct queueNode {
    int vertex;
    struct queueNode *next;
};

struct Queue {
    struct queueNode *front, *rear;
};

// Helper functions for queue operations
struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(struct Queue* q, int v) {
    struct queueNode* newNode = malloc(sizeof(struct queueNode));
    newNode->vertex = v;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

int dequeue(struct Queue* q) {
    if (q->front == NULL) return -1; // Indicate empty queue
    struct queueNode* temp = q->front;
    int v = temp->vertex;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return v;
}

int isQueueEmpty(struct Queue* q) {
    return q->front == NULL;
}

4. Incomplete Adjacency List Structure #

Your struct graph definition cuts off, but a proper adjacency list needs to track a list of neighbors for each vertex. Here's what the complete structure should look like, plus initialization code:

Fix:

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

struct graph {
    struct listnode** list; // Array of linked list heads
    int numVertices;
};

// Initialize adjacency list
adjlist = malloc(sizeof(struct graph));
adjlist->numVertices = size;
adjlist->list = malloc(size * sizeof(struct listnode*));
for (int i = 0; i < size; i++) {
    adjlist->list[i] = NULL;
}

Final Checks to Perform #

Since your full code is incomplete, make sure your BFS function follows these core steps from Cormen's algorithm:

• Start by enqueuing the source node, setting its distance to 0, color to GRAY, and parent to -1
• While the queue isn't empty, dequeue a node and iterate through all its adjacent vertices
• For each adjacent vertex that's still WHITE, update its parent, distance, set color to GRAY, then enqueue it
• Avoid out-of-bounds array access (critical since you're using a fixed size define)

内容的提问来源于stack exchange，提问作者PKBEST