#include<iostream>

using namespace std;

#define Inf 65535
#define NotAVerter -1

/////////////////////邻接表的相关定义//////////////////////
typedef struct EdgeNode *position;
typedef struct Led_table* Table;
 
 
 struct EdgeNode     //边表结点 
{ 
    int adjvex;    // 邻接点域,存储该顶点对应的下标 
    int weight;     // 对应边的权值
    position next; // 链域,指向下一个邻接点
};
 
struct Led_table       // 邻接表结构 
{ 
    int data;                //邻接表的大小
    position *firstedge;       //边表头指针，可以理解为数组
}; 
 
 
//////////////////////////邻接表相关函数定义///////////////
Table Creat_Lable (int MaxElements)    //MaxElements参数为希望创建的节点数
{
     
    Table table1 = static_cast<Table> (malloc(sizeof(struct Led_table)));
    table1->data = http://www.mamicode.com/MaxElements;"out of space!!!";
    }
 
    table1->firstedge  = static_cast<position*>(malloc(sizeof(position)*(table1->data)));
    if (table1->firstedge  == NULL)
    {
       cout << "out of space!!!";
    }
 
    //给每个表头赋值，从0开始
    for (int i = 0; i <= table1->data - 1; ++i)
    {
        table1->firstedge [i] = static_cast<position>(malloc(sizeof(EdgeNode)));   //申请一个节点
        if (table1->firstedge [i]  == NULL)
            {
               cout << "out of space!!!";
            }
        table1->firstedge [i]->adjvex = 0;   
        table1->firstedge [i]->weight = 0;   //此参数在此时没有意义
        table1->firstedge [i]->next = NULL;
 
    }
    return table1;
 
}
 
 
void Insert (Table table1, int v, int w, int weig)   //表示存在一条边为<v,w>,且权重为weig
{
    position p = static_cast<position>(malloc(sizeof(EdgeNode)));   //申请一个节点
    if(p == NULL)
    {
       cout << "out of space!!!";
    }
    p->adjvex = w;
    p->weight = weig;
    p->next = table1->firstedge [v]->next;
    table1->firstedge [v]->next = p;
         
}


void Double_Insert (Table table1, int v, int w, int weig)   //无向边，双向插入
{
	Insert (table1, v,  w,  weig);
	Insert (table1, w,  v,  weig);
}

/////////////////////最小生成树Prim算法/////////////////////////
typedef struct Prim_tree *Prim_node ;
 
 struct Prim_tree     //
{ 
    bool know;
    int dist;    // 邻接点域,存储该顶点对应的下标 
    int path;     // 对应边的权值
};
 
Prim_node Prim_init(Table table1, int start)     //节点初始化
{
    Prim_node Node  = static_cast<Prim_node>(malloc(sizeof(Prim_tree)*(table1->data)));
    if (Node  == NULL)
    {
       cout << "out of space!!!";
    }
    for(int i = 0; i != table1->data; ++i)
    {
        Node[i].know = false;
        Node[i].dist = Inf;
        Node[i].path = NotAVerter;
    }
    Node[start].dist = 0;   //起点处的距离设为0
    return Node;
}

 void Prim_Algorithm (Table table1,Prim_node Node)  //prim 算法
 {
    int v;  
    for (int j = 0; j != table1->data; ++j)
    {
		int zh = Inf;
        for (int i = 0; i != table1->data; ++i)    //找路径最小且没有标记过的点
        {
           if(!Node[i].know && zh > Node[i].dist )  //如果这个点是未知的，且距离比较小
           {
              zh = Node[i].dist;
              v = i;
           }
        
        }

        Node[v].know = true;    //标记这个点
        position p = table1->firstedge [v]->next;
        while (p != NULL)   //
        {
            if(!Node[p->adjvex].know && Node[p->adjvex].dist > p->weight  )
            {
                Node[p->adjvex].dist =  p->weight;
                Node[p->adjvex].path = v;
            }
            p = p->next;
        }
 
    }
     
 
 }
 
 

int main ()
{
	 Table table_1 = Creat_Lable (7);    //创建一个大小为7的邻接表
 
  //根据图来为邻接表插入数据
   
  Double_Insert (table_1, 0, 1, 2);Double_Insert (table_1, 0, 2, 4);Double_Insert (table_1, 0, 3, 1);
  Double_Insert (table_1, 1, 3, 3);Double_Insert (table_1, 1, 4, 10);
  Double_Insert (table_1, 2, 5, 5);
  Double_Insert (table_1, 3, 2, 2);Double_Insert (table_1, 3, 5, 8);Double_Insert (table_1, 3, 6, 4);
  Double_Insert (table_1, 4, 3, 7);Double_Insert (table_1, 4, 6, 6);
  Double_Insert (table_1, 6, 5, 1);
   
  Prim_node Node_1 = Prim_init(table_1, 0);   //初始化节点
 
  Prim_Algorithm (table_1,Node_1);

  for (int i = 0; i != table_1->data; ++i)
  {
	  cout << Node_1[i].dist << endl;
  }





   return 0;
}