学习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; }