删除图中重复边的BFS实现异常求助：函数无效与段错误

我需要处理图中的重复出边：每个顶点允许有多条指向同一终点的出边，边的属性为距离-成本-时间（括号内数字顺序），要求删除同一终点下耗时更长的边，只保留耗时最短的。比如示例第一行中，3→2的两条边里，要删除耗时45小时的那条。

示例邻接表：

### 3 -> 2 (50-300-40) ---> 2 (55-450-45) ---> 4 (45-450-45) ---> 4 (75-600-60) ---> 1 (40-450-40) ---> 1 (85-750-90) ---> NULL
### 2 -> 1 (50-450-45) ---> 3 (45-300-30) ---> 4 (80-700-80) ---> NULL
### 4 -> 2 (55-535-60) ---> 3 (75-545-65) ---> 4 (20-200-20) ---> NULL

我编写了以下C语言代码，尝试通过BFS遍历图并调用delete_edge实现需求，但单独调用delete_edge无法修改图，且BFS调用时出现段错误，请求排查：

void delete_edge(graph *g, int source_no, int dest_no) {
    // Find the source vertex
    node *source_vertex = &g->heads[source_no];
    list_node *current = source_vertex->head;
    list_node *prev = NULL;

    // Create a new adjacency list
    list_node *new_head = NULL;
    list_node *new_tail = NULL;

    // Traverse the adjacency list of the source vertex
    while (current != NULL) {
        if (current->index_of_item == dest_no) {
            // Found the edge to delete, skip it
            list_node *temp = current;
            current = current->next;
            free(temp);

            if (prev != NULL) {
                prev->next = current;
            } else {
                source_vertex->head = current;
            }
        } else {
            // Add the current edge to the new adjacency list
            if (new_head == NULL) {
                new_head = current;
                new_tail = current;
            } else {
                new_tail->next = current;
                new_tail = current;
            }

            prev = current;
            current = current->next;
        }
    }

    // Set the next pointer of the new tail to NULL
    if (new_tail != NULL) {
        new_tail->next = NULL;
    }
}



void bfs_delte_version(graph *g) {
    // Initialize the color of all vertices as White
    for (int i = 0; i < g->number_of_vertices; i++) {
        g->heads[i].color = White;
    }

    // Start BFS from the first node (source)
    node *source = &g->heads[0];
    source->color = Gray;

    queue *q = make_queue();
    enqueue(q, source);

    while (!is_empty_queue(q)) {
        queue_node *u = dequeue(q);
        list_node *temp = u->n->head;

        while (temp != NULL) {
            if (g->heads[temp->index_of_item].color == White) {
                g->heads[temp->index_of_item].color = Gray;
                enqueue(q, &g->heads[temp->index_of_item]);
            } else {
                // Delete multiple occurring edges
                delete_edge(g, u->n->data, temp->index_of_item);
            }

            temp = temp->next;
        }

        u->n->color = Black;
        printf("%d\n", u->n->data);
    }
}

问题排查与修复 #

1. delete_edge函数的核心问题 #

• 逻辑冲突：同时在原链表上执行删除操作（free节点、修改prev->next），又尝试构建新链表，两种操作互相干扰，导致链表结构混乱，无法正确修改图。
• 需求不符：当前逻辑是删除所有指向dest_no的边，而不是保留耗时最短的边，完全违背需求。
• 未更新表头：构建新链表后，没有将source_vertex->head指向new_head，导致修改无法生效。

2. BFS函数的段错误原因 #

• 遍历链表时修改链表：在遍历temp指针的过程中调用delete_edge，会free当前正在遍历的节点或修改链表的next指针，导致temp = temp->next访问已释放的内存，触发段错误。
• 顶点编号不匹配：如果u->n->data（顶点编号）与g->heads的索引不对应，会导致访问数组越界，引发段错误。
• 内存泄漏/野指针：队列节点u未释放，可能导致内存泄漏；若队列实现存在问题，也可能产生野指针。

3. 修复方案 #

重写边处理函数（实现保留最短时间边）

先统计每个终点的最短耗时，再重新构建链表，只保留符合条件的边：

#include <limits.h>

// 保留source顶点指向每个终点的最短时间边，删除其余更长的边
void keep_min_time_edges(graph *g, int source_idx) {
    node *source_vertex = &g->heads[source_idx];
    list_node *current = source_vertex->head;
    int min_time[g->number_of_vertices];

    // 初始化所有终点的最短时间为最大值
    for (int i = 0; i < g->number_of_vertices; i++) {
        min_time[i] = INT_MAX;
    }

    // 第一步：遍历邻接表，记录每个终点的最短耗时
    while (current != NULL) {
        int dest_idx = current->index_of_item;
        if (current->time < min_time[dest_idx]) { // 假设list_node有time字段存储耗时
            min_time[dest_idx] = current->time;
        }
        current = current->next;
    }

    // 第二步：重新构建邻接表，只保留耗时等于最短时间的边
    list_node *new_head = NULL;
    list_node *new_tail = NULL;
    current = source_vertex->head;

    while (current != NULL) {
        list_node *next_node = current->next; // 先保存下一个节点，避免free后丢失
        int dest_idx = current->index_of_item;

        if (current->time == min_time[dest_idx]) {
            // 保留这条边
            if (new_head == NULL) {
                new_head = current;
                new_tail = current;
                new_tail->next = NULL;
            } else {
                new_tail->next = current;
                new_tail = current;
                new_tail->next = NULL;
            }
        } else {
            // 删除这条边
            free(current);
        }
        current = next_node;
    }

    // 更新source顶点的邻接表头
    source_vertex->head = new_head;
}

修改BFS逻辑（避免遍历中修改链表）

先处理当前节点的所有重复边，再遍历处理后的邻接表：

void bfs_process_edges(graph *g) {
    // 初始化所有顶点颜色为White
    for (int i = 0; i < g->number_of_vertices; i++) {
        g->heads[i].color = White;
    }

    queue *q = make_queue();
    node *source = &g->heads[0];
    source->color = Gray;
    enqueue(q, source);

    while (!is_empty_queue(q)) {
        queue_node *u = dequeue(q);
        node *current_node = u->n;

        // 先处理当前节点的重复边，保留最短时间的
        keep_min_time_edges(g, current_node->data); // 注意：若current_node->data不是heads索引，需调整为对应索引

        // 遍历处理后的邻接表，继续BFS
        list_node *temp = current_node->head;
        while (temp != NULL) {
            int dest_idx = temp->index_of_item;
            if (g->heads[dest_idx].color == White) {
                g->heads[dest_idx].color = Gray;
                enqueue(q, &g->heads[dest_idx]);
            }
            temp = temp->next;
        }

        current_node->color = Black;
        printf("%d\n", current_node->data);
        free(u); // 释放队列节点，避免内存泄漏
    }
    free(q); // 释放队列结构
}

关键注意点 #

• 确保list_node结构体包含time字段，存储边的耗时；若字段名不同，需对应修改。
• 确认顶点编号与g->heads数组的索引对应，若不对应，需调整keep_min_time_edges的参数为正确的索引值。
• 队列实现需正确管理内存，make_queue、enqueue、dequeue、is_empty_queue需保证无内存泄漏和野指针。

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