建立图

桃扇骨 2022-07-14 07:43 149阅读 0赞

学习MOOC上的

#include <stdio.h>
    #include <windows.h>
    #define MaxVertexNum 100 /* 最大顶点数设为100 */
    #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        int V1,V2;  //有向边<V1,V2>
        int Weight; //权重 
    };
    typedef PtrToENode Edge;
    
    /* 图结点的定义*/
    typedef struct GNode *ptrToGNode;
    
    struct GNode{
        int Nv; /* 顶点数 */
        int Ne; /* 边数 */
        int G[MaxVertexNum][MaxVertexNum];  /* 邻接矩阵*/
        char Data[MaxVertexNum];    /* 存顶点的数据*/
    };
    typedef ptrToGNode MGraph;  //以邻接矩阵存储的图类型
    MGraph CreateGraph( int count) 
    /*初始化一个有count个顶点但没有边的图*/
    {
        int V,W;
        MGraph Graph;
    
        Graph = (MGraph)malloc(sizeof(struct GNode));   //建立图
        Graph->Nv = count;
        Graph->Ne = 0;
        /*初始化邻接矩阵*/
        for(V=0; V<Graph->Nv; V++)
            for(W=0; W<Graph->Nv; W++)
                Graph->G[V][W] = INFINITY;
        return Graph;
    }
    
    void InsertEdge(MGraph Graph,Edge E)
    {
        Graph->G[E->V1][E->V2] = E->Weight;
        /* 若是无向图,还要插入边<v2,v1>*/
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        int V;
        int Nv,i;
    
        scanf("%d",&Nv);    //读入顶点个数
        Graph = CreateGraph(Nv);    //初始化有Nv个顶点但没有边的图
    
        scanf("%d",&(Graph->Ne));   //读入边数
        if(Graph->Ne != 0) {    //如果有边
            E = (Edge)malloc(sizeof(struct ENode)); //建立边结点
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵*/
            for(i=0; i<Graph->Ne; i++){
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
                InsertEdge( Graph, E);
            }
        }
    
        for(V=0; V<Graph->Nv; V++)
            scanf(" %c", &(Graph->Data[V]));
    
        return Graph;
    }