![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
[主观题]
下面()算法可用于求无向图的所有连通分量。
下面()算法可用于求无向图的所有连通分量。
A、广度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径
查看答案
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
A、广度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径
若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。
(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥,将把图分割成两个连通分量。
(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法,判断连通图G中是否有桥,若有。输出这样的桥。
无向图G如图14.19所示
(1)求G的全部点割集和边割集,并指出其中的割点和桥(割边),
(2)求G的点连通度k(G)和边连通度λ(G).
图7中所示的无向图G中,实线边所表示的子图为G的一棵生成树T。
(1)求G对应T的所有基本回路。
(2)求G对应T的所有基本割集。
下面有关图的相关概念说法不正确的是【】
A.有e条边的无向图,在邻接表中有e个结点
B.有向图的邻接矩阵是对称的
C.任何无向图都存在生成树
D.不同的求最小生成树的方法最后得到的生成树的权值之和是相等的
A、无向完全图
B、无向连通图
C、无向强连通图
D、无向树图