#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>

#define TRUE 1  
#define FALSE 0
#define ERROR 0  
#define OVERFLOW 0
#define OK 1  
#define INFINITY 65535         //表示無(wú)窮大-->在帶權(quán)的圖中用到，即網(wǎng)  
#define MAX_VERTEX_NUM 20         //圖的最大頂點(diǎn)數(shù)
#define MAX_INFO 20          //每條弧附帶信息最大長(zhǎng)度  
  
typedef int Status;  
typedef int VRType;      //頂點(diǎn)關(guān)系類型  
typedef char InfoType;      //附加信息類型  
typedef int VertexType;  //頂點(diǎn)數(shù)據(jù)類型  
  
//C語(yǔ)言中枚舉中的數(shù)據(jù)是整型的，默認(rèn)從0開(kāi)始依次賦值 
typedef enum {DG,DN,UDG,UDN} GraphKind;     //圖的種類:分別代表有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng) 
  
typedef struct {      //鄰接矩陣
    VRType adj;         //頂點(diǎn)關(guān)系類型，對(duì)無(wú)權(quán)圖用1或0表示是否相鄰；對(duì)帶權(quán)圖，就表示權(quán)值，有權(quán)值表示有邊，沒(méi)邊數(shù)值就為INFINITY（無(wú)窮大）
    InfoType *info;         //附加信息指針  
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  
  
typedef struct {  
    
    VertexType vexs[MAX_VERTEX_NUM];    //定義一個(gè)數(shù)組用來(lái)存放圖中的頂點(diǎn)
    
    AdjMatrix arcs;     //鄰接矩陣  表示頂點(diǎn)之間的關(guān)系（其實(shí)就是有沒(méi)有邊）
    
    int vexnum;     //圖的當(dāng)前頂點(diǎn)數(shù)
    
    int arcnum;     //圖的弧數(shù)
    
    GraphKind kind;     //圖的種類
}MGraph;  




//------------------------返回圖G中的  頂點(diǎn)v  在存放頂點(diǎn)的數(shù)組中  的位置---------------------------------
int LocateVex(MGraph G,VertexType v) {  
  
    for(int i = 0;i < G.vexnum; i++){
        if(G.vexs[i] == v){
            return i;
        }
    }
    return -1;
}

//------------------------創(chuàng)建無(wú)向圖---------------------------------
Status CreateUDG(MGraph &G) {  
    int i,j,k,infoflag,len;  
    char c;  
    //設(shè)置一個(gè)暫存區(qū)和一個(gè)臨時(shí)指針  
    char str[MAX_INFO];  
    char *info;  
  
    VertexType v1,v2;  
  
    len = 0;  
  
    //確定頂點(diǎn)數(shù)/弧數(shù)/弧是否攜帶信息
    printf("請(qǐng)分別輸入 頂點(diǎn)數(shù)量、邊的數(shù)量、邊是否攜帶信息（要攜帶輸入1否則輸入0）\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //確定各個(gè)頂點(diǎn)的值  
    printf("依次輸入頂點(diǎn)（用-1表示頂點(diǎn) V1  依此類推）\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;  
    }  
  
  
    //確定鄰接矩陣  
    printf("圖中有%d條邊\n",G.arcnum);
     if(G.arcnum>0){
        printf("請(qǐng)依次輸入這些邊(用兩個(gè)頂點(diǎn)表示一條邊)及其權(quán)值\n\n\n");
    }
    for(k = 0; k < G.arcnum; k++) {  
    scanf("%d%d",&v1,&v2);
        printf("%d條邊輸入完成\n\n\n",k+1);
    i = LocateVex(G,v1);  
    j = LocateVex(G,v2);  
  
    if(i >= 0 && j >= 0)  
        G.arcs[i][j].adj = G.arcs[j][i].adj = 1;  //無(wú)向圖,對(duì)稱矩陣  
    //如果頂點(diǎn)有附帶信息,則輸入并申請(qǐng)空間  
    if(infoflag) {  
        printf("please enter the info:");  
        while( (c = getchar()) != '#')  
        str[len++] = c;  
  
        info = (char *) malloc(len * sizeof(char));  
        str[len] = '\0';  
  
        strcpy(info,str);  
  
        G.arcs[i][j].info = G.arcs[j][i].info = info;  
    }  
    }  
  
    G.kind = UDG;  
  
    return OK;  
}  
//------------------------創(chuàng)建有向圖---------------------------------

Status CreateDG(MGraph &G) {  
    int i,j,k,len,infoflag;  
    VertexType v1,v2;  
  
    char str[MAX_INFO];  
    char *info;  
    char c;  
  
    //確定頂點(diǎn)數(shù)/弧數(shù)  
    printf("請(qǐng)分別輸入 頂點(diǎn)數(shù)量、弧的數(shù)量、弧是否攜帶信息（要攜帶輸入1否則輸入0）\n");  
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //確定各個(gè)頂點(diǎn)的值  
    printf("依次輸入頂點(diǎn)（用-1表示頂點(diǎn) V1  依此類推）\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;  
    }  
  
  
    //確定鄰接矩陣  
      
    printf("圖中有%d條弧\n",G.arcnum);
     if(G.arcnum>0){
        printf("請(qǐng)依次輸入這些弧(用兩個(gè)頂點(diǎn)表示一條弧)及其權(quán)值\n\n\n");
    }
    for(k = 0; k < G.arcnum; k++) {  
    scanf("%d%d",&v1,&v2);
    printf("%d條弧輸入完成\n\n\n",k+1);
    i = LocateVex(G,v1);  
    j = LocateVex(G,v2);  
  
    if(i >= 0 && j >= 0)  
        G.arcs[i][j].adj = 1;    //有向圖  
  
    //如果頂點(diǎn)有附帶信息,則輸入并申請(qǐng)空間  
    if(infoflag) {  
        printf("please enter the info:");  
        while( (c = getchar()) != '#')  
        str[len++] = c;  
  
        info = (char *) malloc(len * sizeof(char));  
        strcpy(info,str);  
  
        G.arcs[i][j].info = info;  
    }  
    }  
  
    G.kind = DG;  
  
    return OK;  
}  


//------------------------創(chuàng)建有向網(wǎng)---------------------------------
Status CreateDN(MGraph &G) {  
    int i,j,k,len,infoflag,w;  
    VertexType v1,v2;  
  
    char str[MAX_INFO];  
    char *info;  
    char c;  
  
    //確定頂點(diǎn)數(shù)/弧數(shù)  
    printf("請(qǐng)分別輸入 頂點(diǎn)數(shù)量、弧的數(shù)量、弧是否攜帶信息（要攜帶輸入1否則輸入0）\n");  
    
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //確定各個(gè)頂點(diǎn)的值  
    printf("依次輸入頂點(diǎn)（用-1表示頂點(diǎn) V1  依此類推）\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; //有向網(wǎng)  
        G.arcs[i][j].info = NULL;  
    }  
  
  
    //確定鄰接矩陣  
    printf("圖中有%d條弧",G.arcnum);
    if(G.arcnum>0){
        printf("請(qǐng)依次輸入這些弧(用兩個(gè)頂點(diǎn)表示一條弧)及其權(quán)值\n\n\n");
    }
    for(k = 0; k < G.arcnum; k++) {  
    scanf("%d%d%d",&v1,&v2,&w);
    printf("%d條弧輸入完成\n\n\n",k+1);
    i = LocateVex(G,v1);  
    j = LocateVex(G,v2);  
  
    if(i >= 0 && j >= 0)  
        G.arcs[i][j].adj = w;    //有向圖  
  
    //如果頂點(diǎn)有附帶信息,則輸入并申請(qǐng)空間  
    if(infoflag) {  
        printf("please enter the info:");  
        while( (c = getchar()) != '#')  
        str[len++] = c;  
  
        info = (char *) malloc(len * sizeof(char));  
        strcpy(info,str);  
  
        G.arcs[i][j].info = info;  
    }  
    }  
  
    G.kind = DN;  
  
    return OK;  
}  
  
//------------------------創(chuàng)建無(wú)向網(wǎng)---------------------------------
Status CreateUDN(MGraph &G) {  
    int i,j,k,len,infoflag,w;  
    VertexType v1,v2;  
  
    char str[MAX_INFO];  
    char *info;  
    char c;  
  
    //確定頂點(diǎn)數(shù)/弧數(shù)  
    printf("請(qǐng)分別輸入 頂點(diǎn)數(shù)量、邊的數(shù)量、邊是否攜帶信息（要攜帶輸入1否則輸入0）\n");  
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //確定各個(gè)頂點(diǎn)的值  
    printf("依次輸入頂點(diǎn)（用-1表示頂點(diǎn) V1  依此類推）\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; //無(wú)向網(wǎng)  
        G.arcs[i][j].info = NULL;  
    }  
  
  
    //確定鄰接矩陣  
    printf("圖中有%d條邊\n",G.arcnum);  
    if(G.arcnum>0){
        printf("請(qǐng)依次輸入這些邊(用兩個(gè)頂點(diǎn)表示一條邊)及其權(quán)值\n\n\n");
    }
    for(k = 0; k < G.arcnum; k++) {  
    scanf("%d%d%d",&v1,&v2,&w);
    printf("%d條邊輸入完成\n\n\n",k+1);
    i = LocateVex(G,v1);  
    j = LocateVex(G,v2);  
  
    if(i >= 0 && j >= 0)  
        G.arcs[i][j].adj = G.arcs[j][i].adj = w;  //無(wú)向網(wǎng)  
  
    //如果頂點(diǎn)有附帶信息,則輸入并申請(qǐng)空間  
    if(infoflag) {  
        printf("please enter the info:");  
        while( (c = getchar()) != '#')  
        str[len++] = c;  
  
        info = (char *) malloc(len * sizeof(char));  
        strcpy(info,str);  
  
        G.arcs[i][j].info = info;  
    }  
    }  
  
    G.kind = UDN;  
  
    return OK;  
}  
  
  
  
  
//------------------------創(chuàng)建圖---------------------------------

Status CreateGraph(MGraph &G) {  
    printf("請(qǐng)輸入要?jiǎng)?chuàng)建的圖的種類   (有向圖:0,有向網(wǎng):1,無(wú)向圖:2,無(wú)向網(wǎng):3):\n");  
    scanf("%d",&G.kind);  
  
    switch(G.kind) {  
    case UDG:  
        return CreateUDG(G);  
        break;  
    case DG:  
        return CreateDG(G);  
    case UDN:  
        return CreateUDN(G);  
        break;  
    case DN:  
        return CreateDN(G);  
        break;  
    default:  
        return ERROR;  
    }  
}   

//------------------------普里姆算法構(gòu)造 最小生成樹(shù)---------------------------------
void MiniSpanTree_PRIM(MGraph G,VertexType u){
    //用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)T，輸出T的各條邊
    if(G.kind==DG||G.kind==UDG){
        printf("\n此圖中不存在權(quán)值無(wú)法構(gòu)造最小生成樹(shù)！\n");
        return;
    }
    else{
        printf("從頂點(diǎn)%d出發(fā)構(gòu)造網(wǎng)的最小生成樹(shù)為\n",u);
        if(G.arcnum==0){
            printf("\n空樹(shù)\n");
        }
    }
    
    struct {    //定義一個(gè)輔助數(shù)組closedge（緊鄰的邊），來(lái)記錄從U到V-U具有最小代價(jià)的邊      //集合U表示已記錄的頂點(diǎn)，集合V表示全部頂點(diǎn)
        VertexType adjvex;  //頂點(diǎn)
        VRType lowcost;     //附在頂點(diǎn)上的一條邊的權(quán)值 與上面的adjvex合起來(lái)就可以具體表示到想要表示的邊了
    }closedge[MAX_VERTEX_NUM];
    
    int k=LocateVex(G,u);       //頂點(diǎn)u的位置
    
    
    for(int j=0;j<G.vexnum;j++){    //輔助數(shù)組初始化
        if(j!=k){
            closedge[j]={u,G.arcs[k][j].adj};
        }
    }

    closedge[k].lowcost=0;      //初始化U={u}
    for(int i=1;i<G.vexnum;i++){    //選擇其余G.vexnum-1個(gè)頂點(diǎn)
        //k=minimum(closedge);        //書(shū)上本來(lái)是調(diào)用這個(gè)函數(shù) 由于用到的結(jié)構(gòu)體是在主函數(shù)內(nèi)部調(diào)用的 定義這個(gè)函數(shù)不方便 就用下面9行代替了
        for(k=0;!closedge[k].lowcost;k++){    //保證closedge[k].lowcost不是0
        }
        int min=INFINITY;
        for(int s=0;s<G.vexnum;s++){    //求出T的下一個(gè)結(jié)點(diǎn)：第k頂點(diǎn)(權(quán)值最小的點(diǎn))
            if(closedge[s].lowcost<min&&closedge[s].lowcost!=0){
                k=s;
                min=closedge[s].lowcost;
            }
        }
        
        printf("%d_____(%d)_____%d\n",closedge[k].adjvex,closedge[k].lowcost,G.vexs[k]);    //輸出生成樹(shù)的邊
        closedge[k].lowcost=0;      //第k頂點(diǎn)并入U(xiǎn)集  （用lowcost域==0來(lái)表示并入U(xiǎn)集的頂點(diǎn)）
        for(int j=0;j<G.vexnum;j++){
            if(G.arcs[k][j].adj<closedge[j].lowcost){       //新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};
            }
        }
    }
    printf("\n\n\n");
}

//------------------------遍歷輔助 變量和函數(shù)---------------------------------

Status visited[MAX_VERTEX_NUM]; // 訪問(wèn)標(biāo)志數(shù)組(全局量) TRUE表示已訪問(wèn) FALSE表示未訪問(wèn)
void(*VisitFunc)(VertexType v);     //函數(shù)變量

//------------------------輔助函數(shù) 1 :返回v的第一個(gè)鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn)，則返回-1---------------------------------
int FirstAdjVex(MGraph G,VertexType v){      // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)
    int     i, j = 0, k;  
    k = LocateVex(G, v);  
    if (k < 0)  
    return ERROR;  
    
    if(G.kind%2==1){    //表示要遍歷的不是圖是網(wǎng)
        j=INFINITY;
    }
    
    for (i = 0; i < G.vexnum; i++)  
    if (G.arcs[k][i].adj != j)  
        return i;  
    return -1;  
}  

//------------------------輔助函數(shù) 2 :返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)，若w是v的最后一個(gè)鄰接頂點(diǎn)，則返回-1 ---------------------------------
int NextAdjVex(MGraph G,VertexType v,VertexType w){        // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)
    int     i, j = 0, k1, k2;  
    k1 = LocateVex(G, v);   // k1為頂點(diǎn)v在圖G中的序號(hào)  
    k2 = LocateVex(G, w);   // k2為頂點(diǎn)w在圖G中的序號(hào)
    
    if(G.kind%2==1){    //表示要遍歷的不是圖是網(wǎng)
        j=INFINITY;
    }
    
    for (i = k2+1; i < G.vexnum; i++)      
    if (G.arcs[k1][i].adj != j)
        return i;  
    return -1;  
}  
//------------------------輔助函數(shù) 3 :訪問(wèn)---------------------------------
void visit(VertexType i){
    printf("%d ",i);
}  
//------------------------輔助函數(shù) 4（多個(gè)函數(shù)） 隊(duì)列 :---------------------------------
typedef VRType QElemType; // 隊(duì)列元素類型
typedef struct QNode{
    QElemType       data;
    struct QNode    *next;
}*QueuePtr;
typedef struct LinkQueue{
    QueuePtr    front, rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)    //初始化隊(duì)列
{
    Q.front = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front) exit(OVERFLOW);

    Q.front->next = NULL;
    Q.rear = Q.front;

}
void EnQueue(LinkQueue &Q, QElemType e)     //入隊(duì)列
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) exit(OVERFLOW);

    p->next = NULL;
    memcpy(&(p->data), &e, sizeof(QElemType));
    Q.rear->next = p;
    Q.rear = p;
}

Status QueueEmpty(LinkQueue Q)      //判斷隊(duì)列是否為空
{
    if (Q.front == Q.rear)
    return TRUE;
    else
    return FALSE;
}
Status DeQueue(LinkQueue &Q, QElemType &e)      //出隊(duì)列
{
    QueuePtr p = Q.front, q;
    if (Q.front == Q.rear)
    return FALSE;

    q = p->next;
    memcpy(&e, &(q->data), sizeof(QElemType));
    p->next = q->next;
    if (Q.rear == q)
    Q.rear = Q.front;
    free(q);

    return OK;
}
//------------------------深度優(yōu)先遍歷---------------------------------
void DFS(MGraph G,int v){     //從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。
   int w;  
   visited[v] = TRUE;    // 設(shè)置訪問(wèn)標(biāo)志為TRUE(已訪問(wèn))  
   VisitFunc(G.vexs[v]); // 訪問(wèn)第v個(gè)頂點(diǎn)  
   for(w = FirstAdjVex(G,G.vexs[v]); w >= 0; w = NextAdjVex(G,G.vexs[v],G.vexs[w]))  
    if(!visited[w])  
        DFS(G,w);    // 對(duì)v的尚未訪問(wèn)的序號(hào)為w的鄰接頂點(diǎn)遞歸調(diào)用DFS  
}  

void DFSTraverse(MGraph G,void(*Visit)(VertexType v)){   // 初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：從第1個(gè)頂點(diǎn)起，深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次
    printf("\n深度優(yōu)先遍歷\n");
    int v;  
    VisitFunc=Visit; // 使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù)  
    for(v=0;v<G.vexnum;v++)  
    visited[v]=FALSE; // 訪問(wèn)標(biāo)志數(shù)組初始化(未被訪問(wèn))  
    for(v=0;v<G.vexnum;v++)  
    if(!visited[v])  
        DFS(G,v); // 對(duì)尚未訪問(wèn)的頂點(diǎn)v調(diào)用DFS  
    printf("\n");  
}  


//------------------------廣度優(yōu)先遍歷---------------------------------
void BFSTraverse(MGraph G,void(*Visit)(VertexType)){
    int v,u,w;  
    LinkQueue Q;     // 使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited
    
    printf("\n廣度優(yōu)先遍歷\n");
    
    for(v=0;v<G.vexnum;v++)  
    visited[v]=FALSE;     // 置初值
    
    InitQueue(Q);     // 置空的輔助隊(duì)列Q
    
    
    for(v=0;v<G.vexnum;v++){
    if(!visited[v]){     // v尚未訪問(wèn)
        visited[v]=TRUE;         // 設(shè)置訪問(wèn)標(biāo)志為TRUE(已訪問(wèn))
        Visit(G.vexs[v]);  
        EnQueue(Q,v);         // v入隊(duì)列
        while(!QueueEmpty(Q)){          // 隊(duì)列不空
        DeQueue(Q,u);         // 隊(duì)頭元素出隊(duì)并置為u
        for(w = FirstAdjVex(G,G.vexs[u]); w >= 0; w=NextAdjVex(G,G.vexs[u],G.vexs[w])){
            if(!visited[w]){         // w為u的尚未訪問(wèn)的鄰接頂點(diǎn)的序號(hào)
                visited[w]=TRUE;
                Visit(G.vexs[w]);
                EnQueue(Q,w);
            }
        }
        }  
    }
    }
   printf("\n");  
}  



































//------------------------主函數(shù)---------------------------------
int main(){
    MGraph G;
    CreateGraph(G);
    
    MiniSpanTree_PRIM(G,-1);
    
    DFSTraverse(G,visit);
    BFSTraverse(G,visit);
    
    
    
    return 0;
}