面试题：C语言实现带路径记录的深度优先搜索

#include <stdio.h>
#include <stdlib.h>

// 定义边的结构体
typedef struct Edge {
    int to;
    int weight;
    struct Edge* next;
} Edge;

// 定义图的结构体
typedef struct Graph {
    int V;
    Edge** adj;
} Graph;

// 创建新的边
Edge* createEdge(int to, int weight) {
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->to = to;
    newEdge->weight = weight;
    newEdge->next = NULL;
    return newEdge;
}

// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->adj = (Edge**)malloc(V * sizeof(Edge*));
    for (int i = 0; i < V; ++i) {
        graph->adj[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int from, int to, int weight) {
    Edge* newEdge = createEdge(to, weight);
    newEdge->next = graph->adj[from];
    graph->adj[from] = newEdge;
}

// 辅助结构体用于记录路径
typedef struct Path {
    int* nodes;
    int* weights;
    int top;
    int capacity;
} Path;

// 创建路径结构体
Path* createPath(int capacity) {
    Path* path = (Path*)malloc(sizeof(Path));
    path->nodes = (int*)malloc(capacity * sizeof(int));
    path->weights = (int*)malloc(capacity * sizeof(int));
    path->top = -1;
    path->capacity = capacity;
    return path;
}

// 添加节点到路径
void addToPath(Path* path, int node, int weight) {
    if (path->top + 1 >= path->capacity) {
        path->capacity *= 2;
        path->nodes = (int*)realloc(path->nodes, path->capacity * sizeof(int));
        path->weights = (int*)realloc(path->weights, path->capacity * sizeof(int));
    }
    path->nodes[++path->top] = node;
    path->weights[path->top] = weight;
}

// 打印路径
void printPath(Path* path) {
    for (int i = 0; i <= path->top; ++i) {
        printf("%d", path->nodes[i]);
        if (i < path->top) {
            printf("-%d->", path->weights[i + 1]);
        }
    }
    printf("\n");
}

// 深度优先搜索辅助函数
void DFSUtil(Graph* graph, int vertex, int* visited, Path* path) {
    visited[vertex] = 1;
    addToPath(path, vertex, 0);
    Edge* edge = graph->adj[vertex];
    while (edge != NULL) {
        if (!visited[edge->to]) {
            DFSUtil(graph, edge->to, visited, path);
        }
        edge = edge->next;
    }
    printPath(path);
    path->top--;
}

// 深度优先搜索
void DFS(Graph* graph, int start) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; ++i) {
        visited[i] = 0;
    }
    Path* path = createPath(graph->V);
    DFSUtil(graph, start, visited, path);
    free(visited);
    free(path->nodes);
    free(path->weights);
    free(path);
}

int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1, 10);
    addEdge(graph, 0, 2, 5);
    addEdge(graph, 1, 2, 1);
    addEdge(graph, 1, 3, 2);
    addEdge(graph, 2, 1, 3);
    addEdge(graph, 2, 3, 9);
    addEdge(graph, 2, 4, 2);
    addEdge(graph, 3, 4, 4);
    addEdge(graph, 4, 3, 6);

    printf("深度优先搜索从节点0开始:\n");
    DFS(graph, 0);

    return 0;
}

数据结构设计：
- Edge结构体表示边，包含目标节点to、权重weight和指向下一条边的指针next。
- Graph结构体表示图，包含节点数V和邻接表adj。
- Path结构体用于记录路径，包含节点数组nodes、权重数组weights、栈顶指针top和容量capacity。
函数实现：
- createEdge函数创建新的边。
- createGraph函数创建图并初始化邻接表。
- addEdge函数向图中添加边。
- createPath函数创建路径结构体。
- addToPath函数向路径中添加节点及其权重。
- printPath函数打印路径。
- DFSUtil是深度优先搜索的递归辅助函数，用于遍历图并记录路径。
- DFS函数初始化访问数组和路径结构体，调用DFSUtil进行深度优先搜索，并在结束时释放相关内存。
main函数：
- 创建一个图并添加一些边。
- 调用DFS函数从节点0开始进行深度优先搜索，并输出所有路径。

星途面试题库

面试题：C语言实现带路径记录的深度优先搜索

知识考点

面试题答案