minspantreeoftu.cpp

关于数据结构的各章节的c原代码实现

// minspantreeoftu.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
struct nedge
{
	int from;
	int to;
	int weight;
	struct nedge* next;
};
typedef struct nedge edge;
typedef edge* list;
list head=NULL;
int node[6];
list creatlist(int *edges,int n)
{
  list root=NULL;
  list p;
  list newnode;
  root=(list)malloc(sizeof(edge));
  root->next=NULL;
  p=root;
  for (int i=0;i<n;i++)
  {
	  newnode=(list)malloc(sizeof(edge));
	  newnode->from=edges[3*i];
	  newnode->to=edges[3*i+1];
	  newnode->weight=edges[3*i+2];
	  newnode->next=NULL;
	  p->next=newnode;
	  p=newnode;
  }
  root=root->next;
  return root;

}
int samegroup(int from,int to)
{
while(node[from]>0)from=node[from];
while(node[to]>0)to=node[to];
if(from==to)return 1;
else
return 0;

}
void uniongroup(int from,int to)
{
while(node[to]>0)to=node[to];
node[to]=from;
}
void minsqantree()
{
list p;
p=head;
while (p!=NULL)
{
	if (!samegroup(p->from,p->to))
	{
		printf("从顶点%d到%d权值%d\n",p->from,p->to,p->weight);
		uniongroup(p->from,p->to);
	}
	p=p->next;
}

}
int main(int argc, char* argv[])
{  
	int edges[8][3]={{1,2,2},{2,4,3},{1,4,4},{3,5,5},{2,5,6},{2,3,8},{3,4,10},{4,5,15}};
     head=creatlist(edges[0],8);
    for (int i=1;i<6;i++)
      node[i]=-1;
	printf("图的最小生成树：\n");
	minsqantree();
	printf("顶点数组内容：\n");
	printf(" 1   2   3   4   5\n");
	for (i=1;i<6;i++)
	{
		printf(" [%d]",node[i]);
	}
	printf("\n");
	return 0;
}