假设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]采用邻接表存储,设计一个算法求无向图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的连通分量个数。

2022-05-30

假设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]采用邻接表存储,设计一个算法求无向图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的连通分量个数。

答案：

解: 采用遍历方式求无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的连通个数。若用深度优先遍历方法，先给 [tex=4.571x1.357]EcMBA8gIIeBuzkvHiC+5cg==[/tex]数组置初值 [tex=0.5x1.0]Sc0he7miKB3YF9rgXf2dDw==[/tex], 然后从 [tex=0.5x1.0]Sc0he7miKB3YF9rgXf2dDw==[/tex]顶点开始遍历该图，调用[tex=2.143x1.0]QEZzjIXlaSbrmTtpQCys1A==[/tex]的次数即为连通分量的数。对应的算法如下:int visited[ MAXV];    //全局变量int ConNum ( AGraph  G)    //判断无向图G的连通性{    int i, num = 0;    for ( i - 0;i n;i++)            visited[ i]= 0;    for ( i - o ; i n;i++)            if (visited[ i ] == o)            {    num++;                DFs(c,i) ;    //调用DFS算法            }            return nun;}

举一反三

内容

0
证明或否定断言：连通无向图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的任何边，是[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的某一棵生成树的弦。
1
设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[br][/br][tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通的并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。
2
设计一个函数利用周游图的方法输出一个无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中从顶点[tex=0.786x1.0]8w3MvouHWcBTSZ1PQdyQ+Q==[/tex]到[tex=0.786x1.071]nMxUPKIHz37baTvRKn5TQg==[/tex]的长度为[tex=0.5x0.786]BgHR5DBWke5rTEC5XEckiQ==[/tex]的简单路径，假设无向图采用邻接表存储结构。
3
证明：若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]和[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]是同构的有向图，则[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]和[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]的逆图也是同构的。
4
设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。