假设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]采用邻接表存储,设计一个算法,输出图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中从顶点[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]到[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]的所有简单路径。

公告：维护QQ群：833371870，欢迎加入！
公告：维护QQ群：833371870，欢迎加入！
公告：维护QQ群：833371870，欢迎加入！

2022-06-09

假设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]采用邻接表存储,设计一个算法,输出图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中从顶点[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]到[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]的所有简单路径。

答案：

解: 采用基于深度优先匾伽算法,用[tex=2.0x1.214]60QgBHhP1bYchH9IcCF6sg==[/tex]数组存放找到的路径,[tex=0.571x1.0]TcM6B5Wrs5vy9dWrxRPSdg==[/tex]存放 [tex=2.0x1.214]60QgBHhP1bYchH9IcCF6sg==[/tex] 中顶点个 数(初始值为 [tex=0.5x1.0]Sc0he7miKB3YF9rgXf2dDw==[/tex])。将 [tex=4.714x1.357]nMOzfcroa0EoA7cd3nGh2g==[/tex]改为[tex=10.357x1.357]LskIBUDODCmke5V0UQFTbAE29t30O1SEZI/jtfTA2z6/pRRP1ybCNjNiK1oLPMoB[/tex], 先将 [tex=4.143x1.357]vh6+6z+GjMvKvdKh9FA0mtuIRqFNfuR2qXoBsAU/Zzc=[/tex] 置为[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex] (表示[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex] 已访问过),再从 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 顶点找到一个相邻顶点 [tex=0.786x0.786]RaAINhYHT2QFWQ2tWIaawg==[/tex], 如果 [tex=2.286x1.0]RzVbDPeXKhJD6mDZOLY+CA==[/tex]则将 [tex=0.786x0.786]RaAINhYHT2QFWQ2tWIaawg==[/tex]加人[tex=2.0x1.214]60QgBHhP1bYchH9IcCF6sg==[/tex] 中,输出 [tex=2.0x1.214]60QgBHhP1bYchH9IcCF6sg==[/tex]中所有顶点构成一条从 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 到 [tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex]的路径。如果 [tex=2.857x1.214]wkegqFNcKQc+6z3G15qUYw==[/tex]再判断 [tex=0.786x0.786]RaAINhYHT2QFWQ2tWIaawg==[/tex] 是否是 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 的一个未访问过的相邻顶点，如果未访问过,则将 [tex=0.786x0.786]RaAINhYHT2QFWQ2tWIaawg==[/tex]加入[tex=2.0x1.214]60QgBHhP1bYchH9IcCF6sg==[/tex] 删,再递归调用 [tex=12.071x1.357]NivhDsrxuVssNTGOChbb096CaUItw+SiGdsqKRUXxk4/HUGScJDGD35KYLEcREHFn4WYbjEgf7Yy3LXF5yii9A==[/tex] 表示从[tex=0.786x0.786]RaAINhYHT2QFWQ2tWIaawg==[/tex]开始继续找路程。对应的算法如下:int visited[ MAXV];    //全局变量void PathAl1 ( ALGraph * G,int u,int v,int path[ ] .int d){    ArcNode * p;    int j,w;    visited[ u] = 1;    p=G-> adjlist[ u].firstarc;    //p指向顶点u的第一条边的边头节点    while (pl= NUJI.T.)    {    w=p-> adjvex;    //w为u的邻接顶点        if ( w -- v)        {    path[d+1 ] = w;            for (j=0;j<= d+ 1;j++ )                printf(" 号 2d" , path[ j]);            printf( "\n" ) ;        }        else if (visited[ w] == o)    //若该顶点未标记访问,则递归访问之        {    path[ d + 1]= w;            PathAll (G, w, v , path, d + 1);        }        p-p-> nextarc;    //找u的下一个邻接顶点    }    visited[ u]= o ;    //恢复环境}设计如下主函数:void main( ){    int i,j;    int. u = o,v = 3, path[ MAXV];    MGraph g;    ALGraph * G;    int A[ MAXV][ 5] = { {0,1,0,1,1}.{1,0,1,1,o}，                                    { 0,1,0,1,1}, { 1,1,1,0,1},{1,0,1,1,0}};    g.n - 5;g.e- 0;    for ( i = o;i

举一反三

内容

0
设[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]、[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]和[tex=0.786x0.786]44SGfA2gQ2VZlXa1QKZD0Q==[/tex]是一个简单图的3个顶点，简单图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的簇系数[tex=2.286x1.357]LwqQzNryA4iLraKFpWGw+w==[/tex]是当[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]和[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]是邻居且[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]和[tex=0.786x0.786]44SGfA2gQ2VZlXa1QKZD0Q==[/tex]是邻居时，[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]和[tex=0.786x0.786]44SGfA2gQ2VZlXa1QKZD0Q==[/tex]是邻居的概率。设[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]、[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]和[tex=0.786x0.786]44SGfA2gQ2VZlXa1QKZD0Q==[/tex]是一个简单图的3个顶点，当这些顶点构成的所有3对顶点之间都有边相连时，这3个顶点构成一个三角形。求用图中三角形个数以及图中长度为2的通路的条数表示的[tex=2.286x1.357]LwqQzNryA4iLraKFpWGw+w==[/tex]的公式。
1
设[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]条边。
2
图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点，[tex=2.357x1.143]dkoxwOpyXKTw0HsOj3nnBg==[/tex]条边，证明[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中至少有一个顶点度数大于等于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]。
3
设[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]条边。
4
有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的有向图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]最多有条边。