概念
在当初学习《数据结构》总共学习了四种有关数据的逻辑结构：集合、线性、树、图。而图Graph是其中最为复杂的数据结构，因为在图形结构中，结点之间的关系是任意的，图中任意两个元素之间都有可能相关。
图的存储结构
关于图的存储结构总共有四种：数组表示法、邻接表、十字链表、邻接多重表。既然有这么多种表示法，肯定各有各的好处理。记住一句真理：既然存在，那么肯定有它存在的意义。呵呵......
1、数组表示法即邻接矩阵表示法
#define Type int #define MAX_VERTEX_NUM 20 typedef struct ArcCell{ Type adj;//对于无向图作为是否相邻的标志；对于有向图作为权值 char *info;//该弧相关信息的指针 }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; struct MGraph{ Type vertex[MAX_VERTEX_NUM]; AdjMatrix arcs; int verNum, arcNum; };
或者
#define Type int #define MAX_VERTEX_NUM 20 typedef struct VertexNode{ int Index;//点的编号默认为从1开始 char info; }; struct MGraph{ VertexNode vertex[MAX_VERTEX_NUM]; int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int n, e; };
2、邻接表
//边结点 typedef struct ArcNode{ int adjvex;//该弧指向的顶点的位置 ArcNode *nextarc;//下一条弧的指针 char* info;//该弧相关信息 }ArcNode; //顶点结点 typedef struct VerNode{ Type data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针 }VerNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int n, e;//图的当前顶点数和弧数 }ALGraph;
至于十字链表和邻接多重表就不再此介绍了，反正到现在我还没有遇到过用这两种存储结构去写算法！以后在讨论吧。
原文：http://www.cnblogs.com/tgycoder/p/5022468.html