网课答案LOGO
关注微信公众号《课帮忙》查题
关注微信公众号《课帮忙》查题
关注微信公众号《课帮忙》查题
关注微信公众号《课帮忙》查题
关注微信公众号《课帮忙》查题
关注微信公众号《课帮忙》查题
  • 2022-07-23
    设无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 采用邻接表表示,设计如下算法:[tex=1.214x1.286]b05N/7NYPh6to/3pWZjU5A==[/tex]求顶点[tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex] 到顶点 [tex=3.286x1.357]S6+9cM2MnfjfyP1v4Jw3cbtvLXLKVNp7jIo7zqtOUag=[/tex] 的最短路俠长度;[tex=1.786x1.286]vR0uZJ0+MnChig/sIe/LgQ==[/tex] 求顶点 [tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]到其余各顶点的最短路径。 要求输出路径上的所有顶点(提示: 利用 [tex=2.071x1.0]0CmjuZSGvi9L/QbNU/jOdQ==[/tex] 遍历的思想）。
    • 解: [tex=1.286x1.357]VAHhaW1te0xvoqDVN54/dg==[/tex] 利用广度优先遍历的思想,求[tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]和 [tex=0.429x1.214]rmIPPJrP+tFN2kAYPlU/4g==[/tex] 两顶点间的最短路径转化为求从[tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]到[tex=0.429x1.214]rmIPPJrP+tFN2kAYPlU/4g==[/tex] 的层 数,为此设计一个[tex=3.5x1.357]6J8eNF90VxvUfVhXlK8Lcufv6brH6qrXoPbViZQxMCA=[/tex]数组记录每个顶点的层次。对应的算法如下:int ShortPath1 ( ALGraph n G,int i,int j){    int qu[ MAXV] , leve1[ MAXV];    int front = 0,rear = 0,k,lev;    //lev保存从i到访间顶点的层数    ArcNodc r p;    visited[ i]= 1;    rear tt ;qu[ rear] = i; level[ rear] - 0;    //顶点i己访问,将其进队    while (frontl= rear)    //队列非空时循环    {    front = ( front + 1)% MAXV ;    k = qu[ front];    //出队顶点k    lev = level[ frant];    if (k==j)        return lev;    //找到顶点j,返回    p= G-> adjlist[ k ] .firstarc;    //取k的边表头指针    while (p!= NUITL)    //依次搜索邻接点    {    if ( visited[ p- > adjvex] == 0)    //若未访问过        {    visited[ p- > adjvex] = 1;            rear - ( rear + 1)  MAXV;            q[ rear ] = p->adjvex;    //访问过的邻接点进队            level[ rear] =- lev + 1;        }        p=p-> nextarc;    //找顶点k的下一邻接点        }    }    return - 1 ;    //如果未找到顶点j,返回―特殊值-1}(2)基本思想与(l)的算法相同,对应的算法如下:void ShortPath2 ( ALGraph * G, int i){    int qu[ HAXV], level[ MAXV];    int front = 0,rear = 0,k,lev;     //lev保存从i到访问顶点的层数    ArcHode  p;    visited[ i]= 1;    rear tt ; qu[ rear」 = i; level[ rear] = 0;    //顶点i已访问,将其进队    while (front!= rear)    //队非空则执行    {    front = ( front + 1) % MAXV;        k = qu[ front];    //出队        lev = level[ front];        if (k!= i)            printf(”顶点告d到顶点告d的最短距离是﹔失 dn",i,k,lev) ;        p = G- > adjlist[ k].firstarc;    //取k的边表头指针        while (p!= NULL)    //依次搜索邻接点        {    if ( visited[ p- > adjvex ] == o)    //若未访问过            {    visited[ p- > adjvex] = 1;                rear = (rear + 1) %MAXV;                qu[rear ] = p-> adjvex;    //访问过的邻接点进队                leve1[ rear] = lev + 1;            }            p=p- >nextarc;    //找顶点i的下一邻接点        }    }}设计如下主函数:void main(){    int i,j;    int u = 0,v= 3;    MGraph g;    ALGraph  G;    int A[ MAXV ][ 5J= {{0,1,0,1,1},{1,0,1,1,0},                                    { 0,1,0,1,1}.{1,1,1,0,1},{1,0,1,1,0} };    g.n = 5;g.e = 8;    for (i = o;i
    公众号
    广告招租

    举一反三

    内容

    • 0

      给定如图所示的带权无向图[tex=0.786x1.0]4swj+MXBfXw/BCBdKDogfg==[/tex]，根据该图的邻接表存储结构,从顶点 1 出发,调用[tex=2.143x1.0]QEZzjIXlaSbrmTtpQCys1A==[/tex]和[tex=2.071x1.0]0CmjuZSGvi9L/QbNU/jOdQ==[/tex]算法遍历该图,写出可能经过的顶点序列。[img=217x181]17a5cdf43148c0d.png[/img]

    • 1

      用邻接矩阵 [tex=7.214x1.357]kATQ3mu8sfNQW88IQFFrH2O/WOxLIk13fPf+/NE7uPUenl3EqD8SzR7jg7z+suIo[/tex] 存储有向图 [tex=1.071x1.214]eDoPgWfEuHliITfe0BvTnQ==[/tex] 其第 [tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]行的所有元索之和等于顶点[tex=0.357x1.0]+eJLelx8thmbkEj/Y0iCOw==[/tex]的[input=type:blank,size:4][/input]。

    • 2

      一辆飞机场的交通车载有 25 名乘客,途经 9 个站,每位乘客都等可能在 9 个站中任意一站下车,交通车只在有乘客下车时才停车,求下列各事件的概率:(1) 交通车在第 [tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex] 站停车;(2) 交通车在第 [tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]  站和第 [tex=0.429x1.214]rmIPPJrP+tFN2kAYPlU/4g==[/tex] 站至少有一站停车;(3) 交通车在第 [tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]  站和第 [tex=0.429x1.214]rmIPPJrP+tFN2kAYPlU/4g==[/tex] 站均停车;(4) 在第 [tex=0.357x1.0]O88k7AtkDgTC9kv/8dY0lg==[/tex]  站有 3 人下车.

    • 3

      6个顶点11条边的所有非同构的连通的简单非平面图有[tex=2.143x2.429]iP+B62/T05A6ZTM0eeaWiQ==[/tex]个，其中有[tex=2.143x2.429]ndZSw3zT0QTOVLVdoUto1Q==[/tex]个含子图[tex=1.786x1.286]J+vVZa2YaMpc6mJBbqVvWw==[/tex]，有[tex=2.143x2.429]lmhx48evnQMhi03NovPXig==[/tex]个含与[tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex]同胚的子图。供选择的答案[tex=3.071x1.214]3KinXFh3SXhZ7nIe1y9KEV6aadxhhJWeEy6Dij1iObdMUZkY6ZA5J2dVVjPSuhEf[/tex]：(1) 1 ;(2) 2 ;(3) 3 ; (4) 4 ;(5) 5 ;(6) 6 ; (7) 7 ; (8) 8 。

    • 4

      设 A 为无向图 G 的邻接矩阵 (为 0 / 1 矩阵), 其定义如下,[tex=2.714x1.214]fIyWVyfZ5cZqGHNFEImFpQ==[/tex][tex=6.071x1.357]cqRI70kLLxk+WJOym9k0/nQ+gDaUnL4SN0Nk+GcSb2A=[/tex] 当n>1证明[tex=1.214x1.0]qov0Q3uTe7nD+nhinDdBZQ==[/tex] 的元素 A[i][j] 表示顶点 i 到顶点 j的长度为 n 的路径数目.