微分销系统价格,企业关键词排名优化哪家好,外贸网站建设平台哪个好,核酸收费?例题
根据下列顶点之间的关系#xff0c;画出相应的图结构 A - B, C, D B - A, C, C - A, D, E, D - B, E, E - C,
数据结构#xff1a;使用邻接表表示图#xff0c;每个顶点有一个链表来存储与它相邻的顶点。 功能#xff1a; 创建图。 添加边。 打…例题
根据下列顶点之间的关系画出相应的图结构 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广度优先搜索。
主函数
创建图并添加边。打印图的邻接表。执行广度优先搜索。释放图的内存。
