一个有n个顶点e条弧的有向图的逆邻接表中,有2e个表结点。

一个有n个顶点e条弧的有向图的逆邻接表中,有2e个表结点。


参考答案和解析
C 解析:与某个顶点、相关的所有弧是指所有以vi为尾和所有以vi为头的弧。n个顶点的有向图的邻接表含有n个出边表,每个顶点有且只有一个出边表,第i个出边表中的结点表示以顶点v1为尾的弧。每个出边表设置一个头结点,所有头结点构成一个向量,该向量称为顶点表。因为弧是有方向的,所以每一条弧只用一个边表结点来表示,e条弧则有p个结点,因此有,n个顶点和e条弧的有向图的邻接表含有n个顶点表结点和vi个边表结点。要删除以顶点vi为尾的弧只要删除第i个出边表中的结点就行了,但要删除以顶点vi为头的弧则需在其他出边表中查找顶点信息域为i的结点。为此,需对n个顶点表结点和e个边表结点进行通遍扫描,故其时间复杂度为O(n+e)。

相关考题:

在n个顶点和e条边的无向图的邻接表中,边结点的个数为()。 A.nB.n*eC.eD.2*e

●具有n个顶点e条边的无向图的邻接表,其边表结点总数为 (50) 。(50) A.nB.eC.2eD.n+e

n个顶点、e条边的无向图采用邻接表存储方法,该邻接表中共有()个边结点。 A、eB、2eC、nD、2n

对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为( )。 A、 2*nB、 2*eC、 nD、 e

一个有向图的邻接表和逆邻接表中结点的个数可能不等。() 此题为判断题(对,错)。

设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和边表接点的个数分别为()。A.n,eB.e,nC.2n,eD.n,2e

设无向图G有n个顶点m条边,则其邻接表中表结点数是()A、nB、2nC、mD、2m

对于具有n个顶点和e条边的无向图,在其对应的邻接链表中一共包含()个表结点。

对于具有n个顶点和e条边的有向图,在其对应的邻接链表中一共包含()个表结点。

设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为()A、n,eB、e,nC、2n,eD、n,2e

设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。A、2nB、nC、n/2D、n(n-1)

对于具有n个顶点和e条边的有向图和无向图,在它们对应的邻接表中,所含边结点的个数分别为()和()

设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有()条有向边。A、nB、n-1C、mD、m-1

一个有向图的邻接表和逆邻接表中的结点个数一定相等。

设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。A、n-1B、nC、n+1D、2n-1

在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链表的表头指针向量的大小至少为()。A、 nB、 2nC、 eD、 2e

在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链接的表头指针向量大小至少为()A、nB、2nC、eD、2e

对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别为()和()条。

填空题对于具有n个顶点和e条边的有向图,在其对应的邻接链表中一共包含()个表结点。

单选题设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。A2nBnCn/2Dn(n-1)

单选题设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为()An,eBe,nC2n,eDn,2e

单选题设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。An-1BnCn+1D2n-1

单选题设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有()条有向边。AnBn-1CmDm-1

填空题对于具有n个顶点和e条边的有向图和无向图,在它们对应的邻接表中,所含边结点的个数分别为()和()

判断题一个有向图的邻接表和逆邻接表中的结点个数一定相等。A对B错

单选题设无向图G有n个顶点m条边,则其邻接表中表结点数是()AnB2nCmD2m

填空题对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别为()和()条。

单选题在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链表的表头指针向量的大小至少为()。A nB 2nC eD 2e