高端网站定制开发网络服务推广
例题
根据下列顶点之间的关系，画出相应的图结构
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：广度优先搜索。
主函数：
- 创建图并添加边。
- 打印图的邻接表。
- 执行广度优先搜索。
- 释放图的内存。