分类: 图

6 篇文章

6-4 图的深度遍历-邻接表实现 (10 分)
本题要求实现邻接表存储图的深度优先遍历。 函数接口定义: void DFS(ALGraph *G,int i); 其中ALGraph是邻接表存储的图,定义如下: #define MAX_VERTEX_NUM 10 /*定义最大顶点数*/ typedef int Vertex; typedef struct ArcNode{ /*表结点*/ int …
6-3 图的广度遍历-邻接表实现 (10 分)
本题要求实现邻接表存储图的广度优先遍历。 函数接口定义: void BFS(ALGraph *G,int i); 其中ALGraph是邻接表存储的图,定义如下: #define MAX_VERTEX_NUM 10 /*定义最大顶点数*/ typedef int Vertex; typedef struct ArcNode{ /*表结点*/ int …
6-2 图的广度遍历-邻接矩阵实现 (10 分)
本题要求实现邻接矩阵存储图的广度优先遍历。 函数接口定义: void BFS(MGraph G,Vertex i); 其中MGraph是邻接矩阵存储的图,定义如下: #define MaxVertexNum 10 /*定义最大顶点数*/ typedef int Vertex;/* 用顶点下标表示顶点,为整型 */ typedef struct{ i…
6-1 图的深度遍历-邻接矩阵实现 (10 分)
本题要求实现邻接矩阵存储图的深度优先遍历。 函数接口定义: void DFS(MGraph G,Vertex v); 其中MGraph是邻接矩阵存储的图,定义如下: #define MaxVertexNum 10 /*定义最大顶点数*/ typedef int Vertex;/* 用顶点下标表示顶点,为整型 */ typedef struct{ i…
Kruskal算法的思想
from: https://yq.aliyun.com/articles/674316 Kruskal算法的思想如下 假设有n个顶点的连通图。首先先构造有顶点构成的集合0,每个顶点都是一个集合,不含有任何边。在边找一个最小权值的边判断这个边的俩个顶点是否来自于两个不同的集合,若是就将它俩归并为一个集合,然后将这个边添加到要构成的图的集合中。直到上述…
Kruskal算法[贪心算法]
Kruskal算法的高效实现需要一种称作并查集的结构。我们在这里不介绍并查集,只介绍Kruskal算法的基本思想和证明,实现留在以后讨论。Kruskal算法的过程: (1) 将全部边按照权值由小到大排序。(2) 按顺序(边权由小到大的顺序)考虑每条边,只要这条边和我们已经选择的边不构成圈,就保留这条边,否则放弃这条边。 算法 成功选择(n-1)条边…