对于图来说, 邻接矩阵是不错的一种图存储结构, 但是我们也发现, 对于边数相对顶点较少的图, 这种结构是存在对存储空间的极大浪费的因此我们考虑另外一种存储结构方式: 邻接表 (Adjacency List), 即数组与链表相结合的存储方法
邻接表的处理方法是这样的
1 图中顶点用一个一维数组存储, 另外, 对于顶点数组中, 每个数据元素还需要存储指向第一个邻接点的指针, 以便于查找该顶点的边信息
2 图中每个顶点 vi 的所有邻接点构成一个线性表, 由于邻接点的个数不定, 所以用单链表存储, 无向图称为顶点 vi 的边表, 有向图称为顶点 vi 作为弧尾的出边表
例如图 7-4-6 就是一个无向图的邻接表结构
若是有向图, 邻接表的结构是类似的, 如图 7-4-7, 以顶点作为弧尾来存储边表容易得到每个顶点的出度, 而以顶点为弧头的表容易得到顶点的入度, 即逆邻接表
对于带权值的网图, 可以在边表结点定义中再增加一个 weight 的数据域, 存储权值信息即可, 如图 7-4-8 所示
下面示例无向图的邻接表创建:(改编自大话数据结构)
- #include
- using namespace std;
- #define MAXVEX 100 /* 最大顶点数, 应由用户定义 & nbsp;*/
- typedef char VertexType; /* 顶点类型应由用户定义 & nbsp;*/
- typedef int EdgeType; /* 边上的权值类型应由用户定义 & nbsp;*/
- typedef struct EdgeNode/* 边表结点 & nbsp; */
- {
- int adjvex;/* 邻接点域, 存储该顶点对应的下标 & nbsp;*/
- EdgeType weight;/* 用于存储权值, 对于非网图可以不需要 & nbsp;*/
- struct EdgeNode *next; /* 链域, 指向下一个邻接点 & nbsp;*/
- } EdgeNode;
- typedef struct VextexNode/* 顶点表结点 & nbsp;*/
- {
- VertexType data;/* 顶点域, 存储顶点信息 & nbsp;*/
- EdgeNode *firstedge;/* 边表头指针 & nbsp;*/
- } VextexNode, AdjList[MAXVEX];
- typedef struct
- {
- AdjList adjList;
- int numNodes, numEdges; /* 图中当前顶点数和边数 & nbsp;*/
- } GraphAdjList;
- void CreateALGraph(GraphAdjList *Gp)
- {
- int i, j, k;
- EdgeNode *pe;
- cout << "输入顶点数和边数 (空格分隔):" << endl;
- cin >> Gp->numNodes >> Gp->numEdges;
- for (i = 0 ; i < Gp->numNodes; i++)
- {
- cout << "输入顶点信息:" << endl;
- cin >> Gp->adjList[i].data;
- Gp->adjList[i].firstedge = NULL;/* 将边表置为空表 & nbsp;*/
- }
- for (k = 0; k < Gp->numEdges; k++)/* 建立边表 & nbsp;*/
- {
- cout << "输入边 (vi,vj) 的顶点序号 i,j(空格分隔):" << endl;
- cin >> i >> j;
- pe = (EdgeNode *)malloc(sizeof(EdgeNode));
- pe->adjvex = j;/* 邻接序号为 j */
- /* 将 pe 的指针指向当前顶点上指向的结点 & nbsp;*/
- pe->next = Gp->adjList[i].firstedge;
- Gp->adjList[i].firstedge = pe;/* 将当前顶点的指针指向 pe */
- pe = (EdgeNode *)malloc(sizeof(EdgeNode));
- pe->adjvex = i;
- pe->next = Gp->adjList[j].firstedge;
- Gp->adjList[j].firstedge = pe;
- }
- }
- int main(void)
- {
- GraphAdjList GL;
- CreateALGraph(&GL);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2507262.html