最小生成树
Created|Updated
|Post Views:
Minimum Spanning Tree
- 若图中有v个顶点，那么将生成v-1条边
- 这棵树包含了全部的顶点
- 不能有回路，且向树添加一条边就有回路
- 图连通<=>最小生成树存在
- 不唯一
Related Articles
2020-05-23
二叉查找树
前言二叉查找树的插入，删除等操作上都运用了递归来实现。首先，需要了解递归在执行递归调用之后的语句要以之前保存的变量反方向执行。 Insert这里的if-else看成一块，而return看成另一块。 每次插入会比较节点的大小，大的return右孩子，小的return左孩子，直到找的到孩子为NULL就创建节点T->Left = Insert(X, T->Left);T->Right = Insert(X, T->Right); 如果，我们传入根节点，那么递归调用之前的语句被执行后，均按被调函数相反的顺序执行。所以，最后会传回根节点。 123456789101112131415161718192021SearchTree Insert(ElementType X, SearchTree T){ if(T == NULL) { /* Create and return a one-node tree */ T = malloc(sizeof(TreeNode)); if(T == N...
2020-05-28
图的遍历
Depth_First_Search过程 从某个顶点v1出发，然后找到并访问与v1的邻接点（且从未访问过）v2，再从v2出发访问与v2相邻的顶点。–>这就是递归思想 直到所有的顶点被访问到。 因为要记录该点是否被访问过，所以需要一个数组bool visited[MAXVEX]; 邻接矩阵遍历12345678910111213141516171819202122void DFS(MGraph G, int i){ int j; visited[i] = true; printf("%c ", G.vexs[i]); for(j = 0; j < G.numVertexs; j++) { //有边(i--j)，且 j 顶点没被访问 if(G.arc[i][j] == 1 && visited[j] == false) DFS(G, j); }}void DFSTraverse(MGraph G)...
2020-05-05
线性表的顺序存储结构
前言线性表有一种物理结构叫顺序存储结构。它由一系列连续的存储单元组成，从而使得逻辑上相邻的两个元素也连续。 这样的结构可以使用一维数组来实现。数组的下标从0开始，但我们的元素是从1开始。所以，我们可以这样看：元素均对应，但标志不一样（只需在用[]时，-1即可） 12345#define MaxSize 50 // 定义线性表的最大长度typedef struct{ ElemType data [MaxSize] ; // 表的元素 int length; // 线性表的当前长度}SqList; // 表的类型定义 注意线性表长度和数组长度不同 操作Insert 如果线性表长度等于数组长度，退出 如果插入到线性表长度+1以外，退出 如果不是插到最后（length + 1），那么for，从最后一个元素到第i个，一个个往后退 Delete 如果线性表为空，退出 如果删除表以外的数据，退出 如果不是删除最后位置，for，从i+1到length一个个向前移 示例11234567891011121314151617#define TSIZE ...
2020-05-03
双链表交换元素
前言双链表和单链表的插入，删除，交换。可以想象成锁链，但是，前后的链不能断开联系 交换123456789101112void SwapWithNextAndLast(Position BeforeP){ Position P = BeforeP->next; Position AfterP = P->next; P->next = AfterP->next; BeforeP->next = AfterP; AfterP->next = P; P->next->last = P;//注意这行！不能用AfterP->last，因为P和AfterP的位置改变 P->last = AfterP; AfterP->last = BeforeP;} 插入*只要把S指针与前后相连，S->next，S->prior与前后指针相连。*就完成了。 主要方法 把S的prior,next搞定 再将After的prior与S连上，为了不断线 最后，切断B...
2020-05-26
图的存储结构
前言由于图的多方向性，不能用顺序存储结构来实现。如果我用多重链表的话，那么结构中的多个指针就会造成空间资源的浪费（因为图的顶点上的度是不确定的）。因此图的存储结构，不应该使用物理存储去实现。图的实现被提供了5种存储结构。1. 邻接矩阵 2.邻链表 3.十字链表 4. 邻接多重链表 5. 边集数组。 邻接矩阵由顶点数组（一维）和边或弧数组（二维）组成 无向图 例如a[i][j]的0，1值表示，从i–j这个edge是否存在，1存在，0不存在。所以类似于a[i][i]这样的顶点到顶点的值都为0 无向图的边数组是一个对称矩阵，即满足a[i][j] == a[j][i]因为它是无向的，i–j不存在，则j–i也不存在。那么i–j存在，则，j–i也存在啊所以，在无向图中a[i][j]和a[j][i]无区别 Vi的度就是把第i行（或列）的元素加起来 有向图 有向图就不是对称矩阵了。因为它们顶点的指向是有方向的，i–>j不一定j–>i。 出度和入度。有向图中，要研究这两个。只要知道前面的指向问题，就可以知道。Vi的出度是看矩阵中的行a[i]--[]，Vi的入度是看矩阵中的...
2020-05-17
遍历二叉树
概念二叉树的遍历是从根节点出发，按照某几种不同的顺序遍历每个节点，使得每个节点被遍历仅一遍。这些遍历方法分为：1. 前序遍历2. 中序遍历3. 后序遍历4. 层序遍历规则：若树为空(T == NULL)，则空操作返回(return)，否则执行访问（递归） 说明如何看待遍历顺序？![(https://i.loli.net/2020/05/19/1W6rsVNP9hJubB8.png) 这张图已经完美说明了。首先，把这颗树加上空节点看成是完全二叉树，然后就它们的孩子嵌套并于括号括起来。 前序遍历 打印顺序：父母。左子孙。右子孙。 12345678void PreOrderTraverse(Tree T){ if(T == NULL) return; printf("%c", T->e); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);} 中顺遍历 打印顺序：左子孙。父母。右子孙。 12345678void InOrd...
Contents