图：存储（邻接表法）
本帖最后由 Julia999 于 2019-8-5 09:27 编辑邻接表法是啥?emm,好吧，我应该是离散课划水了吧，但是离散课有讲嘛？{:10_277:}
为啥存储邻接矩阵法不就好了，干嘛还多搞一个，增加学习负担？？emmm，我也是这么觉得来着，但是邻接矩阵法存储稀疏图会有许多的空间浪费，于是,,,,就有了,,,邻接表法。。。。
邻接表法：为每一个定点建立一个单链表存放与他相邻的边
定点表：
采用顺序存储，每个数组元素存放顶点的数据和指向边表的头指针
边表（出边表）
采用链式存储，单链表中存放与一个顶点相邻的所有边，一个链表结点表示一条从该顶点到链表结点顶点的边
#define MaxVertexNum 100
//边表结点
typedef struct ArcNode{
int adjvex;//下一个结点的数据部分，也就是存下一个节点的数组下标
struct ArcNode *next;//指向下一个节点的指针部分
//InfoType info; //如果该边是有权值的，那么就加上权重部分
}ArcNode;
//顶点表
typedef struct VNode{
VertexType data;//存放数据
ArcNode *first;//指向一个属于他的边表的头指针
}VNode,AdjList;//声明一个数组类型的变量，顶点表
//邻接表
typedef struct{
AdjList vetices;//顶点表
int vexnum,arcnum;//顶点的数量，边的数量
}ALGraph;
若G为无向图，存储空间为O(|V|+2|E|)
若G为有向图，存储空间为O(|V|+|E|)
邻接表更加适用于稀疏图（因为只有顶点和边存在的情况下，才会生成空间去存储）
若G为无向图，则节点的度为该节点边表的长度
若G为有向图，则节点的初度为该节点边表的长度，计算入度则要遍历整个邻接表
邻接表是不唯一的，边表节点的顺序根据算法输入的不同可能不同
邻接矩阵 VS 邻接表
适用性： 稠密图 稀疏图
存储方式： 顺序存储 顺序存储+链式存储
判断两顶点是否有边：邻接矩阵比邻接表更适合
找出某顶点相邻的边：邻接表比邻接矩阵效率高
页:
[1]