DFS算法无法为无环图着色的C语言代码问题求解

你的代码核心问题是混淆了邻接表边节点与顶点属性的存储结构：用同一个node结构体既表示邻接表中连接顶点的边节点，又试图用它存储顶点的color/d/f等属性。这会导致无出边的顶点（g->adj[i]为NULL）无法访问其属性，直接触发空指针错误。

具体问题点 #

1. 数据结构设计错误：node同时承担两种角色，顶点属性没有独立存储。当顶点没有出边时，g->adj[i]为NULL，访问g->adj[i]->color会直接崩溃。
2. DFStest初始化逻辑错误：循环中直接访问g->adj[i]->color，但无出边的顶点对应的g->adj[i]是NULL，必然触发空指针引用。
3. DFS遍历逻辑错误：DFS_VISIT_test中遍历邻接表时，错误地认为边节点（v）包含color属性，但边节点只是指向目标顶点的索引，不是顶点本身的属性载体。

解决方案：拆分数据结构 #

将顶点属性与邻接表边节点分离，重新设计结构：

• 新增Vertex结构体存储每个顶点的状态属性（color、d、f、parent）
• Graph结构体包含顶点数组和邻接表两部分
• 邻接表的node仅存储目标顶点的索引和链表指针

修改后的完整代码 #

#include "pch.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// 邻接表边节点：仅存储目标顶点索引和下一个边节点指针
typedef struct AdjNode {
    int key;
    struct AdjNode* next;
} AdjNode;

// 顶点结构体：存储顶点的状态属性
typedef struct Vertex {
    int color;  // 0:未访问, 1:访问中, 2:已访问
    int d;      // 发现时间
    int f;      // 完成时间
    struct Vertex* parent;
} Vertex;

// 图结构体：包含顶点数组和邻接表
typedef struct Graph {
    int nr;             // 顶点数量
    Vertex* vertices;   // 顶点属性数组
    AdjNode** adj;      // 邻接表
} Graph;

AdjNode* createAdjNode(int v) {
    AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->key = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int n) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->nr = n;
    
    // 初始化顶点属性数组
    graph->vertices = (Vertex*)malloc(n * sizeof(Vertex));
    for (int i = 0; i < n; i++) {
        graph->vertices[i].color = 0;
        graph->vertices[i].d = 0;
        graph->vertices[i].f = 0;
        graph->vertices[i].parent = NULL;
    }
    
    // 初始化邻接表
    graph->adj = (AdjNode**)malloc(n * sizeof(AdjNode*));
    for (int i = 0; i < n; i++) {
        graph->adj[i] = NULL;
    }
    
    return graph;
}

void addEdge(Graph* graph, int s, int d) {
    AdjNode* newNode = createAdjNode(d);
    newNode->next = graph->adj[s];
    graph->adj[s] = newNode;
}

void printGraph(Graph* g) {
    for (int i = 0; i < g->nr; i++) {
        AdjNode* temp = g->adj[i];
        printf("\n%d -> ", i);
        while (temp) {
            printf("%d -> ", temp->key);
            temp = temp->next;
        }
        printf("NULL");
    }
    printf("\n");
}

// DFS访问函数：传入顶点索引，而非边节点
void DFS_VISIT_test(Graph* G, int u_idx, int* time, AdjNode** s) {
    Vertex* u = &G->vertices[u_idx];
    *time = *time + 1;
    u->d = *time;
    u->color = 1;  // 标记为访问中
    
    AdjNode* v_node = G->adj[u_idx];
    while (v_node) {
        int v_idx = v_node->key;
        Vertex* v = &G->vertices[v_idx];
        if (v->color == 0) {
            v->parent = u;
            DFS_VISIT_test(G, v_idx, time, s);
        }
        v_node = v_node->next;
    }
    
    // 将顶点索引压入栈（拓扑排序结果）
    AdjNode* q = createAdjNode(u_idx);
    q->next = *s;
    *s = q;
    
    u->color = 2;  // 标记为已访问完成
    *time = *time + 1;
    u->f = *time;
}

void DFStest(Graph* g) {
    AdjNode* s = NULL;  // 栈初始化为空
    int time = 0;
    
    // 遍历所有顶点，未访问则启动DFS
    for (int i = 0; i < g->nr; i++) {
        if (g->vertices[i].color == 0) {
            DFS_VISIT_test(g, i, &time, &s);
        }
    }
    
    // 打印拓扑排序结果
    printf("\n拓扑排序结果：");
    while (s) {
        printf("%d ", s->key);
        AdjNode* temp = s;
        s = s->next;
        free(temp);  // 释放栈节点内存
    }
    printf("\n");
    
    // 打印每个顶点的发现时间和完成时间
    printf("\n顶点  发现时间  完成时间\n");
    for (int i = 0; i < g->nr; i++) {
        printf("%d     %d        %d\n", i, g->vertices[i].d, g->vertices[i].f);
    }
}

int main(){
    Graph* g = createGraph(5);
    /*
     * 拓扑排序测试图
                               0
                             /   \
                            1     2
                            \      \
                             3     4
    */
    addEdge(g, 0, 2);
    addEdge(g, 0, 1);
    addEdge(g, 1, 3);
    addEdge(g, 2, 4);
    
    printf("图的邻接表：");
    printGraph(g);
    
    DFStest(g);
    
    // 释放内存（简化版，实际需完整释放所有节点）
    free(g->vertices);
    for (int i = 0; i < g->nr; i++) {
        AdjNode* temp = g->adj[i];
        while (temp) {
            AdjNode* next = temp->next;
            free(temp);
            temp = next;
        }
    }
    free(g->adj);
    free(g);
    
    return 0;
}

关键修改说明 #

1. 拆分数据结构：新增Vertex存储顶点属性，AdjNode仅做邻接表边节点，彻底分离两种角色，避免空指针问题。
2. DFS逻辑修正：DFS_VISIT_test接收顶点索引，直接访问Vertex数组中的属性，不再依赖邻接表节点。
3. 初始化与遍历修正：所有顶点属性初始化独立完成，无论是否有出边都能正常访问color等属性。
4. 内存管理优化：添加了栈节点和图结构的内存释放逻辑，避免内存泄漏。

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