#include<iostream.h>
#define MaxVerNum 20
typedef struct Node{
 int adjvex;
 struct Node *next;
}EdgeNode;
typedef struct vNode{
 int vertex;
 EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVerNum];
typedef struct{
 AdjList adjlist;
 int n,e;
}ALGraph;
typedef struct{
 int db[MaxVerNum];
 int front,rear;
}Queue;
typedef struct{
 int v1;
 int v2;
 int cost;
}EdgeType;
ALGraph *CreatALGraph(EdgeType edges[])
{ ALGraph *G;
 G=new ALGraph;
 int i,j,k;
 EdgeNode *s;
 cout<<"请输入顶点和边数（输入格式为：顶点数，边数）："<<endl;
 cin>>G->n>>G->e;
 cout<<"请输入顶点信息："<<endl;
 for(i=0;i<G->n;i++)
 { cin>>G->adjlist[i].vertex;
  G->adjlist[i].firstedge=NULL;
 }
 cout<<"请输入边的信息（格式为：V1,V2,权值）："<<endl;
 for(k=0;k<G->e;k++)
 { cin>>i>>j>>edges[k].cost;
  edges[k].v1=i;
  edges[k].v2=j;
  s=new EdgeNode;
  s->adjvex=j-1;
  s->next=G->adjlist[i-1].firstedge;
  G->adjlist[i-1].firstedge=s;
  s=new EdgeNode;
  s->adjvex=i-1;
  s->next=G->adjlist[j-1].firstedge;
  G->adjlist[j-1].firstedge=s;
 }
 return G;
}
int visited[MaxVerNum];
//深度
void DFSAL(ALGraph *G,int i)
{ EdgeNode *p;
 cout<<G->adjlist[i].vertex<<" ";
 visited[i]=1;
 p=G->adjlist[i].firstedge;
 while(p)
 { if(!visited[p->adjvex])
  DFSAL(G,p->adjvex);
  p=p->next;
 }
}
void DFSTraverseAL(ALGraph *G)
{ int i;
 for(i=0;i<G->n;i++)
  visited[i]=0;
 for(i=0;i<G->n;i++)
  if(!visited[i])
   DFSAL(G,i);
}
//广度
Queue *InitQueue()
{ Queue *Q;
 Q=new Queue;
 Q->front=-1;
 Q->rear=-1;
 return Q;
}
void EnQueue(Queue *Q,int k)
{ Q->rear++;
 Q->db[Q->rear]=k;
}
int DeQueue(Queue *Q)
{ int k;
 Q->front++;
 k=Q->db[Q->front];
 return k;
}
void BFSTraverseAL(ALGraph *G)
{ int k;
 for(k=0;k<G->n;k++)
  visited[k]=0;
 EdgeNode *p;
 Queue *Q;
 Q=InitQueue();
 int m;
 cout<<G->adjlist[0].vertex<<" ";
 visited[0]=1;
 EnQueue(Q,0);
 while(Q->front!=Q->rear)
 { m=DeQueue(Q);
  p=G->adjlist[m].firstedge;
  while(p!=NULL)
  { if(visited[p->adjvex]!=1)
   { cout<<G->adjlist[p->adjvex].vertex<<" ";
    visited[p->adjvex]=1;
   }
   EnQueue(Q,p->adjvex);
   p=p->next;
  }
 }
}
//最小生成树
EdgeType edges[MaxVerNum];
void Tidycost(EdgeType edges[],ALGraph *G)
{ int i,j,swap;
 EdgeType tmp;
 for(i=1;i<G->e;i++)
 { swap=0;
  for(j=1;j<G->e-1;j++)
   if(edges[j].cost>edges[j+1].cost)
   { tmp=edges[j];
    edges[j]=edges[j+1];
    edges[j+1]=tmp;
    swap=1;
   }
  if(swap==0)break;
 }
}
int Find(int father[],int v)
{ int t;
 t=v;
 while(father[t]>=0)
  t=father[t];
 return t;
}
void Kruskal(EdgeType edges[],ALGraph *G)
{ int father[MaxVerNum];
 int i,j,vf1,vf2,n;
 n=G->n;
 for(i=0;i<n;i++)
  father[i]=-1;
 i=0;
 j=0;
 while(i<MaxVerNum && j<n-1)
 { vf1=Find(father,edges[i].v1);
  vf2=Find(father,edges[i].v2);
  if(vf1!=vf2)
  { father[vf2]=vf1;
   j++;
   cout<<edges[i].v1<<"-"<<edges[i].v2<<":"<<edges[i].cost<<endl;
  }
  i++;
 }
}
void main()
{ ALGraph *G;
 G=CreatALGraph(edges);
 DFSTraverseAL(G);
 cout<<endl;
 BFSTraverseAL(G);
 cout<<endl;
 Tidycost(edges,G);
 Kruskal(edges,G);
}