第1关：求图（邻接矩阵存储）最小生成树的普里姆（Prim）算法
任务描述
本关任务：图的存储结构为邻接矩阵，要求编写函数利用普里姆（Prim）算法求图的最小生成树。
测试说明
平台会对你编写的代码进行测试：
测试输入：
3
lt3.txt
0
输入说明：
第一行输入3，表示输入图的类型为无向网。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
5
8
0
1
2
3
4
0 1 1
0 2 3
0 3 4
0 4 7
1 2 2
2 3 5
2 4 8
3 4 6
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；
第三行输入利用普里姆算法构造最小生成树的起点。
预期输出：
无向网
5个顶点8条边。顶点依次是: 0 1 2 3 4
图的邻接矩阵:
∞ 1 3 4 7
1 ∞ 2 ∞ ∞
3 2 ∞ 5 8
4 ∞ 5 ∞ 6
7 ∞ 8 6 ∞
用普里姆算法从g的第0个顶点出发输出最小生成树的各条边:
最小代价生成树的各条边为:
边(0,1),权值为1
边(1,2),权值为2
边(0,3),权值为4
边(3,4),权值为6
输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后分行输出从第0个顶点出发用普里姆算法构造的最小生成树的各条边。
代码如下
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include"MGraph.h"
typedef struct min
{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G); // 求SZ.lowcost的最小正值，并返回其在SZ中的序号
void MiniSpanTree_PRIM(MGraph G,VertexType u); // 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
int main()
{
MGraph g;
int n;
CreateGraphF (g); // 利用数据文件创建无向图
Display(g); // 输出无向图
scanf("%d",&n);
printf("用普里姆算法从g的第%d个顶点出发输出最小生成树的各条边:\n",n);
MiniSpanTree_PRIM(g,g.vexs[n]); // Prim算法从第1个顶点构造最小生成树
return 0;
}
int minimum(minside SZ,MGraph G)
{ //求SZ.lowcost的最小正值，并返回其在SZ中的序号
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; // 第一个不为0的值
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0&&min>SZ[j].lowcost) // 找到新的大于0的最小值
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{
// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
/********** Begin **********/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j){
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
closedge[k].lowcost=0;
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i){
k=minimum(closedge,G);
printf("边(%s,%s),权值为%d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost){
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
/********** End **********/
}
第2关：求图（邻接表存储）最小生成树的普里姆（Prim）算法
任务描述
本关任务：图的存储结构为邻接表，要求编写函数利用普里姆（Prim）算法求图的最小生成树。
测试说明
平台会对你编写的代码进行测试：
测试输入：
3
lt3.txt
0
输入说明：
第一行输入3，表示输入图的类型为无向网。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
5
8
0
1
2
3
4
0 1 1
0 2 3
0 3 4
0 4 7
1 2 2
2 3 5
2 4 8
3 4 6
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；
第三行输入利用普里姆算法构造最小生成树的起点。
预期输出：
无向网
5个顶点：
0 1 2 3 4
8条弧(边):
0→4 :7 0→3 :4 0→2 :3 0→1 :1
1→2 :2 1→0 :1
2→4 :8 2→3 :5 2→1 :2 2→0 :3
3→4 :6 3→2 :5 3→0 :4
4→3 :6 4→2 :8 4→0 :7
用普里姆算法从g的第0个顶点出发输出最小生成树的各条边:
最小代价生成树的各条边为:
边(0,1),权值为1
边(1,2),权值为2
边(0,3),权值为4
边(3,4),权值为6
输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后分行输出从第1个顶点出发用普里姆算法构造的最小生成树的各条边。
代码如下
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include"ALGraph.h"
#define INFINITY 4270000
typedef int VRType;
typedef struct min
{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int GetWeight(ALGraph G,VertexType a,VertexType b );//获取权值
int minimum(minside SZ,ALGraph G); // 求SZ.lowcost的最小正值，并返回其在SZ中的序号
void MiniSpanTree_PRIM(ALGraph G,VertexType u);// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
int main()
{
ALGraph g;
int n;
CreateGraphF (g); // 利用数据文件创建无向图
Display(g); // 输出无向图
scanf("%d",&n);
printf("用普里姆算法从g的第%d个顶点出发输出最小生成树的各条边:\n",n);
MiniSpanTree_PRIM(g,g.vertices [n].data); // Prim算法从第1个顶点构造最小生成树
}
int GetWeight(ALGraph G,VertexType a,VertexType b )//获取权值
{ int pa,pb;
pa=LocateVex(G,a);
pb=LocateVex(G,b);
ArcNode* p;
p=G.vertices[pa].firstarc;
if(pa == pb)
return 0;
while(p!=NULL)
{ if( p->data.adjvex == pb)
return p->data.info;
else
p=p->nextarc;
}
return INFINITY;
}
int minimum(minside SZ,ALGraph G)
{ /* 求SZ.lowcost的最小正值，并返回其在SZ中的序号 */
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; /* 第一个不为0的值 */
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0 && min>SZ[j].lowcost) /* 找到新的大于0的最小值 */
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(ALGraph G,VertexType u)
{
// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
/********** Begin **********/
int k;
minside sz;
k=LocateVex(G,u);
for(int i=0;i<G.vexnum;i++)
{
strcpy(sz[i].adjvex,u);
sz[i].lowcost=GetWeight(G,G.vertices[k].data ,G.vertices[i].data);
}
sz[k].lowcost=0;
printf("最小代价生成树的各条边为:\n");
for(int i=1;i<G.vexnum;i++)
{
k=minimum(sz,G);
printf("边(%s,%s),权值为%d\n", sz[k].adjvex,G.vertices [k].data,sz[k].lowcost);
sz[k].lowcost=0;
for(int j=0;j<G.vexnum;j++)
{
int min=GetWeight(G,G.vertices [k].data ,G.vertices[j].data);
if( min!=INFINITY && min!=0 && min<sz[j].lowcost)
{
strcpy(sz[j].adjvex,G.vertices[k].data );
sz[j].lowcost=GetWeight(G,G.vertices[k].data ,G.vertices[j].data);
}
}
}
/********** End **********/
}
第3关：求图（邻接矩阵存储）最小生成树的克鲁斯卡尔（Kruskal）算法
任务描述
本关任务：图的存储结构为邻接矩阵，要求编写函数利用克鲁斯卡尔（Kruskal）算法求图的最小生成树。
测试说明
平台会对你编写的代码进行测试：
测试输入：
3
lt3.txt
输入说明：
第一行输入3，表示输入图的类型为无向网。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
5
8
0
1
2
3
4
0 1 1
0 2 3
0 3 4
0 4 7
1 2 2
2 3 5
2 4 8
3 4 6
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；
预期输出：
无向网
5个顶点8条边。顶点依次是: 0 1 2 3 4
图的邻接矩阵:
∞ 1 3 4 7
1 ∞ 2 ∞ ∞
3 2 ∞ 5 8
4 ∞ 5 ∞ 6
7 ∞ 8 6 ∞
用克鲁斯卡尔构造g的最小生成树的各条边:
边(0,1),权值为1
边(1,2),权值为2
边(0,3),权值为4
边(3,4),权值为6
输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后分行输出用克鲁斯卡尔算法构造的最小生成树的各条边。
代码如下
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include"MGraph.h"
#define MAXE 100
typedef struct
{ int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
void SortEdge(Edge E[],int e); //对E数组按权值递增排序
void Kruskal(MGraph g); // 用克鲁斯卡尔算法构造网G的最小生成树T，输出T的各条边
int main()
{
MGraph g;
CreateGraphF (g); // 利用数据文件创建无向图
Display(g); // 输出无向图
printf("用克鲁斯卡尔构造g的最小生成树的各条边:\n");
Kruskal(g); // 用克鲁斯卡尔算法构造最小生成树
return 0;
}
void SortEdge(Edge E[],int e) //对E数组按权值递增排序
{
int i,j,k=0;
Edge temp;
for (i=1;i<e;i++)
{ temp=E[i];
j=i-1; //从右向左在有序区E[0..i-1]中找E[i]的插入位置
while (j>=0 && temp.w<E[j].w)
{ E[j+1]=E[j]; //将权值大于E[i].w的记录后移
j--;
}
E[j+1]=temp; //在j+1处插入E[i]
}
}
void Kruskal(MGraph g) //输出求得的最小生树的所有边
{
// 用克鲁斯卡尔算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
/********** Begin **********/
int num,i,k=0,t1,t2,j;
int parent[g.vexnum];
Edge E[100];
for(i = 0; i < g.vexnum; i++){
parent[i] = -1;
}
for(i = 0; i < g.vexnum; i++){
for(j = 0; j<g.vexnum; j++){
if(i>j&&g.arcs[i][j].adj!=INFINITY){
E[k].u = i;
E[k].v = j;
E[k].w = g.arcs[i][j].adj;
k++;
}
}
}
SortEdge(E,g.arcnum);
for(num = 0,i=0;i < g.arcnum; i++){
t1 = E[i].u;
t2 = E[i].v;
while(parent[t1]>-1) {
t1 = parent[t1];
}
while(parent[t2]>-1) {
t2 = parent[t2];
}
if(t1!=t2){
printf("边(%s,%s),权值为%d\n",g.vexs[E[i].u],g.vexs[E[i].v],g.arcs[E[i].u][E[i].v].adj);
parent[t1] = t2;
num++;
if(num == g.vexnum-1)
return;
}
}
/********** End **********/
}
第4关：求图（邻接表存储）最小生成树的克鲁斯卡尔（Kruskal）算法
任务描述
本关任务：图的存储结构为邻接表，要求编写函数利用克鲁斯卡尔（Kruskal）算法求图的最小生成树。
测试说明
平台会对你编写的代码进行测试：
测试输入：
3
lt3.txt
输入说明：
第一行输入3，表示输入图的类型为无向网。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
5
8
0
1
2
3
4
0 1 1
0 2 3
0 3 4
0 4 7
1 2 2
2 3 5
2 4 8
3 4 6
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；
预期输出：
无向网
5个顶点8条边。顶点依次是: 0 1 2 3 4
图的邻接矩阵:
∞ 1 3 4 7
1 ∞ 2 ∞ ∞
3 2 ∞ 5 8
4 ∞ 5 ∞ 6
7 ∞ 8 6 ∞
用克鲁斯卡尔构造g的最小生成树的各条边:
边(0,1),权值为1
边(1,2),权值为2
边(0,3),权值为4
边(3,4),权值为6
输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后分行输出用克鲁斯卡尔算法构造的最小生成树的各条边。
代码如下
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include"ALGraph.h"
#define INFINITY 4270000 // 用整型最大值代替∞
#define MAXE 100 // 定义边数最大值
typedef struct
{ int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
void SortEdge(Edge E[],int e); //对E数组按权值递增排序
void Kruskal(ALGraph g); // 用克鲁斯卡尔算法构造网G的最小生成树T，输出T的各条边
int main()
{
ALGraph g;
CreateGraphF (g); // 利用数据文件创建无向图
Display(g); // 输出无向图
printf("用克鲁斯卡尔构造g的最小生成树的各条边:\n");
Kruskal(g); // 用克鲁斯卡尔算法构造最小生成树
return 0;
}
void SortEdge(Edge E[], int e) //对E数组按权值递增排序
{
Edge a[20];
int i, j, k = 0, n = 0;
Edge temp;
for (i = 1;i < e;i++) //对E数组按权值递增排序，无向网的同一条边被读取了两次
{
temp = E[i];
j = i - 1; //从右向左在有序区E[0..i-1]中找E[i]的插入位置
while (j >= 0 && temp.w < E[j].w)
{
E[j + 1] = E[j]; //将权值大于E[i].w的记录后移
j--;
}
E[j + 1] = temp; //在j+1处插入E[i]
}
for (i = 0;i < e ;i++) //在按权值递增有序的E数组中删去多余的一条边
{
for (j = i;j < e;j++)
{
if (E[j].u == E[i].v && E[j].v == E[i].u)
{
a[n] = E[i];
n++;
}
}
}
for (i = 0;i < n;i++)
{
E[i] = a[i];
}
}
void Kruskal(ALGraph g) //输出求得的最小生树的所有边
{
// 用克鲁斯卡尔算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
/********** Begin **********/
int i,j,u1,v1,sn1,sn2,k;
int vset[MAX_VERTEX_NUM]; //建立数组vset
Edge E[MAXE]; //建立存放所有边的数组E
k=0; //E数组的下标从0开始计
ArcNode *p;
for(i=0;i<g.vexnum;i++)
{
p=g.vertices[i].firstarc;
while(p)
{
E[k].u = i;
E[k].v = p->data.adjvex;
E[k].w = p->data.info;
p = p->nextarc;
k++; //累计边数，无向网每条边被累计两次
}
}
SortEdge(E,k); //采用直接插入排序对E数组按权值递增排序，要保证相同的边在数组中相邻
for (i=0;i<g.vexnum ;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<g.vexnum ) //生成的边数小于n时循环
{ u1=E[j].u;
v1=E[j].v; //取一条边的头尾顶点
sn1=vset[u1];
sn2=vset[v1]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf("边(%s,%s),权值为%d\n",g.vertices [u1].data ,g.vertices [v1].data ,E[j].w);
k++; //生成边数增1
for (i=0;i<g.vexnum ;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++;
}
/********** End **********/
}
辅助文件
lt.txt
6
9
武汉
上海
长沙
南京
成都
广州
武汉 长沙 9
武汉 成都 2
长沙 上海 2
长沙 南京 2
上海 南京 5
上海 广州 4
上海 成都 3
南京 广州 8
成都 广州 6
lt2.txt
7
9
高等数学
程序设计基础
C语言
离散数学
数据结构
编译原理
操作系统
高等数学 C语言
高等数学 离散数学
程序设计基础 数据结构
程序设计基础 C语言
C语言 数据结构
离散数学 数据结构
离散数学 编译原理
数据结构 编译原理
数据结构 操作系统
lt3.txt
5
8
0
1
2
3
4
0 1 1
0 2 3
0 3 4
0 4 7
1 2 2
2 3 5
2 4 8
3 4 6
MGraph.h
#ifndef __MGraph_H__
#define __MGraph_H__
typedef int VRType; // 顶点关系类型
typedef char VertexType[20]; // 顶点类型
// 图的数组(邻接矩阵)存储表示
#define INFINITY 4270000 // 用整型最大值代替∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网}
typedef struct
{
VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组
typedef struct // 图的数组(邻接矩阵)存储
{
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum,arcnum; // 图的当前顶点数和弧数
GraphKind kind; // 图的种类标志
}MGraph;
/*邻接矩阵的8个基本操作函数声明*/
int LocateVex(MGraph G,VertexType u);//若图G中存在顶点u，则返回该顶点在图中位置；否则返回-1
VertexType* GetVex(MGraph G,int v);// 根据图G中某个顶点的序号v，返回该顶点的值
void visit(VertexType i);// 访问输出顶点的值
int FirstAdjVex(MGraph G,VertexType v);// v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点v在G中没有邻接顶点，则返回-1
int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是图G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1
void CreateGraphF(MGraph &G);//采用数组(邻接矩阵)表示法，由文件构造无向网G
void DestroyGraph(MGraph &G);//销毁图G
void Display(MGraph G);//输出邻接矩阵存储表示的图G
#endif
MGraph.cpp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"MGraph.h"
/*邻接矩阵的8个基本操作函数定义*/
int LocateVex(MGraph G,VertexType u)
{
//初始条件：图G存在，u和G中顶点有相同特征
// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i]) == 0)
return i; // VertexType是char [16]类型
return -1;
}
VertexType* GetVex(MGraph G,int v)
{
// 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值
if( v>=G.vexnum || v<0 )
exit(0);
return &(G.vexs[v]);
}
void visit(VertexType i)
{
printf("%s ",i);
}
int FirstAdjVex(MGraph G,VertexType v)
{
// 初始条件：图G存在，v是G中某个顶点
// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1
int i,j=0,k;
k=LocateVex(G,v); // k为顶点v在图G中的序号
if(G.kind%2) // 网
j=INFINITY;
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=j)
return i;
return -1;
}
int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点
// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1
int i,j=0,k1,k2;
k1=LocateVex(G,v); // k1为顶点v在图G中的序号
k2=LocateVex(G,w); // k2为顶点w在图G中的序号
if(G.kind%2) // 网
j=INFINITY;
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=j)
return i;
return -1;
}
void CreateGraphF(MGraph &G)
{
// 采用数组(邻接矩阵)表示法，由文件构造无向网G
int i,j,k,w;
char filename[13];
VertexType va,vb;
FILE *graphlist;
//printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&G.kind);
//printf("请输入数据文件名：");
scanf("%s",filename);
graphlist=fopen(filename,"r"); // 以graphlist指针 打开数据文件
fscanf(graphlist,"%d",&G.vexnum);
fscanf(graphlist,"%d",&G.arcnum);
for(i=0;i<G.vexnum;++i) // 构造顶点向量
fscanf(graphlist,"%s",G.vexs[i]);
for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
for(j=0;j<G.vexnum;++j)
{
if(G.kind%2) // 网
G.arcs[i][j].adj=INFINITY;
else // 图
G.arcs[i][j].adj=0;
}
for(k=0;k<G.arcnum;++k)
{
if(G.kind%2) // 网
fscanf(graphlist,"%s%s%d",va,vb,&w);
else // 图
fscanf(graphlist,"%s%s",va,vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
if(G.kind == 0) // 有向图
G.arcs[i][j].adj =1;
else if(G.kind == 1)
G.arcs[i][j].adj=w; // 有向网
else if(G.kind == 2) // 无向图
G.arcs[i][j].adj = G.arcs[j][i].adj=1;
else
G.arcs[i][j].adj = G.arcs[j][i].adj = w;
}
fclose(graphlist); // 关闭数据文件
}
void DestroyGraph(MGraph &G)
{
// 初始条件：图G存在。操作结果：销毁图G
int i,j,k=0;
if(G.kind%2) // 网
k=INFINITY; // k为两顶点之间无边或弧时邻接矩阵元素的值
G.vexnum=0; // 顶点数为0
G.arcnum=0; // 边数为0
}
void Display(MGraph G)
{
// 输出邻接矩阵存储表示的图G
int i,j;
switch(G.kind)
{
case DG: printf("有向图\n"); break;
case DN: printf("有向网\n"); break;
case UDG:printf("无向图\n"); break;
case UDN:printf("无向网\n");
}
printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum);
for(i=0;i<G.vexnum;++i) // 输出G.vexs
printf("%s ",G.vexs[i]);
printf("\n图的邻接矩阵:\n"); // 输出G.arcs.adj
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
if(G.kind%2)
{
if(G.arcs[i][j].adj==INFINITY)
printf("%s\t","∞");
else
printf("%d\t",G.arcs[i][j].adj);
}
else
printf("%d\t",G.arcs[i][j].adj);
printf("\n");
}
}
ALGraph.h
#ifndef __ALGraph_H__
#define __ALGraph_H__
typedef char VertexType[20]; // 顶点类型为字符串
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网}
typedef struct
{
int adjvex; // 该弧所指向的顶点的位置
int info; // 网的权值指针
}ElemType;
typedef struct ArcNode
{
ElemType data; // 除指针以外的部分都属于ElemType
struct ArcNode *nextarc; // 指向下一条弧的指针
}ArcNode; // 表结点
typedef struct
{
VertexType data; // 顶点信息
ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM]; // 头结点
typedef struct
{
AdjList vertices;
int vexnum,arcnum; // 图的当前顶点数和弧数
GraphKind kind; // 图的种类标志
}ALGraph;
#define LNode ArcNode // 定义单链表的结点类型是图的表结点的类型
#define next nextarc // 定义单链表结点的指针域是表结点指向下一条弧的指针域
typedef ArcNode *LinkList; // 定义指向单链表结点的指针是指向图的表结点的指针
int equal(ElemType a,ElemType b);
void visit(VertexType i);
int LocateVex(ALGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
int FirstAdjVex(ALGraph G,VertexType v); // 返回v的第一个邻接顶点的序号；否则返回-1
int NextAdjVex(ALGraph G,VertexType v,VertexType w);//v是图G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号
void CreateGraphF(ALGraph &G);// 采用邻接表存储结构，由文件构造没有相关信息图或网G
void Display(ALGraph G); // 输出图的邻接表G
#endif
ALGraph.cpp
#include<stdio.h>
#include<string.h>
#include"ALGraph.h"
#include"LinkList.h"
int LocateVex(ALGraph G,VertexType u)
{ // 初始条件：图G存在，u和G中顶点有相同特征
// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ // 初始条件：图G存在，v是G中某个顶点
// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1
LinkList p;
int v1;
v1=LocateVex(G,v); // v1为顶点v在图G中的序号
p=G.vertices[v1].firstarc;
if(p)
return p->data.adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ // 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点
// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1
LinkList p,p1; // p1在Point()中用作辅助指针
ElemType e;
int v1;
v1=LocateVex(G,v); // v1为顶点v在图G中的序号
e.adjvex=LocateVex(G,w); // e.adjvex为顶点w在图G中的序号
p=Point(G.vertices[v1].firstarc,e,equal,p1); // p指向顶点v的链表中邻接顶点为w的结点
if(!p||!p->next) // 没找到w或w是最后一个邻接点
return -1;
else // p->data.adjvex==w
return p->next->data.adjvex; // 返回v的(相对于w的)下一个邻接顶点的序号
}
void CreateGraphF(ALGraph &G)
{ // 采用邻接表 存储结构，由文件构造没有相关信息图或网G(用一个函数构造4种图)
int i,j,k,w; // w是权值
VertexType va,vb; // 连接边或弧的2顶点
ElemType e;
char filename[13];
FILE *graphlist;
//printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&G.kind);
//printf("请输入数据文件名：");
scanf("%s",filename);
graphlist=fopen(filename,"r"); // 以读的方式打开数据文件，并以graphlist表示
fscanf(graphlist,"%d",&G.vexnum);
fscanf(graphlist,"%d",&G.arcnum);
for(i=0;i<G.vexnum;++i) // 构造顶点向量
{
fscanf(graphlist,"%s",G.vertices[i].data);
G.vertices[i].firstarc=NULL; // 初始化与该顶点有关的出弧链表
}
for(k=0;k<G.arcnum;++k) // 构造相关弧链表
{
if(G.kind%2) // 网
fscanf(graphlist,"%s%s%d",va,vb,&w);
else // 图
fscanf(graphlist,"%s%s",va,vb);
i=LocateVex(G,va); // 弧尾
j=LocateVex(G,vb); // 弧头
e.info=0; // 给待插表结点e赋值，图无权
e.adjvex=j; // 弧头
if(G.kind%2) // 网
{
e.info = w;
}
ListInsert(G.vertices[i].firstarc,1,e); // 插在第i个元素(出弧)的表头
if(G.kind>=2) // 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头
{
e.adjvex=i; // e.info不变，不必再赋值
ListInsert(G.vertices[j].firstarc,1,e); // 插在第j个元素的表头
}
}
fclose(graphlist); // 关闭数据文件
}
void Display(ALGraph G)
{ // 输出图的邻接表G
int i;
LinkList p;
switch(G.kind)
{
case DG: printf("有向图\n"); break;
case DN: printf("有向网\n"); break;
case UDG:printf("无向图\n"); break;
case UDN:printf("无向网\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->data.adjvex].data);
if(G.kind%2) // 网
printf(":%d\t",p->data.info );
p=p->nextarc;
}
printf("\n");
}
}
int equal(ElemType a,ElemType b)
{
if(a.adjvex==b.adjvex)
return 1;
else
return 0;
}
void visit(VertexType i)
{
printf("%s ",i);
}
LinkList.h文章来源：https://www.toymoban.com/news/detail-455442.html
#ifndef __LinkList_H__
#define __LinkList_H__ // 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#include"ALGraph.h"
typedef LNode * LinkList; // 另一种定义LinkList的方法
// 不带头结点的单链表的部分基本操作(9个)
#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的
void InitList(LinkList &L);
void ClearList(LinkList &L);
int ListEmpty(LinkList L);
int ListLength(LinkList L);
int GetElem(LinkList L,int i,ElemType &e);
int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType));
int ListInsert(LinkList &L,int i,ElemType e);
int ListDelete(LinkList &L,int i,ElemType &e);
void ListTraverse(LinkList L,void(*vi)(ElemType));
LinkList Point(LinkList L,ElemType e,int(*equal)(ElemType,ElemType),LinkList &p);//查找表L中满足条件的结点。如找到
#endif
LinkList.cpp文章来源地址https://www.toymoban.com/news/detail-455442.html
#include<stdio.h>
#include<stdlib.h>
#include"LinkList.h"
// 不带头结点的单链表的部分基本操作(9个)
void InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
L=NULL; // 指针为空
}
#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的
void ClearList(LinkList &L)
{ // 初始条件：线性表L已存在。操作结果：将L重置为空表
LinkList p;
while(L) // L不空
{
p=L; // p指向首元结点
L=L->next; // L指向第2个结点(新首元结点)
free(p); // 释放首元结点
}
}
int ListEmpty(LinkList L)
{ // 初始条件：单链表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if(L)
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int i=0;
LinkList p=L;
while(p) // p指向结点(没到表尾)
{
p=p->next; // p指向下一个结点
i++;
}
return i;
}
int GetElem(LinkList L,int i,ElemType &e)
{ // L为不带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j=1;
LinkList p=L;
if(i<1) // i值不合法
return ERROR;
while(j<i&&p) // 没到第i个元素，也没到表尾
{
j++;
p=p->next;
}
if(j==i) // 存在第i个元素
{
e=p->data;
return OK;
}
else
return ERROR;
}
int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType))
{ // 初始条件：线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在，则返回值为0
int i=0;
LinkList p=L;
while(p)
{
i++;
if(compare(p->data,e)) // 找到这样的数据元素
return i;
p=p->next;
}
return 0;
}
int ListInsert(LinkList &L,int i,ElemType e)
{ // 在不带头结点的单链线性表L中第i个位置之前插入元素e
int j=1;
LinkList p=L,s;
if(i<1) // i值不合法
return ERROR;
s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
s->data=e; // 给s的data域赋值
if(i==1) // 插在表头
{
s->next=L;
L=s; // 改变L
}
else
{ // 插在表的其余处
while(p&&j<i-1) // 寻找第i-1个结点
{
p=p->next;
j++;
}
if(!p) // i大于表长+1
return ERROR;
s->next=p->next;
p->next=s;
}
return OK;
}
int ListDelete(LinkList &L,int i,ElemType &e)
{ // 在不带头结点的单链线性表L中，删除第i个元素，并由e返回其值
int j=1;
LinkList p=L,q;
if(i==1) // 删除第1个结点
{
L=p->next; // L由第2个结点开始
e=p->data;
free(p); // 删除并释放第1个结点
}
else
{
while(p->next&&j<i-1) // 寻找第i个结点，并令p指向其前趋
{
p=p->next;
j++;
}
if(!p->next||j>i-1) // 删除位置不合理
return ERROR;
q=p->next; // 删除并释放结点
p->next=q->next;
e=q->data;
free(q);
}
return OK;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{ // 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()
LinkList p=L;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
LinkList Point(LinkList L,ElemType e,int(*equal)(ElemType,ElemType),LinkList &p)
{ //查找表L中满足条件的结点。如找到，返回指向该结点的指针，p指向该结点的前驱(若该结点是首元结点，则p=NULL)。
//如表L中无满足条件的结点，则返回NULL，p无定义。函数equal()的两形参的关键字相等，返回OK；否则返回ERROR
int i,j;
i=LocateElem(L,e,equal);
if(i) // 找到
{
if(i==1) // 是首元结点
{
p=NULL;
return L;
}
p=L;
for(j=2;j<i;j++)
p=p->next;
return p->next;
}
return NULL; // 没找到
}
到了这里，关于图的最小生成树算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
