用邻接表表示图

 1 //用邻接表表示图
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4  
 5 #define DataType char
 6 #define MaxVertexNum 20
 7 #define Vertex int
 8 #define WeightType int
 9 typedef struct GNode *PtrToGNode;
10 struct  GNode
11 {
12     int Nv;            //顶点数
13     int Ne;            //边数
14     AdjList G;        //邻接表
15 };
16  
17 struct ENode{
18     Vertex v1, v2;
19     int weight;
20 };
21  
22 typedef struct ENode* Edge;
23  
24 typedef PtrToGNode LGraph;    //以邻接表方式存储的图类型
25  
26 typedef struct Vnode {
27     PtrToAdjVNode FirstEdge;
28     DataType Data; //存顶点的数据
29 }AdjList[MaxVertexNum];
30  
31 typedef struct AdjVNode *PtrToAdjVNode;
32 struct AdjVNode {
33     Vertex AdjV;            //邻接点下标
34     WeightType Weight;        //边的权重
35     PtrToAdjVNode Next;        
36 };
37  
38 //初始化一个有VertexNum个顶点但没有边的图
39  
40 LGraph CreateGraph(int VertexNum)
41 {
42     Vertex v;
43     LGraph Graph;
44     Graph = (LGraph)malloc(sizeof(struct GNode));
45     Graph->Nv = VertexNum;
46     Graph->Ne = 0;
47  
48     for (v = 0; v < Graph->Nv; v++)
49         Graph->G[v].FirstEdge = NULL;
50  
51     return Graph;
52 }
53  
54 void InsertEdged(LGraph Graph, Edge E)
55 {
56     PtrToAdjVNode NewNode;
57     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
58     NewNode->AdjV = E->v2;
59     NewNode->Weight = E->weight;
60  
61     //将v2插入v1的表头
62     NewNode->Next = Graph->G[E->v1].FirstEdge;
63     Graph->G[E->v1].FirstEdge = NewNode;
64  
65     //若是无向图，还要插入边<v2, v1>
66     //为v1建立新的邻接点
67     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
68     NewNode->AdjV = E->v1;
69     NewNode->Weight = E->weight;
70     //将v1插入v2的表头
71     NewNode->Next = Graph->G[E->v2].FirstEdge;
72     Graph->G[E->v2].FirstEdge = NewNode;
73 }