图ZXZ
#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);
}
