用邻接表来表示图

typedef struct GNode *PtrToGNode; struct GNode{ int Nv;//顶点数 int Ne;//边数 AdjList G;//邻接表。AdjList要自己去定义 }; typedef PtrToGNode LGraph;//以邻接表存储的图类型 typedef struct VNode{ PtrToAdjVNode FirstEdge; DataType Data;//存顶点的数据 }AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{//这个链表里代表每一个边的这个结点的结构体 Vertex AdjV;//邻接点下标 WeightType Weight;//边权重 PtrToAdjVNode Next; }; typedef int Vertex;//用顶点下标表示顶点，为整型 LGraph CreateGraph(int VertexNum)//建立图的过程。一.初始化LGraph一个有VertexNum（整数）个顶点但没有边的图 { Vertex V,W;//定义为顶点类型，就是整型 ，虽都是整型，这里V,W是两个顶点，不是两个整数 LGraph Graph; //什么叫没有边，把这个邻接矩阵任意一对顶点V,W之间边定义为0 //或如果是有权图，把它初始化为INFINITY（很大的数代表无穷大），代表有权图没有边 Graph=(LGraph)malloc(sizeof(struct GNode)); Graph->Nv=VertexNum; Graph->Ne=0; //注意这里默认顶点编号从0开始，到(Graph->Nv-1) for(V=0;V<Graph->Nv;V++) Graph->G[V].FirstEdge=NULL; return Graph; } void InsertEdge(LGraph Graph,Edge E)//二.向LGraph中插入一条边。首先有条边。那边的类型如何定义 {//插入边过程是把顶点插入链表过程 PtrToAdjVNode NewNode; /*******************插入边<v1,v2>*********************/ /*为V2建立新的邻接点*/ NewNode=(PtrToAdjVNode)malloc(sieof(struct AdjVNode)); NewNode->AdjV=E->V2; NewNode->Weight=E->Weight; //将v2插入v1的表头 NewNode->Next=Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge=NewNode; /*******************若是无向图，还要插入边<v2,v1>*********************/ /*为V1建立新的邻接点*/ NewNode=(PtrToAdjVNode)malloc(sieof(struct AdjVNode)); NewNode->AdjV=E->V1; NewNode->Weight=E->Weight; //将v1插入v2的表头 NewNode->Next=Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge=NewNode; }