-
算法 - 最小生成树实现
算法能力是一个门槛，也是个有基础的门槛
无论你是iOS工程师，android工程师，java工程师，前端，后端还是全栈等等…
算法能力的强弱一方面在于思想，你是否有计算机思维抽象具体问题的能力
更重要的还在与基础了，如果你没有基础转化的能力，空有思想，在其他领域可能有助于你的工作效率问题，但在互联网尤其计算机从业方面无济于事
我是一名iOS工程师，但我不喜欢这样的定位，虽然现在公司的要求都会明确工种划分，但我自认为是个小强，我始终把自己定位称为一名计算机从业者，继续打怪升级
算法，是一个很好的试炼石
尤其是客户端程序员由于工作划分的原因，有很多人算法能力慢慢被弱化，工作上可能用不上，但我们客户端程序员不能找借口，市场是不会跟你商量的，尤其是年龄渐长之后，你pk的砝码又是什么呢
现在的客户端计算能力越来越强，手机上能处理的问题越来越多，手机的处理能力不弱于单台服务器，我们手机跟手机之间本身就是一个网络，是很重要的结点，那我们客户端的程序员们还有什么理由需要麻痹自己呢
快快行动起来吧，从算法基础开始，切不可被行业贴上了撕不掉的标签，总有一天，这个便签会完全限制掉你
本篇文章我想分享一个最小生成树，它并不是树，只是一种说辞
最小生成树是什么
首先了解图的概念
这是一个无向连通图，点之间的连线上的数字代表权重
最小生成树就是这个连通图子图并满足条件
- n个顶点，只会有n-1条边
- 最小生成树中 所有边 权重之和是最小的
最小生成树能做什么
我主要针对客户端程序员分享一些用途
可以考虑这样一个场景
-
一个app中包含很多功能页面，很多个场景，很多个入口
-
用户对于一款app的的使用习惯是多种多样的，随着app功能的迭代复杂，app的内容访问并不是线性的，而是相互重叠的
-
比如淘宝app，可以从搜索进入商品页，也可以从活动 - 产品直播 - 商品，还可以从商品 - 订单 - 详情 - 商品链接 - 直播间 - 商品
-
相信你已经看出来了，类似于这样的场景会很多，这是app产品复杂的结果
-
如果现在要对以往的功能进行用户数据统计，分析用户对于系列功能的黏度，功能使用的覆盖程度，使用频率分析，并根据分析结果进行调整
-
一般常规的做法是设计一套埋点框架，数据交给服务器，服务器来分析这些统计的数据
-
难道客户端就绑手绑脚了，只能做到这个程度
-
我觉得不然，从抽象角度看，app中的功能页面也好，功能点也好，用户对于app中各种功能的访问其实就是复杂的图结构而已
-
不同的用户沿着不同的路径进行探究，在图的路径上会延伸到各种功能结点，单个用户并不按照一定的规律访问
作为客户端程序员，你会怎么做
抛开所有的业务，这不就是一个求图的最小生成树问题么
- 客户端把用户的访问结点按照几天或者一周的时间维度抽象出来
- 把用户的结点跳转进行图中的边构建
- 解出构建连通图的最小生成树权重值
- 如果构建出来的图不是连通图，说明功能设计上有些不够圆滑，用户在某些功能跟功能之间是没有路径的，这就导致抽象出来的图不是连通的
- 每个用户的数据构建出来的图多少会有差异，怎么区分用户与用户呢
- 如果用户的功能结点够多，最终权重值比别的用户低，说明这个用户是比较纯粹的，对于功能的使用是比较单一的，不会反复跳切，也就是说不会因为app的功能版本升级马上关注
- 如果用户的权重值很高，说明是重度用户，可以统计这部分用户的比重，单个用户的分析就可由手机端处理完成，就不需要再由服务器端薅头发了，对于单用户的统计分析，客户端是占有很大优势的，离用户够近
- 如果用户的结点不多，但是计算的权重值也不是很低，说明可能卡在了某些功能入口处，用户不知道使用一些有门槛的功能入口进入，根据用户比重，可以考虑适当调整功能页面的分配，做个简单的调整
像这种例子，客户端会存在很多场景
最小生成树算法实现
在考虑怎么实现之前，你需要了解图的结构怎么存储
-
邻接矩阵
- 如果要存储 A - B，也就是两点一线
- 一个一维数组，存储顶点
- 一个二维数组，存储边，也就是连线
- 比如 A是0号元素，B是1号元素，array[0][1] 就代表 A-B的连线的权重
-
邻接表
- 链接矩阵存储会存在空间的浪费，邻接表就出现了
克鲁斯卡尔Kruskal算法
Kruskal是把邻接矩阵转换成 边表，也就是 15条边的数组，
每个元素包含结构 A - B(10) begin,end,weigh
数组按照权重大小排序
创建一维数组 parent，存储连通的下标
遍历边表数组，通过parent查找连通结点
普里姆Prim算法
Prim是通过随意取一个开始顶点进行遍历
比如从A开始，有两条边，A-B(10), A-F(11)
选择权重小的 A-B(10)
B又有3个连接顶点 B-C B-I B-G
这个时候有4条边进行比较 B-C(18) B-I(12) B-G(16) A-F(11)
选择权重小的A-F(11)
F又有连接的结点 F-G(17) F-E(26)
有5条边进行比较 B-C(18) B-I(12) B-G(16) F-G(17) F-E(26)
依此规律进行
代码实现
以下代码部分囊括了
- 图的邻接矩阵实现方式
- 邻接表方式
- 图的遍历
- 深度优先遍历
- 广度优先遍历
- 最小生成树实现
- 克鲁斯卡尔Kruskal算法
- 普里姆Prim算法
- 还有具体构建实例图的输入数据，见代码后
// 深度优先遍历 - 邻接矩阵方式 #define VERTEXMAX 50 //最大顶点数 #define EDGEMAX 50 // 最大边数 #define GRAPH_INFINITY 65535 // 标识无穷 #define TRUE 1 #define FALSE 0 typedef char VertexType; typedef int EdgeType; int verts_visit[VERTEXMAX]; // 标识已遍历过的结点 // 邻接矩阵存储结构 typedef struct MatrixGraph { VertexType verts[VERTEXMAX]; // 顶点 EdgeType matrix[VERTEXMAX][VERTEXMAX]; // 邻接矩阵 int num_vertex; // 顶点数 int num_edge; // 边数 int direct; // true - 有向图 false - 无向图 } MatrixGraph; void CreateMatrixGraph(MatrixGraph *graph) { printf("输入顶点数:"); scanf("%d", &graph->num_vertex); printf("输入边数:"); scanf("%d", &graph->num_edge); printf("顶点数: %d, 边数: %d\n", graph->num_vertex, graph->num_edge); // 初始化，对角线 0， 其余 无穷 for (int i = 0; i < graph->num_vertex; i++) { for (int j = 0; j < graph->num_vertex; j++) { if (i == j) { graph->matrix[i][j] = 0; } else { graph->matrix[i][j] = GRAPH_INFINITY; } } } for (int i = 0; i < graph->num_vertex; i++) { printf("输入第%d个顶点: ", i + 1); getchar(); scanf("%c", &graph->verts[i]); } printf("顶点："); for (int i = 0; i < graph->num_vertex; i++) { printf("%c ", graph->verts[i]); } printf("\n"); printf("有向图1 还是 无向图0: "); scanf("%d", &graph->direct); for (int k = 0; k < graph->num_edge; k++) { int i, j, w; printf("输入第%d条边(i, j, w): ", k + 1); // w- 标识权重 getchar(); scanf("%d, %d, %d", &i, &j, &w); graph->matrix[i][j] = w; if (!graph->direct) { graph->matrix[j][i] = w; } } int edges = 0; for (int i = 0; i < graph->num_vertex; i++) { for (int j = i + 1; j < graph->num_vertex; j++) { if (graph->matrix[i][j] != 0 && graph->matrix[i][j] != GRAPH_INFINITY) { edges++; printf("<%c-%c>(%d) ", graph->verts[i], graph->verts[j], graph->matrix[i][j]); } } printf("\n"); } printf("总共%d条边\n", edges); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
// 邻接矩阵方式-深度优先遍历实现 第i个顶点 void MG_DFS(MatrixGraph *graph, int i) { verts_visit[i] = TRUE; printf("%c ", graph->verts[i]); for (int j = 0; j < graph->num_vertex; j++) { if (graph->matrix[i][j] != 0 && graph->matrix[i][j] != GRAPH_INFINITY && !verts_visit[j]) { MG_DFS(graph, j); } } } // 可能包含非连通图 void MG_Traverse(MatrixGraph *graph) { printf("开始深度优先遍历\n"); for (int i = 0; i < graph->num_vertex; i++) { verts_visit[i] = FALSE; } for (int i = 0; i < graph->num_vertex; i++) { if (!verts_visit[i]) { MG_DFS(graph, i); } } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
// 邻接表存储结构 typedef struct EdgeNode { // 表头指向的 结点， 标识边 int table_index; // 在table中的索引下标 int weigh; // 权重 struct EdgeNode *next; } EdgeNode; typedef struct VertNode { VertexType ch; EdgeNode *firstEdgeNode; } VertNode, AdjTable[100]; typedef struct AdjGraph { AdjTable table; int arc_num; // 边数 int node_num; // 结点数 int direct; // 是否有向图 } AdjGraph, *AdjGraphLink; void CreteAdjTableGraph(MatrixGraph *graph, AdjGraphLink TG) { TG->direct = graph->direct; TG->node_num = graph->num_vertex; TG->arc_num = graph->num_edge; for (int i = 0; i < graph->num_vertex; i++) { TG->table[i].ch = graph->verts[i]; TG->table[i].firstEdgeNode = NULL; } for (int i = 0; i < graph->num_vertex; i++) { for (int j = i + 1; j < graph->num_vertex; j++) { if (graph->matrix[i][j] != 0 && graph->matrix[i][j] != GRAPH_INFINITY) { EdgeNode *eNode = (EdgeNode *)malloc(sizeof(EdgeNode *)); eNode->table_index = j; eNode->weigh = graph->matrix[i][j]; eNode->next = NULL; if (TG->table[i].firstEdgeNode == NULL) { TG->table[i].firstEdgeNode = eNode; } else { eNode->next = TG->table[i].firstEdgeNode; TG->table[i].firstEdgeNode = eNode; } if (!TG->direct) { EdgeNode *eNode1 = (EdgeNode *)malloc(sizeof(EdgeNode *)); eNode1->table_index = i; eNode->weigh = graph->matrix[j][i]; eNode1->next = NULL; if (TG->table[j].firstEdgeNode == NULL) { TG->table[j].firstEdgeNode = eNode1; } else { eNode1->next = TG->table[j].firstEdgeNode; TG->table[j].firstEdgeNode = eNode1; } } } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
// 深度优先遍历-邻接表方式实现 第i个顶点 void MG_DFS_adjtable(AdjGraphLink graph, int i) { verts_visit[i] = TRUE; printf("%c ", graph->table[i].ch); EdgeNode *p = graph->table[i].firstEdgeNode; while (p) { if (!verts_visit[p->table_index]) { MG_DFS_adjtable(graph, p->table_index); } p = p->next; } } // 可能包含非连通图 void MG_Traverse_adjtable(AdjGraphLink graph) { printf("邻接表方式 - 开始深度优先遍历\n"); for (int i = 0; i < graph->node_num; i++) { verts_visit[i] = FALSE; } for (int i = 0; i < graph->node_num; i++) { if (!verts_visit[i]) { MG_DFS_adjtable(graph, i); } } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
// 邻接矩阵方式 - 判断是否完全连通图 bool MatrixGraph_Check_Completely_Connected(MatrixGraph *graph) { for (int i = 0; i < graph->num_vertex; i++) { verts_visit[i] = FALSE; } int loop_count = 0; for (int i = 0; i < graph->num_vertex; i++) { if (!verts_visit[i]) { loop_count++; MG_DFS(graph, i); } } if (loop_count > 1) { return false; } return true; } // 邻接表方式 - 判断是否完全连通图 bool AdjGraph_Check_Completely_Connected(AdjGraphLink graph) { for (int i = 0; i < graph->node_num; i++) { verts_visit[i] = FALSE; } int loop_count = 0; for (int i = 0; i < graph->node_num; i++) { if (!verts_visit[i]) { loop_count++; MG_DFS_adjtable(graph, i); } } if (loop_count > 1) { return false; } return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
#define QUEUE_MAX 50 // 广度优先遍历 依赖 队列 typedef struct QueueNode { int data[QUEUE_MAX]; int front; // 队列的头 int rear; // 队列的尾 } QueueNode, *Queue; void InitQueue(Queue queue) { queue->front = 0; queue->rear = 0; } bool QueueEmpty(Queue queue) { return queue->front == queue->rear; } bool QueueFull(Queue queue) { return (queue->rear + 1) % QUEUE_MAX == queue->front; } // 队首元素 int QueueHead(Queue queue) { return queue->front; } // 队尾元素 int QueueRear(Queue queue) { return queue->rear; } // 队列中元素长度 int QueueLen(Queue queue) { return (queue->rear - queue->front + QUEUE_MAX) % QUEUE_MAX; } // 入队 bool EnQueue(Queue queue, int data) { if (QueueFull(queue)) { return false; } queue->data[queue->rear] = data; queue->rear = (queue->rear + 1) % QUEUE_MAX; return true; } // 出队 bool DeQueue(Queue queue, int *data) { if (QueueEmpty(queue)) { return false; } *data = queue->data[queue->front]; queue->front = (queue->front + 1) % QUEUE_MAX; return true; } // 遍历队列 void Queue_Traverse(Queue queue) { if (QueueEmpty(queue)) { return; } int i = queue->front; printf("队列中的元素:\n"); while (queue->front != queue->rear) { printf("%d ", queue->data[i]); i = (i + 1) % QUEUE_MAX; } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
// 邻接矩阵广度优先遍历 void BFS_MatrixTraverse(MatrixGraph *graph) { printf("邻接矩阵 广度优先遍历\n"); // verts_visit 重置 for (int i = 0; i < graph->num_vertex; i++) { verts_visit[i] = FALSE; } // 创建队列 QueueNode qu; Queue queue = &qu; InitQueue(queue); // 防止出现 不连通图的情况 for (int i = 0; i < graph->num_vertex; i++) { if (!verts_visit[i]) { verts_visit[i] = TRUE; printf("%c ", graph->verts[i]); // 入队 if (!EnQueue(queue, i)) { printf("操作入队列出现异常....\n"); return; } while (!QueueEmpty(queue)) { // 出队 i存储出队的元素 if (!DeQueue(queue, &i)) { printf("操作出队列出现异常....\n"); return; } // 遍历 出队的元素i 的结点 连通的其他结点 for (int j = 0; j < graph->num_vertex; j++) { if (graph->matrix[i][j] != 0 && graph->matrix[i][j] != GRAPH_INFINITY && !verts_visit[j]) { verts_visit[j] = TRUE; printf("%c ", graph->verts[j]); if (!EnQueue(queue, j)) { printf("操作入队列出现异常....\n"); return; } } } } } } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
// 邻接表广度优先遍历 void BFS_AdjTraverse(AdjGraphLink graph) { printf("邻接表 广度优先遍历\n"); // verts_visit 重置 for (int i = 0; i < graph->node_num; i++) { verts_visit[i] = FALSE; } // 创建队列 QueueNode qu; Queue queue = &qu; InitQueue(queue); // 防止出现 不连通图的情况 for (int i = 0; i < graph->node_num; i++) { if (!verts_visit[i]) { verts_visit[i] = TRUE; printf("%c ", graph->table[i].ch); // 入队 if (!EnQueue(queue, i)) { printf("操作入队列出现异常....\n"); return; } while (!QueueEmpty(queue)) { // 出队 i存储出队的元素 if (!DeQueue(queue, &i)) { printf("操作出队列出现异常....\n"); return; } // 遍历 出队的元素i 的结点 连通的其他结点 EdgeNode *enode = graph->table[i].firstEdgeNode; while (enode != NULL) { if (!verts_visit[enode->table_index]) { verts_visit[enode->table_index] = TRUE; printf("%c ", graph->table[enode->table_index].ch); if (!EnQueue(queue, enode->table_index)) { printf("操作入队列出现异常....\n"); return; } } enode = enode->next; } } } } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
// void Prim_Mini_GenTree_MatrixGraph(MatrixGraph *graph) { // 1.确认是个连通图 if (!MatrixGraph_Check_Completely_Connected(graph)) { printf("----oops, 当前图是个非连通图....\n"); return; } int min; int sum = 0; // 存储 最小生成树 各边的权重累加之和 // 2.定义两个数组 // curr_associated_vertindex - 关联的顶点 下标 // curr_weigh_cost - 相关联的顶点之间的 权重weighs int curr_associated_vertindex[VERTEXMAX]; int curr_weigh_cost[VERTEXMAX]; // 第一个顶点 从 graph->verts[0]开始 curr_associated_vertindex[0] = 0; // curr_weigh_cost[0] = 0; // 表示 结点 已经加入到 最小生成树 // 3.第一个结点已经加入到最小生成树， 对 以上两个数组进行初始化 for (int i = 1; i < graph->num_vertex; i++) { curr_associated_vertindex[i] = 0; // 比如 第一个结点 已经找到了两条边， // 其余的边在矩阵里 都用 GRAPH_INFINITY标识，就表示不存在 curr_weigh_cost[i] = graph->matrix[0][i]; } // 4.循环curr_weigh_cost数组，找到最小权值，并获取到 关键顶点 // (从1开始, 因为0已经加入最小生成树了) int keyvert, j; printf("\n"); for (int i = 1; i < graph->num_vertex; i++) { min = GRAPH_INFINITY; j = 1; keyvert = 0; // 从1开始，找与 第一个结点有关的所有结点 // 5.拿第一个结点举例 // 5.1 - curr_associated_vertindex 中存储了 0结点 下标 // 5.2 - 遍历 curr_weigh_cost 中所有 与 0结点 相连的 权值 // 5.3 - 权值最小的，就把 相连结点 的下标 // 存进 curr_associated_vertindex里 while (j < graph->num_vertex) { // curr_weigh_cost里存放的是当前 相关的 结点 // 比如刚开始 - 具体实现其实存了邻接矩阵 [0][j] // 多个节点， 有些结点其实不存在，weight = 65535， // 只有一部分是正常的weigh 值 if (curr_weigh_cost[j] != 0 && curr_weigh_cost[j] < min) { // 如果 与结点 关联的结点 已经加入到了 最小生成树， // 会把 curr_weigh_cost中 相应位置的weigh 变为了0 min = curr_weigh_cost[j]; keyvert = j; } j++; } // curr_associated_vertindex[keyvert] 就存储了 上一次找到的结点 printf("(V%d-V%d)(%c-%c)[%d]\n", curr_associated_vertindex[keyvert], keyvert, graph->verts[curr_associated_vertindex[keyvert]], graph->verts[keyvert], graph->matrix[curr_associated_vertindex[keyvert]][keyvert]); sum += graph->matrix[curr_associated_vertindex[keyvert]][keyvert]; // keyvert加入最小生成树 为新增的结点 找到 与它有联系的 顶点 curr_weigh_cost[keyvert] = 0; // 6. 然后把刚加入最小生成树的结点 相关的结点 找出来， // 并找出当前节点 相连的结点 // 6.1 - 权值最小的结点 下标 存进 curr_associated_vertindex里 // 6.2 - 结点的最小权值 存进 curr_weigh_cost里 // 6.3 - 这样 curr_associated_vertindex里包含了 // 需要参与比较的结点 下标 // curr_weigh_cost里 包含了 以上结点 相关联 的边的 权重 for (j = 1; j < graph->num_vertex; j++) { // curr_weigh_cost 很多位置 默认你会存储 无穷大 // 还有一种情况， 如果别的结点 与 循环的当下结点 // 都 与另外同一个节点关联，哪个小就留哪个 if (curr_weigh_cost[j] != 0 && graph->matrix[keyvert][j] < curr_weigh_cost[j]) { curr_weigh_cost[j] = graph->matrix[keyvert][j]; // 解释意思： 新加到生成树的结点， 找出与此结点相连的所有结点 // 找到了，就把 相连的点index 加入到 // curr_associated_vertindex中 // 注意：此时加入到 curr_associated_vertindex // 中的是 curr_weigh_cost的 索引 // 因为下次要比较 所有与 点相关的 权值最小的 curr_associated_vertindex[j] = keyvert; // 比如 v1 结点 连接了 v8 v2 v6 三个顶点 // 则 curr_associated_vertindex 中存储 // 就是 0 0 1 0 0 0 1 0 1 // 三个顶点都 存储了 1 } } } printf("最小生成树 权重： %d\n", sum); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
typedef struct Kruskal_Edge { int begin; int end; int weigh; } KEdge; void swap(KEdge array[], int i, int j) { KEdge temp = array[i]; array[i] = array[j]; array[j] = temp; } void q_sort(KEdge array[], int left, int right) { if (right < left) { return; } int mid_i = left; int l = left; int r = right; while (l < r) { while (l < r && array[r].weigh >= array[mid_i].weigh) { r--; } while (l < r && array[l].weigh <= array[mid_i].weigh) { l++; } if (l < r) { swap(array, l, r); } } swap(array, left, l); q_sort(array, left, l - 1); q_sort(array, r + 1, right); } void quicksort(KEdge array[], int n) { q_sort(array, 0, n - 1); } int find(int *parent, int f) { while (parent[f] > 0) { f = parent[f]; } return f; } // Kruskal - 邻接矩阵 - 最小生成树 // 转化成边表数组 void Kruskal_Mini_GenTree_MatrixGraph(MatrixGraph *graph) { KEdge *edges = (KEdge *)malloc(sizeof(KEdge) * graph->num_edge); int index = 0; for (int i = 0; i < graph->num_vertex; i++) { for (int j = i + 1; j < graph->num_vertex; j++) { if (graph->matrix[i][j] != GRAPH_INFINITY) { KEdge edge; edge.begin = i; edge.end = j; edge.weigh = graph->matrix[i][j]; edges[index] = edge; index++; } } } printf("邻接矩阵转换为边表:\n"); for (int i = 0; i < graph->num_edge; i++) { printf("(%d, %d, %d)\n", edges[i].begin, edges[i].end, edges[i].weigh); } printf("\n"); int *parent = (int *)malloc(sizeof(int) * graph->num_vertex); for (int i = 0; i < graph->num_vertex; i++) { parent[i] = 0; } // 边表数组 按照权值排序 quicksort(edges, graph->num_edge); // int m = 0, n = 0; int sum = 0; for (int i = 0; i < graph->num_edge; i++) { n = find(parent, edges[i].begin); m = find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("(V%d-V%d)(%c-%c)[%d]\n", edges[i].begin, edges[i].end, graph->verts[edges[i].begin], graph->verts[edges[i].end], edges[i].weigh); sum += edges[i].weigh; } } printf("Kruskal 最小生成树 总权重：%d\n", sum); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
void test_graph_mini_gentree(void) { MatrixGraph graph; CreateMatrixGraph(&graph); MG_Traverse(&graph); // 用邻接矩阵的数据 初始化 邻接表 AdjGraph adj_table_graph; CreteAdjTableGraph(&graph, &adj_table_graph); MG_Traverse_adjtable(&adj_table_graph); // 邻接矩阵广度优先遍历 BFS_MatrixTraverse(&graph); // 邻接表广度优先遍历 BFS_AdjTraverse(&adj_table_graph); // prim最小生成树 - 邻接矩阵 printf("prim - 邻接矩阵方式 - 最小生成树: \n"); Prim_Mini_GenTree_MatrixGraph(&graph); // kruskal 最小生成树 - 邻接矩阵 printf("kruskal - 邻接矩阵方式 - 最小生成树: \n"); Kruskal_Mini_GenTree_MatrixGraph(&graph); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
构建数据
A B C D E F G H I
0 1 2 3 4 5 6 7 8
输入第1条边(i, j): 0,1 权重 10
输入第2条边(i, j): 0,5 11
输入第3条边(i, j): 1,6 16
输入第4条边(i, j): 5,6 17
输入第5条边(i, j): 1,8 12
输入第6条边(i, j): 6,7 19
输入第7条边(i, j): 1,2 18
输入第8条边(i, j): 8,2 8
输入第9条边(i, j): 2,3 22
输入第10条边(i, j): 8,3 21
输入第11条边(i, j): 6,3 24
输入第12条边(i, j): 7,3 16
输入第13条边(i, j): 7,4 7
输入第14条边(i, j): 3,4 20
输入第15条边(i, j): 5,4 26 -
相关阅读:
JavaScript高阶笔记总结（Xmind格式）：第一天
python+vue+elementui精品课程教学网站系统pycharm源码
linux多个jdk时，java -version显示的版本有错误
python--数据容器--字典
一文详解用 eBPF 观测 HTTP
基于Go语言的网盘开发（GloudDisk）
全栈性能测试工具：RunnerGo
MongoDB文档存储
Spring系列19：SpEL详解
Day 4 Qt
- 原文地址：https://blog.csdn.net/qq_42431419/article/details/126357856
