对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问题?①图中有多少条边?②任意两个顶点i和j是否有边相连?③任意一个顶点的度是多少?
①图中有多少条边?邻接矩阵表示:无向图:邻接矩阵中非零元个数的一半或上三角矩阵非零元的个数或下三角矩阵非零元的个数。有向图:邻接矩阵中非零元的个数。邻接表表示:无向图:每个顶点边表结点个数的和的一半。有向图:每个顶点边表结点个数的和。②任意两个顶点i和j是否有边相连?邻接矩阵表示:无向图:邻接矩阵中第i行第j列(或第j行第i列)元素是否非零。有向图:邻接矩阵中第i行第j列元素是否非零。邻接表表示:无向图:第i个(第j个)顶点的边表是否有值为j(i)的结点。有向图:第i个顶点的边表是否有值为j的结点。③任意一个顶点的度是多少?邻接矩阵表示:无向图:顶点vi的度为:第i行(或第i列)非零元的个数。有向图:顶点vi的度为:第i行非零元的个数与第i列非零元的个数的和(顶点vi的出度为:第i行非零元的个数,入度为:第i列非零元的个数)。邻接表表示:无向图:该顶点边表结点的个数。有向图:顶点vi的度为:该顶点边表结点的个数与其他顶点的边表中值为i的结点个数的和。
举一反三
- 简答题4.对n个顶点的无向图和有向图____,采用邻接矩阵和邻接表表示时,如何求解以下问题:____图中有多少条边?____任意两个顶点i和j是否有边相连?____任意一个顶点的度是多少?
- n个顶点的无向图，采用邻接表存储，回答下列问题？⑴图中有多少条边？⑵任意两个顶点i和j是否有边相连？⑶任意一个顶点的度是多少？
- 对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题:图中有 多少条边?任意两个顶点i和j之间是否有边相连?任意一个 顶点的度是多少?
- 对n个顶点的无向图,采用邻接表表示时,如何判别图中有多少条边和任意一个顶点的度是多少?
- 对[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]个顶点的无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex], 采用邻接矩阵表示，判别下列有关问题:(1) 图中有多少条边?(2) 任意两个顶点[tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]和[tex=0.429x1.214]rmIPPJrP+tFN2kAYPlU/4g==[/tex]是否有边相连?(3) 任意一个顶点的度是多少?
内容
- 0
对n个顶点和e条边的无向图，采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂性分别为（）和（）。
- 1
[color=#000000]对[/color][color=#000000][i]n[/i][/color][color=#000000]个顶点的有向图，采用邻接矩阵和邻接表表示时，如何判别下列问题： [/color][color=#000000]（[/color][color=#000000]1[/color][color=#000000]）图中有多少条边？ [/color][color=#000000]（[/color][color=#000000]2[/color][color=#000000]）任意两个顶点 [/color][color=#000000][i]i [/i][/color][color=#000000]和 [/color][color=#000000][i]j [/i][/color][color=#000000]是否有边相连？ [/color][color=#000000]（[/color][color=#000000]3[/color][color=#000000]）任意一个顶点的度是多少？[/color]
- 2
有n个顶点和e条边的有向图，在其对应的邻接表中，有____个边结点；有n个顶点和e条边的无向图，在其对应的邻接表中，有____个边结点
- 3
有n个顶点的无向连通图至少有多少条边？有n个顶点的有向连通图至少有多少条边？
- 4
有n个顶点，e条边的无向图的邻接表表示中有e个表结点。