真的很郁闷，自己纠错了两天还是不行


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INT_MAX                 1000
#define INFINITY                INT_MAX         
#define MAX_VERTEX_NUM          20            
#define ERROR                   false
#define OK                   true      
typedef struct ArcCell {
 int adj;                                 
 char *info;                           
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
 int vexs[MAX_VERTEX_NUM];            
 AdjMatrix arcs;                              
 int vexnum, arcnum;
 int kind;                                                      
}MGraph;


typedef struct ArcNode{
    int            adjvex;
    struct ArcNode *nextarc;
    int            *info;
}ArcNode;
typedef struct VNode{
    int     data;
    ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
    AdjList vertices;
    int     vexnum,arcnum;
    int     kind;
}ALGraph;

//邻接矩阵 (udn)

int LocateVex(MGraph G, int u)
{
 int i;
 for (i=0; i<G.vexnum; ++i){
     if (G.vexs[i]==u)
   return i;
 }
 return -1;
}
int CreateDG(MGraph &G) {
 int i,j,k;
 int v1,v2;  
 
 printf("构建有向图，请输入顶点的数目和边的数目：\n");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("请依次输入对应的顶点值：\n");
 for( i = 0; i < G.vexnum; ++i ) {
  scanf("%d",&G.vexs[i]);
 }
 for( i = 0; i < G.vexnum; ++i ) {
  for( j = 0; j <G.vexnum; ++j ) {
   G.arcs[i][j].adj = 0;
   G.arcs[i][j].info = NULL;   
  }
 }
 for( k = 0; k < G.arcnum; ++k ) {
   printf("请输入第%d条边的第一个顶点的值：",k+1);
  scanf("%d",&v1);
  printf("请输入第%d条边的第二个顶点的值：",k+1);
  scanf("%d",&v2);
  i=LocateVex(G,v1);   
  j=LocateVex(G,v2);   
  G.arcs[i][j].adj=1;
 }
}

int CreateDN(MGraph &G) {
 int i,j,k,w;
 int v1,v2;  
 printf("构建有向网，请输入顶点的数目和边的数目：\n");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("请依次输入对应的顶点的值：\n");
 for( i = 0; i < G.vexnum; ++i ) {
  scanf("%d",&G.vexs[i]);
 }
 
 for( i = 0; i < G.vexnum; ++i ) {
  for( j = 0; j <G.vexnum; ++j ) {
   G.arcs[i][j].adj = INFINITY;
   G.arcs[i][j].info = NULL;  
  }
 }
 for( k = 0; k < G.arcnum; ++k ) {
   printf("请输入第%d条边的第一个顶点的值：",k+1);
  scanf("%d",&v1);
  printf("请输入第%d条边的第二个顶点的值：",k+1);
  scanf("%d",&v2);
  printf("请输入权值\n");
  scanf("%d",&w);
  i=LocateVex(G,v1);   
  j=LocateVex(G,v2);   
  G.arcs[i][j].adj=w;
 }

}


int CreateUDG(MGraph &G) {
 int i,j,k;
 int v1,v2;
 printf("构建无向图，请输入顶点的数目和边的数目：\n");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("请依次输入对应的顶点的值：\n");
 for( i = 0; i < G.vexnum; ++i ) {
  scanf("%d",&G.vexs[i]);
 }
 
 for( i = 0; i < G.vexnum; ++i ) {
  for( j = 0; j <G.vexnum; ++j ) {
   G.arcs[i][j].adj = 0;
   G.arcs[i][j].info = NULL;  
  }
 }
 for( k = 0; k < G.arcnum; ++k ) {
   printf("请输入第%d条边的第一个顶点的值：",k+1);
  scanf("%d",&v1);
  printf("请输入第%d条边的第二个顶点的值：",k+1);
  scanf("%d",&v2);
  i=LocateVex(G,v1);   
  j=LocateVex(G,v2);   
  G.arcs[i][j].adj=1;
 }
}
int CreateUDN(MGraph &G) {  
 int i,j,k,w;
int v1,v2;  
 printf("构建无向网，请输入顶点的数目和边的数目：\n");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("请依次输入对应的顶点的值：\n");
 for( i = 0; i < G.vexnum; ++i ) {
  scanf("%d",&G.vexs[i]);
 }
 
 for( i = 0; i < G.vexnum; ++i ) {
  for( j = 0; j <G.vexnum; ++j ) {
   G.arcs[i][j].adj = INFINITY;
   G.arcs[i][j].info = NULL;   
  }
 }
 for( k = 0; k < G.arcnum; ++k ) {
  printf("请输入第%d条边的第一个顶点的值：",k+1);
  scanf("%d",&v1);
  printf("请输入第%d条边的第二个顶点的值：",k+1);
  scanf("%d",&v2);
  printf("请输入权值\n");
  scanf("%d",&w);
  i=LocateVex(G,v1);  
  j=LocateVex(G,v2);   
  G.arcs[i][j].adj=w;
 }
}
//邻接表
int CreateUDG2(ALGraph &G){
    int i,s,d;
    ArcNode *p,*q;
    printf("请输入顶点数，边数：\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请输入顶点值（字符）\n");
    for(i=0;i<G.vexnum;i++){
        getchar();
        scanf("%c",&G.vertices[i].data);
        G.vertices[i].firstarc=NULL;
    }
    printf("请输入顶点序号：\n");
    for(i=0;i<G.arcnum;i++){
        scanf("%d%d",&s,&d);
        p=(ArcNode*)malloc(sizeof(ArcNode));
        q=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=d;
        q->adjvex=s;
        p->nextarc=G.vertices[s].firstarc;
        G.vertices[s].firstarc=p;
        q->nextarc=G.vertices[d].firstarc;
        G.vertices[d].firstarc=q;
    }
}
int CreateDG2(ALGraph &G){
    int i,s,d;
    ArcNode *p;
    printf("请输入顶点数，边数：\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请输入顶点值（字符）\n");
    for(i=0;i<G.vexnum;i++){
        getchar();
        scanf("%c",&G.vertices[i].data);
        G.vertices[i].firstarc=NULL;
    }
    printf("请输入顶点序号：\n");
    for(i=0;i<G.arcnum;i++){
        scanf("%d%d",&s,&d);
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=d;
        p->nextarc=G.vertices[s].firstarc;
        G.vertices[s].firstarc=p;
    }
}
int CreateDN2(ALGraph &G){
    int i,s,d,IncInfo;
    ArcNode *p;
    printf("请输入顶点数，边数：\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请输入顶点值（字符）");
    for(i=0;i<G.vexnum;i++){
        getchar();
        scanf("%c",&G.vertices[i].data);
        G.vertices[i].firstarc=NULL;
    }
    printf("请输入顶点序号：\n");
    for(i=0;i<G.arcnum;i++){
        scanf("%d%d",&s,&d);
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=d;
        p->nextarc=G.vertices[s].firstarc;
        G.vertices[s].firstarc=p;
        printf("此边是否含有其他信息？（0.是 1. 否）");
        scanf("%d",&IncInfo);
        if(IncInfo){
            printf("请输入相关信息\n");
            scanf("%s",p->info);
        }
    }   
}
int CreateUDN2(ALGraph &G){
    int i,s,d,IncInfo;
    ArcNode *p,*q;
    printf("请输入顶点数，边数：\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请输入顶点值（字符）\n");
    for(i=0;i<G.vexnum;i++){
        getchar();
        scanf("%c",&G.vertices[i].data);
        G.vertices[i].firstarc=NULL;
    }
    printf("请输入顶点序号：\n");
    for(i=0;i<G.arcnum;i++){
        scanf("%d%d",&s,&d);
        p=(ArcNode*)malloc(sizeof(ArcNode));
        q=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=d;
        q->adjvex=s;
        p->nextarc=G.vertices[s].firstarc;
        G.vertices[s].firstarc=p;
        q->nextarc=G.vertices[d].firstarc;
        G.vertices[d].firstarc=q;
        printf("此边是否含有其他信息？（0.是 1. 否）");
        scanf("%d",&IncInfo);
        if(IncInfo){
            printf("请输入相关信息\n");
            scanf("%s",p->info);
        }
    }
}
int CreateGraph2(ALGraph &G) {
 printf("请输入你要创建的图的类型：\n1、有向图；2、有向网；3、无向图；4、无向网\n");
 scanf("%d",&G.kind);
  switch(G.kind) {
 case 1: CreateDG2(G);break;   
 case 2: CreateDN2(G);break;   
 case 3: CreateUDG2(G);break;  
 case 4: CreateUDN2(G);break;  
 default:return ERROR;
 }
}
int CreateGraph(MGraph &G) {
 printf("请输入你要创建的图的类型：\n1、有向图；2、有向网；3、无向图；4、无向网\n");
 scanf("%d",&G.kind);
  switch(G.kind) {
 case 1: CreateDG(G);break;   
 case 2: CreateDN(G);break;   
 case 3: CreateUDG(G);break;  
 case 4: CreateUDN(G);break;  
 default:return ERROR;
 }
}

int(*VisitFunc)(int v,ALGraph G);
bool visited[MAX_VERTEX_NUM];
//DFS
int DFS(ALGraph G,int v){
    ArcNode *p;
    visited[v]=true;
    (*VisitFunc)(v,G);
    for(p=G.vertices[v].firstarc;p;p=p->nextarc){
        if(!visited[p->adjvex])
          DFS(G,p->adjvex);
    }
}
//DFSraverse
int DFSTraverse(ALGraph G,int(*Visit)(int v,ALGraph G)){
    int v;
    VisitFunc=Visit;
    for(v=0;v<G.vexnum;++v)
       visited[v]=false;
    for(v=0;v<G.vexnum;++v){
        if(!visited[v])
        DFS(G,v);
    }
}


//v函数
int Printelem(int v,ALGraph G){
    printf("%c ",G.vertices[v].data);
}
//prim算法
typedef struct{
        char adjvex;
        int lowcost;
    }CLOSEDGE,closedge[MAX_VERTEX_NUM];

int minimum(closedge SZ,MGraph G)
{
    int i=0,j,k,min;
    while(SZ[i].lowcost!=0)
        i++;
    min=SZ[i].lowcost;
    k=i;
    for(j=i+1;j<G.vexnum;j++)
        if(SZ[j].lowcost>0)
            if(min>SZ[j].lowcost)
            {
                min=SZ[j].lowcost;
                k=j;
            }
    return k;
}
int MiniSpanTree_PRIM(MGraph G,int u){
    int k,j,i;
    closedge T;
    k=LocateVex(G,u);
    for(j=0;j<G.vexnum;++j){
        if(j!=k)
          {T[j].adjvex=u;
          T[j].lowcost=G.arcs[k][j].adj;
          }
    }
    T[k].lowcost=0;
    for(i=1;i<G.vexnum;++i){
        k=minimum(T,G);
        printf("(%d-%d)",T[k].adjvex,G.vexs[k]);
        T[k].lowcost=0;
        for(j=0;j<G.vexnum;++j){
        if(G.arcs[k][j].adj<T[j].lowcost)
          {
          T[j].adjvex=G.vexs[k];
          T[j].lowcost=G.arcs[k][j].adj;
          }
    }
}
}
int main(){
    int t,i;
    do{
        printf("请选择进行的操作：\n1.构建图 2.遍历 3.构建最小生成树\n");
    scanf("%d",&i);
    switch(i){
        case 1:printf("请选择存储结构：1.邻接矩阵 2.邻接表\n");
               scanf("%d",&t);
               if(t==1){
                 MGraph G;
                 CreateGraph(G);
               }
              else {
                ALGraph G;
                CreateGraph2(G);
              }
              printf("\n");
              break;
        case 2:printf("请先构建图\n");
               ALGraph K;
               CreateGraph2(K);
               DFSTraverse(K,Printelem);
               printf("\n");
               break;
        case 3:printf("请先构建无向网\n");
               MGraph M;
               char o;
               CreateUDN(M);
               printf("请输入最小生成树的起点\n");
               scanf("%d",&o);
               printf("\n");
               MiniSpanTree_PRIM(M,o);
               printf("\n");
               break;
        }
    }while(i);

}

ps:我去年刚在慕课上学的算法，小白一个，别被版主的名头吓到了

1.我复制了代码，但没能搞清你的思路架构。调试都做不到（主要是一看到这么长的代码就头疼，没有过看别人代码的经历），所以希望你能把题目、以及题目的测试案例也贴出来，看着方便些。
2.你看下我这个测试流程有没错。我这图是等长的边，应该结果是1-2 1-3 1-4，你的程序不知道为什么跑出三个1-1来，我想第一你就没做筛选，你没有机制去判断这个要去的地方是不是已经去过了（或者你看下这里有没有问题）
3.我看你那个最小生成树的函数好短，我自己曾经写过一个Prim的练习作业，里面的Prim就要长得多。

#include <stdio.h>
#include <stdlib.h>
#define FULL 101
typedef struct LNode *Vertex;

struct LNode {
    int b,lenth;
    Vertex Next;
};

Vertex CreatV(int);
void FreeV(Vertex,int);
int Prim(Vertex,int);
Vertex InsertV(Vertex,int,int);

int main() {
    int N,M;
    scanf("%d%d",&N,&M);
    Vertex V=CreatV(N+1);
    for(int i=0; i<M; i++) {
        int from,to,lenth;
        scanf("%d%d%d",&from,&to,&lenth);
        InsertV(&V[to],from,lenth);
        InsertV(&V[from],to,lenth);
    }
    int lenth=Prim(V,N+1);
    printf("%d",lenth);
    return 0;
}
int Prim(Vertex V,int n) {
    printf("*");
    int lenth=0;
    int min=0;
    for(int i=1; i<n; i++) {
        if(V[i].Next)
            if(V[i].Next->lenth<V[min].Next->lenth)min=i;
    }
    int*a=(int*)malloc(sizeof(int)*n-1),right=1;
    a[0]=min;
    lenth+=V[min].Next->lenth;
    a[right++]=V[min].Next->b;
    FreeV(V,a[0]);
    while(right<n-1) {
        min=-1;
        for(int i=0; i<right; i++) {
            if(V[a[i]].Next){
                if(min!=-1){
                    if(V[a[i]].Next->lenth<V[a[min]].Next->lenth)min=i;
                }else min=i;
               

            }
        }
        if(min==-1)return 0;
        int i;
        for(i=0; i<right; i++)
            if(a[i]==V[a[min]].Next->b)break;
        if(i==right) {
            printf("%d",V[a[min]].Next->b) ;
            a[right++]=V[a[min]].Next->b;
            lenth+=V[a[min]].Next->lenth;
        }
        FreeV(V,a[min]);
    }
    printf("%d ",a[0]);
    return lenth;
}
void FreeV(Vertex V,int X) {
    Vertex temp=V[X].Next;
    V[X].Next=temp->Next;
    X=temp->b;
    free(temp);
    temp=V[X].Next;
    V[X].Next=temp->Next;
    free(temp);
}
Vertex CreatV(int num) {
    Vertex V=(Vertex)malloc(sizeof(struct LNode)*num);
    for(int i=0; i<num; i++) {
        V[i].Next=NULL;
        V[i].b=0;
        V[i].lenth=0;
    }
    V[0].Next=(Vertex)malloc(sizeof(struct LNode));
    V[0].Next->b=0;
    V[0].Next->lenth=FULL;
    V[0].Next->Next=NULL;
    return V;
}
Vertex InsertV(Vertex V,int b,int lenth) {
    Vertex head=V;
    while(V->Next) {
        if(V->Next->lenth>lenth)break;
        if(V->Next->lenth==lenth&&V->Next->b>b)break;
        V=V->Next;
    }
    Vertex New=(Vertex)malloc(sizeof(struct LNode));
    New->lenth=lenth;
    New->b=b;
    New->Next=V->Next;
    V->Next=New;
    return head;
}

厉害

谢谢你愿意亲自看一下！

已经生成完整的代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INT_MAX                 100
#define INFINITY                INT_MAX         
#define MAX_VERTEX_NUM          20              
#define ERROR                   false
#define OK                   true
typedef int VRType;
typedef char InfoType;
typedef char VertexType;
typedef bool Status;
typedef enum {DG, DN, UDG, UDN} GraphKind;      

typedef struct ArcCell {
 VRType adj;                                 
 InfoType *info;                             
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

struct MGraph
{
 VertexType vexs[MAX_VERTEX_NUM];            
 AdjMatrix arcs;                             
 int vexnum, arcnum;                        
 GraphKind kind;                             
};

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int *info;
}ArcNode;

typedef struct VNode{
    VertexType data;
    ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
    int kind;
}ALGraph;

Status CreateDG(MGraph &G);
Status CreateDN(MGraph &G);
Status CreateUDG(MGraph &G);
Status CreateUDN(MGraph &G);
Status CreateDG1(ALGraph &M);
Status CreateDN1(ALGraph &M);
Status CreateUDG1(ALGraph &M);
Status CreateUDN1(ALGraph &M);

int LocateVex(MGraph G, VertexType u)
{
 
 int i;
 
 for (i=0; i<G.vexnum; ++i)
  if (G.vexs[i]==u)
   return i;
  
  return -1;
}


Status CreateGraph(MGraph &G) {
 
 
 printf("请输入你要创建的图的类型：\n1、有向图邻接矩阵；2、有向网邻接矩阵；3、无向图邻接矩阵；4、无向网邻接矩阵\n");
 scanf("%d",&G.kind);
 switch(G.kind-1) {
 case DG:  CreateDG(G);break;   
 case DN:  CreateDN(G);   break;
 case UDG:  CreateUDG(G);  break;
 case UDN:  CreateUDN(G);break;  
 default:return ERROR;
 }
}


Status CreateGraph1(ALGraph &M) {
 
 
 printf("请输入你要创建的图的类型：\n1、有向图邻接表；2、有向网邻接表；3、无向图邻接表；4、无向网邻接表\n");
 scanf("%d",&M.kind);
 switch(M.kind-1) {
 case DG:  CreateDG1(M);break;   
 case DN:  CreateDN1(M);break;   
 case UDG:  CreateUDG1(M);break;   
 case UDN:  CreateUDN1(M);break;  
 default:return ERROR;
 }
}

Status CreateDG(MGraph &G)                                
{
    G.kind=DG;
    int i, j, k;
    VertexType v1, v2;
    printf("请输入有向图的顶点和边数：\n");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    printf("输入%d个顶点的值:", G.vexnum);
    for (i = 0;i<G.vexnum;i++) {
        scanf("%c", &G.vexs[i]);
        getchar();
    }
    for (i = 0;i<G.vexnum;i++)                                               
        for (j = 0;j<G.vexnum;j++)
        {
            G.arcs[i][j].adj = 0;
            G.arcs[i][j].info = 0;
        }
    printf("输入%d条边的两个顶点:\n", G.arcnum);
    for (k = 0;k<G.arcnum;k++) {                                    
        scanf("%c %c", &v1, &v2);
        getchar();                           
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G.arcs[i][j].adj = 1;
    }
    return 1;
}

Status CreateDN(MGraph &G)                                 
{
    G.kind=DN;
    int i, j, k, w;
    VertexType v1, v2;
    printf("请输入有向网的顶点和边数：\n");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    printf("输入%d个顶点的值:", G.vexnum);
    for (i = 0;i<G.vexnum;i++) {
        scanf("%c", &G.vexs[i]);
        getchar();
    }
    for (i = 0;i<G.vexnum;i++)
        for (j = 0;j<G.vexnum;j++)
        {
            G.arcs[i][j].adj = INFINITY;
            G.arcs[i][j].info = 0;
        }
    printf("输入%d条边的两个顶点及权值:\n", G.arcnum);
    for (k = 0;k<G.arcnum;k++)
    {
        scanf("%c %c %d", &v1, &v2, &w);
        getchar();
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G.arcs[i][j].adj = w;
    }
    return 1;
}

Status CreateUDG(MGraph &G)
{
    G.kind=UDG;
    printf("请输入无向图的顶点数与边数：\n");
    scanf("%d %d",&G.vexnum, &G.arcnum);
    int i,j;
    printf("输入%d个顶点的值：",G.vexnum);
        getchar();
        for(i=0;i<G.vexnum;i++)
        {
        scanf("%c",&G.vexs[i]);
        getchar();
        }
    for(i=0; i<G.vexnum; ++i)
    {
        for(j=0; j<G.vexnum; ++j)  
        {
            G.arcs[i][j].adj = 0;
            G.arcs[i][j].info = NULL;
        }
    }
    int k;
    VertexType v1, v2;
    for(k=0; k<G.arcnum; ++k)
    {  
        printf("请输入第%d条边依附的顶点：\n", k+1);  
        
        scanf("%c %c",&v1, &v2);
        getchar();
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);
        if(i==-1 || j==-1)
            return ERROR;
        G.arcs[i][j].adj = 1;
        G.arcs[j][i].adj = G.arcs[i][j].adj;
    }
    return OK;  
}



Status CreateUDN(MGraph &G)                     
{
    G.kind=UDN;
    int i, j, k, w;
    VertexType v1, v2;
    printf("请输入无向网的顶点和边数：\n");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    printf("输入%d个顶点的值:\n", G.vexnum);
    for (i = 0;i<G.vexnum;i++) {
        scanf("%c", &G.vexs[i]);
        getchar();
    }
    for (i = 0;i<G.vexnum;i++)
        for (j = 0;j<G.vexnum;j++)
        {
            G.arcs[i][j].adj = INFINITY;
            G.arcs[i][j].info = 0;
        }
    printf("输入%d条边的两个顶点及权值:\n", G.arcnum);
    for (k = 0;k<G.arcnum;k++)
    {
        scanf("%c %c %d", &v1, &v2, &w);
        getchar();
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G.arcs[i][j].adj = w;
        G.arcs[j][i] = G.arcs[i][j];
    }
    return 1;
}


void PrintMGraph(MGraph &G)
{
    int i, j;
    printf("邻接矩阵为：\n");
    for (i = 0;i<G.vexnum;++i)
    {
        for (j = 0;j<G.vexnum;++j)
            printf("%5d", G.arcs[i][j]);
        printf("\n");
    }
}

Status CreateDG1(ALGraph &M){
    int i,s,d,k;
    printf("构建有向图邻接表，请输入顶点的数目和边的数目：\n");
    scanf("%d%d",&M.vexnum,&M.arcnum);
    printf("请依次输入对应的顶点的值：\n");
    for( i=0;i<M.vexnum;i++ ) {
        getchar();
    scanf("%c",&M.vertices[i].data);
    M.vertices[i].firstarc=NULL;
  }
  for( k = 0; k < M.arcnum; k++ ) {
  printf("请输入第%d条边的两个顶点的序号：\n",k+1);
  scanf("%d%d",&s,&d);
  ArcNode *p;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=d;
  p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
}
}




Status CreateDN1(ALGraph &M){
    int i,s,d,k,*w;
    printf("构建有向网邻接表，请输入顶点的数目和边的数目：\n");
    scanf("%d%d",&M.vexnum,&M.arcnum);
    printf("请依次输入对应的顶点的值：\n");
    for( i = 0; i < M.vexnum; i++ ) {
        getchar();
    scanf("%c",&M.vertices[i].data);
    M.vertices[i].firstarc=NULL;
  }
  for( k = 0; k < M.arcnum; k++ ) {
  printf("请输入第%d条边的两个顶点的序号：\n",k+1);
  scanf("%d%d",&s,&d);
  ArcNode *p;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=d;
  printf("请输入该边权值\n");
  scanf("%d",&w);
  p->info=w;p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
}
}



Status CreateUDG1(ALGraph &M){
    int i,s,d,k;
    printf("构建无向图邻接表，请输入顶点的数目和边的数目：\n");
    scanf("%d%d",&M.vexnum,&M.arcnum);
    printf("请依次输入对应的顶点的值：\n");
    for( i = 0; i < M.vexnum; i++ ) {
        getchar();
    scanf("%c",&M.vertices[i].data);
    M.vertices[i].firstarc=NULL;
  }
  for( k = 0; k < M.arcnum; k++ ) {
  printf("请输入第%d条边的两个顶点的序号：\n",k+1);
  scanf("%d%d",&s,&d);
  ArcNode *p,*q;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  q=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=d;q->adjvex=s;
  p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
  q->nextarc=M.vertices[d].firstarc;M.vertices[d].firstarc=q;
}
}


Status CreateUDN1(ALGraph &M){
    int i,s,d,k,*w;
    printf("构建无向网邻接表，请输入顶点的数目和边的数目：\n");
    scanf("%d%d",&M.vexnum,&M.arcnum);
    printf("请依次输入对应的顶点的值：\n");
    for( i = 0; i < M.vexnum; i++ ) {
        getchar();
    scanf("%c",&M.vertices[i].data);
    M.vertices[i].firstarc=NULL;
  }
  for( k = 0; k < M.arcnum; k++ ) {
  printf("请输入第%d条边的两个顶点的序号：\n",k+1);
  scanf("%d%d",&s,&d);
  ArcNode *p,*q;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  q=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=d;q->adjvex=s;
  printf("请输入该边权值\n");
  scanf("%d",&w);
  p->info=w;p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
  q->info=w;q->nextarc=M.vertices[d].firstarc;M.vertices[d].firstarc=q;
}
}


void PrintALGraph(ALGraph &G){
     int q;
        ArcNode *e;
        printf("所构建的邻接表如下所示\n");
        for(q=0;q<G.vexnum;++q){
            printf("%c->",G.vertices[q].data);
            e=G.vertices[q].firstarc;
        while(e){
            printf("%d->",e->adjvex);
            e=e->nextarc;
        }
        printf("\n");
    }

       }
      


bool visited[MAX_VERTEX_NUM+1];   
int (*VisitFunc)(MGraph &G,int v);   
int FirstAdjVex(MGraph &G, VertexType v)  
{   
    int m = LocateVex(G,v);  
    if(m== -1)  
        return -1;  
    int adjValue = 0;   
    if(G.kind == DN || G.kind == UDN)  
        adjValue = INFINITY;
    for(int i=0; i < G.vexnum; ++i)  
    {  
        if(G.arcs[m][i].adj != adjValue)  
            return i;  
    }  
    return -1;  
}  
  
int NextAdjVex(MGraph &G, VertexType v, VertexType w)  
{  
   
    int m=LocateVex(G,v);  
    int n=LocateVex(G,w);
   
    if(m == -1 || n== -1)  
    {  
        return -1;  
    }  
    int adjValue = 0;   
    if(G.kind == DN || G.kind == UDN)  
        adjValue = INFINITY;  
    for(int i=n+1; i < G.vexnum; ++i)  
    {  
        if(G.arcs[m][i].adj != adjValue)  
        {
            return i;
       }
    }
    return -1;   
}

VertexType GetVex(MGraph &G, int v)  
{  
   
    if(v >= G.vexnum || v < 0)
        return 0;
    return G.vexs[v];
}

void DFS(MGraph &G, int v)  
{
    visited[v] = true;
    VisitFunc(G,v);
    for(int w = FirstAdjVex(G,GetVex(G,v)); w >= 0; w = NextAdjVex(G,GetVex(G,v),GetVex(G,w)))
        if(!visited[w])
            DFS(G,w);
}

void DFSTraverse(MGraph &G, int(*Visit)(MGraph &G,int v))
{  
    int v=0;char y='\0';
    printf ("\n请输入遍历首顶点：");
    getchar ();
    scanf ("%c",&y);
    printf ("深度优先搜索遍历的结果为：");
    VisitFunc=Visit;
    for ( ;v<G.vexnum;v++) visited[v]=0;
        v=LocateVex (G,y);
        DFS (G,v);
    for (v=0;v<G.vexnum;v++)
        if (!visited[v])
        DFS (G,v);
}

int VisitVex(MGraph &G,int v)  
{
    printf("%3c",G.vexs[v]);
    return OK;
}

typedef struct{
        char adjvex;
        int lowcost;
    }CLOSEDGE,closedge[MAX_VERTEX_NUM];

int minimum(closedge closedge,MGraph G)
{
    int min=INFINITY,k=0,i;
    for(i=0;i<G.vexnum;i++)
    {
        if(closedge[i].lowcost != 0 && closedge[i].lowcost < min)
        {
            min = closedge[i].lowcost;
            k = i;
        }
    }
    return k;
}
int MiniSpanTree_PRIM(MGraph G,char u){
    int k,j,i;
    closedge T;
    k=LocateVex(G,u);
    for(j=0;j<G.vexnum;++j){
        if(j!=k)
          {T[j].adjvex=u;
          T[j].lowcost=G.arcs[k][j].adj;
          }
    }
    T[k].lowcost=0;
    for(i=1;i<G.vexnum;++i){
        k=minimum(T,G);
        printf("(%c,%c) ",T[k].adjvex,G.vexs[k]);
        T[k].lowcost=0;
        for(j=0;j<G.vexnum;++j){
        if(G.arcs[k][j].adj<T[j].lowcost)
          {
          T[j].adjvex=G.vexs[k];
          T[j].lowcost=G.arcs[k][j].adj;
          }
    }
}
}

int main()
{   
    MGraph G;
    ALGraph M;
    int a,k;
    char u;
  for(k=1;;k++)
    {
     printf("1.创建邻接矩阵 2.创建邻接表 3.DFS遍历 4.邻接矩阵构建最小生成树（先构建无向网）\n");
     printf("请输入您的选择:\n");
     scanf("%d",&a);
     getchar();
     switch(a)
          {
        case 1:
             CreateGraph(G);
             PrintMGraph(G);
             break;
        case 2:
             CreateGraph1(M);
             PrintALGraph(M);
             break;
        case 3:
             DFSTraverse(G,VisitVex);
             printf("\n");
             break;
        case 4:
            printf("请输入最小生成树的起点：");
            scanf("%c",&u);
        MiniSpanTree_PRIM(G,u);
        printf("\n");break;
        default:exit(0); break;
        }
    }
    return 0;
}