医院内外网站建设,做网站素材在哪里找,阿里代运营公司前十名,自己建网站做代理商嵌入式软件开发第三部分#xff0c;各类常用的数据结构及扩展#xff0c;良好的数据结构选择是保证程序稳定运行的关键#xff0c;#xff08;1#xff09;部分包括数组#xff0c;链表#xff0c;栈#xff0c;队列。#xff08;2#xff09;部分包括树#xff0c;…嵌入式软件开发第三部分各类常用的数据结构及扩展良好的数据结构选择是保证程序稳定运行的关键1部分包括数组链表栈队列。2部分包括树堆。3部分包括散列表图。
七 散列表哈希表 散列表Hash Table是一种根据关键字直接访问存储位置的数据结构它能够实现快速查找、插入和删除操作。散列表通过把关键字映射到表中一个位置来访问记录以加快查找速度。这个映射函数叫作散列函数Hash Function存放记录的数组叫作散列表Hash Table。 散列表在计算机领域有着广泛的应用下面介绍其中一些具体的应用 数据库索引数据库中的索引通常使用散列表实现。每个索引项包含一个键值和一个指向对应数据项的指针。当需要查找某个数据项时首先从索引中找到对应的键值然后通过指针快速访问该数据项。 缓存系统缓存系统通常使用散列表来存储缓存数据。当需要访问某个数据时先在散列表中查找对应的缓存项如果存在则直接返回结果。如果不存在则从原始数据源中获取数据并将其存储到散列表中。 字典字典通常使用散列表来存储单词和对应的解释。当需要查找某个单词的解释时可以通过散列表中的键值快速找到对应的解释。 文件系统部分文件系统如NTFS文件系统使用散列表来加速文件查找。文件系统中的散列表保存了文件名和对应的磁盘块号通过散列表可以快速定位到指定文件的存储位置。 哈希加密密码学中的哈希函数被广泛应用于密码加密和校验。哈希函数把任意长度的输入消息通过运算转换成固定长度的输出值这个输出值可以作为消息的数字指纹能够验证消息的完整性和真实性。 总之散列表作为一种快速、高效的数据结构被广泛应用于各种场景中如数据库索引、缓存系统、字典、文件系统等。 散列表的核心思想是通过哈希函数将关键字映射到散列表地址上实现快速查找。具体来说散列表的操作可以分为以下几个步骤 哈希函数的设计哈希函数用来将任意长度的输入例如电话号码映射为固定长度的输出例如散列表的地址。好的哈希函数能够尽可能地把输入均匀地映射到各个散列表地址上避免散列冲突即多个关键字映射到同一个散列表地址上。 散列冲突的处理由于哈希函数的输出值有限不同的关键字可能会被映射到同一个散列表地址上。因此需要在散列表中采用一些方法来处理散列冲突。常见的解决冲突的方法包括链地址法、开放地址法、再哈希法等。 再哈希法设定若干个哈希函数如果冲突了就用备用函数计算。多个哈希函数计算出来的还是同一个地址的概率就很低了开放地址法当发生冲突时形成一个探查序列从冲突的那个地址开始沿着序列逐个探查常用的探测再散列有线性再散列和二次再散列。以二次再散列来说加如地址5冲突则依次探测51165229。。。。。挺好理解的链地址法链地址就是在数组上插入链表发生冲突后就插在链表头上。所以不管有多少冲突都没有问题 添加元素将键值对存储到散列表中需要先通过哈希函数计算出该键对应的散列表地址然后把值存放在该地址上。 查找元素查找指定键对应的值时需要用哈希函数计算出该键对应的散列表地址然后在该地址上查找相应的值。如果存在散列冲突则按照冲突处理方法进行查找。
散列表的时间复杂度主要取决于哈希函数的设计和散列冲突的处理方式。通常情况下在哈希函数均匀分布的情况下散列表的查找、插入和删除的时间复杂度平均为 O(1)。因此散列表是一种高效的数据结构被广泛应用于各种场景中如数据库索引、缓存系统、字典等。
基于链地址法构建散列表利用链表
1向散列表中添加元素
// 向散列表中添加元素
void insert(HashTable* hashtable, char* key, int value) {// 计算关键字的哈希值并定位到该位置int pos hash(key);// 判断该位置上是否已经有节点ListNode* node hashtable-data[pos];while (node ! NULL strcmp(node-key, key) ! 0) {node node-next;}// 如果该位置上没有节点则创建一个新节点并插入到链表头部if (node NULL) {ListNode* new_node new_node(key, value);new_node-next hashtable-data[pos];hashtable-data[pos] new_node;hashtable-size;}// 如果该位置上已经有节点则更新该节点的值else {node-value value;}
}
2在散列表中查找元素
// 在散列表中查找元素如果找到则返回其对应的值否则返回-1
int search(HashTable* hashtable, char* key) {// 计算关键字的哈希值并定位到该位置int pos hash(key);// 遍历链表查找该元素ListNode* node hashtable-data[pos];while (node ! NULL strcmp(node-key, key) ! 0) {node node-next;}// 找到了该元素返回其对应的值if (node ! NULL) {return node-value;}// 没找到该元素返回-1else {return -1;}
}
3从散列表中删除元素
// 从散列表中删除元素
void remove_node(HashTable* hashtable, char* key) {// 计算关键字的哈希值并定位到该位置int pos hash(key);// 遍历链表查找该元素ListNode* node hashtable-data[pos];ListNode* prev NULL;while (node ! NULL strcmp(node-key, key) ! 0) {prev node;node node-next;}// 处理该位置上的节点if (node ! NULL) {// 如果该节点是链表头部则将下一个节点设置为新的链表头部if (prev NULL) {hashtable-data[pos] node-next;}// 否则将该节点从链表中删除else {prev-next node-next;}free(node);hashtable-size--;}
}全部程序
#include stdio.h
#include stdlib.h
#include string.h// 最大的散列表大小
#define MAX_SIZE 100// 定义一个结构体保存散列表节点的信息
typedef struct {char* key; // 关键字int value; // 存储的值
} ListNode;// 定义散列表的结构体
typedef struct {ListNode* data[MAX_SIZE]; // 散列表的数据int size; // 散列表的大小
} HashTable;// 哈希函数将字符串映射成散列表地址
int hash(char* key) {int hash_code 0;for (int i 0; i strlen(key); i) {hash_code hash_code * 31 key[i];}return hash_code % MAX_SIZE;
}// 创建新的节点并返回指针
ListNode* new_node(char* key, int value) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node-key (char*)malloc(sizeof(char) * strlen(key));strcpy(node-key, key);node-value value;return node;
}// 向散列表中添加元素
void insert(HashTable* hashtable, char* key, int value) {// 计算关键字的哈希值并定位到该位置int pos hash(key);// 判断该位置上是否已经有节点ListNode* node hashtable-data[pos];while (node ! NULL strcmp(node-key, key) ! 0) {node node-next;}// 如果该位置上没有节点则创建一个新节点并插入到链表头部if (node NULL) {ListNode* new_node new_node(key, value);new_node-next hashtable-data[pos];hashtable-data[pos] new_node;hashtable-size;}// 如果该位置上已经有节点则更新该节点的值else {node-value value;}
}// 在散列表中查找元素如果找到则返回其对应的值否则返回-1
int search(HashTable* hashtable, char* key) {// 计算关键字的哈希值并定位到该位置int pos hash(key);// 遍历链表查找该元素ListNode* node hashtable-data[pos];while (node ! NULL strcmp(node-key, key) ! 0) {node node-next;}// 找到了该元素返回其对应的值if (node ! NULL) {return node-value;}// 没找到该元素返回-1else {return -1;}
}// 从散列表中删除元素
void remove_node(HashTable* hashtable, char* key) {// 计算关键字的哈希值并定位到该位置int pos hash(key);// 遍历链表查找该元素ListNode* node hashtable-data[pos];ListNode* prev NULL;while (node ! NULL strcmp(node-key, key) ! 0) {prev node;node node-next;}// 处理该位置上的节点if (node ! NULL) {// 如果该节点是链表头部则将下一个节点设置为新的链表头部if (prev NULL) {hashtable-data[pos] node-next;}// 否则将该节点从链表中删除else {prev-next node-next;}free(node);hashtable-size--;}
}// 打印散列表中的内容
void print_hashtable(HashTable* hashtable) {printf(Size of hashtable: %d\n, hashtable-size);for (int i 0; i MAX_SIZE; i) {ListNode* node hashtable-data[i];if (node ! NULL) {printf(Pos: %d\n, i);while (node ! NULL) {printf(%s : %d\n, node-key, node-value);node node-next;}}}
}int main() {// 创建一个新的散列表HashTable* hashtable (HashTable*)malloc(sizeof(HashTable));hashtable-size 0;for (int i 0; i MAX_SIZE; i) {hashtable-data[i] NULL;}// 向散列表中添加元素insert(hashtable, apple, 10);insert(hashtable, banana, 20);insert(hashtable, orange, 30);insert(hashtable, grape, 40);// 在散列表中查找元素int value search(hashtable, banana);printf(The value of banana is %d\n, value);// 从散列表中删除元素remove_node(hashtable, grape);// 打印散列表中的内容print_hashtable(hashtable);// 释放散列表所占用的内存for (int i 0; i MAX_SIZE; i) {ListNode* node hashtable-data[i];while (node ! NULL) {ListNode* temp node;node node-next;free(temp-key);free(temp);}}free(hashtable);return 0;
}
八 图
图是一种非线性的数据结构它由节点顶点和边组成。节点之间的连线称为边它们可以用来表示各种复杂的现实世界中的关系例如社交网络、电路等。 以下是图的基本概念 顶点也称为节点表示图中的一个元素。 边表示两个顶点之间的关系。 有向图如果边有方向则称该图为有向图。 无向图如果边没有方向则称该图为无向图。 权表示边的重要程度或代价。 路径是通过一系列边连接在一起的顶点序列用来描述从一个顶点到另一个顶点的路线。 环是指至少含有一个顶点的路径其中第一个顶点与最后一个顶点是相同的。 连通如果图中每两个顶点之间都存在至少一条路径则称该图为连通图。 强连通如果图是有向图且对于任意两个顶点 u 和 v都存在一条从 u 到 v 和一条从 v 到 u 的路径则称该图为强连通图。 图的类型 图有两种类型有向图和无向图。在有向图中边是有方向的表示从一个顶点到另一个顶点有一个单向的路径而在无向图中边是没有方向的表示两个顶点之间的路径是双向的。 常用的图的存储结构有以下几种 邻接矩阵使用一个二维数组来表示图中顶点之间的关系其中数组的行和列分别表示图中的顶点用 0 或 1 来表示是否存在边。当然在带权图中可以用数组元素的值来表示边的权值。 邻接表使用一个链表数组来表示图中顶点之间的关系每个链表表示一个顶点的邻接点集。链表中的节点包含两部分信息邻接点的编号和这条边的权值如果是带权图。 关联矩阵使用一个二维数组来表示图中顶点和边之间的关系其中数组的行表示顶点列表示边用 0 或 1 表示该顶点与该边是否相关。当然在带权图中可以用数组元素的值来表示边的权值。 常用的图算法有以下几种 深度优先搜索DFS从一个起点开始依次遍历所有与之相邻的顶点并不断深入直到无法继续为止。在进行搜索的过程中需要使用一个栈来记录已经访问的顶点。 广度优先搜索BFS从一个起点开始先访问其所有相邻的顶点然后再访问这些相邻顶点的相邻顶点依次类推。在进行搜索的过程中需要使用一个队列来记录已经访问的顶点。 最短路径算法用于找出图中两个顶点之间的最短路径其中常用的算法包括 Dijkstra 算法和 Floyd-Warshall 算法。 最小生成树算法用于找出图中的一棵生成树使得该生成树的所有边权值之和最小。其中常用的算法包括 Prim 算法和 Kruskal 算法。 基于邻接表存储结构的深度优先搜索DFS
在下面的代码中我们使用邻接表存储图并采用递归的方式实现深度优先搜索。具体来说我们使用一个 visited 数组来记录每个顶点是否被访问过然后从某个未被访问的顶点开始依次遍历其所有邻接点并对每个未被访问的邻接点递归调用 DFS 函数。在 DFS 函数中我们首先将当前顶点标记为已经被访问过然后输出当前顶点的信息并遍历它的所有邻接点。如果某个邻接点还没有被访问过就递归调用 DFS 函数。最后在主函数中我们通过 InsertVertex 和 InsertArc 函数构造了一个简单的图并对它进行深度优先遍历。
#define MAX_VERTEX_NUM 100 // 定义最大顶点数
#define FALSE 0
#define TRUE 1// 邻接表中每个链表结点的定义
typedef struct ArcNode {int adjvex; // 邻接点的编号struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;// 邻接表中每个头结点的定义
typedef struct VNode {char data; // 顶点的数据域ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];// 图的定义
typedef struct {AdjList vertices; // 邻接表int vexnum, arcnum; // 顶点数和边数
} ALGraph;int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过// 初始化图
void InitGraph(ALGraph *G) {G-vexnum G-arcnum 0;for (int i 0; i MAX_VERTEX_NUM; i) {G-vertices[i].data \0;G-vertices[i].firstarc NULL;}
}// 插入一个顶点返回该顶点在邻接表中的位置
int InsertVertex(ALGraph *G, char v) {if (G-vexnum MAX_VERTEX_NUM) {printf(Error: Too many vertices\n);return -1;} else {G-vertices[G-vexnum].data v;G-vertices[G-vexnum].firstarc NULL;return G-vexnum;}
}// 插入一条边 (vi, vj)
void InsertArc(ALGraph *G, int vi, int vj) {ArcNode *p (ArcNode*)malloc(sizeof(ArcNode)); // 分配一个新的链表结点p-adjvex vj;p-nextarc G-vertices[vi].firstarc; // 将新结点插入到链表的头部G-vertices[vi].firstarc p;G-arcnum;
}// 深度优先搜索算法
void DFS(ALGraph *G, int v) {visited[v] TRUE; // 标记当前顶点已被访问printf(%c , G-vertices[v].data);ArcNode *p G-vertices[v].firstarc;while (p ! NULL) { // 遍历 v 的所有邻接点if (!visited[p-adjvex]) {DFS(G, p-adjvex); // 对每个未被访问的邻接点递归调用 DFS}p p-nextarc;}
}// 对图进行深度优先遍历
void DFSTraverse(ALGraph *G) {memset(visited, FALSE, sizeof(visited)); // 初始化 visited 数组for (int i 0; i G-vexnum; i) {if (!visited[i]) {DFS(G, i); // 对每个未被访问的顶点进行 DFS}}
}int main() {ALGraph G;InitGraph(G);int v1 InsertVertex(G, A);int v2 InsertVertex(G, B);int v3 InsertVertex(G, C);int v4 InsertVertex(G, D);InsertArc(G, v1, v2);InsertArc(G, v2, v3);InsertArc(G, v3, v4);InsertArc(G, v4, v1);DFSTraverse(G);return 0;
}基于邻接表存储结构的广度优先搜索BFS基于队列
在下面的代码中我们使用邻接表存储图并采用队列的方式实现广度优先搜索。具体来说我们使用一个 visited 数组来记录每个顶点是否被访问过然后从某个未被访问的顶点开始依次遍历其所有邻接点并将每个未被访问的邻接点加入队列中。在队列非空的情况下依次取出队首元素并遍历它的所有邻接点将未访问的邻接点加入队列中。直到队列为空为止。
在 BFS 函数中我们首先初始化队列将起始顶点加入队列中并标记其已被访问。然后在队列非空的情况下依次取出队首元素 u并输出该顶点的信息。接着我们遍历 u 的所有邻接点如果某个邻接点 v 还没有被访问过就将它加入队列并标记 visited[v] 为 1。
在 BFSTraverse 函数中我们对图中每个未访问的顶点分别调用 BFS 函数即可。
总之广度优先搜索算法是一种基于队列的搜索方式可以在无权图中找到从起始顶点到其他所有顶点的最短路径。
#include stdio.h
#include stdlib.h#define MAX_VERTEX_NUM 100 // 定义最大顶点数// 邻接表中每个链表结点的定义
typedef struct ArcNode {int adjvex; // 邻接点的编号struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;// 邻接表中每个头结点的定义
typedef struct VNode {char data; // 顶点的数据域ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];// 图的定义
typedef struct {AdjList vertices; // 邻接表int vexnum, arcnum; // 顶点数和边数
} ALGraph;int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过// 初始化图
void InitGraph(ALGraph *G) {G-vexnum G-arcnum 0;for (int i 0; i MAX_VERTEX_NUM; i) {G-vertices[i].data \0;G-vertices[i].firstarc NULL;}
}// 插入一个顶点返回该顶点在邻接表中的位置
int InsertVertex(ALGraph *G, char v) {if (G-vexnum MAX_VERTEX_NUM) {printf(Error: Too many vertices\n);return -1;} else {G-vertices[G-vexnum].data v;G-vertices[G-vexnum].firstarc NULL;return G-vexnum;}
}// 插入一条边 (vi, vj)
void InsertArc(ALGraph *G, int vi, int vj) {ArcNode *p (ArcNode*)malloc(sizeof(ArcNode)); // 分配一个新的链表结点p-adjvex vj;p-nextarc G-vertices[vi].firstarc; // 将新结点插入到链表的头部G-vertices[vi].firstarc p;G-arcnum;
}// 广度优先搜索算法
void BFS(ALGraph *G, int v) {// 初始化队列int head 0, tail 0;int queue[MAX_VERTEX_NUM];queue[tail] v;visited[v] 1;while (head ! tail) { // 队列非空时int u queue[head]; // 取出队首元素printf(%c , G-vertices[u].data);ArcNode *p G-vertices[u].firstarc;while (p ! NULL) { // 遍历 u 的所有邻接点if (!visited[p-adjvex]) {queue[tail] p-adjvex; // 将未访问的邻接点入队visited[p-adjvex] 1; // 标记邻接点已被访问过}p p-nextarc;}}
}// 对图进行广度优先遍历
void BFSTraverse(ALGraph *G) {memset(visited, 0, sizeof(visited)); // 初始化 visited 数组for (int i 0; i G-vexnum; i) {if (!visited[i]) {BFS(G, i); // 对每个未被访问的顶点进行 BFS}}
}int main() {ALGraph G;InitGraph(G);int v1 InsertVertex(G, A);int v2 InsertVertex(G, B);int v3 InsertVertex(G, C);int v4 InsertVertex(G, D);InsertArc(G, v1, v2);InsertArc(G, v1, v4);InsertArc(G, v2, v3);InsertArc(G, v3, v4);BFSTraverse(G);return 0;
}基于邻接矩阵存储结构的 Dijkstra 算法计算最短路径
在下面的代码中我们使用邻接矩阵存储图并采用 Dijkstra 算法计算单源最短路径。具体来说我们需要维护三个数组dist 数组、path 数组和 visited 数组。其中dist[i] 表示从起始点到顶点 i 的最短距离path[i] 表示从起始点到顶点 i 的最短路径上的前驱结点visited[i] 记录每个顶点是否已确定最短路径。
Dijkstra 算法的基本思想是将所有顶点分成两个集合已确定最短路径的顶点集合 S 和未确定最短路径的顶点集合 T初始时S 只包括起始点。然后每次从 T 中找出距离起始点最近的一个顶点 u并将 u 加入 S 集合中标记为已确定最短路径。然后用 u 松弛其邻接点更新其它顶点的最短路径长度和前驱结点。依次进行 n 次这样的过程n 为顶点数直到所有顶点的最短路径都已确定。
在 Dijkstra 函数中我们首先初始化 dist 数组和 path 数组将起始点到各顶点的距离初始化为边的权值前驱结点初始化为起始点如果有边相连。然后将起始点加入 S 集合中标记为已确定最短路径。接着在 T 集合中找出距离起始点最近的那个顶点 min_v将其加入 S 集合中标记为已确定最短路径。然后用 min_v 松弛其邻接点更新其他顶点的最短路径长度和前驱结点。重复上述步骤直到所有顶点的最短路径都已确定。
在 PrintPath 函数中我们采用递归的方式输出从起始点到终点的最短路径。首先判断是否已到达起始点如果是则直接输出否则递归输出终点的前驱结点最后再输出终点。
总之Dijkstra 算法是一种贪心算法能够求解单源最短路径问题。它的时间复杂度为 O(n^2)比较适用于稠密图。
#include stdio.h
#include limits.h#define MAX_VERTEX_NUM 100 // 定义最大顶点数// 邻接矩阵的定义
typedef struct {int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值int vexnum, arcnum; // 顶点数和边数
} MGraph;// 初始化图
void InitGraph(MGraph *G) {G-vexnum G-arcnum 0;for (int i 0; i MAX_VERTEX_NUM; i) {for (int j 0; j MAX_VERTEX_NUM; j) {G-edges[i][j] INT_MAX; // 初始化为无穷大}}
}// 添加一条边 (vi, vj)权值为 w
void AddArc(MGraph *G, int vi, int vj, int w) {G-edges[vi][vj] w;G-arcnum;
}// Dijkstra 算法求单源最短路径
void Dijkstra(MGraph *G, int start, int dist[], int path[]) {int visited[MAX_VERTEX_NUM] {0}; // 记录每个顶点是否已确定最短路径for (int i 0; i G-vexnum; i) {dist[i] G-edges[start][i]; // 初始化 dist 数组为起始点到各顶点的距离if (G-edges[start][i] INT_MAX) {path[i] start; // 如果起始点到该顶点有边则将其前驱为起始点} else {path[i] -1; // 如果起始点到该顶点没有边则将其前驱置为 -1}}dist[start] 0; // 起始点到自身距离为 0visited[start] 1; // 起始点已确定最短路径for (int i 1; i G-vexnum; i) { // 其余 n-1 个顶点依次进入 S 集合int min_dist INT_MAX;int min_v -1;for (int j 0; j G-vexnum; j) { // 找出当前未确定最短路径的顶点中距离最小的那个if (!visited[j] dist[j] min_dist) {min_dist dist[j];min_v j;}}if (min_v -1) break; // 如果找不到这样的顶点说明剩下的顶点都不连通visited[min_v] 1; // 将该顶点加入 S 集合中标记为已确定最短路径for (int j 0; j G-vexnum; j) { // 更新其他顶点的最短路径if (!visited[j] G-edges[min_v][j] INT_MAX dist[min_v] G-edges[min_v][j] dist[j]) {dist[j] dist[min_v] G-edges[min_v][j]; // 通过 min_v 松弛 jpath[j] min_v; // 更新 j 的前驱为 min_v}}}
}// 输出从起始点到终点的最短路径
void PrintPath(MGraph *G, int start, int end, int path[]) {if (end start) { // 如果已到达起始点直接输出printf(%d , start);return;}if (path[end] -1) { // 如果终点没有前驱说明不连通printf(Error: Not connected\n);return;}PrintPath(G, start, path[end], path); // 递归输出前驱printf(%d , end);
}int main() {MGraph G;InitGraph(G);int v0 0, v1 1, v2 2, v3 3, v4 4;AddArc(G, v0, v1, 10);AddArc(G, v0, v3, 30);AddArc(G, v0, v4, 100);AddArc(G, v1, v2, 50);AddArc(G, v2, v4, 10);AddArc(G, v3, v2, 20);AddArc(G, v3, v4, 60);int dist[MAX_VERTEX_NUM] {0}; // 存储起始点到各顶点的最短距离int path[MAX_VERTEX_NUM] {-1}; // 存储各顶点到起始点的最短路径上的前驱结点Dijkstra(G, v0, dist, path);for (int i 0; i G.vexnum; i) {printf(%d , dist[i]);}printf(\n);PrintPath(G, v0, v4, path);return 0;
}基于邻接矩阵存储结构的 Prim 算法最小生成树
在下面的代码中我们使用邻接矩阵存储图并采用 Prim 算法计算最小生成树。具体来说我们需要维护两个数组dist 数组和 path 数组。其中dist[i] 表示顶点 i 到最小生成树的最短距离path[i] 表示顶点 i 到最小生成树上的前驱结点。visited 数组用于记录每个顶点是否已加入生成树。
Prim 算法的基本思想是将所有顶点分成两个集合已加入生成树的顶点集合 S 和未加入生成树的顶点集合 T初始时S 只包括起始点。然后每次从 T 中找出距离 S 最近的一个顶点 u并将 u 加入 S 集合中。然后用 u 松弛其邻接点更新 T 中的顶点到生成树的距离和前驱结点。重复上述步骤直到所有顶点都已加入生成树。
在 Prim 函数中我们首先初始化 dist 数组和 path 数组将起始点到各顶点的距离初始化为边的权值前驱结点初始化为起始点如果有边相连。然后将起始点加入生成树中标记为已访问。接着在 T 集合中找出距离 S 最近的那个顶点 min_v将其加入 S 集合中。然后用 min_v 松弛其邻接点更新其他顶点到生成树的距离和前驱结点。重复上述步骤直到所有顶点都已加入生成树。
总之Prim 算法是一种贪心算法能够求解最小生成树问题。它的时间复杂度为 O(n^2)比较适用于稠密图。
#include stdio.h
#include limits.h#define MAX_VERTEX_NUM 100 // 定义最大顶点数// 邻接矩阵的定义
typedef struct {int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值int vexnum, arcnum; // 顶点数和边数
} MGraph;// 初始化图
void InitGraph(MGraph *G) {G-vexnum G-arcnum 0;for (int i 0; i MAX_VERTEX_NUM; i) {for (int j 0; j MAX_VERTEX_NUM; j) {G-edges[i][j] INT_MAX; // 初始化为无穷大}}
}// 添加一条边 (vi, vj)权值为 w
void AddArc(MGraph *G, int vi, int vj, int w) {G-edges[vi][vj] w;G-edges[vj][vi] w; // 无向图需要添加两条边G-arcnum;
}// Prim 算法求最小生成树
void Prim(MGraph *G, int start, int dist[], int path[]) {int visited[MAX_VERTEX_NUM] {0}; // 记录每个顶点是否已加入生成树for (int i 0; i G-vexnum; i) {dist[i] G-edges[start][i]; // 初始化 dist 数组为起始点到各顶点的距离if (G-edges[start][i] INT_MAX) {path[i] start; // 如果起始点到该顶点有边则将其前驱为起始点} else {path[i] -1; // 如果起始点到该顶点没有边则将其前驱置为 -1}}visited[start] 1; // 将起始点加入生成树中标记为已访问for (int i 1; i G-vexnum; i) { // 其余 n-1 个顶点依次加入生成树int min_dist INT_MAX;int min_v -1;for (int j 0; j G-vexnum; j) { // 找出当前未加入生成树的顶点中距离最小的那个if (!visited[j] dist[j] min_dist) {min_dist dist[j];min_v j;}}if (min_v -1) break; // 如果找不到这样的顶点说明剩下的顶点都不连通visited[min_v] 1; // 将该顶点加入生成树中标记为已访问for (int j 0; j G-vexnum; j) { // 更新其他顶点到生成树的距离if (!visited[j] G-edges[min_v][j] dist[j]) {dist[j] G-edges[min_v][j]; // 通过 min_v 更新 j 的到生成树的距离path[j] min_v; // 更新 j 的前驱为 min_v}}}
}int main() {MGraph G;InitGraph(G);int v0 0, v1 1, v2 2, v3 3, v4 4;AddArc(G, v0, v1, 10);AddArc(G, v0, v3, 30);AddArc(G, v0, v4, 100);AddArc(G, v1, v2, 50);AddArc(G, v2, v4, 10);AddArc(G, v3, v2, 20);AddArc(G, v3, v4, 60);int dist[MAX_VERTEX_NUM] {0}; // 存储每个顶点到最小生成树的最短距离int path[MAX_VERTEX_NUM] {-1}; // 存储每个顶点到最小生成树上的前驱结点Prim(G, v0, dist, path);for (int i 0; i G.vexnum; i) {printf(%d , path[i]);}printf(\n);return 0;
}
