若无向图中有n个顶点、e条边,则它的邻接表需多少个头结点,多少个表结点
时间: 2024-05-26 14:17:59 浏览: 27
对于一个无向图,每个顶点的邻接表中需要包含与其直接相邻的所有顶点。因此,我们需要n个头结点,每个头结点对应一个顶点,用于存储该顶点的相关信息,如顶点编号、入度、出度等等。同时,每个表结点用于记录与该顶点直接相邻的另一个顶点的信息,需要有e个这样的表结点,每个表结点包括两个字段:邻接点编号和指向下一个邻接点的指针。因此,总共需要n个头结点和e个表结点。
相关问题
10. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示, 则表头向量大小为 ( ),邻接表的边结点个数为( )。
对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示,表头向量大小为 n,邻接表的边结点个数为 2e。
无向图每条边都对应着两个顶点之间的关系,因此每个顶点在邻接表中都需要维护与它相邻的所有顶点,也就是说,表头向量需要有 n 个元素。而每条边都需要在邻接表中表示出来,由于每个顶点的度数等于与它相邻的边数,因此邻接表的边结点个数为 2e。
无向图和有向图的邻接表中表头结点和顶点的数量关系是什么
对于无向图和有向图的邻接表来说,顶点的数量与表头结点的数量是相同的。因为邻接表中的每个表头结点对应着一个顶点,而且每个顶点都至少对应一个表头结点。如果一个顶点的度数为0,那么该顶点的邻接表对应的表头结点为空,但是这种情况并不会影响表头结点的数量与顶点的数量相等。因此,无论是无向图还是有向图,邻接表中表头结点的数量都等于顶点的数量。