C语言算法问答集：深入理解图算法-C++-PHP中文网

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

WBOY

发布： 2024-10-08 20:48:02

原创

834人浏览过

图的表示和遍历：表示：使用邻接链表（链表数组），每个链表表示一个顶点相邻的顶点。遍历：通过深度优先搜索（dfs）算法递归遍历各顶点及其相邻顶点。

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

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

问题：如何在 C 语言中表示和遍历图？

代码：

立即学习“C语言免费学习笔记（深入）”；

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

查看详情

// 使用邻接链表表示图
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 条边的无向图。以下是如何使用上述代码创建并遍历该图：

登录后复制

// 创建图
Graph *graph = create_graph(5);

// 添加边
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 4);
add_edge(graph, 2, 4);
add_edge(graph, 3, 4);
add_edge(graph, 3, 2);
add_edge(graph, 4, 1);

// 深度优先搜索
dfs(graph, 0);