QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1512|回复: 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

    0 o  K$ X% P- H4 }$ ?! S图的存储结构——邻接多重表(多重邻接表)的实现
    / `0 e7 S2 O6 V4 I; |8 B7.2 图的存储结构
    2 \! d( Z/ ]& d: N4 d0 N) J" S5 L) h% o( C
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist( s+ r  Q5 ~9 z  d2 u! l% i6 o
    邻接多重表的类定义
    - {6 \6 \* y7 e% U. p. V邻接多重表的顶点结点类模板" u2 r. M4 O+ E4 W, C
    邻接多重表的边结点类模板% j$ j( K: R9 I0 N8 M
    邻接多重表的类模板! S, z3 e$ W% R. v4 t8 Z
    邻接多重表与邻接表的对比
    * ]; T4 k" C5 N7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    ; m! w/ Z/ N% p* Z$ z, V& |1 W$ U! Q3 X5 r  Q& ~% z* Q9 F
    在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。% k) |: E1 V6 }
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。+ ]# z( `* \9 x

    - c' w8 a3 J& G% k; |8 j邻接多重表的类定义9 Z4 }! o; V$ v* O
    1.png 0 y, {! g3 L, m4 i% O- s
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:3 d1 u5 }/ r8 ]( l' x0 Q+ M1 P& p
    data域存储有关顶点的信息;+ j1 P8 S% k' ]
    firstarc域是链接指针,指向第一条依附于该顶点的边。
      k( ~0 S) z1 }+ ~2 k3 U0 X所有的顶点结点组成一个顺序表。

    , r: W6 j' F$ i) T- s/ m

    ( H! Q! I& m  utemplate <class ElemType ,class WeightType>" |9 Q# B7 }9 q3 Q6 v) k
    class MultiAdjListNetworkVex
    " u6 f- m' ?. U5 H1 h{
    0 b& C- V9 }# j4 Ypublic:
      V( W7 z2 r$ u0 R        ElemType data;
    3 t1 \% o2 r" b- Z        MultiAdjListNetworkArc<WeightType> *firstarc;3 _, P+ E9 F/ h( C$ m4 \

    8 a# W* s4 A- c        MultiAdjListNetworkVex()
    8 _; o+ E! ?1 U. n        {9 n6 Z" H. K( j' T$ n5 S
                    firstarc = NULL;
    3 n, P6 d+ a- ~# O- f        }
    + d& ?5 R: f. c; ]8 J        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
    $ T9 m% H: A9 b4 k- u        {
    & V$ F+ S4 u! H1 X1 |. Q# c  S, R                data = val;) s% r/ g5 |$ a/ X
                    firstarc = adj;
    5 q3 [8 C5 ^  g  F        }+ x+ N6 E2 _# i) N9 H! ~2 U
    };
    . \: O9 s" S6 `4 y0 Q6 `9 r: d; ~; j* P2 {/ o
    邻接多重表的边结点类模板6 [* s' l4 z( F6 ?& k7 @& S

    : [# H$ ~6 F2 j在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    / s. }' ^. Q4 o4 R- @7 T+ n8 itag是标记域,标记该边是否被处理或被搜索过;
      a3 I5 ^: C) i5 _2 _# Dweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;: E/ M2 p7 o; M  k) Y" S
    nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;8 a8 a9 k8 W  D1 M
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
    , g! _6 l! s5 ]9 J: d' R6 [0 ]. Q2 B3 O4 ?( Q
    2.png 5 p# S' K( S2 F
    template <class WeightType>! L4 Z: p7 c8 W" X! |
    class MultiAdjListNetworkArc4 o! y3 B* m) E4 ]+ c' y: c
    {: `/ ?% M  f# _) ]- g! h
    public:3 A7 o8 L$ s+ d1 K$ D% ^" o
        int mark;                                       //标记该边是否被搜索或处理过, ~( N5 G7 l8 X9 i3 }. E2 M
            WeightType weight;                              //边的权重* U# E2 F) j- n5 c( u
            int adjVex1;                                    //边的一个顶点
    6 _( Z8 ~6 S: a; m$ w        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1! o7 R" R' N# w  C0 e$ ?5 Y
            int adjVex2;
    . O# e* ^  e) z4 c. m        MultiAdjListNetworkArc<WeightType>* nextarc2;
    6 o; q, ]$ l, e& g
    - l& m4 h! u% n# o4 c% m        MultiAdjListNetworkArc()
    6 R( x' y1 o6 [5 H4 m) ^        {, S8 N; E* F- y" m6 |) I7 J
                    adjVex1= -1;% w& r* t2 L1 h" a
                    adjVex2= -1;
    3 F( E  w  w$ H% {6 V5 B: C& `        }/ G. q8 g: |$ ?* ?, c
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    + k+ E% E8 e7 \* k        {
    : O7 w5 F& W) U5 Q                adjVex1 = v1;       adjVex2 = v2;: H% Y4 j" `7 E! \5 K. i& g
                    weight = w;6 o# Z+ P6 P  Q
                    nextarc1 = next1;   nextarc2=next2;. V( e' x/ o; z1 F
                    mark = 0;           //0表示未被搜索,1表示被搜索过) B  Z+ e! R! t+ p: P$ x- i2 I
            }
    : t! k# ^, m$ C5 m& ?* J% J: c3 K
    8 R# j" Q7 k; r: L- Y$ J邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>; Q- r3 n. Q; [
    class MultiAdjListNetwork
    3 g7 U: l' f& ?3 x{
    5 v# F/ m# Z8 }9 \/ Zprotected:  L! X2 Y; Q: Z3 a$ g
        int vexNum, vexMaxNum, arcNum;, I1 u) W. h: E; {; A) T5 M4 `
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;6 r% @2 p8 z* c  b" I
        int* tag;; O, n/ E' ?7 |3 Q6 T! G9 j! @
        WeightType infinity;8 ?) p3 E& Y0 p* M! |% }( z. O+ P; A9 t
    5 h% W# {. i& f
    public:
    1 a# c5 r" ~# h  x% \, n# ~) e0 t! X    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);" A/ ~4 E; I4 s- `& F+ z% z7 h+ \

    - N3 c4 s+ i% W3 A& i5 K    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);0 u9 R2 \6 x5 l2 a2 c

    * }& n$ _% b7 g; e' W    void Clear();
    9 d) M3 j, L) a" N2 t* r) w! V    bool IsEmpty()/ w1 f3 B; `/ R+ g2 g5 @( o
        {
    * g8 M4 K+ `; a/ \( n        return vexNum == 0;
    ! A$ ?0 c4 H, q0 N0 F' n0 c1 F    }
    ) Y( z  }2 A& @( }6 H    int GetArcNum()const) D8 l, O8 V: L. [( x! ?
        {  N3 v0 N! ?6 _5 {9 a, y& e
            return arcNum;6 d8 p- t2 w, O
        }2 Y3 k& H' _) k
        int GetvexNum()const% [' H6 ~& ?4 X
        {
    ; g3 K& Q+ a7 W  a* b9 ^8 e        return vexNum;/ X% i7 H, Q' k+ d
        }5 \4 b2 V6 t: ]) u6 P+ F, X# ^

    & X% H2 Y! ?8 p" j" u& X# A$ {$ d
    + q. w1 k2 s+ ?    int FirstAdjVex(int v)const;
    ; o5 X/ F4 I, V' |& Z    int NextAdjVex(int v1, int v2)const;
    / O6 K7 A* V3 t! E! A9 ?    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;: Z5 P7 q- V/ h0 f5 r
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;; X0 B" M7 S/ s( ~
    ( v' n, Y! l; ]: U
        void InsertVex(const ElemType& d);
    ) u0 s9 N/ \! O* _" J% r$ B    void InsertArc(int v1, int v2, WeightType w);
      x! j. n" ?0 @+ x# D  @- V5 U1 _! Y1 n8 k, a* T0 }
        void DeleteVex(const ElemType& d);
    & i1 [! N2 \: d! p0 \* V    void DeleteArc(int v1, int v2);2 G* Z3 j9 {' B% w9 X3 [: y$ w
    1 I6 Q; c' m! Q, C  ^/ O7 W4 G
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    6 R# H. V1 X/ h. D, g    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);& R6 y$ h0 x3 N( L/ y  B, K

    6 @* W  p6 D2 Z* Y9 K/ I    ///深度优先遍历; z% L; g1 J& ~/ s9 j1 y- H
        void DFS1(const int v);
    9 j# r% i. z. Q" ]8 x3 j; x    void DFS1Traverse();! h0 O, q" m. @9 [& U. E8 M
        void DFS2();' K' ]% E/ ]2 h1 ]* K

    + ?3 [! i7 e) H, {' C$ X    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    & z: ?0 R* l8 @& g1 F9 H    void DFS3();2 P' Y9 P5 d0 b
    5 u' a8 p" n9 V! k5 K
        void BFS();% d$ N9 L3 V2 \& q' G5 ~0 o* Y
        void Show();7 d8 p; n! h/ \$ `: i6 L8 h
    };+ |8 l0 B2 I8 D

    $ H* k' p% p( \2 _2.函数的实现  l# J1 ^2 m) J
    研讨题,能够运行,但是代码不一定是最优的。
    ( Q2 Z5 N" l' n" M0 z6 v  k4 i; P7 @
    + N$ {& l: S2 m3 a; d! j#include <stack>7 b' x( a* Q' Y
    #include <queue>
    0 u0 A. m" z2 e' [/ T  b& ]% g! g& Y
    template <class ElemType,class WeightType>
    . f- B2 g4 e9 [/ }/ N* A* LMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)( n, A' r' {8 r- Y4 n9 o
    {7 G' t6 i2 P3 W# C# l# }6 z2 ?8 q
        if(vertexMaxNum < 0)
    1 g4 |6 |  y; |1 `9 L        throw Error("允许的顶点最大数目不能为负!");
    % r6 R) h: p# E% j    if (vertexMaxNum < vertexNum)3 g, E  I/ y7 s
            throw Error("顶点数目不能大于允许的顶点最大数目!");
    , l% O, m4 g$ E! K" v4 q0 P4 x    vexNum = vertexNum;2 Y$ \: f! B. N7 \0 s% }) D$ r( K) w: T& c
        vexMaxNum = vertexMaxNum;
    ) N$ K! W1 l' ~" Z$ k# C& N4 \    arcNum = 0;$ {" n( F- f2 X* c1 G6 x
        infinity = infinit;
    9 h6 [( z2 {7 B3 r2 P6 D9 v5 a    tag = new int[vexMaxNum];
    9 W. x& w0 f" ?- Q: }6 P; e  n7 |* r    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];8 T) u2 Q3 H) m* |! D' q
        for (int v = 0; v < vexNum; v++)
    & z1 ]2 \! k9 Y) Z4 j9 j: B    {4 V- w7 C3 e1 R4 T0 M" Q7 J8 Y
            tag[v] = 0;7 R6 n% _% d% P2 f" l# J; S
            vexTable[v].data = es[v];
    2 {" X9 I$ Z& f% [- N        vexTable[v].firstarc = NULL;; w# t' c4 L, B
        }
    " \- f& ^; e; Z6 T}% ?3 e1 g6 W" m- |* f# H: c2 V
    template <class ElemType,class WeightType>
    ' u5 N( a" Y- a0 c  m9 A- uMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)5 o. k. j/ g# c7 L
    {! `, ]3 z: c7 B9 ?
        if (vertexMaxNum < 0)3 y! o# l3 i2 h( H
            throw Error("允许的顶点最大数目不能为负!");5 \- Y9 o( b3 }9 v1 W
        vexNum = 0;1 R2 \$ O0 t( e8 Z
        vexMaxNum = vertexMaxNum;3 ~! u6 v+ @' X! o9 ?
        arcNum = 0;
    2 I  M! k3 c- K& V" m6 k    infinity = infinit;, U# h# U# ^  y) R
        tag = new int[vexMaxNum];9 a( H& w6 J- C
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    8 u: l- Q+ e/ G& X}/ P( o' k3 R% I; V0 v; g) u2 y
    template<class ElemType, class WeightType>
      n9 f1 z: @+ v: x/ _0 F" ]int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    ; k- j' c( ^+ u/ P) S{  K# a  ~" K) g
        if (v < 0 || v >= vexNum)
    " ?8 n/ P8 t8 L- E        throw Error("v不合法!");: \. {# G% O9 |4 Y
        if (vexTable[v].firstarc == NULL)9 Q$ o: ]$ }6 I
            return -1;* V# h. U& c, t* z4 q) \5 \0 S
        else' z  U/ ~% J/ V' \! H- c- p
            return vexTable[v].firstarc->adjVex1;
    : R3 M5 K/ U  \' B* U, \}9 d' j! w/ E" Y6 X/ C9 F  M# a

    - Z+ W4 Y! t; r" Ftemplate<class ElemType, class WeightType>: Y. P6 ~0 X. m; T- p- A! ?! \
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    4 G5 _$ |% s- B3 O{* E& q! m4 e1 T, W$ L9 n
        MultiAdjListNetworkArc<WeightType>* p;; Z: N8 z7 D& P4 x
        if (v1 < 0 || v1 >= vexNum)* ]9 k1 G! K1 x7 B
            throw Error("v1不合法!");: K7 Z) ]3 ^+ s* [; p1 Y
        if (v2 < 0 || v2 >= vexNum)3 U/ j% f, \6 w4 m5 |5 A/ Z
            throw Error("v2不合法!");
    9 ?* i( U& I% i# u  O/ E8 m% L    if (v1 == v2)* @: Q- }! X! u& O5 ]
            throw Error("v1不能等于v2!");
    & q" j  L: \" Y# M* ~    p = vexTable[v1].firstarc;
    ; I1 ?3 \) U1 D; O    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
    + i% b6 v6 U2 `( x9 D. p        p = p->nextarc;
    . R0 g6 |+ P$ N/ j; ~    if (p == NULL || p->nextarc == NULL)3 c0 w/ R5 T0 ?/ L* }: ]! B
            return -1;  //不存在下一个邻接点
    / d2 C3 D, B1 _: C4 m# D    else if(p->adjVex1==v2)
    ) n! P: g4 ~' W        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);- z9 A6 ?  C8 p; r1 A
        else% t# w# O# c4 o' a& g7 N  \! q
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    $ a" [3 Z  j4 i, R}  M$ ~: O% ^; I" W& H
    template<class ElemType, class WeightType>
    1 [/ e7 x. o8 x3 N3 Q2 tvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
      }2 K3 X6 q) C* `( v6 j{/ c3 }+ f5 y2 Q8 h9 u
        if (IsEmpty()) return;
    ' K; w  E" P7 i7 r. y    int n = vexNum;$ w0 M7 m. E% |+ D# h6 O2 s2 i
        for (int u = 0; u < n ; u++)' Q) o! D8 B3 s& k
            DeleteVex(vexTable[0].data);( K' x. U  R5 R
        return;
    6 }/ J/ h/ K8 G3 S% [* \* X4 U8 J}8 O2 Z; a$ Q: N4 q% c+ \1 ?
    template<class ElemType, class WeightType>9 {1 a+ y% T' U- y# H
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()0 d5 g& |' i% o/ S: ~8 M7 i
    {
    5 Y+ D2 a: e  H5 N! `    Clear();: _0 L! t( M# C5 c9 j) L- x7 u
    }
    : e1 E. Z2 L; V; M9 o! h: ^template<class ElemType, class WeightType>
    / m3 x1 v% S1 @) [! B( v. z0 iMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)+ v  \7 K1 L- M6 j+ X/ Z
    {
    2 S4 q/ F& L, F( d7 `0 Q    vexMaxNum = copy.vexMaxNum;" Z- z* X% I: |5 K
        vexNum = copy.vexNum;
    6 y, }$ j9 J4 L& b, G+ j, o* S    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];; f9 j) f( @  n  p; f- D
        arcNum = 0;
    / }) Q9 R  ~& I3 V5 K+ _    infinity = copy.infinity;
    6 s1 K0 J4 Y/ b* \" m& [1 Z    tag = new int[vexMaxNum];* x5 b" [+ M% D0 |" h( z1 F" u
    0 }6 H( O( ]' o9 v
        for (int v = 0; v < vexNum; v++)
    4 i/ G" l( w( N7 O) e4 ~    {0 K8 |2 }5 a: v, |# R. O3 m
            tag[v] = 0;
    6 P# M, M4 k# W. p' }        vexTable[v].data = copy.vexTable[v].data;
    0 U1 u- g' Q, ]6 ~        vexTable[v].firstarc = NULL;! V. `2 m& T0 N0 q# G( [4 h' J
        }, j2 @3 b4 s+ C9 e. L8 F
        MultiAdjListNetworkArc<WeightType>* p;, T$ w' ]/ b, ]5 X: ]% k* F$ u+ p2 }/ d
    ! X! ^% t/ ^* u) K+ R7 v
        for (int u = 0; u < vexNum; u++)
    ( ^6 E3 L! F1 Y- ^) m& R    {4 v0 T& S" e4 a( M
            p = copy.vexTable.firstarc;
    % P& C. F1 c: k. D        while (p != NULL)
    . }% z# a6 \5 ]" y+ R: x! C/ y        {) l! }" b* x. g3 |
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    / Q6 ^& v) e9 S2 S7 D4 B$ B+ \0 k            p=NextArc(u,p);
    9 {% |3 p3 M; E* h  j3 @        }9 c. E, {9 y0 B9 |6 o
        }8 X, A: Q( m; [  |1 m
    }4 `) V. ?  g" X( Z# J
    template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&0 o# E, h) }7 ~4 g4 K0 R
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    " V% g* K7 h0 Z, \7 s{4 ^5 ]. o( t/ u4 ]
        if (this == &copy) return *this;1 ^; T& r6 R# n$ i
        Clear();$ _9 |. ~( _2 G9 a( G" ^7 W
        vexMaxNum = copy.vexMaxNum;; i/ d; c$ d3 D3 P/ U& B* Y  e
        vexNum = copy.vexNum;
    8 k* ~  D; \& ~+ w+ |! ^    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
      S* \) f+ A$ t* s( B    arcNum = 0;
    ' ~5 v# S- h! n% u  v9 U! d    infinity = copy.infinity;7 ], z+ |& r+ ]: k* I4 v
        tag = new int[vexMaxNum];# G$ C, v/ h* I' A, S1 P* K3 Y

    # p- H' l" e- U' D8 e& j! t' p    for (int v = 0; v < vexNum; v++)
    7 T' q9 ^6 d, D2 i& X* N4 Z; u    {
    # M7 ]9 q- d! `        tag[v] = 0;4 N7 V7 ]& t% b; A8 C8 B2 c1 s
            vexTable[v].data = copy.vexTable[v].data;
    8 ^( g. @! \: d: Y        vexTable[v].firstarc = NULL;
    0 C8 i$ A: n. B6 I& N* r$ j% C7 Q' z    }
    6 ^% v! j: z7 t7 O. E9 L- e    MultiAdjListNetworkArc<WeightType>* p;/ M4 n4 ~8 {; x+ r* k
    + M" s  h% ~* P* ~
        for (int u = 0; u < vexNum; u++)
    3 ~  k/ R4 _9 N6 O    {
    ; r: ?7 g" z4 |$ c        p = copy.vexTable.firstarc;$ `/ R* i+ m5 M1 ]
            while (p != NULL)" `- r2 g* w! S% ]+ ~0 m/ {7 Y
            {; J0 m. X, p0 a' _: d
                InsertArc(p->adjVex1, p->adjVex2, p->weight);) `7 \7 \# I6 {8 ?/ ~
                p=NextArc(u,p);# P! X+ J! V0 l" O0 q# f% ^& n
            }
    ( i& N3 _! k& o- P' |0 ?9 p" Y    }; Q' O% H6 p8 k1 l( D' V
        return *this;& c$ J$ l7 s& k! A% h' S$ q0 _" B  D
    }
    $ b# d: f( O8 F( [: H  q8 Utemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    % T! e+ v0 ~: t, RMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    3 s# B/ B1 W$ E, b9 o2 u6 N" \{' K: I! `/ U3 a+ n+ O# G7 S
        if(p==NULL) return NULL;2 h! r  M" a! `: ~
        if(p->adjVex1==v1)
    & m9 E& m* q' b0 N+ _1 I7 A" I        return p->nextarc1;9 m- d2 i1 I4 h( H  o+ y* v
        else
    - x$ {* m& P1 c6 I        return p->nextarc2;
    1 z+ S0 _" ?" g* O# S+ g}5 S3 z! F1 b) g) E! B" a4 `# Z" Z; W8 b2 u
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*8 j6 b+ \1 J- p% ]8 @. B
    MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    * y' S( t! T1 c, t{: ^% g5 m4 o4 V/ E
        if(p==NULL)return NULL;' y6 k! H/ K( z
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;) M3 q) \6 s1 v. a. P
        if(q==p)
    ; n( j" E' A/ M9 V; b        return NULL;! d6 O& _4 i5 A
        while(q)% Z' \8 H6 d9 `% j8 r
        {: o+ W9 r. ^$ F( T. A* G4 G' @( B
            if(q->nextarc1==p ||q->nextarc2==p)
    ) G( D4 s* X& D- p. S6 v4 o, z" w0 H            break;
      `9 x( Y" T5 v: s( s5 ~  C( l        q=NextArc(v1,q);
    0 M6 J$ D4 m) Y- R/ S. e    }
    9 N' O0 R# p, k7 |+ R6 C    return q;
    & L; R; i0 {" w0 C}, _8 s. D# p: u" G" @, q" W
    template<class ElemType, class WeightType>
    # \& |! I! U* O& lvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)3 m1 P4 e& a7 T5 V; ]
    {
    8 L' O' M$ |+ f    if (vexNum == vexMaxNum): ~7 c  H" d* ^9 R1 B
            throw Error("图的顶点数不能超过允许的最大数!");
    6 l0 u0 r) k8 W3 w    vexTable[vexNum].data = d;4 K  I4 D! u) s( T# |" ?3 E8 i
        vexTable[vexNum].firstarc = NULL;
    - M4 H; x6 _1 P3 a    tag[vexNum] = 0;9 z  N# t0 J' g
        vexNum++;
    - q, e. ?6 N8 o' @; f}% n8 t/ k7 S- M6 [6 D" l! O
    template<class ElemType, class WeightType>
    9 J. {5 \, Q+ }6 N$ m# rvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)0 p8 J2 t5 |1 ^
    {
    9 R6 s; {  s( ]: i' H# `    MultiAdjListNetworkArc<WeightType>* p,*q;
    7 @( n1 E$ F3 ^) P/ D    if (v1 < 0 || v1 >= vexNum)
    3 {$ \4 y$ R2 v7 N# m( K, n        throw Error("v1不合法!");
    9 {& D1 {% J6 T! F" t- W$ d    if (v2 < 0 || v2 >= vexNum)
    6 x: D3 u6 Z' h9 z        throw Error("v2不合法!");1 i- U1 [7 k. {
        if (v1 == v2): _) t" ]! H7 V+ Q
            throw Error("v1不能等于v2!");& B3 m3 D6 H% @2 b
        if (w == infinity)
    ' V7 S" y- O! C% D6 `( K9 N        throw Error("w不能为无穷大!");
    4 j8 A6 E% Y# u  @9 u) m, a7 e! `) ^% s$ C, X8 l, W

    9 ?$ u7 M' x& ]" P2 `    p = vexTable[v1].firstarc;3 p# n5 h1 Q" Q
        while(p)
    4 A9 u6 c' l& q    {0 J! x0 z8 f; i+ @
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中; V' r+ s8 A, R* V$ D$ ]' e
            {
    " `& @* y4 E0 K( B8 z            if(p->weight!=w)
    5 D8 q. ?& U, T. k. B, o  w                p->weight=w;
    7 W$ \8 B1 F1 O" |            return;+ b+ r+ A0 O, m! s
            }
    ( Z* Q0 c) x& m) q
    & q5 ^* G3 C% a) p3 ~        p=NextArc(v1,p);  Z! j3 t; k/ _3 Q: [' n7 @
        }& E$ q; _$ [7 B0 P
        p = vexTable[v1].firstarc;" r( I) K2 S, A4 }+ U3 @, y- F; y6 |, V: B
        q = vexTable[v2].firstarc;
    * q! H( y6 g- m" x/ S    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    9 q' Y6 r" L2 Z8 h7 p+ {! t    vexTable[v2].firstarc =vexTable[v1].firstarc;
    ( t7 o1 ?0 u: s9 y" H1 Y3 L    arcNum++;4 f7 S: R7 R- _8 S9 S3 a4 k) T3 ~
    }2 Z3 c, l" ~* ?8 Y3 ^+ U5 Y, R

    3 |3 U6 X6 b1 Wtemplate<class ElemType, class WeightType>* Z+ [; O- B/ Q* N
    void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
    - e8 M1 k/ }) W4 _: w{
    " y' m3 P8 F8 o
    . M9 h6 j$ u: ?8 \! ~    MultiAdjListNetworkArc<WeightType>* p, * q,*r;6 m$ P9 D. Q7 h3 M: q
        if (v1 < 0 || v1 >= vexNum)
    , q' ?4 z# T; |! ]        throw Error("v1不合法!");
    , K1 _9 }5 J) Q0 M, z; \) \    if (v2 < 0 || v2 >= vexNum)/ c; [" s8 m4 R9 U" R
            throw Error("v2不合法!");; [. n2 u9 X& O8 T3 V
        if (v1 == v2)
    * Q5 F0 W# d4 L        throw Error("v1不能等于v2!");
    7 w: g8 D* n8 X& q2 ~! L" N" ^6 n: \1 O2 F
        p = vexTable[v1].firstarc;
    0 o2 V* `2 G% {  X8 K: O+ ?    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2); C; n, r* u* f* E: r( `) l
        {" q6 U% ~0 @& M$ Y4 a3 P% u/ z. }5 J  Z
            q = p;# f1 y# N: M" B0 |1 ^; P
            p = NextArc(v1,p);
    5 \* t! @; @2 s" S8 N, N$ b    }//找到要删除的边结点p及其前一结点q
    - k8 Y" w6 D& o. r  ?/ c$ t9 k+ ^6 D3 s  F9 J
        if (p != NULL)//找到v1-v2的边/ w9 N* r0 T2 x
        {, a5 q4 C% M" b9 v! ^1 |- p/ Y
            r=LastArc(v2,p);
    ! q" h  @4 t) Z5 I; k+ v        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL7 N8 E, ^8 g0 C% C7 `- _5 L
                if(p->adjVex2==v2)$ y* @! m* X: R) k
                    vexTable[v1].firstarc = p->nextarc1;
    ! S% w9 m' ]" H            else vexTable[v1].firstarc=p->nextarc2;
    % W5 ?' ]0 j5 a0 Y. i1 K* e! _        else//不是第一条边$ W" u" Z( y1 |! _
            {
    7 Y# d$ a- j- F" t2 j0 }/ s            if(q->adjVex1==v1)
    1 B4 X# i) s' s* h% @8 k                q->nextarc1 = NextArc(v1,p);
    & ~& {  H: }. m' B( g4 S2 n            else% u/ [& ~8 L$ N& F! v( T6 G3 E% e
                    q->nextarc2=NextArc(v1,p);
    - A% ?5 H% H+ H) Q9 k# r( M* S
      {' T1 O6 b+ W* o2 i5 e3 v        }+ o- R5 N4 ]5 ~0 f9 n
            if(r==NULL)
    9 x1 x' y( @- d0 F% M! S: p# H) H) u            if(p->adjVex2==v2)
    . X2 o8 d+ Y" M  b9 \# x                vexTable[v2].firstarc = p->nextarc2;
    # q# y5 X. j( a. p$ k7 v            else vexTable[v2].firstarc=p->nextarc1;
    7 t6 h5 h8 J3 o4 A! g. U        else' O& i% c8 Z/ e$ x% l
            {
    . r! v2 }0 v% W9 n$ j! ^% s3 X            if(r->adjVex2==v2)
    3 K$ S. H. G* }                r->nextarc2 = NextArc(v2,p);' f' O) F. N7 [+ ]1 V5 ?; K5 L
                else6 U+ i4 b& ]# I% x* j: R
                    r->nextarc1=NextArc(v2,p);
    " J4 h: g0 h% x) M( E8 }5 m4 |        }* e( L4 F- f3 G6 c; e
            delete p;" ?5 U, l6 R# q$ C- X5 {
            arcNum--;2 ]1 I5 C4 @  L" a6 k+ B$ u1 O/ N
        }. I/ D+ K% a% G. R4 W0 r! q$ |( ]

    " v& L& \: y9 B5 G2 k}
    2 v; I7 @9 C& P' E* P, rtemplate<class ElemType, class WeightType> void) D9 _4 D& @6 y) Z
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    6 ^( ~0 T# `& g: b& m# ^( U0 _{$ U/ P: z- i, J# Z" ?3 L
        int v;) [2 i0 E& \7 r( ^! ?
        MultiAdjListNetworkArc<WeightType>* p;- T4 I6 O1 n* }. }' t
        for (v = 0; v < vexNum; v++)//找到d对应顶点
    . N9 q& Z1 ^$ Y+ C. ^        if (vexTable[v].data == d)
    ! k5 \) L9 K! b1 ?            break;- C; ^" S0 C. y) t
        if(v==vexNum)
    , ~% e: ^: x/ Y5 \4 p' A        throw Error("图中不存在要删除的顶点!");
    $ X" E9 T, l6 R& P5 r. R( t4 D1 s5 \* n" O- B) b% ]* V7 [
        for (int u = 0; u < vexNum; u++)//删除与d相连的边4 `9 T& [5 f( R
            if (u != v)' @. |0 X2 E" d' o
            {9 d  z8 e  C5 i* }
                DeleteArc(u, v);* s& u  Y7 C4 F) F
            }! ^  N( h3 `) j3 U6 w0 |" |8 ^
        vexTable[v].firstarc=NULL;2 X: L) T9 X2 X2 S

    5 J: W2 S( f. R' ~/ `% V    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    1 U, g5 O0 k, b, W; t  z    vexTable[v].data = vexTable[vexNum].data;' _4 z9 g3 v8 l$ Q; G6 b
        vexTable[v].firstarc = vexTable[vexNum].firstarc;: X6 T2 L2 Y/ l0 T" \
        vexTable[vexNum].firstarc = NULL;
    * }' z* D8 U- I9 d7 l    tag[v] = tag[vexNum];
    $ P9 l) \" L3 D    //原来与最后一个顶点相连的边改为与v相连3 _6 x% x$ H2 f/ Y9 x( l3 i7 x
        for (int u = 0; u < vexNum; u++)% C1 k4 Q% I' t9 T. Y2 J
        {! Y) b" o% L9 }4 q' i
            if (u != v)
    , X! j3 m" T8 T' L        {2 c3 b. m5 t# ?( B4 g
                p = vexTable.firstarc;
    - J. a- ?- i3 X. L# V1 E# k            while (p)
    & l; k" {  Z7 W' e( S0 a            {) G5 ]/ z$ T2 H$ z
                    if (p->adjVex1==vexNum)
    1 A! e3 n2 s3 h# ?2 e& ?/ W                    p->adjVex1= v;8 R6 g+ e1 P# [! l4 e3 a* P
                    else if(p->adjVex2==vexNum)
    1 X0 D, R2 r+ F! X; H, ?# g1 V: C                    p->adjVex2=v;
    + s) T; K( a% r) K+ o                p = NextArc(u,p);! h2 K. D$ K9 O- V
                }
    - o% [3 L) Y9 f  i5 {. n. K        }( [% I6 u  _; M; A9 v
        }7 ~6 O" t" m) ^+ }6 Y  |1 R
    }
      ]7 O6 `" U- n) B, f9 l* ^///深度优先遍历. ~6 d6 H, c, l* r
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)' {1 s: }9 P2 G: V
    {
    ! B) b! J4 A" c( E    tag[v]=1;
    ) F9 |8 ]; V. n    cout<<setw(3)<<vexTable[v].data;0 l3 ~% H4 O# q' x% V
        MultiAdjListNetworkArc<WeightType> *p;2 N% q% i1 X# J
        p=vexTable[v].firstarc;
    & Y# x1 ~9 ]# m( S, g  ~5 U    while(p)! R( K) U5 ~) s0 l. e/ {
        {
    " }  [( s; g" z: e1 g' t        if(tag[p->adjVex1]==0)
    ) g. |% E7 z1 h3 i0 t& T            DFS1(p->adjVex1);
    ' D: p* H1 g) f3 i' b: |        else if(tag[p->adjVex2]==0)! S) w6 \1 d- W2 }6 ]7 P; d- b
                DFS1(p->adjVex2);
    / h" x1 [! n: v6 }" J        p=NextArc(v,p);# P# F, o: C7 B3 o4 @/ S; x
        }
    . Q9 q5 p1 j1 j+ K+ M4 A. ]+ Z}7 ~7 t% |6 V% v$ D
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
    ; j; S9 z. t  b+ a  m% j{
      Q, k6 O- n( P9 ]! o    for(int i=0; i<vexNum; i++)
    % v; a, O& K4 T$ n/ d. l8 W; d        tag=0;/ A# y* Y* K7 `
        for(int v=0; v<vexNum; v++)
    , Y. D  H1 J- z: |    {" C- `$ R3 X+ F9 e. z9 J5 c- {
            if(tag[v]==0)( o& t9 z# e" ]3 l: z$ H
                DFS1(v);6 u' v% y( Z5 Y& g  B+ r
        }
    " d8 G2 P0 o$ S  N}  f2 t  b  E; d6 f
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()0 s2 T5 L5 Y0 F0 @6 U6 |
    {, L+ Z# v2 R+ R: {+ k$ h7 Y# l
        stack<int> s;
    / t2 y/ j2 i+ Z, Y( c- n2 X    int tmp;
    0 C8 T! N  d) I6 f1 D# I    MultiAdjListNetworkArc<WeightType> *p,*q;
    9 W1 h0 \6 x, P$ k  ?1 m6 R    for(int i=0; i<vexNum; i++)$ A3 `; b+ {. i0 n/ ^9 b
            tag=0;
      B% E' s2 g/ ]0 B. k    for(int i=0; i<vexNum; i++)
    2 Y1 G+ c, V9 |+ r4 `    {% x, \; @( k/ p
            tmp=i;' N) u& n; D7 |/ E6 l* U2 l& ~
            while(tag[tmp]==0||!s.empty()), w( V1 s" n3 z! i6 s1 C$ ]
            {
    : d  z4 [2 [/ Z0 W            p=vexTable[tmp].firstarc;5 h/ t" R2 e' {
                while(tag[tmp]==0)
      y& g9 G2 n( \7 @" a' B5 @- }/ I' e4 y            {
    # s0 |' ]% K9 |  Q                s.push(tmp);
    9 p- Q. f9 v* ^                cout<<setw(3)<<vexTable[tmp].data;5 k, A5 f' ~0 D& m2 X
                    tag[tmp]=1;
      s, w) y, Y7 u/ _) A4 ]                p=vexTable[tmp].firstarc;
    3 B( @: d" Q5 d' \! p+ [3 [                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
    . @6 |3 [  E9 U7 m- Z$ P' |                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);: T8 e0 B  j1 y( `
                    //cout<<" 1st     tmp="<<tmp<<endl;
    $ p" X. s3 U7 j9 i" b+ m            }% @4 I+ Y4 s: Z, _3 U5 `9 b
                if(!s.empty())8 k2 R8 o; a) G4 |) `# Y7 i. @
                {
    - g2 U. _1 k" {3 [                tmp=s.top();
    & E( v  q9 A1 t/ I                s.pop();
    1 x3 b1 k6 r+ x                q=vexTable[tmp].firstarc;
    3 Y$ \8 t3 F7 i6 j                int t=tmp;* c0 K% K3 g6 I
                    while(q&&tag[tmp]!=0)
    ' q; C9 p6 Y4 p+ }0 `                {5 A" J7 r' J: @/ s
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);. q- W! d; a2 z2 b. k5 e0 Z
                        //cout<<" 2nd     tmp="<<tmp<<endl;
    ! ^4 ]1 F: o- A) L; `; ?                    q=NextArc(t,q);+ r4 c5 v, H, |0 @7 I( P( O
                    }
    8 D5 v+ p/ `# q$ X) n                if(tag[tmp]==0)) y& v$ j+ a3 q! t: S  C
                        s.push(t);0 I; s. Z* R1 c
                    ///1、对应上面连通分支只有1个点的情况
    ( z2 t2 K$ {4 Z                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈9 O: w6 G7 w6 @0 Q$ t* R+ n( X* E
                    ///tmp要么等于找到的第一个未访问节点,, {2 |; _% v; e- U0 }
                    ///要么等于与t相连最后一个点(已被访问过)
    2 |4 M% d& r+ A# ~* O  h: L/ G- S! `                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点' v( J. o3 J2 _! w2 ]. U4 E
                }6 ?# C, l9 R9 u: h4 o7 {1 O
            }
    ( [! h" O2 h; g* U- @/ m    }& c# D5 j' {5 {6 ?- E# F
    }: O# l1 R) t( I7 v, n! n0 N& ?, t0 e
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1$ V. j9 Y( P5 }7 B- P  L# v
    template<class ElemType, class WeightType> int
    * ]4 v1 l8 s1 jMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
    " e9 Z! o. T/ e{
    ! O3 x+ e0 n0 Q    if(head==pre), N0 L4 k& t! h) y, O
            return -1;
    1 E6 `5 R# M. h7 i1 K/ J7 {4 J+ s3 U( W# W. q. s* B1 U
        MultiAdjListNetworkArc<WeightType> *p;
    / g. Q" J! N, I8 E    p=vexTable[head].firstarc;: u- ]; v& A; A  S* Z
        if(pre==-1&&p!=NULL)
    . ]1 n4 L. V  Y3 W        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    6 h; J) }( F, |) `) g2 U! U3 e$ L    //pre!=-1&&p!=NULL
    9 g- o+ u& U1 q- u4 y; A: X9 M    while(p!=NULL)
    . l% s. w3 {# A0 i3 f' \    {
    5 D; k: f0 ~' E1 k, z# m* s        if(p->adjVex1==head && p->adjVex2!=pre)4 e8 }# U0 N' p) P; i+ ^6 e
                p=p->nextarc1;! j0 \3 m& g" q& D
            else if(p->adjVex2==head && p->adjVex1!=pre)
    ; h! h3 S2 [; g3 Y; l# y8 R, N) {            p=p->nextarc2;$ K$ v7 `! o. g  S4 }* Z
            else if(p->adjVex1==head && p->adjVex2==pre)( O$ m$ b: x" [- X7 q: I
            {
    3 _& {+ J) b5 y/ g1 _! H            p=p->nextarc1;. t) F1 K$ G! P1 _2 @
                break;
    * p! B* X  j6 v7 f( h! D1 x        }& b7 x9 B" q' q  U5 Q2 L
            else if(p->adjVex2==head && p->adjVex1==pre)4 G: |* u/ }8 c0 X7 Z/ ~) q! F& U4 e$ p
            {
    9 {) f  ?2 n( I3 x0 H4 W( P            p=p->nextarc2;
    # O+ |# U3 k! m3 R            break;
    & K. K$ O" P8 r. K2 A- A. T$ m        }- t9 O3 e) \+ @; e
        }" J( ?5 Q2 f$ Z5 E, _5 l: F
        if(p!=NULL)
    8 p4 [, U6 B1 W1 _- L    {
    ; T) g$ h1 _( ]" g3 p4 M        return p->adjVex1==head?p->adjVex2:p->adjVex1;( R& G- W& }- [$ @
        }
    ( B) P, w; m" V; d# `    else. }, ?" G9 H2 ^) F) k1 ^3 |
            return -1;
    : O2 L! N4 S  |. A  a; Z}
    3 S3 ~- p! e$ v, O- j5 S) m' F$ a" U) a0 h( C  D
    2 l$ g! V  V3 ^. j. L& ^0 W6 I
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    + i7 F+ j+ y# T( i" ]8 I) Y! f{
    1 t5 E! R; J, n4 ~4 E& T) ?7 F" w    stack<int> s;* A2 s5 d( H) S
        int p,cur,pre;4 k" s3 T( i# s4 z+ U# p
        //MultiAdjListNetworkArc<WeightType> *p,*q;) W9 B) X, b% }2 ]* }- u
        for(int i=0; i<vexNum; i++) tag=0;//初始化- w' W3 o; O* J4 T  O5 c# x
    ! h- {& c9 \2 D! v0 c* _
        for(int i=0; i<vexNum; i++)& h1 L7 r: o3 ]" Q* x' _: v
        {
    - B" a6 S. p# \7 m        cur=i;pre=-1;2 C; s: k0 I" ]* N
            while(tag[cur]==0||!s.empty()), e. V8 p( F+ T. @# C( O5 ~
            {1 D/ K' C6 r( [& G+ x- S% U
                while(tag[cur]==0)
    ; G' {* l6 I% B& `5 s            {
    ( y3 d8 M) u$ D                cout<<vexTable[cur].data<<"  ";. w8 \/ X; v, |! R" J# e/ K
                    s.push(cur);
    ; t3 F: P6 {' Z" x7 Z3 J9 \* M! P                tag[cur]=1;
    ' S3 P1 N% [$ g! ~  }               //初次访问,标记入栈9 K* t+ o9 ^/ x) U) V6 i$ A
    ! V! x" y# a( i. _. c
                   p=GetAdjVex(cur,pre);//p是cur的连通顶点
    3 B; ]* C. g5 n, l2 r4 D               if(p==-1)8 J0 \( F" n; k; }  f6 q* E
                   {* v4 b+ K' c; ~! B7 x7 \
                       pre=cur;s.pop();
    ) o0 j+ I' x  e                   break;
    ! `7 G$ u4 A9 \. S               }. W! G  x8 r2 L* o4 }/ c
                   else  a5 Z# u1 i$ I) Y3 C- |& w0 g
                   {
    % b# T" A5 L# r. Y3 Y0 w                   pre=cur;
    ) o5 I% c( k) |& N                   cur=p;( N8 R/ l& N$ @2 L+ V5 o
                   }
    ! N+ F: D  b5 c2 m' t
    1 F5 ]" Q5 ?2 U5 l0 P4 E            }
    7 Z) r0 ~% M9 G0 J) I5 X            while(!s.empty())/ M- \1 ]" p& Q2 `' E5 X, ]
                {
    ' h* F3 ~* @4 l# {  u                cur=s.top();% [# f7 [3 u# w+ G9 S  b/ ~
                    p=GetAdjVex(cur,pre);6 H" u6 G1 k4 c) e8 _
                    if(tag[p]==0)
    9 t5 X+ e# [9 A  J                {
    $ k! ~+ W5 `, Y8 b                    pre=cur;
    1 b; |' {) r% Y& W# f) ~; g' Z1 ]                    cur=p;9 e) E! u1 R- `9 z2 L/ L* J- R
                        break;* F4 y! i9 C7 A2 |% ]
                    }
      V% j2 `1 ^0 R4 d                else
    ( p, g% e$ p0 S" I& ]                {! [1 L8 ~; Y4 ^9 E3 Z. u
                        pre=s.top();
    0 x( |! m& L$ q                    s.pop();
    ' g/ R- G+ f/ f$ n( N4 N                }; K8 e( k0 Y: C: D) W
    ! x. |* j0 x' U
                }2 h- F7 A% K* u

      t8 f- s0 e4 f" ?2 I) @        }' P3 ^. A6 g, i5 J; {
        }
    7 o3 W% |4 c" {! r5 P) X4 X) Z}
    ! o1 N$ }0 b5 x3 h2 ^) Jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()) ]8 s  \) V( l
    {: u( ?* a; G  v7 w
        for(int i=0; i<vexNum; i++)# x0 C  g# X1 B8 n
            tag=0;
    $ e% r" I( H4 D0 L( i    queue<int> q;; L, W* S; j6 N2 }, X
        int tmp,t;% J$ p5 k, a; D  F5 K/ A
        MultiAdjListNetworkArc<WeightType> *p;
    # X+ [2 A) b: B0 {    for(int i=0; i<vexNum; i++)
    , }1 l# e& f2 @6 `- |    {1 _/ k: `& O5 |% s* i
            if(tag==0)6 X) l8 W- X$ W* @8 D( j
            {
    ( P, n' o' v" P            tag=1;! y: G3 k6 f& p- K! ~. N
                q.push(i);
    # r7 L% O' L; @' `9 L4 e0 M5 B            cout<<setw(3)<<vexTable.data;$ T1 a' }; m. E" e. d; w5 {# E
            }
    + }  d2 O' p" ~+ C6 V        while(!q.empty())
    ! X$ `4 ]) `' n/ e& U9 y        {3 R0 P3 p( M) S) m1 V. S! c5 K
                tmp=q.front();
    0 t- j* d2 G7 L3 h' f            q.pop();
    " c. o1 C& J4 f- f7 m            p=vexTable[tmp].firstarc;* x) Z+ q& w+ l
                while(p!=NULL)- {. `& L+ n' V, H8 }# v" m5 f! y
                {
    3 w2 P- `3 x: d, I. l- @! j8 ~                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    6 ?8 }8 K* f- E$ L5 A3 }9 V                if(tag[t]==0)" g! w( x2 M. z- V
                    {
    2 Y) N5 ~# P$ A3 p5 H+ b3 D9 Y                    cout<<setw(3)<<vexTable[t].data;
      E: v0 s  `3 c; l                    tag[t]=1;
    * V+ i- T: ^3 S6 B                    q.push(t);( z( ?( a. k& w. ^  V: O* o6 N
                    }, \9 h. i9 E5 a# h0 {2 ~3 F0 @
                    p=NextArc(tmp,p);
    . I) w* u( {0 D; x/ k6 _6 r            }8 J' Q! e! [$ N& F# J$ }
            }+ g) D. U8 D9 Z  {  U
        }
    " @) X' l: R4 P, \2 X+ G}! K7 n1 ]) v/ q
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show(); Z0 O" h0 V. G1 M
    {7 b& j8 b( n+ O) ?* N) w
        MultiAdjListNetworkArc<WeightType> *p;
    * k' p/ E) O1 Y2 i# B    cout << "无向图有" << vexNum << "个点,分别为:";0 ?/ b) t/ [4 ^
        for (int i = 0; i < vexNum; i++)
    # q4 O( e) w; I9 s! ~' }- h        cout << vexTable.data << " ";* m4 A3 I" `5 f7 O) J
        cout << endl;- W( w3 L* w6 {& l. @, J6 C
        cout << "无向图有" << arcNum << "条边"<<endl;
    2 V1 P% h3 _' k3 ^( W    for (int i = 0; i < vexNum; i++)' n2 ]+ R/ ~* {3 X8 v: F
        {
    8 @! j. m3 Z; g6 t        cout<<"和" << vexTable.data << "有关的边:";
    & v8 n- G; v; ?& i        p = vexTable.firstarc;
    / C- ?; B7 Z- ~        while (p != NULL)
    / R! F7 {& p' Q& l. u* B; `        {
    7 M" \3 w1 u) X- X. [* W            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";4 r5 X5 u$ l3 ^) N6 x
                p=NextArc(i,p);% ]. p4 |4 j2 {, Y& y! E" p
            }, u! ?+ F$ W. U
            cout << endl;
    5 ?- _0 ?. }# y/ i) j, @5 i    }
    ! g* X* N( Y) g) v9 g}
    % |- u, c" ^* Z9 e; }2 U; v: F: h" H$ A& E# m( J7 e
    ) Z* O2 m8 k8 o5 o2 [* w
    邻接多重表与邻接表的对比% L; L8 d, T3 q

    ; U) l% K9 v: ~' L' C: I: e: s9 d邻接表链接
    + `* O# @' ?0 Z$ _5 l, G在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。4 n/ R7 c2 v# T* H$ e8 c' X& f1 _
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。9 C$ f6 P+ V! c+ J; j; y
    为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    ; U/ z, }5 t5 {————————————————4 b7 H6 f  E% n5 b0 _
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。! U9 F& d7 b8 a  o  D
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
      ]4 ?5 f9 y1 m1 _& D8 W& x% r0 R# v2 G

    - j" p6 m, A/ M1 F" ~  [( R5 E; B8 e' P; I3 I0 |2 X

    ) u$ G& Q+ g/ N! c1 C2 W+ R————————————————9 C8 {& s) A: I! e2 `  U8 t  j( h
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    6 a3 P7 T% Z) F1 @: V$ w原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    ) |6 I( }) G; q7 Q$ ~3 y! d( U5 @5 g) s5 ^/ I4 C% A
    ) P  w' I/ r9 Y; t
    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-4 22:45 , Processed in 3.394838 second(s), 54 queries .

    回顶部