QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1517|回复: 0
打印 上一主题 下一主题

图的存储结构——邻接多重表(多重邻接表)的实现

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-4-26 15:26 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
      r- c* p7 b/ Y0 \" u
    图的存储结构——邻接多重表(多重邻接表)的实现
    / N+ V4 I2 j& y4 {( Q" e7.2 图的存储结构
    & Q0 |, L/ @" i3 C; z' E. T1 C
    & h# i2 Y; f) Q9 J. H$ u7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    2 h4 Q. t7 }! _! Y; t邻接多重表的类定义2 \9 ^; O7 u9 Y9 z. y8 W: p# n
    邻接多重表的顶点结点类模板
    ) [: b6 ~! e4 M; S: K. q7 G+ r5 h邻接多重表的边结点类模板4 F  z# L1 z# P0 `1 ?& t
    邻接多重表的类模板% G2 a5 l- p" d1 B# O! r! X
    邻接多重表与邻接表的对比* p6 n1 \: n4 L# _+ o
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    / V% {( A6 r! M* Y* ~# B6 Q+ D
    ; \. D3 i: ~$ W+ A在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。6 R7 L( d1 @6 n  D
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    ' D5 C, |- x/ [3 L' m! D
    & J# ^2 I, L" B" g邻接多重表的类定义
    0 L) f! S7 Q7 {' a' r5 [ 1.png " h- _; w: v/ {2 g" c
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:
    ( U" ^/ S# B7 I9 R9 Ldata域存储有关顶点的信息;# A' u4 M# B. M0 V& l  W4 t( k( J/ O
    firstarc域是链接指针,指向第一条依附于该顶点的边。
    $ K3 P$ Z+ j, k/ e1 M所有的顶点结点组成一个顺序表。


    + ^! P" D# P% \+ s
    - [7 J; w, x1 m, ctemplate <class ElemType ,class WeightType>- x) {) d6 g2 i/ l# e
    class MultiAdjListNetworkVex
    7 V% ^. M& H% d. c{$ @  X, D( W- h% m3 j
    public:
    / V) z) {, j; f; {- L& G        ElemType data;7 E! r; x6 n" _0 q6 d. H
            MultiAdjListNetworkArc<WeightType> *firstarc;
      N' p, X* s- s
    & D. i, F, z4 q: W# K: |% r+ D" z        MultiAdjListNetworkVex()0 `; s8 ^; p5 u
            {
    : A, h3 w  W% A% I: h- L8 a4 S                firstarc = NULL;# Q/ d) t( [5 S6 S7 w) R
            }
    : K0 k9 r! h2 v/ G( `" \" F* m$ F        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL), n% O: ?8 q' ^" o, F' ~% m3 m9 J
            {
    6 I9 r5 |: H5 H+ c                data = val;
    ) |7 f6 h6 `# {. u                firstarc = adj;* ~8 J! |1 s, o# A9 O
            }9 g( d  P$ X- x" X2 F* H+ j% J( V. x
    };
    3 P# d9 J2 a% Q) r
    , Q) Z4 G1 e- r1 Q邻接多重表的边结点类模板
    6 O- ]! Q( i4 j4 i: W1 w" ~; s; ~6 G1 g. L% B
    在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    7 f; c# @, K% F& c5 M$ F# M+ Atag是标记域,标记该边是否被处理或被搜索过;- D- @$ j' d) b4 }" W8 |6 K
    weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;9 \+ k1 w6 m- k. U6 q7 e9 Z9 J
    nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;
    3 v& h, S( |1 r3 B7 K8 I0 vnextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。- S& l8 C# c9 `- s! K

    ! \% M  o) F. | 2.png
    4 B, c7 [' A: j6 h. U* H& Vtemplate <class WeightType>
    6 }2 D' }  t& J8 R! `class MultiAdjListNetworkArc
    & ?9 d  _: Q" v) H( p{
    5 _% w( ~8 t* Y3 jpublic:
    9 \( g7 n& w' t. P: E2 m2 N! p2 G+ f5 c    int mark;                                       //标记该边是否被搜索或处理过
    ) F: x, @0 F- G        WeightType weight;                              //边的权重1 h" F8 Q' `/ ^" @% V
            int adjVex1;                                    //边的一个顶点/ a7 V5 j: D* {2 Q# Y6 w; F: c/ k
            MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-19 N. N' w) I- E9 |
            int adjVex2;0 p8 c* g9 x2 E3 e& h7 M
            MultiAdjListNetworkArc<WeightType>* nextarc2;
    1 _" c% R4 q7 L9 r4 d
    & j' ^' }5 C1 ?5 M. b1 |, K        MultiAdjListNetworkArc()
    * Z. H5 b$ q* {0 ~, D        {! c7 f8 G! g& T' m" @  }5 O( J4 \
                    adjVex1= -1;0 j3 g2 v- S+ {- l% l" n& J2 E
                    adjVex2= -1;- O6 E$ J6 j$ j
            }2 \2 c4 y! x2 c4 S: U" O- S8 S
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    4 I9 |  n/ d6 |2 n4 E% ]7 }        {
    1 ]* w. m) j9 u                adjVex1 = v1;       adjVex2 = v2;) u1 x+ P' i6 K2 V0 ?+ _9 o
                    weight = w;9 m( j: j& z8 _0 Z' W: e* N! T
                    nextarc1 = next1;   nextarc2=next2;
    7 j) I" s) C6 e  P( Z/ H# Q. A                mark = 0;           //0表示未被搜索,1表示被搜索过" Z, Y1 H% `6 O, H& T$ k' X( M
            }
    : s8 Z; P0 K: }" E3 b3 Z: F; L( Z: U" X" k, b  H. @5 |( T* d, h
    邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>7 m( j8 q0 c9 v
    class MultiAdjListNetwork) a* c  W/ U& M
    {$ F& U3 P$ X" z+ B; m
    protected:
    % z, h$ t8 J5 e1 d! D    int vexNum, vexMaxNum, arcNum;
    ) K' {- @" G  O2 w. h: |    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    4 z2 d+ w; Q5 ~# p$ g, e9 \    int* tag;
    # i' d# {, Q" |0 p' l    WeightType infinity;
      b2 N2 {# {+ r$ W% g- B% x8 T+ d; P6 h! x2 @; }* |
    public:
    / m; U" m0 s; G$ n    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    7 B& x2 w6 o+ H7 i0 b% x& }. Y/ i  E2 {4 M& ^
        MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);# H7 k. E5 A2 i( q
    $ y9 }" M  m! B
        void Clear();
    * M% v/ Y: b) x3 O    bool IsEmpty()
    ; J4 ~* f/ h: O' o* R, g& D$ O    {5 @/ Q: ~. |* h2 g
            return vexNum == 0;
    ; t0 @# t/ q0 j/ }    }
    ( w3 |0 X9 U9 [( z    int GetArcNum()const
    ) D' d1 Q; G- n, }. W. W; U    {
    2 O3 m9 I7 q% W; e5 W        return arcNum;' R  I) M( Y5 A9 o* t5 G! Q: d' t
        }+ ~1 H) X9 ~3 `* w, v: g
        int GetvexNum()const
    9 ?6 h! a$ A8 Q/ A/ x* ^    {& W6 |* E  N+ Q. V2 F3 R1 ], k# n8 H
            return vexNum;
      S  U7 X  _" Q/ _. G    }# e# j# Y$ e7 M2 l" H

    5 t; t+ P, R. v
    + `( V: k: S4 W: }    int FirstAdjVex(int v)const;4 P! }" j/ [* ^! y' M- j
        int NextAdjVex(int v1, int v2)const;! o# e  e& J. h7 J) L/ w+ m
        MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    0 U2 S# o5 Q, ^$ V8 i$ M) F1 A    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;4 h* E0 m8 ]4 \5 w# _( V
    0 Y" |7 |# H. J) ^
        void InsertVex(const ElemType& d);! K& o% q% B# e, _! O
        void InsertArc(int v1, int v2, WeightType w);+ V% B  |, Z" Y: O. }1 ?
    7 t# `& @% A5 P
        void DeleteVex(const ElemType& d);3 W4 d: i4 \! h& K. i
        void DeleteArc(int v1, int v2);
    ' O/ s$ c; C; C) J4 H2 c
    ) G0 H  |: r0 x+ C' |    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    % E; j! S& Y# u( m* ]' l    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);) h# E( J1 n  Y. N9 `7 J

    $ l& g! G) z/ Q0 b, k+ i    ///深度优先遍历
    3 O3 t; W1 S/ q; m3 P    void DFS1(const int v);
    $ a' [$ K3 w- g$ O$ h3 m    void DFS1Traverse();7 d9 z. a, b) |0 Z: ]! h0 ~. z
        void DFS2();+ h) z5 X# B, o/ P( J9 N* l# [

    $ A+ ?0 H% m( R* `* O    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    6 G4 d7 H  {. |' B4 j+ P4 A1 F    void DFS3();1 z4 r4 A9 l; z2 Q' |4 _5 A

    . [1 N1 m# K" t' x    void BFS();6 U. l$ E5 b' W8 E
        void Show();
    ) T7 i& p1 J: G) ]! |; z};
    % r: z9 v% F. J1 f8 C  [- F: d) m7 D1 R0 G8 P& ]& D6 V% m" k
    2.函数的实现& B7 W9 p3 [( ]5 d! O& @1 b6 {( Q
    研讨题,能够运行,但是代码不一定是最优的。
    : c% R0 I; L2 g3 X* w$ S4 `8 Z, x, l0 \1 x
    #include <stack>
    . R* ^" F8 j: @$ }9 X. g" E#include <queue>
    : P9 V4 o6 _6 Y3 c7 e3 s2 e
    / ^5 \# }+ ]8 v) M$ r% k/ q8 s) u5 Xtemplate <class ElemType,class WeightType>* D4 K$ H, f+ D3 a) P
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)7 l; `' P# t6 U  u1 f) k
    {
    1 j7 y0 G- ?" p# Q    if(vertexMaxNum < 0)
    0 j+ E! I& {' k7 T        throw Error("允许的顶点最大数目不能为负!");
    ) D3 _% O; F2 B- c    if (vertexMaxNum < vertexNum)
    ' G6 Y3 R* s  E4 ~        throw Error("顶点数目不能大于允许的顶点最大数目!");
      v+ \$ z7 v5 L    vexNum = vertexNum;# B7 Z- k7 T6 g9 D  k
        vexMaxNum = vertexMaxNum;
    . Y& \2 W. z" u8 |! n% ^4 j! v. {. n    arcNum = 0;# A) c9 J; v" g
        infinity = infinit;
    , u: ?( G- B. ^( X4 c! d( q: {    tag = new int[vexMaxNum];+ G1 y- `/ ]+ y9 o
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];% w0 i/ J! \% C$ K8 g- y
        for (int v = 0; v < vexNum; v++)0 R$ M& ]3 r$ c  b, i. w' m- e/ \
        {; G# k% o. o9 X, |# S& [7 ?
            tag[v] = 0;( b& P7 K* Q+ s5 T- K
            vexTable[v].data = es[v];! W% c5 x: k! }7 J3 o0 G) S+ N
            vexTable[v].firstarc = NULL;
    * P) G, v$ x9 y# h( }; r4 I( K5 X! k    }
    % y. p, y2 f; @4 U$ Z4 z5 f3 A. A}
    5 K  F0 S0 X- ~, _/ z7 Y* }template <class ElemType,class WeightType>
      S* n: C- g/ u1 V3 ~MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)9 y" H" F8 b2 u
    {$ K0 h& I! ]* j5 ^5 ?! M+ I
        if (vertexMaxNum < 0)
    2 i" ^- ~% t% G2 _        throw Error("允许的顶点最大数目不能为负!");8 h/ D! J# s7 i; x: R8 }
        vexNum = 0;! K' M! a* v4 _) T, T3 U
        vexMaxNum = vertexMaxNum;. Z. h2 u+ n) v/ ?2 B+ }
        arcNum = 0;6 ~  w4 J- `  I  Q, R8 H
        infinity = infinit;
    8 Y8 F. g7 k7 }0 I/ y5 C8 F    tag = new int[vexMaxNum];$ x# M1 K$ I5 x1 o7 I4 w
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];% R, @7 N; V8 _9 ~% |
    }
    0 z6 b. ?8 T7 C7 L' g) wtemplate<class ElemType, class WeightType>
    : E; O7 _' Q+ n0 R6 Cint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const( k6 Q# A/ Y0 G0 I. v! ?7 p
    {
    : k& @) V: e) h: q) y& T, Z    if (v < 0 || v >= vexNum)
    # D' A2 U& i2 e; _% \        throw Error("v不合法!");
    * f' _5 W8 C, Q. v( R    if (vexTable[v].firstarc == NULL)
    3 u) ]; j0 M5 z. t        return -1;
    " n' |( O5 K1 }% |4 ?( v    else8 j- q  `; `3 }: i3 W$ E% @
            return vexTable[v].firstarc->adjVex1;3 q4 [2 H* X: p5 a; j
    }
    5 @# W, d1 j: M, C& t0 Y
    6 }. h* j. f4 {* {. ltemplate<class ElemType, class WeightType>
    ) \. d& }6 m. ?1 f7 M) Wint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const* l: _0 x$ ]  ]3 G; r& i) N9 B
    {0 v- C! H7 F/ T: U& S
        MultiAdjListNetworkArc<WeightType>* p;
    1 _/ i, u& k% c7 G    if (v1 < 0 || v1 >= vexNum)
    ' o) o- G  }# o% A0 ?; Y% B        throw Error("v1不合法!");
    7 O+ ^; c. ~' T) o; a  j    if (v2 < 0 || v2 >= vexNum)) e: s7 b6 M) [. |' i7 f
            throw Error("v2不合法!");) w: P& P" \) l4 |6 U0 _
        if (v1 == v2)
    7 ~* s, v$ I$ O- U7 U* E1 @( t1 X        throw Error("v1不能等于v2!");$ ]' R0 Q. i- z0 k
        p = vexTable[v1].firstarc;
    . e2 y1 j! U/ Q8 ]    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)  R2 H* B( K, _" F3 o) I5 |
            p = p->nextarc;
    ( z8 k( w4 b5 m# r0 F; ?    if (p == NULL || p->nextarc == NULL)
    6 y- p# Q3 f: h        return -1;  //不存在下一个邻接点
    ) X* {; j5 j' j' }5 g2 }! _7 H    else if(p->adjVex1==v2)5 I% z, V# i2 W; U! t5 v! c
            return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    - s2 v4 T+ V+ @    else
    ' J* G6 j+ z" \+ ^: @& C. c        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    : g- y, p  o1 y% _7 O}
    4 u( k. R3 I9 o8 E% V) o$ rtemplate<class ElemType, class WeightType>
    % f1 |# t- K7 f0 M5 \' ]void MultiAdjListNetwork<ElemType, WeightType>::Clear(): S- e8 h2 i  |( J- U. m
    {
    / l/ Z" w3 t# j) N/ U    if (IsEmpty()) return;
    $ O+ w  y4 `, G# I9 B5 p    int n = vexNum;
    - p, w7 H5 O" z, E3 t    for (int u = 0; u < n ; u++)' o5 y& C" b2 a6 ~
            DeleteVex(vexTable[0].data);* ^+ ]; ?5 C9 Z1 }" x2 l
        return;- C) F/ O/ z: j7 D+ L
    }0 |: S: v$ I- [; U9 w" J
    template<class ElemType, class WeightType>
    ; G& X- F0 J) Q# C3 E1 \MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
    ; y" G9 E/ {, B: I{
    8 p8 ~. a( z2 N& U- \    Clear();
    # G! A3 q& ~! s6 F}
    4 E+ p2 z0 q( G4 r* a9 ~! ztemplate<class ElemType, class WeightType>5 d% q# n$ H; W5 \1 S
    MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    . v: D$ z$ s; w' w{
    1 l7 z  C5 t0 }4 J- s' U    vexMaxNum = copy.vexMaxNum;! ~  b$ c1 w( Y" D$ r; m8 O3 V
        vexNum = copy.vexNum;
    0 Q) W, t7 O9 S3 g3 u    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    & `0 u  Y0 {* ?; H0 X4 \    arcNum = 0;
    5 o9 ?# u1 Y3 k3 m" V) U    infinity = copy.infinity;
    ' S% B2 E& v1 c) w    tag = new int[vexMaxNum];
    1 }3 Q( N  B- t
    ( z% L( {$ E2 f4 J3 \1 H    for (int v = 0; v < vexNum; v++)
    5 L8 E$ |2 C/ y! [2 q, R5 ^( P5 U) ~    {
    & Q" I9 c; @# k$ [, H; o        tag[v] = 0;( o" R3 G/ L: L9 Y( f
            vexTable[v].data = copy.vexTable[v].data;
    ( a& v. ]3 O+ u& M: G3 y) w        vexTable[v].firstarc = NULL;
    . g# J/ @& ^5 e" l, M) w    }
    & A2 f' }$ ?" q; [5 ~    MultiAdjListNetworkArc<WeightType>* p;
    # Z, N. D- D3 P& h* d( |9 X
    2 C4 R( B3 M1 e! E    for (int u = 0; u < vexNum; u++)+ I9 X( L: L- {
        {: m6 y  L, Z/ w4 n' \
            p = copy.vexTable.firstarc;
    $ Y3 J$ W5 Y! t3 J: F1 k        while (p != NULL)
    2 Z9 A# s, B5 B8 O! T        {6 w, ]9 q( K0 j4 i6 M
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    0 f* k4 c) O1 y: y# O2 j  F            p=NextArc(u,p);
    9 X) d0 _0 j6 j8 d. N# n        }
    , m. H2 `' }" v4 V3 O# t    }
    # R1 }# m# |5 r$ c; i( {, m}" o0 d; ~3 T: W4 Y, d* A
    template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
    ) I6 I, r  N! U( E; K0 w! MMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)7 |4 m  Y% r; [0 j3 x' a
    {  k8 n, {( p. o0 c2 }4 ^8 Q) p+ X: W
        if (this == &copy) return *this;% ]# ~- D( C1 C% q& p/ z# w$ i$ O
        Clear();
    / R4 f& C( O/ I" y+ n    vexMaxNum = copy.vexMaxNum;9 y4 T. x# @' Y! V1 A( [8 y" D- d
        vexNum = copy.vexNum;! u( `2 T% b0 D- _8 k/ C3 }$ d$ b
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    & E' [  a8 H4 h  Z    arcNum = 0;
      M4 v: _! L: D0 D2 {3 g    infinity = copy.infinity;
    ' m2 p% P" [0 |- g& X1 A4 r    tag = new int[vexMaxNum];. m+ J1 Q/ ]4 d! V/ d2 e

    * ^1 R$ W8 K! N  g    for (int v = 0; v < vexNum; v++)
    / ~) Q( Z6 X! n    {' N3 ?9 N: p$ Y! m0 D' S
            tag[v] = 0;2 m/ L% f; G; f  B" y" p
            vexTable[v].data = copy.vexTable[v].data;8 w, [3 }8 g1 Y5 e2 f/ ]3 v" x
            vexTable[v].firstarc = NULL;
    4 F# L$ x7 {2 \. q  @    }  `% }# v. v) |( ~  `4 i9 Q
        MultiAdjListNetworkArc<WeightType>* p;
    ' c* ?2 ]* J* w- u4 Y4 {5 |- T1 U. g" z) m6 `! \0 F
        for (int u = 0; u < vexNum; u++)# S2 Y8 k4 E3 v8 a8 v0 l  ~3 D
        {3 G, V& j3 W9 c; n' U
            p = copy.vexTable.firstarc;
    $ U' x; G" n9 T* r- S        while (p != NULL)
    * ~& O, ]% f. M4 o1 E        {/ n  m' T, J% d0 H  Z7 e' A
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    $ r) }: v0 q; Y( ^            p=NextArc(u,p);
    . F* _2 x6 K( g& r# g0 S& ~        }
    & C5 i( V3 P! }& O. L) U) l    }4 p( Z( k6 F6 a+ v
        return *this;
    & ~2 [$ @8 P5 J* Q6 d8 F& E2 N}
    + N+ p- {0 G3 m2 F) Jtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    / ]- ?- x, @- a: AMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    + K. I1 ?2 {/ ?- N{1 P7 L, d! g6 F/ d9 H+ j
        if(p==NULL) return NULL;
    / U* J# }8 g4 h3 J1 y  s( M& V    if(p->adjVex1==v1)
    + _2 I4 G( S  t- i        return p->nextarc1;
    8 i% ]& w3 H' O7 N6 L" q    else
    9 m) T; R* K; V3 W$ D        return p->nextarc2;# V, I6 q. r4 H: q: a5 s
    }
    ! z+ k; w  J# `& N* r6 atemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    8 t( O+ M2 b4 k" JMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    ' f# l. b$ |, C) i. [( `" ^{9 M+ C* G! @" l/ o3 p
        if(p==NULL)return NULL;0 T0 s: L! ?: |: v5 W- @8 P
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;  b: k, m, b3 D. y# `2 n, k% {- I
        if(q==p), d7 Q- S- x3 r5 D$ P
            return NULL;5 e5 w) z1 M) B
        while(q)+ l0 u, {3 l$ s' Q+ _
        {) M1 S3 q$ x1 k' r. Z6 u
            if(q->nextarc1==p ||q->nextarc2==p)- G& o6 \% I$ T! t
                break;
    5 ]: U4 `: C; I% s        q=NextArc(v1,q);2 x0 J8 X% D0 ?3 _3 V& W' T
        }
    # [; t, C# g* L9 ?8 R3 a    return q;
    ) ~8 s# {! E* S% x' _, N5 r2 \+ n' ?}
    6 x' l5 o0 F9 Y3 j  p$ atemplate<class ElemType, class WeightType>7 V5 e' g5 }4 v; I, a  @+ W* \6 L
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
    ! C7 q, J3 s3 [& |: `  i{* R  E1 `! i7 h0 p* h+ t$ g
        if (vexNum == vexMaxNum)
    % R3 P7 V* ^1 i9 k5 Z' C! \. L        throw Error("图的顶点数不能超过允许的最大数!");
    ; |  d( q) |* e  J$ E* q9 D    vexTable[vexNum].data = d;! t% x6 _/ x, X1 S) L5 w- O
        vexTable[vexNum].firstarc = NULL;$ _* Q4 H* W) }$ H6 ~
        tag[vexNum] = 0;
    2 {, s5 k0 B3 t/ I    vexNum++;+ i/ u1 h9 \  d" `/ ]: V, _
    }  {$ U+ H* ^+ k8 O2 f1 o/ F
    template<class ElemType, class WeightType>2 l  x$ r5 B4 |9 U5 a
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w); Q+ M+ h3 I$ N/ l. ]4 D
    {# b2 {* M0 U- L3 d/ N
        MultiAdjListNetworkArc<WeightType>* p,*q;8 Z! Q8 F* Z' ]- U$ D4 ]
        if (v1 < 0 || v1 >= vexNum)
    0 T4 `' _* [3 B5 T        throw Error("v1不合法!");5 n- k) \3 v+ ]) e0 I0 x3 P8 h
        if (v2 < 0 || v2 >= vexNum)+ I; |' x. X2 h
            throw Error("v2不合法!");9 z# X' K$ x( ?; r$ n! t& H
        if (v1 == v2)1 h9 _; E6 g3 R) K' a1 W! J
            throw Error("v1不能等于v2!");
    " W2 C% U8 c" K6 n6 v    if (w == infinity)
    3 u% O2 u( o% ?/ e$ C+ _        throw Error("w不能为无穷大!");8 g0 w& P4 K( `1 F, l- {8 t
    # Z3 U. v& f0 @9 o! Z8 n: O( p

    - _) [0 Y  ?# c% |    p = vexTable[v1].firstarc;
    6 W$ T3 S6 Y' y9 f    while(p); n0 }# a  w  ]& d
        {0 Y1 D4 h7 o3 B& e- e6 p. N
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
    9 W+ A. ^. Y; Y2 r9 V! R        {
    8 }  L/ t$ f* {2 T7 O            if(p->weight!=w)/ z6 j0 `0 G5 C/ B
                    p->weight=w;
    , c" a' W' I! `+ x* {: \& i            return;9 F( `0 v! q+ d( F
            }: b& @1 q5 d: V0 F4 q1 \- _

    2 C3 D/ F) T# Z! J& `( b+ ]        p=NextArc(v1,p);
    " C( g; C* @& C' E* e    }
    9 [$ X$ w( |  J3 Z9 w4 F, D) }    p = vexTable[v1].firstarc;, |8 U$ x6 o& _. s7 c% p! a
        q = vexTable[v2].firstarc;! s1 D" J; a1 ]8 p& i
        vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法8 B: S2 H* T% S" \) ]
        vexTable[v2].firstarc =vexTable[v1].firstarc;. S+ y/ y7 c  T' A3 M! c: P* s* y
        arcNum++;
    0 |5 @$ x0 {8 t9 Z, `: ^) h, ~}  K1 o) u  D  _/ J

    ; n  S, @7 {2 q$ j1 A0 _* mtemplate<class ElemType, class WeightType>
    % v; ?( E& P9 p; t3 g  zvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)6 b  c- m$ x  j' @) t
    {
    , @8 I$ w1 `. C2 F5 ]7 s
    2 d2 z9 y! i* }3 x" B& Y7 O( T    MultiAdjListNetworkArc<WeightType>* p, * q,*r;; ]' {5 p3 G& X/ @
        if (v1 < 0 || v1 >= vexNum)8 s  w' {* t; U, {5 s" H. t& P
            throw Error("v1不合法!");0 {: S, V1 \; \8 z5 j* t* [8 m) ^4 f
        if (v2 < 0 || v2 >= vexNum)
    : \$ k& e' j" _$ L        throw Error("v2不合法!");  {* E. l* `) r" E* t8 q
        if (v1 == v2)1 X" w" c: Q& X( N4 v
            throw Error("v1不能等于v2!");  F" D3 K8 s! f8 R
    3 e9 l6 ]* f: o( A0 o( D7 h
        p = vexTable[v1].firstarc;
    . j9 G  Y; K& H! {7 m' ?    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)- d2 _* J$ |- E" X* z& \3 z
        {  o; Z3 U; ]) ?! }' O) O7 a
            q = p;
    3 w. q. P. T1 \5 D5 I        p = NextArc(v1,p);
      G& W+ Q0 ~7 i    }//找到要删除的边结点p及其前一结点q
    ' A) f7 v4 o0 b  }1 s) P! y+ n- N4 E. n
        if (p != NULL)//找到v1-v2的边
    ) g1 [& }3 W9 s" ^" K2 F/ a    {
    7 T& g& p9 w. k1 P& X4 \3 _* y        r=LastArc(v2,p);
    * b) ~/ Q4 o  b0 U9 @& F4 L        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    $ b: Z+ N8 C2 {5 z1 ^4 \! Y            if(p->adjVex2==v2)
    " ]* c: j0 z, `6 V- i4 F                vexTable[v1].firstarc = p->nextarc1;
    3 y" S) |% G$ C% a" x            else vexTable[v1].firstarc=p->nextarc2;6 k! V/ J- h8 u4 _. ^7 H8 u) j/ ]( Z- L
            else//不是第一条边$ V9 Q4 S; @, a, e9 b
            {& V2 P' c$ `$ L1 H, s8 N( V
                if(q->adjVex1==v1)- _9 [. a3 b0 e) `6 M
                    q->nextarc1 = NextArc(v1,p);  @" C0 A( e/ \& R0 H  l/ |- r# B
                else
    " s& Z, P6 D$ R- _# b& w* Z                q->nextarc2=NextArc(v1,p);
    7 J7 V2 U; Y9 l" a7 [  }- `; T, ]2 v6 ~% W+ O* N
            }
    ! M* ^: S7 b) N- }        if(r==NULL)
    " W8 B, i8 ~" N* R            if(p->adjVex2==v2)1 x7 L2 w# Z6 K* {4 A7 u6 N/ h
                    vexTable[v2].firstarc = p->nextarc2;
    # {* z8 t; i8 P/ D5 z  `9 s; h- G            else vexTable[v2].firstarc=p->nextarc1;
    ! J) P7 r% \9 a" Z        else
    , X  {( o! O8 Z/ x& L$ [        {: z" K7 ~5 Q; ~4 X; X4 u" v
                if(r->adjVex2==v2): J  G' F' a" f: t0 Y
                    r->nextarc2 = NextArc(v2,p);4 M* W- Y- W$ ?$ L
                else
    & e# p. |9 [& c7 y. h6 h5 S                r->nextarc1=NextArc(v2,p);
    4 `/ E6 l" y% F) U' N; y1 ]        }0 h4 c( U  C2 N  L
            delete p;5 a! F4 E7 m" }' x
            arcNum--;
    . p9 Q; L* u1 a$ L5 a9 T' U* n! r    }. [+ N# }# a4 |3 B3 P" Z

    0 S% k( H2 U" }8 N: r: `  X2 ^}
    4 F" h& V5 g" C7 z- j: Etemplate<class ElemType, class WeightType> void1 ^5 L$ o7 m+ `- H( u5 B* x. B6 X; [
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)* T" O( [5 A- |! A9 `7 z) ^0 L
    {
    & n8 G8 L( R. M    int v;' U4 z& v  B. M, Y; ^
        MultiAdjListNetworkArc<WeightType>* p;
    ; \# i' _" ]! ?. \& l    for (v = 0; v < vexNum; v++)//找到d对应顶点
    5 Z# }* j, U1 D: |7 h) _( Q  m        if (vexTable[v].data == d)
    8 l0 p2 a# J9 k& E9 i) y: F            break;/ |& j5 h' B  ^7 E1 z
        if(v==vexNum)
    * Z$ m( S' k& M. P! C        throw Error("图中不存在要删除的顶点!");- F- E/ L/ H% g1 l+ v

    " e; c1 s5 u9 W3 v/ U1 V/ O    for (int u = 0; u < vexNum; u++)//删除与d相连的边
    , H" l0 H* ?) P& D" ^$ h4 W        if (u != v)1 N0 K1 L' [2 D# ~2 V/ Q6 _
            {
    4 P$ P( {" A; k8 ~! s- D9 O            DeleteArc(u, v);3 i% D: w: L' k, F
            }% I' f+ X, x- D* H: d( H; j
        vexTable[v].firstarc=NULL;
    , c! z" H* k9 l0 N0 ^; u# A" k2 ^4 O: ~# S( @5 J, F
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置  W" f7 F# N- F4 N
        vexTable[v].data = vexTable[vexNum].data;# o( ~0 W4 y' y# F. t" [
        vexTable[v].firstarc = vexTable[vexNum].firstarc;
    0 W1 U* A3 a' v( K% q! q    vexTable[vexNum].firstarc = NULL;
    0 }/ r+ z- q' ~    tag[v] = tag[vexNum];5 s* @6 }  P# J/ e) T5 p
        //原来与最后一个顶点相连的边改为与v相连
    # ?$ @5 t% B2 M2 s) A' N    for (int u = 0; u < vexNum; u++)
    + T4 K9 a, e3 t; @) J7 U; Y    {6 w- |1 i" H" L* ?& a' S
            if (u != v)4 F' T( W' Z! V
            {5 M! v( X! b1 X. X
                p = vexTable.firstarc;
    4 B9 N& C4 g5 R0 z; Q0 k            while (p)
    & [. ?$ t; I2 _; a! D/ q3 v3 Q            {2 H2 X1 Y7 ]0 O; M9 y. y" {4 j
                    if (p->adjVex1==vexNum)
    # N6 f0 A5 i4 ~+ Y4 [2 U                    p->adjVex1= v;
    3 m+ ?/ |- s$ D8 z1 E! F                else if(p->adjVex2==vexNum)5 X7 I6 d) v! N5 W2 x9 p* q1 A
                        p->adjVex2=v;
    + t% d& n1 w, f- z% Y& g& G                p = NextArc(u,p);
    ; G6 ^% v1 }6 h( w. e            }
    % r9 m. G( s6 X. f( ?: x/ i        }1 d/ z2 j# p" {. ^1 C# w
        }
    9 H" x, c  H2 E- _3 y) B8 }/ v}2 M6 D1 z0 I( P: K& G) Q
    ///深度优先遍历
    % N9 H* {! b9 S( o- O# O* S! {8 _6 Dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)+ ^. A8 w; N6 |: W* j! ?& o
    {  ~4 m) m$ y% u! S
        tag[v]=1;
    1 X% R& G  P1 J6 w    cout<<setw(3)<<vexTable[v].data;+ X& C* {$ y( v! s7 c5 W$ s( s; c
        MultiAdjListNetworkArc<WeightType> *p;( s6 B! p2 l5 {+ t
        p=vexTable[v].firstarc;
    + z: _7 u0 E* K8 L9 t    while(p)
    2 `: q: F  ^% m  ]; X+ e4 t: R( D    {% Y1 g; \5 T2 b3 o
            if(tag[p->adjVex1]==0)
    # g& C/ H, H& b6 y            DFS1(p->adjVex1);
    & S% r" k# {; v" M8 o# i        else if(tag[p->adjVex2]==0)
    9 u1 X# `; O6 b* h" a# a3 e0 m            DFS1(p->adjVex2);
    , K& A* M. \$ D5 n' Y        p=NextArc(v,p);3 I9 A2 d) ~# \8 [5 N. c1 l& H0 M! r) k: x
        }2 P" P& Q# ~* \$ `5 N3 G. P4 f
    }$ {9 T7 n% P7 a2 p" Q0 f/ \: S
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
    ; t; ?7 @1 q" i{
      A+ s2 z$ ]! V    for(int i=0; i<vexNum; i++)
    , @7 k. |9 R9 r0 H4 g; c        tag=0;
    + y: H( m* c8 J5 o) b4 D( R4 b    for(int v=0; v<vexNum; v++)
    ; F( o) x2 P+ H# E  n' i    {: U5 A" A' m- |6 Q
            if(tag[v]==0)! ~$ Q% T1 W3 ^( C# m. [
                DFS1(v);
    # W& ^) [+ |% Q    }
    . _- I+ [0 \2 r4 n) Q" F1 m! n}
    5 ^4 a2 c6 f  stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()0 t% S0 ^: r3 I/ R& {% `& j
    {  r7 ^8 H9 ^4 i3 k
        stack<int> s;9 T- Z9 y) e( }, \6 ?
        int tmp;
    , B2 |$ S9 ^, C) D9 G    MultiAdjListNetworkArc<WeightType> *p,*q;
    0 m: U/ u# {5 ?% ~    for(int i=0; i<vexNum; i++)7 U: A1 O* o2 V- i' q
            tag=0;1 ^9 v$ k0 }3 r2 r) i0 n% @
        for(int i=0; i<vexNum; i++)  i* z+ z+ ]7 n
        {
    # z6 D1 p# U! W* I6 [        tmp=i;( p: D0 b' s7 K! ]2 ^4 `1 A
            while(tag[tmp]==0||!s.empty())
    + Z0 S* y! P7 A5 e8 a6 V8 H; ?1 I# N        {9 O0 b3 J3 ^6 R
                p=vexTable[tmp].firstarc;
    / V- T- Z) x2 G" O            while(tag[tmp]==0)
    . l: N+ O6 W- I            {
    6 w4 f  l6 ]0 x+ E                s.push(tmp);2 V* ]- y0 {5 e$ J
                    cout<<setw(3)<<vexTable[tmp].data;
    ' x! ?& V5 a6 [5 j+ X& D" W                tag[tmp]=1;, W$ _: u+ N/ H% o1 q
                    p=vexTable[tmp].firstarc;
    : x! ]( a% K: Q  m1 X& A* L) q                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
    + b) h0 g- v, Y. ^7 w( a: k                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);4 z; \) `! U4 l7 a& L' q9 ]
                    //cout<<" 1st     tmp="<<tmp<<endl;9 ?6 v0 a2 H, M+ r& ]+ I# X7 s3 v
                }( a4 z& ~& W$ L( O/ n% E
                if(!s.empty())
    " F: |$ \( P: W  b6 s, Y' o            {
    ' O: m* Y  q3 G7 V# z                tmp=s.top();
    : u. e9 I; B3 F                s.pop();: f. u4 \6 z5 p- V8 Z
                    q=vexTable[tmp].firstarc;
    " J2 O( U$ m0 n  b2 O1 n3 S  z                int t=tmp;- K% S: {) w, w! k) `
                    while(q&&tag[tmp]!=0)
    * K* D4 ?0 [- f6 F' P1 A8 Q6 F                {8 S- |9 Q1 S) [# r5 p7 u1 \& Z
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);5 C; Q( v# [6 s6 \8 c- }/ t
                        //cout<<" 2nd     tmp="<<tmp<<endl;* H. M) }  V5 X: P5 I
                        q=NextArc(t,q);3 f6 j( O+ i9 r
                    }8 H3 T* B* S2 L/ g
                    if(tag[tmp]==0)
    ! A% C; @( k) C                    s.push(t);
    6 B' t* x& @2 Z1 U                ///1、对应上面连通分支只有1个点的情况
    * v, w( U. Q# h9 j; v- v                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈, Q& Y4 N5 c1 }: e! w3 s
                    ///tmp要么等于找到的第一个未访问节点,' l! e9 s2 m( A' @& r7 o8 }3 ~
                    ///要么等于与t相连最后一个点(已被访问过)9 j. A2 J$ z- y& V- N1 N
                    ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    6 Y( r, T' l# X" Z3 P* N            }
    3 Z- j6 m# J, S1 \3 R8 Y        }4 i! N( h9 ^+ i  Z- ?# e6 ~
        }
    & v- z! b/ ]2 N- q}
    3 Z2 |8 ]/ ^* @) s. ^. {; ?# U//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    / _+ b6 ^/ l1 M, |! z; g" s$ btemplate<class ElemType, class WeightType> int' b& i: q" G1 r$ q
    MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre). H; G9 D" N- j6 K
    {
    ! P% G3 l8 }6 L8 k    if(head==pre)
    ' q( i. B0 y' @, e, L1 @$ z6 L        return -1;
    1 v, M  q1 n. \
    ) m8 y6 w0 }" `4 ]& Z    MultiAdjListNetworkArc<WeightType> *p;' @& K. Z9 N4 I& z9 F
        p=vexTable[head].firstarc;4 d: D2 V# R# L0 i
        if(pre==-1&&p!=NULL)
    / K$ ]4 z! d+ J# T( Q; ~; D        return p->adjVex1==head?p->adjVex2:p->adjVex1;2 T8 Z/ L: I, \& V" x( E% `
        //pre!=-1&&p!=NULL8 {" k. v, y3 ^1 k0 h
        while(p!=NULL)0 O% C9 {, I0 a7 C0 O/ c
        {
    . h8 H. i- C1 z0 u4 ~- ?; ^, b3 Q/ c        if(p->adjVex1==head && p->adjVex2!=pre)
    # f' w; b0 g- t# L' X! c            p=p->nextarc1;
    ; K4 ?0 j/ u/ O" z% n        else if(p->adjVex2==head && p->adjVex1!=pre)
    " v  G, [$ l1 _. @8 y. H            p=p->nextarc2;6 D7 o; Q  F2 }
            else if(p->adjVex1==head && p->adjVex2==pre)' ^* F6 X- l, S, I% i# G
            {
      Z: v" K" C1 q4 E8 Y            p=p->nextarc1;
    + E+ o8 a) ?5 w3 J* H3 a' [            break;3 w* e$ ]2 J) I4 h
            }
    % `3 |# |( X0 e1 A1 l        else if(p->adjVex2==head && p->adjVex1==pre)
    9 @+ M0 g# H! X. z: n& g& B) P        {5 U; ~3 e; M4 d/ X: G# s8 h0 H4 _
                p=p->nextarc2;6 Q" P; X. s2 k; X1 z
                break;" ]6 r. I$ O5 T- r, e. K& b! _8 r
            }; v- K* N' o" ^8 o& t
        }: p0 q$ |3 H7 O8 q' r! V
        if(p!=NULL): l- I0 Q  T3 I
        {/ V" i! m! a9 Z; S
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
    3 I9 H& v& B# V; D+ R; ?* Q0 [0 L    }
    ) a% \$ B! o. m/ l    else2 W9 y, H. R. z5 ?4 r9 U- [
            return -1;6 y' A5 o4 o, [) y( b  J
    }
    # V3 a; P( ~& n: ]6 I# K% q! g5 m& Y
    1 M+ K6 M7 v2 f7 R. V. B, e* _
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()8 Y3 j. r2 n8 e
    {. @9 \' x. [' l. x! j# g, o# X
        stack<int> s;
    & j! i3 A! J% R% N    int p,cur,pre;2 C7 T2 [0 n* Q
        //MultiAdjListNetworkArc<WeightType> *p,*q;
    , @' E9 i& k1 h    for(int i=0; i<vexNum; i++) tag=0;//初始化
    8 z! {1 ~# I# P* E+ ~! Y) I
    6 V+ _  [2 u& N4 `6 ^    for(int i=0; i<vexNum; i++)# p- f8 H4 l6 K0 |
        {" }1 `  E# w$ R
            cur=i;pre=-1;" R8 q; @, J& s% [
            while(tag[cur]==0||!s.empty())6 `- X& k# E- T5 m
            {
    . ]: X# D; C3 O6 J; L1 Z            while(tag[cur]==0)0 \4 p/ F3 f: o3 o! z
                {5 c9 H# Q/ l8 N" p; Z
                    cout<<vexTable[cur].data<<"  ";; ], C. B: g. t+ K) ], n9 i/ \
                    s.push(cur);
    ( ~) ?- j/ e# {+ _9 G% _0 V                tag[cur]=1;5 k" P0 C" `6 x) \. G# Z. a
                   //初次访问,标记入栈% T" O8 q3 \' ~  L* x2 W" d

    0 ~1 r; R) k8 f/ p/ g8 a" Y9 U/ M$ j               p=GetAdjVex(cur,pre);//p是cur的连通顶点
    : Z. l" C8 u! L0 _" I/ F. e/ t               if(p==-1)
    7 I9 R+ Z" M' p0 C               {
    . W  w& Y5 ]6 ]7 G                   pre=cur;s.pop();$ e. o8 m) @/ H+ \/ v
                       break;4 ]: H. g8 m9 \. Q1 J5 c  [0 ]
                   }3 @. Q) G7 P4 ~6 i9 l/ ]1 I
                   else
    " |2 ~3 p# W# U$ L# C, T. f+ {               {4 B+ H. w+ \" l( |
                       pre=cur;) T7 ~" |: _4 {9 G  m4 ]% H, l
                       cur=p;5 o; F; C' z+ M1 s4 \4 G. j/ K
                   }  S$ r- G' j& D9 A! c2 _
    7 s% ?% Z2 h% Z" ^" X5 N8 J
                }
    5 i* T& [7 `6 n+ K5 B4 \4 v4 J% v            while(!s.empty())
    3 F+ p. n+ r5 d% v7 I/ J            {
    9 X5 `! ~; F, x* U, s/ s/ Y                cur=s.top();# ^( m& q' X8 w# C3 U
                    p=GetAdjVex(cur,pre);1 ^& X0 f6 G% ]1 n
                    if(tag[p]==0)5 y# S) E2 h6 Y5 g# x% V
                    {
    % ^- @5 g  u) A' G; f                    pre=cur;/ P% N  g7 u, {, X  v0 K
                        cur=p;  S  ]" r; v5 U$ {. @
                        break;5 L. H; J. c; p. c4 I8 d' f
                    }0 U( S& B5 }3 p# i
                    else
    # B9 {6 k4 i' P( Y" Y4 s3 i/ ~+ {                {
    - w% C+ _, |& X  ^! c$ v" ~                    pre=s.top();
    ( A1 d+ [: P! e- b+ H0 Y3 }! L                    s.pop();
    3 M$ Z$ z# _5 e8 v0 I. `8 o* U                }" _' z# l7 }6 S- L0 H5 b& }& w

    . a1 a1 M3 d& C3 t# M# f            }
    % u/ Q' D6 [/ `; O4 S; c% I: g0 T8 I
            }
    8 D. z/ {/ A+ l* g8 F    }
    4 }" e6 u! |( U! `1 A- z}% S, I+ l! b+ k& N$ u/ C3 ^
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
    4 b- p- ^) T: ~: ?{
    * i1 n6 M8 j! }. ~* H; V; o# v    for(int i=0; i<vexNum; i++): J0 ~! G+ y3 T& I+ H4 u5 i0 i
            tag=0;
    3 g* V3 K( g  g* `1 E0 Y; n    queue<int> q;
    + z9 S7 T; u2 J$ e    int tmp,t;, V9 Z/ V, ?; g  y5 V
        MultiAdjListNetworkArc<WeightType> *p;
    ( {/ v; Y3 c. l8 [    for(int i=0; i<vexNum; i++)
    $ @7 z  U/ Y* N+ h1 S    {% z7 Z2 Q6 J1 o$ m
            if(tag==0)6 K. S4 q2 b% u
            {1 f/ F2 d! p" @5 Q
                tag=1;3 L5 q# t1 m0 d# a4 h
                q.push(i);
      a5 Z4 u! {7 B0 d# Q+ W            cout<<setw(3)<<vexTable.data;& f( b7 A2 D# ?" u" H0 f
            }. o! n) z- v: k6 q
            while(!q.empty())
    ! y& Q2 Q& K0 F        {
    $ [  }, G, J0 t  U; V            tmp=q.front();
      u- E3 p! u( K* t            q.pop();
    5 d* M: w: E0 h1 ]8 w1 _            p=vexTable[tmp].firstarc;
    & u( G7 x' ^& t            while(p!=NULL)
    ' C, F! N3 ?: A3 B8 G( ?" B- g" k            {
    4 ^: U( V& O+ d  a/ O$ H+ L7 N7 l                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    / K  Y! R; O6 H9 ^7 S                if(tag[t]==0), B& g* D; @1 P
                    {! r7 _# ?5 f0 L/ F0 _; ~% [2 c
                        cout<<setw(3)<<vexTable[t].data;
    . m0 O; O/ ^  z9 W/ s* s                    tag[t]=1;
    2 k* u. d! M$ V                    q.push(t);
    9 E( k1 ]3 X& \/ R                }
    ) i  F0 V3 w8 _                p=NextArc(tmp,p);
    . h( o) p0 [- c4 Q, G            }
    ! x" b, {2 \+ `" L5 T) e/ {        }- l1 M6 J8 B5 M! x! S: }
        }
    ) P* F* P0 m; n, f  Y, }+ o}
    - y0 }3 N& q. jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()' a7 S8 G9 ~% V; B. t
    {
    0 {6 C, o8 _* e5 E! ^1 I+ W    MultiAdjListNetworkArc<WeightType> *p;
    6 Q3 ?) \1 A- O4 l6 T* Q    cout << "无向图有" << vexNum << "个点,分别为:";
    - |: K4 J# s! _0 t) y+ Z    for (int i = 0; i < vexNum; i++). P" w6 R% k# V  z* e8 W
            cout << vexTable.data << " ";/ v# G/ s  B/ c$ R/ {% u% e4 R1 x. W
        cout << endl;
    3 y5 D2 a/ L$ @2 x5 [- S7 ^# E    cout << "无向图有" << arcNum << "条边"<<endl;6 {8 P: V$ e/ S# s9 _1 E: O- L3 Z
        for (int i = 0; i < vexNum; i++), {& s% {5 C% a$ ^
        {4 o% U0 J* s0 f3 ^
            cout<<"和" << vexTable.data << "有关的边:";& ^' r' g7 P4 m/ S6 p. M: x" m
            p = vexTable.firstarc;
    4 _4 x" l2 B: x        while (p != NULL)
    6 }$ i: y+ e2 P$ i. ?5 D+ B, J        {, }! l1 f( f# V
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";1 _# S8 T3 d; ~5 ?; ^5 ?
                p=NextArc(i,p);
    + x( G( `$ `& n3 [7 H" \! ~        }
    # C9 m" R7 G6 n9 u6 m5 U+ x        cout << endl;& b; W: B# D. G9 V
        }
    1 I( J, ^; R4 u* E2 x. [+ A% V}
    , \( T2 `& n+ O6 A5 ?& \3 _6 D0 l, C) s3 K5 L7 O1 T

    % V8 R7 a  C$ k1 q/ I! O$ K+ r# K* n邻接多重表与邻接表的对比
    0 F' h. y5 X  p- e$ p" }  k0 A# R* Q1 M4 ^' v$ a+ U
    邻接表链接
    : F: `6 b, g! |* U% Q4 Y. Y* O在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。& v: T5 l" ~# L$ s+ P; `8 l0 l7 o+ Q
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。. O( E7 }2 i; Z* `
    为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。& f+ i' L: v9 X% L4 m, r" S
    ————————————————
    ) G* C$ a3 x* R4 L8 r+ U版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    ' n9 ~9 ]- b3 _7 g4 J1 v原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    ' j  k% j0 ^' P* H& O( B/ }  b6 T4 F
    9 c# ]6 @% m$ q" A8 `# i1 _
    4 M' ~1 I  C% }( _; N
    & x" z2 s2 E+ a! B8 e3 o( ]
    ' t( @6 M$ ]* a( O/ O————————————————" ]& b( `, L- G8 K9 V( y
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。7 D: U1 F2 L/ i. J8 }6 s- v; B
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    2 J/ c: Z% _  L* Z% l* g/ l' [, n+ n3 s3 s5 j: L4 y) p

    % @/ L6 s' W9 {( X
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-12-8 02:48 , Processed in 0.532584 second(s), 54 queries .

    回顶部