图的邻接表（c语言 算法 程序）

图的邻接表是一种在计算机科学中用于表示图数据结构的有效方法，特别是在处理大量边的图时。在C语言中实现图的邻接表可以帮助我们更高效地执行各种图算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。本程序虽然可能不完美，但确实是一个良好的起点，可以作为进一步优化的基础。 我们需要定义图的节点和边的数据结构。节点通常包含一个标识符（例如，整数），而边则表示两个节点之间的连接。在邻接表中，每个节点将有一个链表，存储与其相邻的所有节点。 ```c typedef struct Node { int id; // 其他可能的属性，如权重等 } Node; typedef struct Edge { Node *neighbor; // 边可能具有的其他属性，如权重 } Edge; typedef struct AdjListNode { Edge edge; struct AdjListNode *next; } AdjListNode; typedef struct Graph { int num_nodes; Node **nodes; AdjListNode **adj_lists; } Graph; ``` 在C语言中创建这样的数据结构后，我们需要实现几个关键函数来操作图： 1. `createGraph(int num_nodes)`: 创建一个空图，包含`num_nodes`个节点。 2. `addNode(Graph *graph, int id)`: 向图中添加一个新节点。 3. `addEdge(Graph *graph, int node1_id, int node2_id)`: 在两个已存在的节点之间添加一条边。 4. `deleteNode(Graph *graph, int id)`: 从图中删除一个节点及其所有关联的边。 5. `deleteEdge(Graph *graph, int node1_id, int node2_id)`: 删除特定的边。 6. `traverseDFS(Graph *graph, int start_id, void (*visit)(Node *))`: 对图进行深度优先遍历，从`start_id`开始，并调用`visit`函数处理每个访问到的节点。 7. `traverseBFS(Graph *graph, int start_id, void (*visit)(Node *))`: 对图进行广度优先遍历，从`start_id`开始，并调用`visit`函数处理每个访问到的节点。 这些函数的实现将涉及动态内存分配、链表操作以及图遍历算法。深度优先搜索通常使用递归实现，而广度优先搜索则使用队列。 深度优先搜索（DFS）代码示例： ```c void dfsUtil(Graph *graph, int node_id, int visited[], void (*visit)(Node *)) { visited[node_id] = 1; visit(graph->nodes[node_id]); AdjListNode *current = graph->adj_lists[node_id]; while (current != NULL) { if (!visited[current->edge.neighbor->id]) { dfsUtil(graph, current->edge.neighbor->id, visited, visit); } current = current->next; } } void traverseDFS(Graph *graph, int start_id, void (*visit)(Node *)) { int visited[graph->num_nodes]; memset(visited, 0, sizeof(visited)); dfsUtil(graph, start_id, visited, visit); } ``` 广度优先搜索（BFS）代码示例： ```c #include <queue> void bfsUtil(Graph *graph, int start_id, int visited[], void (*visit)(Node *)) { queue<int> q; visited[start_id] = 1; q.push(start_id); while (!q.empty()) { int currentNode = q.front(); q.pop(); visit(graph->nodes[currentNode]); AdjListNode *current = graph->adj_lists[currentNode]; while (current != NULL) { if (!visited[current->edge.neighbor->id]) { visited[current->edge.neighbor->id] = 1; q.push(current->edge.neighbor->id); } current = current->next; } } } void traverseBFS(Graph *graph, int start_id, void (*visit)(Node *)) { int visited[graph->num_nodes]; memset(visited, 0, sizeof(visited)); bfsUtil(graph, start_id, visited, visit); } ``` 以上就是用C语言实现图的邻接表的基本框架。通过这个程序，你可以执行对图的各种操作，如添加、删除节点和边，以及遍历图。在实际应用中，你可能还需要根据具体需求对这些基本功能进行扩展和优化，例如支持带权重的边、添加拓扑排序等功能。