用邻接矩阵来表示图

typedef struct GNode *PtrToGNode; struct GNode{ int Nv;//顶点数 int Ne;//边数 WeightType G[MaxVertexNum][MaxVertexNum]; DataType Data[MaxVertexNum];//存顶点的数据 .有就写 }; typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型 typedef int Vertex;//用顶点下标表示顶点，为整型 MGraph CreateGraph(int VertexNum)//建立图的过程。一.初始化一个有VertexNum（整数）个顶点但没有边的图 { Vertex V,W;//定义为顶点类型，就是整型 ，虽都是整型，这里V,W是两个顶点，不是两个整数 MGraph Graph; Graph=(MGraph)malloc(sizeof(struct GNode)); Graph->Nv=VertexNum; Graph->Ne=0; //注意这里默认顶点编号从0开始，到(Graph->Nv-1) for(V=0;V<Graph->Nv;V++) for(W=0;W<Graph->Nv;W++) Graph->G[V][W]=0;//什么叫没有边，把这个邻接矩阵任意一对顶点V,W之间边定义为0 //或如果是有权图，把它初始化为INFINITY（很大的数代表无穷大），代表有权图没有边 return Graph; } typedef struct ENode *PtrToENode; //定义一个边结点，然后定义指向边结点Enode的指针 struct ENode{//每个结构都可以模仿刚才那个图结点的定义 //这结点里面包含什么，先看哪些东西决定一条边 Vertex V1,V2;//有向边<V1,V2> .一条边有两个顶点决定，一个出发点，一个终点 WeightType Weight;//定义权重，类型和前面邻接矩阵一致。对于有权图 }; typedef PtrToENode Edge;//把边定义为指向结点的指针 void InsertEdge(MGraph Graph,Edge E)//二.向MGraph中插入一条边。首先有条边。那边的类型如何定义 {//当插入一条边时，把这个指向结点的指针插进去 Graph->G[E->V1][E->V2]=E->Weight;//插入边<V1,V2>,就把Graph里面邻接矩阵对应的V1,V2D的这个元素赋值为这个边上权重 //如果是无向图，还有插入边<V1,V2>. Graph->G[E->V2][E->V1]=E->Weight; } MGraph BuildGraph()//完整地建立一个MGraph { MGraph Graph; Edge E; Vertex V; int Nv,i; scanf("%d",&Nv); Graph=CreateGraph(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; } int G[MAXN][MAXN],Nv,Ne; void BuildGraph()//不用之前那么麻烦的话 { int i,j,v1,v2,w; scanf("%d",&Nv); //CreateGraph for(i=0;i<Nv;i++) for(j=0;j<Nv;j++) G[i][j]=0;//或INFINITY scanf("%d",&Ne); for(i=0;i<Ne;i++){ scanf("%d %d %d",&v1,&v2,&w); //InsertEdge G[v1][v2]=w; G[v2][v1]=w; } }