_888 2015-11-21 06:59 采纳率: 0%
浏览 1865

数据结构图的Prims算法

#include
#include
#define Max 10
#define VertexNum 5
typedef struct List
{
int Marked;
int Vertex1;
int Vertex2;
int Weight;
struct List * Next;
} Node,*Edge;
int Edges[10][3]={{1,2,7},{1,3,6},{1,4,5},{1,5,12},{2,3,14},{2,4,8},{2,5,8},{3,4,3},{3,5,9},{4,5,2}};
int Visited[VertexNum+1];
void Prims(Edge Head,int Index)
{
Edge Pointer;
Edge MinEdge;
int EdgeNum=0;
int Weight=0;
int i;
Visited[Index]=1; //设置已查找过
while(EdgeNum != (VertexNum-1)) //当边的数目为顶点的数目减1时,结束循环
{
MinEdge->Weight=999;

    for(i=1;i<=VertexNum;i++)
    {
        Pointer=Head;
        if(Visited[i] == 1)
        {
            while(Pointer->Marked==1)
                Pointer=Pointer->Next;

            if(MinEdge->Weight > Pointer->Weight)
                MinEdge=Pointer;

            while( Pointer != NULL)
            {
                if(Visited[Pointer->Vertex1]==1 && Visited[Pointer->Vertex2]==1)
                    Pointer->Marked=1;
                if(MinEdge->Weight>Pointer->Weight && Pointer->Marked==0 && (Pointer->Vertex1==i || Pointer->Vertex2==i))
                    MinEdge=Pointer;
                Pointer=Pointer->Next;
            }
        }
    }
    Visited[MinEdge->Vertex1]=1;
    Visited[MinEdge->Vertex2]=1;
    EdgeNum++;
    Weight+=MinEdge->Weight;
    printf("[%d,%d]",MinEdge->Vertex1,MinEdge->Vertex2);
    printf("(%d)",MinEdge->Weight);
}
printf("\nTotal weight = %d\n",Weight);

}
void Free_Edge(Edge Head)
{
Edge Pointer;
while( Head != NULL)
{
Pointer=Head;
Head=Head->Next;
free(Pointer);
}
}
void Print_Edge(Edge Head)
{
Edge Pointer;
Pointer=Head;
while( Pointer != NULL)
{
printf("[%d,%d]",Pointer->Vertex1,Pointer->Vertex2);
printf("(%d)",Pointer->Weight);
Pointer=Pointer->Next;
}
printf("\n");
}
Edge Insert_Edge(Edge Head,Edge New)
{
Edge Pointer;
Pointer=Head;
while(Pointer->Next != NULL)
Pointer=Pointer->Next;
Pointer->Next=New;
return Head;
}
Edge Create_Edge(Edge Head)
{
Edge New;
int i;
Head=(Edge)malloc(sizeof(Node));
if(Head == NULL)
printf("Memory allocate Failure !! \n");
else
{
Head->Marked=0;
Head->Vertex1=Edges[0][0];
Head->Vertex2=Edges[0][1];
Head->Weight=Edges[0][2];
Head->Next=NULL;
for(i=1;i {
New=(Edge)malloc(sizeof(Node));
if( New != NULL)
{
New->Marked=0;
New->Vertex1=Edges[i][0];
New->Vertex2=Edges[i][1];
New->Weight=Edges[i][2];
New->Next=NULL;
Head=Insert_Edge(Head,New);
}
}
}
return Head;
}
void main()
{
Edge Head;
int i;
for(i=1;i<=VertexNum;i++)
Visited[i]=0;
Head=Create_Edge(Head);
Print_Edge(Head);
if(Head != NULL)
{
printf("Prims Algorithm : \n");
printf("Start from Vertex 1.\n ");
printf("Find Minimal Spanning Tree.\n");
Prims(Head,1);
free(Head);
}
}

  • 写回答

2条回答 默认 最新

  • _888 2015-11-21 07:01
    关注

    为什么结果运行不出来

    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB动图的问题
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名