|
#2
ehamster2012-06-02 15:17
|
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAX 100
struct Node{
int vertex1;//节点一
int vertex2;//节点二
int weight;//权值
struct Node *next;//定义节点类型
};
typedef struct Node * Edge;//定义节点类指针
Edge head = NULL;
int visited[MAX];
Edge read()
{
int v1, v2, w;
Edge newNode = NULL, pointer = NULL;
while(1)
{
scanf("%d %d %d", &v1, &v2, &w);
if(v1 == -1 || v2 == -1 || w == -1)//或语句判断节点一节点二权值是否为-1，若为-1则跳出循环
break;
newNode = (Edge)malloc(sizeof(struct Node));
newNode->vertex1 = v1;
newNode->vertex2 = v2;
newNode->weight = w;
newNode->next = NULL;
pointer = head;
if(pointer == NULL)//判断是链式存储还是顺序存储
head = newNode;
else
{
if(newNode->weight < pointer->weight)
{
newNode->next = pointer;
head = newNode;
}
else
{
while(pointer != NULL && pointer->next != NULL)
{
if(pointer->weight < newNode->weight && newNode->weight < pointer->next->weight)//按权值大小排序权值节点
{
newNode->next = pointer->next;
pointer->next = newNode;
break;
}
pointer = pointer->next;
}
pointer->next = newNode;
}
}
}
return head;
}
void printLink(Edge edge)
{
Edge pointer = edge;
printf("\n\nEdge link : \n");
while(pointer != NULL)
{
printf("[%d %d]", pointer->vertex1, pointer->vertex2);
printf("(%d)",pointer->weight);
if(pointer->next != NULL)
printf(" ==> ");
pointer = pointer->next;
}
printf("\n");
}
void kruskal(Edge edge, int vexnum){
int visitedEdgeNum = 0, weight = 0;
printf("\nMin generate tree : \n");
while(visitedEdgeNum < vexnum){
if(visited[edge->vertex1] == 0
|| visited[edge->vertex2] == 0){
printf("[%d %d]", edge->vertex1, edge->vertex2);
printf("(%d) ",edge->weight);
weight += edge->weight;
visitedEdgeNum++;
visited[edge->vertex1] = 1;
visited[edge->vertex2] = 1;
}
edge = edge->next;
if(edge == NULL){
break;
}
}
printf("\n\nTotal weight = %d \n\n", weight);
}
void main()
{
int vexnum, i;
Edge edge = NULL;
printf("enter vexnum and edges with weight: \n");//提示输入图的节点数和边的权值
scanf("%d",&vexnum);
for(i=0; i<vexnum; i++)
visited[i]=0;
edge=read();
printLink(edge);
kruskal(edge, vexnum);
}