PTA日常 | 数据结构（C语言） | Minimum spanning tree

PTA日常 | 数据结构（C语言） | Minimum spanning tree

　　这里是芋圆！在敲代码的路上越挫越勇的新人！ＰＴＡ日常是用来整理自己在ＰＴＡ上面遇到的大大大小小的题！希望在记录自己刷题日常的同时也能小小地解决一下广大的网友的疑惑吧！（如果帮助到你啦可以点个赞嘛！）

 

 

---

思路：1.创建题给图

2.每次找到权值最小的一条边和这条边的两个端点（这条边是想要插入的）

3.每找到一条边都判断一下这条边是否可以插入（即插入之后是否会成环！）

4.把满足条件的边按照要求格式输出即可啦！！

---

#include
#include

#define MAX 11

typedef struct node{
	int vex[MAX];
	int arc[MAX][MAX];
	int vexnum,arcnum;
}graphnode,*graph;

graph create()
{
	graph g=malloc(sizeof(graphnode));
	g->vexnum=10;
	g->arcnum=19;
	int i,j;
	for(i=1;i<=10;i++)
	{
		for(j=1;j<=10;j++)
		{
			g->arc[i][j]=0;
		}
	}
	g->arc[1][4]=4;
    g->arc[1][5]=4;
    g->arc[2][1]=3;
    g->arc[2][5]=2;
    g->arc[2][3]=10;
    g->arc[2][6]=3;
    g->arc[3][2]=10;
    g->arc[3][6]=6;
    g->arc[3][7]=1;
    g->arc[4][1]=4;
    g->arc[4][5]=5;
    g->arc[4][8]=6;
    g->arc[5][1]=4;
    g->arc[5][2]=2;
    g->arc[5][4]=5;
    g->arc[5][6]=11;
    g->arc[5][8]=2;
    g->arc[5][9]=1;
    g->arc[6][2]=3;
    g->arc[6][3]=6;
    g->arc[6][7]=2;
    g->arc[6][5]=11;
    g->arc[6][9]=3;
    g->arc[6][10]=11;
    g->arc[7][3]=1;
    g->arc[7][6]=2;
    g->arc[7][10]=8;
    g->arc[8][4]=6;
    g->arc[8][5]=2;
    g->arc[8][9]=4;
    g->arc[9][8]=4;
    g->arc[9][5]=1;
    g->arc[9][6]=3;
    g->arc[9][10]=7;
    g->arc[10][6]=11;
    g->arc[10][7]=8;
    g->arc[10][9]=7;
    return g;
}

graph change(int a,int b,int weight)
{
	graph g=create();
	g->arc[a][b]=weight;
	g->arc[b][a]=weight;
	return g;
}

graph create1()
{
	graph g=malloc(sizeof(graphnode));
	g->vexnum=10;
	g->arcnum=19;
	int i,j;
	for(i=1;i<=10;i++)
	{
		for(j=1;j<=10;j++)
		{
			g->arc[i][j]=0;
		}
	}
	return g;
}

int connected(graph g,int start,int end)//start是开始的地方 end是结束的地方 
{
	int i,j,k;
	int vex[15];
	int front=0,rear=0;
	if(start==end)//开始等于结束的时候，就意味着成环了  只是为了逻辑的连贯性 
	{
		return 1;
	}
	vex[rear]=start;//vex用来表示线路经过的顶点 
	rear++;
	while(frontarc[i][j]!=0)
			{
				if(j==end)
				{
					return 1;//从start出发向外遍历 有另一条路可以通向end==加上从start到end的边一定会成环！
				}
				for(k=0;karcnum>0)//有十个顶点最多只能添9条边！ 如果所有的19条边都遍历完符合条件的不满9条也可以 所以加了arcnum的限制
	{
		min=11;//边上权值的最大值！ 
		for(i=1;i<=10;i++)
		{
			for(j=1;j<=10;j++)
			{
				if(g->arc[i][j]!=0&&g->arc[i][j]arc[i][j];
					I=i;
					J=j;
				}
			}
		}//找到权值最小的那条边 和它的两端！
		g->arc[I][J]=0;
		g->arc[J][I]=0;//把原图中找到的那条边删去 
		int judge=connected(g1,I,J);
		if(judge==0)//判断没有成环之后 再把这条边加进去新图中！ 
		{
			printf("%d,",min);
			edge++;
			g1->arc[I][J]=min;
			g1->arc[J][I]=min;
		}
		g->arcnum--; 
	}
}

int main()
{
	char a,b;
	int weight;
	scanf("%c,%c,%d",&a,&b,&weight);
	int x,y;
	x=a-64;
	y=b-64;
	graph g=change(x,y,weight);
	graph g1=create1();
	Kruskal(g,g1);
}