图

#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         //表示无穷大-->在带权的图中用到，即网  
#define MAX_VERTEX_NUM 20         //图的最大顶点数
#define MAX_INFO 20          //每条弧附带信息最大长度  
  
typedef int Status;  
typedef int VRType;      //顶点关系类型  
typedef char InfoType;      //附加信息类型  
typedef int VertexType;  //顶点数据类型  
  
//C语言中枚举中的数据是整型的，默认从0开始依次赋值 
typedef enum {DG,DN,UDG,UDN} GraphKind;     //图的种类:分别代表有向图，有向网，无向图，无向网 
  
typedef struct {      //邻接矩阵
    VRType adj;         //顶点关系类型，对无权图用1或0表示是否相邻；对带权图，就表示权值，有权值表示有边，没边数值就为INFINITY（无穷大）
    InfoType *info;         //附加信息指针  
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  
  
typedef struct {  
    
    VertexType vexs[MAX_VERTEX_NUM];    //定义一个数组用来存放图中的顶点
    
    AdjMatrix arcs;     //邻接矩阵  表示顶点之间的关系（其实就是有没有边）
    
    int vexnum;     //图的当前顶点数
    
    int arcnum;     //图的弧数
    
    GraphKind kind;     //图的种类
}MGraph;  




//------------------------返回图G中的  顶点v  在存放顶点的数组中  的位置---------------------------------
int LocateVex(MGraph G,VertexType v) {  
  
    for(int i = 0;i < G.vexnum; i++){
        if(G.vexs[i] == v){
            return i;
        }
    }
    return -1;
}

//------------------------创建无向图---------------------------------
Status CreateUDG(MGraph &G) {  
    int i,j,k,infoflag,len;  
    char c;  
    //设置一个暂存区和一个临时指针  
    char str[MAX_INFO];  
    char *info;  
  
    VertexType v1,v2;  
  
    len = 0;  
  
    //确定顶点数/弧数/弧是否携带信息
    printf("请分别输入 顶点数量、边的数量、边是否携带信息（要携带输入1否则输入0）\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //确定各个顶点的值  
    printf("依次输入顶点（用-1表示顶点 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("请依次输入这些边(用两个顶点表示一条边)及其权值\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;  //无向图,对称矩阵  
    //如果顶点有附带信息,则输入并申请空间  
    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;  
}  
//------------------------创建有向图---------------------------------

Status CreateDG(MGraph &G) {  
    int i,j,k,len,infoflag;  
    VertexType v1,v2;  
  
    char str[MAX_INFO];  
    char *info;  
    char c;  
  
    //确定顶点数/弧数  
    printf("请分别输入 顶点数量、弧的数量、弧是否携带信息（要携带输入1否则输入0）\n");  
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //确定各个顶点的值  
    printf("依次输入顶点（用-1表示顶点 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("请依次输入这些弧(用两个顶点表示一条弧)及其权值\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;    //有向图  
  
    //如果顶点有附带信息,则输入并申请空间  
    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;  
}  


//------------------------创建有向网---------------------------------
Status CreateDN(MGraph &G) {  
    int i,j,k,len,infoflag,w;  
    VertexType v1,v2;  
  
    char str[MAX_INFO];  
    char *info;  
    char c;  
  
    //确定顶点数/弧数  
    printf("请分别输入 顶点数量、弧的数量、弧是否携带信息（要携带输入1否则输入0）\n");  
    
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //确定各个顶点的值  
    printf("依次输入顶点（用-1表示顶点 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; //有向网  
        G.arcs[i][j].info = NULL;  
    }  
  
  
    //确定邻接矩阵  
    printf("图中有%d条弧",G.arcnum);
    if(G.arcnum>0){
        printf("请依次输入这些弧(用两个顶点表示一条弧)及其权值\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;    //有向图  
  
    //如果顶点有附带信息,则输入并申请空间  
    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;  
}  
  
//------------------------创建无向网---------------------------------
Status CreateUDN(MGraph &G) {  
    int i,j,k,len,infoflag,w;  
    VertexType v1,v2;  
  
    char str[MAX_INFO];  
    char *info;  
    char c;  
  
    //确定顶点数/弧数  
    printf("请分别输入 顶点数量、边的数量、边是否携带信息（要携带输入1否则输入0）\n");  
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag);
  
    //确定各个顶点的值  
    printf("依次输入顶点（用-1表示顶点 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; //无向网  
        G.arcs[i][j].info = NULL;  
    }  
  
  
    //确定邻接矩阵  
    printf("图中有%d条边\n",G.arcnum);  
    if(G.arcnum>0){
        printf("请依次输入这些边(用两个顶点表示一条边)及其权值\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;  //无向网  
  
    //如果顶点有附带信息,则输入并申请空间  
    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;  
}  
  
  
  
  
//------------------------创建图---------------------------------

Status CreateGraph(MGraph &G) {  
    printf("请输入要创建的图的种类   (有向图:0,有向网:1,无向图:2,无向网: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;  
    }  
}   

//------------------------普里姆算法构造 最小生成树---------------------------------
void MiniSpanTree_PRIM(MGraph G,VertexType u){
    //用普里姆算法从顶点u出发构造网G的最小生成树T，输出T的各条边
    if(G.kind==DG||G.kind==UDG){
        printf("\n此图中不存在权值无法构造最小生成树！\n");
        return;
    }
    else{
        printf("从顶点%d出发构造网的最小生成树为\n",u);
        if(G.arcnum==0){
            printf("\n空树\n");
        }
    }
    
    struct {    //定义一个辅助数组closedge（紧邻的边），来记录从U到V-U具有最小代价的边      //集合U表示已记录的顶点，集合V表示全部顶点
        VertexType adjvex;  //顶点
        VRType lowcost;     //附在顶点上的一条边的权值 与上面的adjvex合起来就可以具体表示到想要表示的边了
    }closedge[MAX_VERTEX_NUM];
    
    int k=LocateVex(G,u);       //顶点u的位置
    
    
    for(int j=0;j<G.vexnum;j++){    //辅助数组初始化
        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个顶点
        //k=minimum(closedge);        //书上本来是调用这个函数 由于用到的结构体是在主函数内部调用的 定义这个函数不方便 就用下面9行代替了
        for(k=0;!closedge[k].lowcost;k++){    //保证closedge[k].lowcost不是0
        }
        int min=INFINITY;
        for(int s=0;s<G.vexnum;s++){    //求出T的下一个结点：第k顶点(权值最小的点)
            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]);    //输出生成树的边
        closedge[k].lowcost=0;      //第k顶点并入U集  （用lowcost域==0来表示并入U集的顶点）
        for(int j=0;j<G.vexnum;j++){
            if(G.arcs[k][j].adj<closedge[j].lowcost){       //新顶点并入U后重新选择最小边
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};
            }
        }
    }
    printf("\n\n\n");
}

//------------------------遍历辅助 变量和函数---------------------------------

Status visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) TRUE表示已访问 FALSE表示未访问
void(*VisitFunc)(VertexType v);     //函数变量

//------------------------辅助函数 1 :返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1---------------------------------
int FirstAdjVex(MGraph G,VertexType v){      // 初始条件：图G存在，v是G中某个顶点
    int     i, j = 0, k;  
    k = LocateVex(G, v);  
    if (k < 0)  
    return ERROR;  
    
    if(G.kind%2==1){    //表示要遍历的不是图是网
        j=INFINITY;
    }
    
    for (i = 0; i < G.vexnum; i++)  
    if (G.arcs[k][i].adj != j)  
        return i;  
    return -1;  
}  

//------------------------辅助函数 2 :返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 ---------------------------------
int NextAdjVex(MGraph G,VertexType v,VertexType w){        // 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点
    int     i, j = 0, k1, k2;  
    k1 = LocateVex(G, v);   // k1为顶点v在图G中的序号  
    k2 = LocateVex(G, w);   // k2为顶点w在图G中的序号
    
    if(G.kind%2==1){    //表示要遍历的不是图是网
        j=INFINITY;
    }
    
    for (i = k2+1; i < G.vexnum; i++)      
    if (G.arcs[k1][i].adj != j)
        return i;  
    return -1;  
}  
//------------------------辅助函数 3 :访问---------------------------------
void visit(VertexType i){
    printf("%d ",i);
}  
//------------------------辅助函数 4（多个函数） 队列 :---------------------------------
typedef VRType QElemType; // 队列元素类型
typedef struct QNode{
    QElemType       data;
    struct QNode    *next;
}*QueuePtr;
typedef struct LinkQueue{
    QueuePtr    front, rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)    //初始化队列
{
    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)     //入队列
{
    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)      //判断队列是否为空
{
    if (Q.front == Q.rear)
    return TRUE;
    else
    return FALSE;
}
Status DeQueue(LinkQueue &Q, QElemType &e)      //出队列
{
    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;
}
//------------------------深度优先遍历---------------------------------
void DFS(MGraph G,int v){     //从第v个顶点出发递归地深度优先遍历图G。
   int w;  
   visited[v] = TRUE;    // 设置访问标志为TRUE(已访问)  
   VisitFunc(G.vexs[v]); // 访问第v个顶点  
   for(w = FirstAdjVex(G,G.vexs[v]); w >= 0; w = NextAdjVex(G,G.vexs[v],G.vexs[w]))  
    if(!visited[w])  
        DFS(G,w);    // 对v的尚未访问的序号为w的邻接顶点递归调用DFS  
}  

void DFSTraverse(MGraph G,void(*Visit)(VertexType v)){   // 初始条件：图G存在，Visit是顶点的应用函数。操作结果：从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次
    printf("\n深度优先遍历\n");
    int v;  
    VisitFunc=Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数  
    for(v=0;v<G.vexnum;v++)  
    visited[v]=FALSE; // 访问标志数组初始化(未被访问)  
    for(v=0;v<G.vexnum;v++)  
    if(!visited[v])  
        DFS(G,v); // 对尚未访问的顶点v调用DFS  
    printf("\n");  
}  


//------------------------广度优先遍历---------------------------------
void BFSTraverse(MGraph G,void(*Visit)(VertexType)){
    int v,u,w;  
    LinkQueue Q;     // 使用辅助队列Q和访问标志数组visited
    
    printf("\n广度优先遍历\n");
    
    for(v=0;v<G.vexnum;v++)  
    visited[v]=FALSE;     // 置初值
    
    InitQueue(Q);     // 置空的辅助队列Q
    
    
    for(v=0;v<G.vexnum;v++){
    if(!visited[v]){     // v尚未访问
        visited[v]=TRUE;         // 设置访问标志为TRUE(已访问)
        Visit(G.vexs[v]);  
        EnQueue(Q,v);         // v入队列
        while(!QueueEmpty(Q)){          // 队列不空
        DeQueue(Q,u);         // 队头元素出队并置为u
        for(w = FirstAdjVex(G,G.vexs[u]); w >= 0; w=NextAdjVex(G,G.vexs[u],G.vexs[w])){
            if(!visited[w]){         // w为u的尚未访问的邻接顶点的序号
                visited[w]=TRUE;
                Visit(G.vexs[w]);
                EnQueue(Q,w);
            }
        }
        }  
    }
    }
   printf("\n");  
}  



































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