实现

邻接矩阵表示图

typedef struct GNode *PrtToGNode;
struct GNode {
    int Nv;  // 顶点数
    int Ne; // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum]; // 存顶点的数据
}
typedef PrtToGNode MGraph;

初始化

初始化一个由 VertexNum 个顶点但没有边的图

typedef int Vertex; // 用顶点下标表示顶点
MGraph CreateGraph( int VertexNum )
{
    Vertex V,M; // 顶点类型
    MGraph Graph;
    Graph = (Mgraph)malloc(sizeof(struct Gnode)); // 矩阵空间
    Graph->Nv = VertexNum; // 图的顶点个数
    Graph->Ne = ; // 无边图
    for (V = 0; V < Graph->Nv; V++) {  // 注意：这里默认顶点编号从0开始，到（Graph->Nv - 1）
        for (W = 0; W < Graph->Nv; W++) {
            Graph->G[V][W] = 0; // 或 INFINITY 
        }
    }
    return Graph;
}

向 MGraph 中插入边

typedef struct ENode *ProToENode;
struct ENode {
    Vertex V1, V2; // 有向边 <V1, V2>
    WeightType Weight; // 权重
};
typedef ProToENode Edge;
void InsertEdge( MGraph Graph, Edge E ){ // 将相应的权重赋给邻接矩阵
    Graph->G[E->V1][E->V2] = E->Weight; // 插入边 <V1, V2>
    Graph->G[E->V2][E->V1] = E->Weight; // 若是无向图，还要插入边 <V2, V1>
}

完整建立一个 MGraph

邻接表表示图