图的存储一般用邻接矩阵或邻接表来存储
邻接矩阵
图的存储要考虑两方面的内容，①顶点的信息，②各个顶点之间的边的信息。顶点信息，我们用0 – n-1来表示各个顶点。边的信息用二维数组来表示。其中这个存储边信息的二维数组就是邻接矩阵。代码如下(C++代码)：
#define MaxVertexNum 100//设置顶点最大为100个 #define maxn 1000000; int MGraph[MaxVertexNum];//邻接矩阵，用来存储图 int n;//存储有多少个顶点 int m;//有几条边
下列是创建图的代码：
void CreateMGraph( int MGraph[] ){ cin>> n >> m;//输入图的顶点数和边数 for(int i = 0;i <G->e;i++){ for(int j = 0;j < G->e;j++){ G->edges[i][j] = maxn;//初始化为无穷大，表示此路不通； } } int a,b,c; for(int i = 0;i < G->e;i++){ cin>>a>>b>>c;//表示从a到b的距离是c MGraph[a][b] = c; MGraph[b][a] = c;//有这句话创建的是无向图，两边都可以走，若是有向图，则这句话可不写 } }
邻接表
邻接表的存储是一种顺序存储和链式存储相结合的存储方式，首先用一个数组来存储顶点信息，称为邻接表的表头节点他有两类元素，代码创建如下
typedef struct node{ int vdata; struct node *next; }VertexNode; VertexNode Map[MaxVertexNum];//这就是那个邻接表的顶点信息数组
第二个就是表结点，表节点有三类元素，分别是自身data,自己是哪号结点，还有后一个节点的地址，代码如下
typedef struct vnode{ int data;//表示路径长短 int Nnode;//表示当前结点是哪个顶点 struct vnode *next; }EdgeNode;//这两个的定义其实是一样的，只不过含义不一样
下面来创建邻接表
void CreateALGraph(){ EdgeNode *s; cin>>n>>m;//输入图的顶点数和边数 int a,b,c; for(int i = 0;i < n;i++){ cin>>a;//输入每个顶点 Map[i]->vdata = a; Map[i]->next = NULL; } for(int i = 0;i < m;i++){ cin>>a>>b>>c; s = (EdgeNode *)malloc(sizeof(EdgeNode)); s->Nnode = b; s->data = c; s->next = Map[a]->next; Map[a]->next = s; } }
下一章来说图的遍历
