图的最小生成树算法

第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

第三行输入利用普里姆算法构造最小生成树的起点。

预期输出：

无向网

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

预期输出：

无向网

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

输出说明：

第一行输出图的类型。

第二行起输出图的顶点和边的数据信息。

最后分行输出用克鲁斯卡尔算法构造的最小生成树的各条边。

代码如下

#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

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

#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

#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;           // 没找到 
}

原文链接：https://blog.csdn.net/qq_45917176/article/details/125647325

第1关：求图（邻接矩阵存储）最小生成树的普里姆（Prim）算法

任务描述

测试说明

代码如下

第2关：求图（邻接表存储）最小生成树的普里姆（Prim）算法

任务描述

测试说明

代码如下

第3关：求图（邻接矩阵存储）最小生成树的克鲁斯卡尔（Kruskal）算法

任务描述

测试说明

代码如下

第4关：求图（邻接表存储）最小生成树的克鲁斯卡尔（Kruskal）算法

任务描述

测试说明

代码如下

辅助文件

你可能也喜欢