C语言算法问答集：深入理解图算法

// 使用邻接链表表示图
typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct Graph {
    int num_vertices;
    Node **adj_list;
} Graph;

// 初始化图
Graph* create_graph(int num_vertices) {
    Graph *graph = (Graph*)malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    graph->adj_list = (Node**)malloc(sizeof(Node*) * num_vertices);

    for (int i = 0; i < num_vertices; i++) {
        graph->adj_list[i] = NULL;
    }

    return graph;
}

// 添加边
void add_edge(Graph *graph, int src, int dest) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->vertex = dest;
    new_node->next = graph->adj_list[src];
    graph->adj_list[src] = new_node;
}

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

    dfs_util(graph, start, visited);
}

void dfs_util(Graph *graph, int vertex, int *visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    Node *current_node = graph->adj_list[vertex];
    while (current_node != NULL) {
        if (!visited[current_node->vertex]) {
            dfs_util(graph, current_node->vertex, visited);
        }
        current_node = current_node->next;
    }
}

**实战案例：**

考虑一个由 5 个顶点和 7 条边的无向图。以下是如何使用上述代码创建并遍历该图：

输出结果：