使用BFS消除有向图循环的代码修正求助

看起来你想用BFS来移除有向图中的环，最终得到一个DAG，但你的代码里有几个关键逻辑错误导致结果不对。我来帮你梳理问题并修正代码：

原代码的核心问题 #

• 索引混淆：你的节点data是1-based（比如节点1、2），但heads数组是0-based，在bfs函数里处理访问标记和节点索引时多次出错，比如visited[neighbor-1]，而neighbor已经是heads数组的0-based索引，不需要额外减1。
• 错误的环检测逻辑：你直接删除指向所有已访问节点的边，但已访问的Black节点是已经处理完的，只有遇到处于Gray状态的节点（当前BFS路径中的节点）才代表出现了环，删除这些边才是正确的。
• 边删除方式错误：删除邻接表中的边时，你直接把head指向temp->next，这会误删当前节点前面的所有边，应该用prev指针跟踪链表，精准删除目标边。
• 找到终点后提前终止：你找到end节点后就break了，没有继续处理整个图的其他环，不符合“移除所有环直到变成DAG”的需求。
• 重复的访问标记：同时使用visited数组和color枚举，逻辑混乱，应该统一用color来跟踪节点状态（White=未访问，Gray=正在访问，Black=已处理）。

修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>

enum color { White, Gray, Black };

typedef struct list_node {
    int index;
    int time;
    int distance;
    int cost;
    struct list_node* next;
} list_node;

typedef struct node {
    int data;
    enum color color;
    list_node* head;
} node;

typedef struct graph {
    int nVertices;
    node heads[];
} graph;

typedef struct Edge {
    int source;
    int dest;
    int time;
    int distance;
    int cost;
} Edge;

Edge edgeList[100];  // Maximum 100 edges (change the size accordingly)
int edgeCount = 0;  // Number of edges added

node* new_node(int data) {
    node* z = (node*)malloc(sizeof(node));
    z->data = data;
    z->head = NULL;
    z->color = White;
    return z;
}

list_node* new_list_node(int item_index, int time, int distance, int cost) {
    list_node* z = (list_node*)malloc(sizeof(list_node));
    z->index = item_index;
    z->time = time;
    z->distance = distance;
    z->cost = cost;
    z->next = NULL;
    return z;
}

graph* new_graph(int nVertices) {
    graph* g = (graph*)malloc(sizeof(graph) + (nVertices * sizeof(node)));
    g->nVertices = nVertices;
    int i;
    for (i = 0; i < nVertices; i++) {
        node* z = new_node(-1);
        g->heads[i] = *z;
    }
    return g;
}

void add_node_to_graph(graph* g, int data) {
    node* z = new_node(data);
    int i;
    for (i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data < 0) {
            g->heads[i] = *z;
            break;
        }
    }
}

int in_graph_head_list(graph* g, int data) {
    int i;
    for (i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data == data)
            return 1;
    }
    return 0;
}

void printgraph(graph* g) {
    int i;
    for (i = 0; i < g->nVertices; i++) {
        node* curr_node = &(g->heads[i]);
        if (curr_node->data < 0) continue; // Skip empty slots
        printf("Node %d: ", curr_node->data);
        list_node* temp = curr_node->head;
        if (temp == NULL) {
            printf("No adjacent nodes.\n");
        } else {
            while (temp != NULL) {
                int adjacent_vertex = g->heads[temp->index].data;
                printf("%d (T=%d, D=%d, C=%d)", adjacent_vertex, temp->time, temp->distance, temp->cost);
                temp = temp->next;
                if (temp != NULL) {
                    printf(" --> ");
                }
            }
            printf("\n");
        }
    }
}

void AddEdges(graph* g, int source, int dest, int time, int distance, int cost) {
    if (!in_graph_head_list(g, source)) {
        add_node_to_graph(g, source);
    }
    if (!in_graph_head_list(g, dest)) {
        add_node_to_graph(g, dest);
    }

    int i, j;
    for (i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data == source) {
            int indexDest = -1;
            for (j = 0; j < g->nVertices; j++) {
                if (g->heads[j].data == dest) {
                    indexDest = j;
                    break;
                }
            }
            if (indexDest != -1) {
                list_node* n = new_list_node(indexDest, time, distance, cost);
                if (g->heads[i].head == NULL) {
                    g->heads[i].head = n;
                } else {
                    list_node* temp = g->heads[i].head;
                    while (temp->next != NULL) {
                        temp = temp->next;
                    }
                    temp->next = n;
                }
                edgeList[edgeCount].source = source;
                edgeList[edgeCount].dest = dest;
                edgeList[edgeCount].time = time;
                edgeList[edgeCount].distance = distance;
                edgeList[edgeCount].cost = cost;
                edgeCount++;
            }
            break;
        }
    }
}

// Queue implementation (reused correctly this time)
typedef struct queue_node {
    node *n;
    struct queue_node *next;
} queue_node;

typedef struct queue {
    int count;
    queue_node *front;
    queue_node *rear;
} queue;

int is_empty_queue(queue *q) {
    return !(q->count);
}

void enqueue(queue *q, node *n) {
    queue_node *new_queue_node = malloc(sizeof(queue_node));
    new_queue_node->n = n;
    new_queue_node->next = NULL;
    if (!is_empty_queue(q)) {
        q->rear->next = new_queue_node;
        q->rear = new_queue_node;
    } else {
        q->front = q->rear = new_queue_node;
    }
    q->count++;
}

queue_node* dequeue(queue *q) {
    if (is_empty_queue(q)) return NULL;
    queue_node *tmp = q->front;
    q->front = q->front->next;
    q->count--;
    if (q->count == 0) {
        q->rear = NULL;
    }
    return tmp;
}

queue* make_queue() {
    queue *q = malloc(sizeof(queue));
    q->count = 0;
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void reset_colors(graph* g) {
    for (int i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data != -1) {
            g->heads[i].color = White;
        }
    }
}

int main(void) {
    graph* g = new_graph(5);
    AddEdges(g, 1, 2, 1, 1, 1);
    AddEdges(g, 1, 3, 1, 1, 1);
    AddEdges(g, 2, 4, 1, 4, 5);
    AddEdges(g, 2, 3, 3, 2, 1);
    AddEdges(g, 2, 1, 2, 1, 3);
    AddEdges(g, 3, 1, 7, 1, 4);
    AddEdges(g, 3, 1, 1, 3, 2);
    AddEdges(g, 3, 4, 4, 3, 1);
    AddEdges(g, 3, 4, 1, 7, 6);
    AddEdges(g, 4, 4, 5, 3, 2);
    AddEdges(g, 4, 3, 1, 1, 1);
    AddEdges(g, 4, 2, 1, 4, 5);
    AddEdges(g, 1, 5, 8, 1, 9);
    AddEdges(g, 1, 5, 1, 8, 4);

    int startNode = 1;
    int endNode = 4;

    printf("Original graph:\n");
    printgraph(g);
    printf("\nStarting to remove cycles...\n");

    // Repeat BFS until no more cycles are found
    bool cycles_removed;
    do {
        cycles_removed = false;
        reset_colors(g);
        queue* q = make_queue();
        node* start_node = NULL;
        for (int i = 0; i < g->nVertices; i++) {
            if (g->heads[i].data == startNode) {
                start_node = &g->heads[i];
                break;
            }
        }
        if (!start_node) break;

        start_node->color = Gray;
        enqueue(q, start_node);

        while (!is_empty_queue(q)) {
            queue_node* q_node = dequeue(q);
            node* current = q_node->n;
            free(q_node);

            list_node* temp = current->head;
            list_node* prev = NULL;

            while (temp != NULL) {
                node* neighbor = &g->heads[temp->index];
                if (neighbor->color == Gray) {
                    // Found a cycle: remove this edge
                    printf("\nEliminating edge from node %d to %d (cycle detected)\n", current->data, neighbor->data);
                    if (prev == NULL) {
                        current->head = temp->next;
                        free(temp);
                        temp = current->head;
                    } else {
                        prev->next = temp->next;
                        free(temp);
                        temp = prev->next;
                    }
                    cycles_removed = true;
                    // Print graph after each removal
                    printf("Current graph state:\n");
                    printgraph(g);
                } else if (neighbor->color == White) {
                    neighbor->color = Gray;
                    enqueue(q, neighbor);
                    prev = temp;
                    temp = temp->next;
                } else {
                    // Black node: already processed, no cycle
                    prev = temp;
                    temp = temp->next;
                }
            }

            current->color = Black;
        }
        free(q);
    } while (cycles_removed);

    printf("\nFinal DAG graph:\n");
    printgraph(g);

    return 0;
}

关键修改说明 #

1. 修复索引混淆：所有节点索引操作统一为0-based，避免了1/0基转换的错误。
2. 正确的环检测：通过Gray状态节点（当前BFS路径中的节点）识别环，只删除构成环的边，不会误删正常的跨路径边。
3. 精准边删除：使用prev指针跟踪链表，安全删除目标边并释放内存，避免内存泄漏。
4. 完整处理所有环：添加循环检测逻辑，重复运行BFS直到没有新环被移除，确保最终得到无环的DAG。
5. 统一状态标记：移除冗余的visited数组，只用color枚举跟踪节点状态，逻辑更清晰。
6. 优化打印逻辑：跳过heads数组中的空槽，输出更整洁。

测试这个代码，它会逐步移除所有构成环的边，最终输出符合要求的DAG。

备注：内容来源于stack exchange，提问作者yasakrami