邻接表表示法(链式)
- 顶点： 按编号顺序将顶点数据存储在一维数组中。
- 关联同一顶点的边： 用线性链表存储。
- 如果有边\弧的信息，还可以在表结点中增加一项，
无向图的邻接表
-
例子：
-
特点：
- 邻接表不唯一
- 若无向图中有n个顶点、e条边，则其邻接表需要n个头结点和2e个表结点。适宜存储稀疏图。
- 无向图中顶点 v i v_i vi的度为第i个单链表中的结点数。
有向图的邻接表
-
例子：
-
邻接表特点：
- 顶点 v i v_i vi的出度为第i个单链表中的结点个数。
- 顶点 v i v_i vi的入度为整个单链表中邻接点域值是i-1的结点个数。
- 找出度易，找入度难
-
逆邻接表：
-
逆邻接表特点：
- 顶点 v i v_i vi的入度为第i个单链表中的结点个数。
- 顶点 v i v_i vi的出度为整个单链表中邻接点域值是i-1的结点个数。
- 找入度易，找出度难
-
当邻接表的存储结构形成后，图便唯一确定。
建立邻接表的算法
- 图的邻接存储表示
- 顶点的存储结构
相应的类型定义如下，
typedef struct VNode
{VerTexType data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];
- 弧(边)的结点结构
相应的类型定义如下，
#define MVNum 100 //最大顶点数
typedef struct ArcNode //边结点
{int adjvex; //该边所指向的顶点的位置struct ArcNode *nextarc; //指向下一条边的指针OtherInfo info; //和边相关的信息(权值等)
}ArcNode;
- 图的结构定义
typedef struct
{AdjList vertices; //存放各个顶点的数组int vexnum, arcnum; //图的当前顶点数和弧数
}ALGraph;
- 邻接表操作举例说明：
ALGraph G; //定义了邻接表表示的图G
G.vexnum = 5; G.arcnum = 5; //图G中包含5个顶点，5条边
G.vertices[1].data = 'b'; //图G中的第2个顶点是b
p = G.vertices[1].firstarc; //指针p指向顶点b的第一条边结点
p->adjvex = 4; //指针p所指边结点是到下标为4的结点的边
- 采用邻接表表示法创建无向网
-
算法思想：
1.输入总顶点数和总边数。
2.建立顶点表：依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。
3.创建邻接表：
依次输入每条边依附的两个顶点
确定两个顶点的序号i和j，建立边结点
将此边结点分别插入到 v i v_i vi和 v j v_j vj对应的两个边链表的头部 -
算法描述：
-
Status CreateUDG(ALGraph &G)
{cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数for (i = 0; i < G.vexnum; ++i) //输入各点，构造表头(顶点)节点表{cin >> G.vertices[i].data; //输入顶点值G.vertices[i].firstarc = NULL; //初始化表头结点的指针域}for (k = 0; k < G.arcnum; ++k) //输入各边，构造邻接表{cin >> v1 >> v2; //输入一条边依附的两个顶点i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = new ArcNode; //生成一个新的边结点*p1p1->adjvex = j; //邻接点序号为jp1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; //将新结点*p1插入顶点vi的边表头部(头插法)p2 = new ArcNode; //生成一个新的边结点*p2p2->adjvex = i; //邻接点序号为ip2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2; //将新结点*p2插入顶点vj的边表头部(头插法)}return OK;
}
邻接表表示法的优缺点
- 优点：
- 方便找任一顶点的所有“邻接点”
- 节约稀疏图的空间：需要N个头指针+2E个结点(每个结点至少2个域)
- 对无向图而言，方便计算任一顶点的度
- 缺点：
- 对有向图而言，只能计算“出度”，需要构造“逆邻接表”来方便计算“入度”。
邻接矩阵与邻接表表示法的关系
-
联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。
-
区别：
- 对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)。
- 邻接矩阵的空间复杂度为 O ( n 2 ) O(n^2) O(n2)，而邻接表的空间复杂度为 O ( n + e ) O(n+e) O(n+e)。
-
用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图。
