10.哈夫曼树
哈夫曼编码是已知的最早用于数据压缩的方案，在解释哈夫曼树之前先要再介绍几个概念。
节点的路径长度：从根节点到某一个节点的路径上的连接数
树的路径长度：所有叶子节点的路径长度之和
节点的带权路径长度：某一个节点的权重乘以这个节点的路径长度
树的带权路径长度（WPL）：每个叶子节点的带权路径长度之和，树形压缩编码性能的体现
在通讯当中，数据都是通过二进制对每个字符进行编码的，对于编码的要求是长度要尽可能的短，且不可产生二异性（同一串编码有两种不同的含义）。哈夫曼编码的作用就是能够构造出相对较短的二进制树并保证不产生二义性，WPL越小，构造出的树性能就越优。哈夫曼编码是变长编码，我们比价熟悉的定长编码有ASCII码，这里的哈夫曼为什么不用定长编码呢？因为每次输入的数据种类是不确定的，这时候如果用定长编码，数据超出范围了就会无法编码，数据量过少又会造成编码空间的浪费，所以变长空间更适合哈夫曼编码。变长就意味着字符的编码后长度是不一样的，那怎么调节每个字符的编码后长度呢？这是根据这个字符整体出现的频率来调节的，出现的频率高的字符，我们就让他的编码长度短。
①哈夫曼编码实现原理
按照二叉树的形状，每一个叶子结点都代表一个字符，从节点到左孩子的路径标记为0，到右孩子的路径标记为1。光是用语言描述比较抽象，比如我们现在要对ABCD四个字符进行编码,A的使用频率为7，B的使用频率为5，C的使用频率为2，D的使用频率为4，那么对应的哈夫曼树如下。
下面是哈夫曼树的抽象数据类型
weight 叶子结点的权值 lChild rChild 指向孩子节点的指针 parent 父节点的指针
1. typedef struct { 2. //叶子结点的权值 3. int weight; 4. //需要指向孩子的指针 5. int lChild, rChild; 6. int parent;//父节点的指针 7. }Node, * HuffmanTree;
②创建哈夫曼树
这里我们使用数组去存储哈夫曼树的节点，相比链表数组这里能够更好地实现哈夫曼树频繁的查找，因为对于哈夫曼树的创建操作的量是比较大的，需要我们先进行查找出使用频率最小的两个节点（包括合并后的节点），再依次往上构建哈夫曼树。这里我们就先已知查找最小的两个节点的函数select（下面会细讲其实现），书写创造哈夫曼树的操作。
比如我们要对m个数据进行哈夫曼编码，根据二叉树的性质，m个子节点的二叉树一共有2m+1个节点。接下来我们要对其做初始化操作，分别是对叶子结点的初始化：将每个节点的权值变成该节点原有的权值，将其父子节初始化为0，非叶子节点的初始化：将每个节点的权值，父子节点全都变成0。接下去我们就开始构建整个哈夫曼树，通过select函数找到使用频率最小的两个节点（包括非叶子节点），并对这两个节点进行合并，修改他们的父子节点，具体代码如下。
1. void creatHuffmanTree(HuffmanTree* huffmanTree, int w[], int n) 2. { 3. //需要有变量 来算哈夫曼树全部的结点数 4. int m = 2 * n - 1; 5. int s1, s2;//为当前结点中。选取的权值最小的两个结点 6. //创建哈夫曼树的结点所需要的空间 m+1 7. //free还是delete 那个空间的长度坚决不能变 会直接跑死 8. *huffmanTree = (HuffmanTree)malloc((m + 1) * sizeof(Node)); 9. //1---n号元素全部存放叶子 初始化叶子结点 10. for (int i = 1; i <= n; i++) 11. { 12. (*huffmanTree)[i].weight = w[i]; 13. (*huffmanTree)[i].lChild = 0; 14. (*huffmanTree)[i].parent = 0; 15. (*huffmanTree)[i].rChild = 0; 16. } 17. //n ---- 最后一个元素是存放非叶子 初始化非叶子结点 18. for (int i = n + 1; i <= m; i++) 19. { 20. (*huffmanTree)[i].weight = 0; 21. (*huffmanTree)[i].lChild = 0; 22. (*huffmanTree)[i].parent = 0; 23. (*huffmanTree)[i].rChild = 0; 24. } 25. //开始构建哈夫曼树 够造的次数是确定的 26. for (int i = n + 1; i <= m; i++) 27. { 28. //先选两个最小的 在从1 ~~ i-1的范围内选择两个父节点为0 并且权值最小的 29. select(huffmanTree, i - 1, &s1, &s2); 30. //选出的两个权值最小的叶子结点 组成一颗新的二叉树 根节点为i 31. (*huffmanTree)[s1].parent = i; 32. (*huffmanTree)[s2].parent = i; 33. (*huffmanTree)[i].lChild = s1; 34. (*huffmanTree)[i].rChild = s2; 35. (*huffmanTree)[i].weight = (*huffmanTree)[s1].weight + (*huffmanTree)[s2].weight; 36. } 37. 38. }
③查找使用频率最小的节点
上面我们通过select去查找使用频率最小的节点，即权值最小的节点，这里我们通过地址传递的方式把两个最小节点给到创建树的函数，具体实现的方式是通过遍历的方式找到找到最小节点，是非常好理解的，具体代码如下。
1. //先选两个最小的 在从1 ~~ i-1的范围内选择两个父节点为0 并且权值最小的 2. void select(HuffmanTree* huffmanTree, int n, int* s1, int* s2) 3. { 4. int min;//需要有个变量记录最小值 5. //第一遍遍历 找出单节点 6. for (int i = 1; i <= n; i++) 7. { 8. //如果此节点的父节点没有 那么把结点的序号赋值给min 跳出 9. if ((*huffmanTree)[i].parent == 0) 10. { 11. min = i; 12. break; 13. } 14. 15. } 16. //继续遍历全部结点 找到权值最小的 17. for (int i = 1; i <= n; i++) 18. { 19. //判断父节点为空 进入下一个判断 20. if ((*huffmanTree)[i].parent == 0) 21. { 22. //判断权值大小 23. if ((*huffmanTree)[i].weight < (*huffmanTree)[min].weight) 24. { 25. min = i; 26. } 27. } 28. } 29. *s1 = min; 30. 31. for (int i = 1; i <= n; i++) 32. { 33. //如果此节点的父节点没有 那么把结点的序号赋值给min 跳出 34. if ((*huffmanTree)[i].parent == 0 && i != (*s1)) 35. { 36. min = i; 37. break; 38. } 39. 40. } 41. //继续遍历全部结点 找到权值最小的 42. for (int i = 1; i <= n; i++) 43. { 44. //判断父节点为空 进入下一个判断 45. if ((*huffmanTree)[i].parent == 0 && i != (*s1)) 46. { 47. //判断权值大小 48. if ((*huffmanTree)[i].weight < (*huffmanTree)[min].weight) 49. { 50. min = i; 51. } 52. } 53. } 54. *s2 = min; 55. }
④通过哈夫曼树实现哈夫曼编码
创建完哈夫曼树之后我们要通过此树来生成每一个数据具体对应的哈夫曼编码。首先我们要分配求出当前编码的工作空间，通过逆向求每个叶子结点对应的哈夫曼编码，再分配这些编码原先数据的存储位置，因为我们是通过从叶子节点一直往根节点走的方式去编码所以这里我们要从右向左逐位存放编码，具体代码如下。
1. //从n个叶子结点到跟 逆向求每个叶子结点对应的哈夫曼编码 2. void creatHuffmanCode(HuffmanTree* huffmanTree, HuffmanCode* huffmanCode, int n) 3. { 4. int c;//当做遍历n个叶子结点的指示标记 5. int p;//指向当前结点的父节点 6. int start;//当做编码的起始指针 7. //分配n个编码的头指针 8. huffmanCode = (HuffmanCode*)malloc((n + 1) * sizeof(char*)); 9. //分配求当前编码的工作空间 10. char* cd = (char*)malloc(n * sizeof(char)); 11. //从右向左逐位存放编码 先写好编码的结束符 12. cd[n - 1] = '\0'; 13. //求编码 14. for (int i = 1; i <= n; i++) 15. { 16. start = n - 1; 17. //从叶子到根节点求编码 18. for (c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent) 19. { 20. if ((*huffmanTree)[p].lChild == c) 21. { 22. cd[--start] = '0'; 23. } 24. else 25. { 26. cd[--start] = '1'; 27. } 28. } 29. //为第i个编码分配空间 30. huffmanCode[i] = (char*)malloc((n - start) * sizeof(char)); 31. 32. strcpy(huffmanCode[i], &cd[start]); 33. } 34. 35. for (int i = 1; i <= n; i++) 36. { 37. printf("%s", huffmanCode[i]); 38. } 39. }
四、图
1.图的基本概念
线性表能表示一对一的关系，树形结构能表示一对多的关系，图就是表示多对多的关系。
图是由两个集合组成：（V）顶点集合和（E）边集合。下面介绍一些基本图的概念。
简单图：在图结构中，如果不存在顶点到其自身的边，且同一条边不会重复出现。
无向图：边没有方向的图
完全图：任意两个顶点间都存在一条边。
端点、邻接点：无向图中一条边两边的顶点为这个边的端点，这两个点互为邻接点，若为有向图则为起点合终点。
无向图中顶点具有的边的数目就叫做顶点的度，有向图中边向外的数目是出度数目，边向里的数目是入度数目。
子图：如果一个图是另一个图的子集（顶点和边都得是），那这个图就是他的子图
路径（顶点序列）：从任一顶点开始，由边或弧的邻接至关系构成的有限长顶点序列称为路径
路径长度：从顶点到另一个顶点经过边的数目
回路和环：开始节点和结束节点相同
欧拉回路：经过图中各边一次且恰好一次
哈密顿回路：经过图中各顶点一次且恰好一次
连通：无向图中两个顶点间如果有路径，就是连通的，如果任意两个顶点间都连通，就叫做连通图，在一个无向图中的一个极大连通子图，叫做那个图的连通分量。
强连通图、强连通分量：即上面的调节里无向图改为有向图。
稠密图、稀疏图：一个图接近完全图是稠密图，一个图边较少的为稀疏图（具体数据人为定义）
权和网：带权的图就是网
连通图的生成树：一个图的极小连通子树就是他得连通图的生成树
2.邻接矩阵
对于这样一个图，我们需要存储他的顶点数据和边的数据，邻接矩阵分别通过一个以为数组和一个二维数组来存储，具体如下。
第一行表示的是每个顶点的数据，下面的表格行与列表示着每个顶点，如果中间的数据为1则表示那两个顶点是连通的，这张表存储加权图的时候，顶点之间的权重写在连通位置取代1就行。这样的存储方式在边较少时会浪费掉很大的内存，里面很多边不存在的情况我们也要用0去表示，为了解决这一问题出现了邻接表存储方式。下面是他的抽象数据类型。
Vertices 存储顶点 Edge 存储边 numV numE 顶点数，边数
1. typedef struct { 2. //一个一维数组 代表顶点信息 二维数组代表边的信息 3. int Vertices[MaxVertices]; 4. int Edge[MaxVertices][MaxVertices]; 5. int numV, numE;//顶点数，和边数 6. }AdjMatrix;
①存储操作
存储操作是通过两个数组实现的，书写的逻辑非常简单，主要是初始化和输入数据两个操作，要注意的是初始化边的时候上下顶点相同的点要以一个特殊数去区分，这里就直接放代码了。
1. #include<stdio.h> 2. #include<stdlib.h> 3. #define MaxVertices 100 4. 5. void CreateGraph(AdjMatrix * G) 6. { 7. int n, e;//n代表顶点数 e代表边数 8. int vi, vj;//输入边的时候 要读取的顶点对 9. printf("输入顶点数和边数"); 10. scanf_s("%d%d", &n, &e); 11. G->numV = n; G->numE = e; 12. //图的初始化操作 13. for (int i = 0; i < n; i++) 14. { 15. for (int j = 0; j < n; j++) { 16. if (i == j) 17. { 18. G->Edge[i][j] = 0; 19. } 20. else { 21. G->Edge[i][j] = 32767; 22. } 23. } 24. 25. } 26. //将顶点存入数组 27. for (size_t i = 0; i < G->numV; i++) 28. { 29. printf("请输入第%d个顶点的信息",i + 1); 30. scanf_s("%d", &G->Vertices[i]); 31. } 32. //输入边的信息 33. for (int i = 0; i < G->numE; i++) 34. { 35. printf("请输入边的信息i,j"); 36. //如果输入的顶点对是值 那还要从顶点集里面查找相对应的下标 37. //如果只是输入顶点的个数，直接算下标就可以了 38. scanf_s("%d%d", &vi, &vj); 39. //如果是无向图 直接等于1 40. //如果是带权图 等于权值 41. //如果有向图 那就不对称 42. G->Edge[vi - 1][vj - 1] = 1; 43. G->Edge[vj - 1][vi - 1] = 1; 44. } 45. 46. }
3.邻接表
邻接矩阵是通过二维数组存储的边，而邻接表是通过在顶点后面用链表来存储边的。
像上面这张图就表示0顶点和1 2 3顶点是想通的。这能非常明确的表现一个顶点的出度，还有一种表为逆邻接表，作用即为表现一个顶点的入度。
下面先介绍邻接表的抽象数据类型，这里主要分为存储边的和存储顶点的，最后集合于GraphAdjList中实现邻接表的所有功能。
1. #define MAXVEX 100//表示顶点的数目 2. //边表的结构 3. typedef struct EdgeNode { 4. int adjvex;//邻接的点所对应的下标 5. struct EdgeNode* next;//指向下一个的指针 6. //int weight//权值 7. }EdgeNode; 8. //顶点表的结构 9. typedef struct VertexNode { 10. char data;//存放信息的值 11. EdgeNode* first;//边表的头指针 12. }VertexNode , AdjList[MAXVEX]; 13. //邻接表的抽象结构 14. typedef struct GraphAdjList { 15. AdjList adjlist;//顶点集合数组 16. int numVertexes, numEdge;//顶点的数量和边的数量 17. }GraphAdjList;
①存储操作
这里我们以无向图举例，在最开始我们还是要输入所有顶点的信息，然后再依次输入边的信息，唯一不同到的地方就是边的存储格式变为链条存储而已，具体代码如下。
1. //无向图构建邻接表 2. void CreateAlGraph(GraphAdjList* G) 3. { 4. printf("输入顶点数和边数"); 5. scanf_s("%d%d", &G->numVertexes, &G->numEdge); 6. int vi, vj;//接收边的顶点对的信息 7. //输入顶点信息 8. for (int i = 0; i < G->numVertexes; i++) 9. { 10. scanf_s("%c",&G->adjlist[i]); 11. getchar(); 12. G->adjlist[i].first = NULL; 13. } 14. //输入图中边的信息 15. for (int i = 0; i < G->numEdge; i++) 16. { 17. scanf_s("%d%d", &vi, &vj );//就当他是下标 18. getchar(); 19. EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));//建立新的边表结点 20. //接下来就是头插 21. e->adjvex = vj; 22. e->next = G->adjlist[vi].first; 23. G->adjlist[vi].first = e; 24. EdgeNode* e1 = (EdgeNode*)malloc(sizeof(EdgeNode));//建立新的边表结点 25. //接下来就是头插 26. e1->adjvex = vi; 27. e1->next = G->adjlist[vj].first; 28. G->adjlist[vj].first = e1; 29. } 30. }
4.十字链表
邻接矩阵的优点在于能同时表现顶点的入度和出度，邻接表的优点在于能通过链式存储用较少的空间，将这两种结构合并就会成为十字链表
上图我们通过十字链表连接之后会生成下图的表，但由于还没有介绍他的抽象数据类型，一些连接方面的细节在下面会细讲。
下面是他的抽象数据类型，由于十字链表的基础结构与邻接表很相似，都是通过数组与链表实现的，只不过数组与链表的节点表示的不同而已，所以这里也是分为边集与顶点集，最后合并实现的十字链表，下面的图左边的是顶点集，右边的是边集。
1. #define MAX 200 2. //边集 3. typedef struct ArcBox { 4. int tailvex, headvex;//弧尾、弧头对应的顶点在数组中的下标 5. struct ArcBox* hlink, * tlink;//弧头、弧尾相同的下一个边（弧） 6. }ArcBox; 7. 8. //顶点集 9. typedef struct VexNode 10. { 11. int data;//数据域 12. ArcBox* firstIn, * firstOut;//以该节点为弧头或弧尾的链表的首节点 13. }VexNode; 14. 15. typedef struct { 16. VexNode xlist[MAX];//存储顶点的一维数组 17. int vexnum, arcnum;//顶点数，和边数 18. }OLGraph;
①存储操作
这里的存储操作的第一步还是建立顶点表，方法与之前都一样这里就不多说了，主要不同的步骤在于构建边表，构建边表的初始化同样是输入存在到的边，但是我们要实现通过输入的边建立相对应的弧变成了两个，就是不论是入度操作还是出度操作我们都要建立对应的弧，具体代码如下。
1. void CreatDG(OLGraph* G) 2. { 3. int vi, vj;//输入的是下标 4. //输入有向图的顶点数和边数 5. scanf_s("%d%d", &G->vexnum, &G->arcnum); 6. //先输入顶点集的数据 7. for (int i = 0; i < G->vexnum; i++) 8. { 9. scanf_s("%d", &G->xlist[i].data); 10. G->xlist[i].firstIn = NULL; 11. G->xlist[i].firstOut = NULL; 12. } 13. //构建十字链表 14. for (int i = 0; i < G->arcnum; i++) 15. { 16. //就当直接输入的下标 17. scanf_s("%d%d", &vi, &vj); 18. //建立弧的节点 19. ArcBox* p = (ArcBox*)malloc(sizeof(ArcBox)); 20. //存储弧头和弧尾所对应的下标的位置 21. p->tailvex = vi; 22. p->headvex = vj; 23. //头插法插入新的边表结点p 24. p->hlink = G->xlist[vj].firstIn;//指向弧头相同的下一个弧 25. p->tlink = G->xlist[vi].firstOut;//指向弧尾相同的下一个弧 26. G->xlist[vi].firstOut = G->xlist[vj].firstIn = p; 27. } 28. }
十字链表的缺点是对于边的操作不方便，如果对边的增删改查很多的时候就不建议用他。
5.临接多重表
邻接多重表是无向图的一种存储结构。如果在无向图中我们的侧重点在顶点上，那么使邻接表是很合适的，当我们的侧重点在边上，也就是需要对边增删查改的时候，用邻接多重表就更加合适了。
临接多重表具体是怎么实现的？这里直接看他的抽象数据类型，左边的图是顶点集，右边的图是边集。顶点集VexNode由顶点的数据域data和指向顶点所连接的边节点的指针firstEdge构成。边集里iVex和jVex是一条边连接的两个节点（Vi，Vj）在顶点集中的下标，headEdge和tailEdge分别是指向有着相同头、尾节点的边节点的指针，代码与图如下。
1. #define MAX 100 2. //确定边的类型 3. typedef struct node { 4. int ivex, jvex; 5. struct node* Vi; 6. struct node* Vj; 7. }ArcNode; 8. //确定顶点表中的属性 9. typedef struct { 10. char vertex; 11. ArcNode* first; 12. }VNode; 13. //邻接多重表的抽象类型 14. typedef struct 15. { 16. VNode Dvex[MAX]; 17. int vexnum, arcnum; 18. }Grap;
①存储操作
前面的初始化操作都是一样的，先接收顶点再接收边的信息，唯一不同的地方还是在于每个边域顶点连接的关系，这里的关系有代码表示最清晰，我就不多说了，代码如下。
1. //建立邻接多重表 2. void creat(Grap* G) 3. { 4. //接收两端的值和相对应的下标 我们就当接收的是下标 5. int vi, vj; 6. //先输入顶点数和边数 7. scanf_s("%d%d", &G->vexnum, &G->arcnum); 8. //输入顶点数组的值 9. for (int i = 0; i < G->vexnum; i++) 10. { 11. //输入顶点数组的值 12. scanf_s("%c", &G->Dvex[i].vertex); 13. //scanf注意清空缓冲区 14. G->Dvex[i].first = NULL; 15. } 16. for (int i = 0; i < G->arcnum; i++) 17. { 18. //先找到边对应的结点对的下标 19. scanf_s("%d%d", &vi, &vj); 20. ArcNode* e = (ArcNode*)malloc(sizeof(ArcNode)); 21. e->ivex = vi; 22. e->jvex = vj; 23. e->Vi = G->Dvex[vi].first; 24. G->Dvex[vi].first = e; 25. e->Vj = G->Dvex[vj].first; 26. G->Dvex[vj].first = e; 27. } 28. }
6.边集数组
边集数组由两个一维数组构成，一个存储顶点的信息，一个存储边的信息。
如上图，如果我们要存储这样的信息，顶点的信息将会直接存储在一维数组里，边的信息会存储他两边的顶点与该边的权值。
这个的实现后面会用到，这里就不实现了。
7.图的遍历
对于图的遍历我们能发现与二叉树的会略有不同，因为通过二叉树的方法我们是没法很好的遍历一个图的，这里我们主要用的是深度优先搜索（DFS）与广度优先搜索（BFS）。
①深度优先搜索
在树中，树的中序、后序遍历方法都是深度优先思想，但是由于图相对于树的性质来说，一个图“子节点”的个数是不确定的，所以肯定会出现遗漏的点，这时候就体现深度优先搜索的另一个思想“回溯”，在递归返回的时候检验经过的节点所有的子节点是否有被遍历过（因为递归前没法确定有一个子节点去依次进入而递归后判断是可以的，这里不理解可以自己实现一下），若没有遍历过则在回溯时遍历。能满足这种操作的，很显然一个是递归，还有栈的压栈和出栈也能很好的实现这个功能。
这里我们先通过DFS实现一次图的遍历，分别是遍历的操作和回溯查找未遍历过得节点，代码如下。
1. #include <stdio.h> 2. #include <stdlib.h> 3. /* 4. 创建无向图并进行深度优先搜索 5. */ 6. #define MAXN 100 7. typedef struct ArcCell { 8. char vexnum[MAXN]; //顶点 9. int arcnum[MAXN][MAXN]; //弧 10. int n, e; //顶点数， 弧数 11. }Graph; 12. 13. void CreateGraph(Graph* G) { //创建图 ，此处注意&G 14. int s, t; 15. scanf("%d %d", &G->n, &G->e); 16. getchar(); 17. for (int i = 0; i < G->n; i++) { 18. scanf("%c", &G->vexnum[i]); 19. } 20. for (int i = 0; i < G->n; i++) { //初始化数据 21. for (int j = 0; j < G->n; j++) { 22. G->arcnum[i][j] = 0; 23. } 24. } 25. for (int i = 0; i < G->e; i++) { //创建图的邻接矩阵 26. scanf("%d %d", &s, &t); 27. G->arcnum[s][t] = 1; 28. G->arcnum[t][s] = 1; 29. } 30. } 31. //需要有个东西来判断顶点是否被访问 32. int Visit[MAXN] = { 0 };//定义一个数组并进行初始化操作 1代表结点被访问 33. 34. void DFSTraverse(Graph G, int i)//对于连通分量进行深度搜索 35. { 36. printf("%c", G.vexnum[i]); 37. for (int j = 0; j < G.n; j++) 38. { 39. if(G.arcnum[i][j] && !Visit[j] ) 40. { 41. Visit[j] = 1; 42. DFSTraverse(G, j); 43. } 44. } 45. } 46. 47. void DFS(Graph G)//对整个图进行深度搜索 48. { 49. //思考邻接矩阵和无向图来思考整个遍历过程 50. for (int i = 0; i < G.n; i++) 51. { 52. if (!Visit[i])//如果相对应的结点没有被访问过 53. { 54. Visit[i] = 1; 55. DFSTraverse(G, i);//连通分量 56. } 57. 58. } 59. } 60. 61. int main() 62. { 63. Graph* g = (Graph*)malloc(sizeof(Graph)); 64. CreateGrahp(g); 65. DFS(g); 66. 67. return 0; 68. }
②广度优先搜索
广度优先搜索在实现的方面与我们之前的层序遍历完全一致，这一块可以用递归或者队列去实现，具体实现的操作是将出队的节点遍历，并将出队节点的连接的节点都入队，每个节点都只能遍历一次所以还需要知道该节点是否出队过，具体代码如下。
1. #include <stdio.h> 2. #include <stdlib.h> 3. #define MAX_VERtEX_NUM 20 //顶点的最大个数 4. #define VRType int //表示顶点之间的关系的变量类型 5. #define InfoType char //存储弧或者边额外信息的指针变量类型 6. #define VertexType int //图中顶点的数据类型 7. typedef enum { false, true }bool; //定义bool型常量 8. bool visited[MAX_VERtEX_NUM]; //设置全局数组，记录标记顶点是否被访问过 9. typedef struct Queue { 10. VertexType data; 11. struct Queue* next; 12. }Queue; 13. typedef struct { 14. VRType adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。 15. InfoType* info; //弧或边额外含有的信息指针 16. }ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM]; 17. typedef struct { 18. VertexType vexs[MAX_VERtEX_NUM]; //存储图中顶点数据 19. AdjMatrix arcs; //二维数组，记录顶点之间的关系 20. int vexnum, arcnum; //记录图的顶点数和弧（边）数 21. }MGraph; 22. 23. //构造无向图 24. void CreateDN(MGraph* G) { 25. scanf_s("%d,%d", &(G->vexnum), &(G->arcnum)); 26. for (int i = 0; i < G->vexnum; i++) { 27. scanf_s("%d", &(G->vexs[i])); 28. } 29. for (int i = 0; i < G->vexnum; i++) { 30. for (int j = 0; j < G->vexnum; j++) { 31. G->arcs[i][j].adj = 0; 32. G->arcs[i][j].info = NULL; 33. } 34. } 35. for (int i = 0; i < G->arcnum; i++) { 36. int v1, v2; 37. scanf_s("%d,%d", &v1, &v2); 38. int n = LocateVex(G, v1); 39. int m = LocateVex(G, v2); 40. if (m == -1 || n == -1) { 41. printf("no this vertex\n"); 42. return; 43. } 44. G->arcs[n][m].adj = 1; 45. G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称 46. } 47. } 48. 49. //初始化队列 50. void InitQueue(Queue** Q) { 51. (*Q) = (Queue*)malloc(sizeof(Queue)); 52. (*Q)->next = NULL; 53. } 54. //顶点元素v进队列 55. void EnQueue(Queue** Q, VertexType v) { 56. Queue* element = (Queue*)malloc(sizeof(Queue)); 57. element->data = v; 58. element->next = NULL; 59. Queue* temp = (*Q); 60. while (temp->next != NULL) { 61. temp = temp->next; 62. } 63. temp->next = element; 64. } 65. //队头元素出队列 66. void DeQueue(Queue** Q, int* u) { 67. (*u) = (*Q)->next->data; 68. (*Q)->next = (*Q)->next->next; 69. } 70. //判断队列是否为空 71. bool QueueEmpty(Queue* Q) { 72. if (Q->next == NULL) { 73. return true; 74. } 75. return false; 76. } 77. 78. int LocateVex(MGraph* G,int v)//根据结点本身的数据 判断顶点在二维数组当中的位置 79. { 80. int i = 0; //遍历一维数组 81. for ( ; i< G->vexnum; i++) 82. { 83. if (G->vexs[i] == v) 84. { 85. break; 86. } 87. } 88. return i; 89. } 90. 91. int FirstAdjVex(MGraph G, int v) 92. { 93. for (int i = 0; i < G.vexnum; i++) 94. { 95. if (G.arcs[v][i].adj)//只要有边 返回下标 96. { 97. return i; 98. } 99. } 100. return -1; 101. } 102. 103. int NextAdjVex(MGraph G, int v, int w) 104. { 105. //从前一个访问位置w的下一个位置开始 查找与之右边的结点 106. for (int i = w + 1; i < G.vexnum; i++) 107. { 108. if (G.arcs[v][i].adj)//只要有边 返回下标 109. { 110. return i; 111. } 112. } 113. return -1; 114. } 115. 116. 117. 118. int visited[20] = {0}; 119. 120. void BFSTraverse(MGraph G) 121. { 122. //对于每一个未被访问的顶点调用广搜 123. Queue* Q; 124. InitQueue(&Q); 125. for (int i = 0; i < G.vexnum; i++) 126. { 127. if (!visited[i]) 128. { 129. visited[i] = 1; 130. printf("%d", G.vexs[i]);//输出已被访问的结点 131. EnQueue(&Q, G.vexs[i]); 132. while (!QueueEmpty(Q))//判断队列是否为空 133. { 134. int u;//看好你的队列取出的是下标还是元素 135. DeQueue(&Q, &u);//元素出队 136. //如果是元素 还要定位下标 遍历 137. u = LocateVex(&Q, u); 138. //查找与数组下标u的顶点之间有边的顶点 139. for ( int w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,w)) 140. { 141. //与之相邻的所有边 入队 142. if (!visited[w]) 143. { 144. visited[w] = 1; 145. printf("%d", G.vexs[i]);//输出已被访问的结点 146. EnQueue(&Q, G.vexs[w]); 147. } 148. } 149. } 150. } 151. } 152. }
8.最小生成树
对于一个连通图而言，他的生成树是一个极小连通子图，而针对带权图来说的边的权值之和最小的生成树就是最小生成树，下面介绍一些生成树的性质。
①对于一个包含n个顶点的完全图有n个生成树
②而对于有n个顶点的连通图而言，生成树有n-1条边
③一个连通图的生成树包含相同的顶点数和边数
④生成树不存在环
⑤生成树的基础上删除任意一条边都会导致图的不连通，而如果添加任意一条边都会形成环
①克鲁斯卡尔算法实现最小生成树逻辑
这个算法的核心思想与贪心算法相同，即每一步都作出当下最优解，通过局部最优解来实现整体最优。克鲁斯卡尔算法就是将每一个顶点都看作一个单独的树，不断地去找与之相邻的权值最小的点，同时不能成环，最后得到的生成树就是一个最小生成树，这里我是通过将权值升序排列来实现找到相邻权值最小的节点的。
已知我们要对权值进行升序排序，并且要在排序后将该边两边的顶点用于加入生成树，从这些我们就可以决定用边集数组去作为我们存储这个图的存储结构，下图就是图经过边集数组存储的样子
最后我们只需要从上往下依次把边与节点添加到树里，当遇到会导致树成环的边将其舍弃，就能形成最小生成树，这里具体怎么实现的判断树是否成环呢？我们通过并查集将所有使用过的边的顶点放在一个集合里，这时候我们要让本就在一条线里的数据有一个共同的标志，比如让一条线里的所有数据都指向该线里最大的数据，这时候如果添加进一个新边，而这条边两边的顶点已经有了共同的最大数据了，那这条边一定会造成树成环，便判断出了我们要舍弃的边。
②克鲁斯卡尔算法实现最小生成树代码实现
1. #include<stdio.h> 2. #include<stdlib.h> 3. #define MAXVEX 200 4. #define INFINTIY 65535 5. //克鲁斯卡尔 6. //邻接矩阵 7. typedef struct AdjacentMatrix 8. { 9. //顶点集 10. int Vertices[MAXVEX]; 11. //边集 12. int Arc[MAXVEX][MAXVEX]; 13. //顶点数 边数 14. int numV, numE; 15. }AdjMatrix; 16. //用带权无向邻接矩阵生成图 17. 18. //边集数组 19. typedef struct 20. { 21. int begin; 22. int end; 23. int weihgt; 24. }Edges; 25. 26. int Find(int* parent, int f) 27. { 28. while(parent[f] > 0) 29. { 30. f = parent[f]; 31. } 32. return f; 33. } 34. 35. void sort(Edges e[], AdjMatrix* G) 36. { 37. int i, j; 38. for(i = 0; i < G->numE; i++) 39. { 40. for(j = 0; j < G->numE; j++) 41. { 42. if(e[i].weihgt > e[j].weihgt) 43. { 44. //交换函数，暂时没学后面会讲 45. Swapn(e, i, j); 46. } 47. } 48. } 49. printf("按权排序后的为：\n"); 50. for(i = 0; i < G->numE; i++) 51. { 52. printf("(%d %d)%d\n", e[i].begin, e[i].end, e[i].weihgt); 53. } 54. } 55. 56. void Kruskal(AdjMatrix* G) 57. { 58. Edges e[20];//边集数组 59. //判断两边之间是否存在环 并查集 60. int parent[MAXVEX]; 61. int k = 0; 62. //根据图的存储来构建边集数组 63. for(int i = 0; i < G->numV; i++) 64. { 65. for(int j = 0; j < G->numV; j++) 66. { 67. //带权图邻接矩阵小于最大值 说明有边 68. if(G->Arc[i][j] < INFINTIY) 69. { 70. e[k].begin = i;//开始节点 71. e[k].end = j;//结束节点 72. e[k].weihgt = G->Arc[i][j]; 73. k++; 74. } 75. } 76. } 77. 78. //针对边集数组排序(按照权值排序) 79. sort(e, G); 80. //由于算法没学 这里构建图的时候按权值排序构建 81. 82. //初始化辅助数组 83. for(int i = 0; i < G->numV; i++) 84. { 85. parent[i] = 0; 86. } 87. //构建最小生成树 88. for(int i = 0; i < G->numE; i++)//循环遍历每一条边 直到放进了所有的边 89. { 90. //并查集 查 91. //在边集数组中 查找每一条边的起点 和 终点 92. int n = Find(parent, e[i].begin); 93. int m = Find(parent, e[i].end); 94. //n m没有构成环 或m n指向自己 95. if(n != m || n == m == 0) 96. { 97. //把这个节点的尾节点的下标放入parent中 98. parent[n] = m; 99. printf("(%d,%d)--%d这两点属于最小生成树的一部分", e[i].begin, e[i].end, e[i].weihgt); 100. } 101. } 102. }
