22智能 图

例题

根据下列顶点之间的关系，画出相应的图结构
A -> B, C, D
B -> A, C,
C -> A, D, E,
D -> B, E,
E -> C,

数据结构：使用邻接表表示图，每个顶点有一个链表来存储与它相邻的顶点。
功能：
创建图。
添加边。
打印邻接表。
执行广度优先搜索（BFS）。

#include <stdio.h>  // 包含标准输入输出库
#include <stdlib.h> // 包含标准库函数，如 malloc 和 free// 定义链表节点结构体
typedef struct ListNode {int value;             // 节点的值struct ListNode* next; // 指向下一个节点的指针
} ListNode;// 定义图的邻接表结构体
typedef struct {int vertex;       // 顶点编号ListNode* adjList; // 邻接链表的头指针
} AdjacencyList;// 图结构体
typedef struct {int numVertices;      // 顶点数量AdjacencyList* adjLists; // 邻接表数组
} Graph;// 创建链表节点的函数
ListNode* createListNode(int value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); // 分配内存newNode->value = value;                                   // 初始化节点值newNode->next = NULL;                                     // 初始化指针return newNode;                                           // 返回新节点
}// 创建图的函数
Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph)); // 分配内存graph->numVertices = vertices;                // 初始化顶点数量graph->adjLists = (AdjacencyList*)malloc(vertices * sizeof(AdjacencyList)); // 分配邻接表数组内存for (int i = 0; i < vertices; i++) {graph->adjLists[i].vertex = i;          // 初始化顶点编号graph->adjLists[i].adjList = NULL;      // 初始化邻接链表为空}return graph;                               // 返回图结构
}// 添加边的函数
void addEdge(Graph* graph, int src, int dest, int bidir) {// 添加从 src 到 dest 的边ListNode* newNode = createListNode(dest);   // 创建新节点newNode->next = graph->adjLists[src].adjList; // 将新节点插入到邻接链表头部graph->adjLists[src].adjList = newNode;if (bidir) {                                // 如果是双向图// 添加从 dest 到 src 的边newNode = createListNode(src);          // 创建新节点newNode->next = graph->adjLists[dest].adjList; // 将新节点插入到邻接链表头部graph->adjLists[dest].adjList = newNode;}
}// 打印邻接表的函数
void printAdjList(Graph* graph) {for (int i = 0; i < graph->numVertices; i++) {printf("%d -> ", graph->adjLists[i].vertex); // 打印顶点编号ListNode* temp = graph->adjLists[i].adjList; // 获取邻接链表头指针while (temp) {printf("%d, ", temp->value);             // 打印邻接节点值temp = temp->next;                       // 移动到下一个节点}printf("\n");                                // 换行}
}// 广度优先搜索的函数
void bfs(Graph* graph, int src) {int* visited = (int*)calloc(graph->numVertices, sizeof(int)); // 分配访问标记数组内存int queue[graph->numVertices];                                // 定义队列int front = 0, rear = 0;                                      // 初始化队列的前后指针visited[src] = 1;                                             // 标记源节点已访问queue[rear++] = src;                                          // 将源节点入队while (front != rear) {                                       // 当队列不为空时int node = queue[front++];                                // 出队一个节点printf("%d, ", node);                                     // 打印节点值ListNode* temp = graph->adjLists[node].adjList;           // 获取当前节点的邻接链表头指针while (temp) {if (!visited[temp->value]) {                          // 如果邻接节点未被访问visited[temp->value] = 1;                         // 标记邻接节点已访问queue[rear++] = temp->value;                      // 将邻接节点入队}temp = temp->next;                                    // 移动到下一个邻接节点}}free(visited);                                                // 释放访问标记数组内存
}int main() {int vertices = 6;                                             // 定义顶点数量Graph* graph = createGraph(vertices);                         // 创建图// 添加边addEdge(graph, 0, 1, 1);                                      // 添加边 (0, 1)addEdge(graph, 1, 2, 1);                                      // 添加边 (1, 2)addEdge(graph, 0, 4, 1);                                      // 添加边 (0, 4)addEdge(graph, 2, 4, 1);                                      // 添加边 (2, 4)addEdge(graph, 2, 3, 1);                                      // 添加边 (2, 3)addEdge(graph, 3, 5, 1);                                      // 添加边 (3, 5)addEdge(graph, 3, 4, 1);                                      // 添加边 (3, 4)printf("The Graph is:\n");                                    // 打印图的信息printAdjList(graph);                                          // 打印邻接表printf("\n");printf("The Breadth First Search from Node 0:\n");            // 打印广度优先搜索结果bfs(graph, 0);// 释放图的内存for (int i = 0; i < vertices; i++) {ListNode* temp = graph->adjLists[i].adjList;              // 获取邻接链表头指针while (temp) {ListNode* toFree = temp;                              // 保存当前节点temp = temp->next;                                    // 移动到下一个节点free(toFree);                                         // 释放当前节点内存}}free(graph->adjLists);                                        // 释放邻接表数组内存free(graph);                                                  // 释放图结构内存return 0;                                                     // 程序结束
}

代码注释说明

头文件包含：

• #include <stdio.h>：包含标准输入输出库。
• #include <stdlib.h>：包含标准库函数，如 malloc 和 free。

结构体定义：

• ListNode：定义链表节点结构体。
• AdjacencyList：定义图的邻接表结构体。
• Graph：定义图结构体。

函数定义：

• createListNode：创建链表节点。
• createGraph：创建图。
• addEdge：添加边。
• printAdjList：打印邻接表。
• bfs：广度优先搜索。

主函数：

• 创建图并添加边。
• 打印图的邻接表。
• 执行广度优先搜索。
• 释放图的内存。