面试题：C语言在复杂图场景下深度优先搜索的优化

优化思路

使用栈而非递归：递归实现深度优先搜索（DFS）会占用大量栈空间，尤其对于大的图可能导致栈溢出。使用手动维护的栈来模拟递归过程，可以有效控制内存占用。
标记顶点状态：为每个顶点设置一个状态标记，避免重复访问，提高搜索效率。可以使用一个布尔数组来标记顶点是否被访问过。
稀疏图特性利用：由于是稀疏图，邻接表存储结构本身已经在一定程度上优化了空间占用。在遍历邻接表时，只需要遍历存在的边，避免无效操作。

关键代码实现

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

// 定义邻接表节点结构
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表结构
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图结构
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 如果是无向图，还需添加反向边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 深度优先搜索
void DFS(Graph* graph, int start) {
    int *stack = (int*)malloc(graph->V * sizeof(int));
    int top = -1;
    int *visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }

    stack[++top] = start;
    visited[start] = 1;

    while (top != -1) {
        int current = stack[top--];
        printf("%d ", current);

        AdjListNode* temp = graph->array[current].head;
        while (temp != NULL) {
            if (!visited[temp->dest]) {
                stack[++top] = temp->dest;
                visited[temp->dest] = 1;
            }
            temp = temp->next;
        }
    }

    free(stack);
    free(visited);
}

你可以这样调用函数：

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

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

    return 0;
}

星途面试题库

面试题：C语言在复杂图场景下深度优先搜索的优化

知识考点

面试题答案

优化思路

关键代码实现