QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1566|回复: 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
    - p3 N" L. R$ |+ P0 K' f/ K
    图的存储结构——邻接多重表(多重邻接表)的实现% p0 i3 ?1 A$ H, G& ?+ B* Y: N
    7.2 图的存储结构
    0 U" M: E) y* U" Y! ]6 Z% K; n4 W  {9 y4 L" h
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    8 G8 F# R/ w& s邻接多重表的类定义
    $ d- r$ o1 r7 P4 I" Z9 O9 j! |' K邻接多重表的顶点结点类模板
    ) @3 y7 ?4 U' P. d8 ~& h: [$ p邻接多重表的边结点类模板" s2 |, C/ X9 b6 i: A, k
    邻接多重表的类模板
    5 `0 I& C1 X5 o/ T) m邻接多重表与邻接表的对比
    - p% `9 E" W5 @6 l. T* e- D- Y7.2.3 邻接多重表(多重邻接表)Adjacency Multilist3 D2 q9 K9 j9 }; v

    : I# N6 [. e  c! f2 Q在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。0 P7 I3 B+ t8 z; X; p
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    5 u. ~" u6 D" @) w- R6 J9 `
    * G% [3 z  b* z2 Y- H邻接多重表的类定义
    " m- k& j7 y$ k# \" O0 U$ y2 J 1.png 1 q! k; s) x* x8 Z
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:
    0 d9 L# x9 l& C( d& ^" Hdata域存储有关顶点的信息;
    ; q( Z8 I1 }  @, ?  L# ~firstarc域是链接指针,指向第一条依附于该顶点的边。
    9 g; Y! C# s4 l" ~所有的顶点结点组成一个顺序表。

    ) ^+ Y/ k" }( y
    # w" Y5 B) `+ }; v8 z: N
    template <class ElemType ,class WeightType>
    7 {9 v4 i6 A9 I; e; c, ]: P2 Oclass MultiAdjListNetworkVex
    $ [5 z/ I. _6 P+ O; O{% k  C" _8 ^% }+ U9 ~' U
    public:& I7 P4 K2 h- u* ~" g
            ElemType data;
    % U2 S& D$ g0 v4 T/ w& m) ]3 x        MultiAdjListNetworkArc<WeightType> *firstarc;% Q. \) l6 [( s1 y8 h  w

    - Y  N5 w) z' r) ~* t* t        MultiAdjListNetworkVex()4 t1 H7 n6 y, o- l1 h: R
            {
    : D( o; N5 ^% a8 N) t                firstarc = NULL;: b" ?! D5 {$ O% a+ Y4 V' a
            }
    - D7 b+ t) ?* j5 m6 D3 [" m        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL): C8 [* {3 A9 \, j: R% e; z2 u
            {
    8 X- B1 X, I( p4 l                data = val;3 f% g: [6 k9 W# H$ q$ t
                    firstarc = adj;
    * v! e+ s5 @+ C: C9 `$ K        }
    0 i5 O% N- E9 I" Y6 `" m};, D7 J6 ?; z$ s' Y

    ( M0 S; H2 X% t, ~: ^) z邻接多重表的边结点类模板0 U& S, {1 `: X( U, n/ q7 o: s
    ! Z; p$ O" \9 \4 ?0 i
    在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    # U0 k& f+ v3 I, r( F  ]tag是标记域,标记该边是否被处理或被搜索过;
    2 ^& O/ f' H9 z: `) fweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    8 i: D( z$ x1 W  p: ]& inextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;2 B2 Y1 I- l! j3 ^( R1 Y
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。3 o  |+ d9 y* Z5 R

    : T( {+ X5 a. Q( p. {3 d  j 2.png
    , C7 Z2 }7 d/ Etemplate <class WeightType>
    / r/ Q0 Z. H/ r) \class MultiAdjListNetworkArc9 G! v3 c) F+ y$ R- k
    {5 [9 p- L# X, J2 ]6 q
    public:
    6 J3 ?( I1 W; N: @$ D% ]    int mark;                                       //标记该边是否被搜索或处理过
    & Q/ w! d0 ~% G+ L9 i        WeightType weight;                              //边的权重/ G( `* [$ ]/ \
            int adjVex1;                                    //边的一个顶点
    4 i" Q& m9 S' v9 b        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1$ e* u+ [# m" O' A
            int adjVex2;
    ' F; O$ R( y9 j+ e2 Z" g0 i        MultiAdjListNetworkArc<WeightType>* nextarc2;
    . Q( K' Z/ m; g" d* R' k- J( ~9 f7 t( P* B3 H
            MultiAdjListNetworkArc()1 x4 U* H: S( ?
            {
    3 C9 V8 N- e8 p- y  z  D                adjVex1= -1;
    ; {: h" Q' d6 q; |- j! D                adjVex2= -1;/ I3 r+ F. [; P+ J6 s
            }
    4 q$ |6 z0 T$ S- n8 c8 ^        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL): Q/ p& f( D  M' e8 E
            {
    ; ~" H9 R/ K. G) Q5 {                adjVex1 = v1;       adjVex2 = v2;
    * y: u# x: q/ K  S0 a: l                weight = w;
    , ^( P/ R6 {+ H# T% ^. b                nextarc1 = next1;   nextarc2=next2;
    . n+ y9 Y7 J1 p                mark = 0;           //0表示未被搜索,1表示被搜索过
    ; m( V3 L9 r* a# a        }
    0 j* O( m: E- a0 G; \' g6 \. h7 X6 H+ F& F
    邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>4 \2 H+ ^9 E8 c7 U) ]  Z* W4 r& {
    class MultiAdjListNetwork: k- P) L- R4 y& N9 w5 g8 Q, r
    {( H+ `  J( H/ a8 n
    protected:
    6 D$ ~$ b+ Z1 c7 ?! u, m; j    int vexNum, vexMaxNum, arcNum;
    % D. B' B6 B0 y0 N    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;8 J$ R9 a3 p% d% K
        int* tag;- N' ?: W3 T# Z2 s% e* T# g% L/ e, ^+ x
        WeightType infinity;
    $ q! E; U. l- h( m) Q$ x( F  l% q$ M
    # t- Q, I* U  `/ T. s) \" h+ x2 ypublic:5 B$ x! O8 H1 ]" v: {5 ?7 ^
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);& Z5 r* L6 j6 B# g2 ^: H8 [
    " b7 D3 H  E4 \8 Q2 G% V
        MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);/ g. J! ?% o& P. o/ u- O

    ( n5 r* H( f3 a8 x: i    void Clear();
    & n9 y& k8 w" @4 y    bool IsEmpty()
    , B; Z+ F# r8 k; r0 K. Q' H    {3 k# R$ ~2 g4 W  \5 X
            return vexNum == 0;; a& a# F2 b, M) n
        }" `& j: g' _. H! H7 y4 h" d
        int GetArcNum()const' @4 O; R8 [5 v, O
        {
    $ l, n4 R0 E+ c        return arcNum;* ~( [/ G8 ^; f/ m" r6 [; Y4 L
        }
    # ~6 R- L; C' [" V    int GetvexNum()const' m- i( C" Y1 b% R1 L( n" F
        {; x/ X9 w4 f/ f* C0 X
            return vexNum;
    6 a/ [/ b0 \0 _. a) @2 t    }6 \% m% E7 u5 W5 G0 C0 g* K

    5 A1 O7 \8 q9 [& {' Z7 g% {) N! o# F* j1 n
        int FirstAdjVex(int v)const;. _; L' W# K8 r) G, c
        int NextAdjVex(int v1, int v2)const;
    + w; v  `1 O2 ]. ~! Z7 g    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
      m( `( }) @! a    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    + a* P% Y4 p* l1 t- C0 \2 E4 O% E' U( M8 U6 C$ Z
        void InsertVex(const ElemType& d);
    ! ?* `& P/ ?4 V    void InsertArc(int v1, int v2, WeightType w);6 p7 L9 y3 n, w9 P- \2 L6 A
    & |3 P2 ]6 k9 A% _, O7 `* d: y
        void DeleteVex(const ElemType& d);
    6 I) c# b: |$ q2 B9 |3 u: k    void DeleteArc(int v1, int v2);
    3 e7 _7 O/ u" J4 E1 w* `, V. O
    & m- N- u+ ^& s, h    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);) ?( k- o, v% U0 T& t4 K/ ?
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);4 G9 \& w$ K' J! g3 W4 K
    7 {8 I$ q; l/ l3 T
        ///深度优先遍历
    : ]4 J( \; |$ D/ W8 w$ `) E    void DFS1(const int v);
    ( o6 O1 n) ~# n! A, ]8 s% q* k    void DFS1Traverse();
    0 T. R' y. K  U! [- }    void DFS2();$ h: G! \# k1 b' o5 o2 Z7 [
    6 ^; l# K& _1 l- d
        int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-14 j5 o- T9 o6 O  G6 x: _1 a. B2 X
        void DFS3();/ Y) i' u% {1 L" e; f* Y1 p

    ; Q  }1 e2 ^; q9 S! L+ O  x    void BFS();. L* `7 K% r7 k$ t
        void Show();
    8 c7 D' H4 m& n3 {& r$ b};
    0 t0 G* I7 d; V- F$ u" z& ^8 H% O- }1 q# ^: G
    2.函数的实现- z4 I7 c! ?* w# p
    研讨题,能够运行,但是代码不一定是最优的。  s5 K9 q: y2 U' b/ _- M
    # _; @: D6 V3 ^" i
    #include <stack>* h7 M& j4 D, y$ c6 [* w, J
    #include <queue>5 F8 F% l- p* ^3 ~0 Z

    : N) V+ @! T# D+ F5 Z+ stemplate <class ElemType,class WeightType>7 h7 N5 w; t# W( Z/ P% r: A
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    % A9 `; i# ]! D! V# I. s$ }4 p{
    ) |' g/ f% k, P' F    if(vertexMaxNum < 0)  }: U* L% q; S- A0 n9 F* C* x
            throw Error("允许的顶点最大数目不能为负!");
    2 o  p* ~$ w% i( W& \2 F4 M    if (vertexMaxNum < vertexNum)* P+ W* i; \  C0 V9 Q
            throw Error("顶点数目不能大于允许的顶点最大数目!");
    + i2 k- B0 \6 {5 ?3 B    vexNum = vertexNum;
    5 C, D. G3 h" k& ]    vexMaxNum = vertexMaxNum;- p7 d9 m( j5 }9 Y8 x5 m
        arcNum = 0;0 P1 r& ^# V1 H+ [7 r- r0 V
        infinity = infinit;( L! D# W" i8 ]: z' H7 [% j* O) f
        tag = new int[vexMaxNum];
    + r+ z6 ]. W, g$ G6 T    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];5 f6 a8 d) P% q4 I4 x- T
        for (int v = 0; v < vexNum; v++)
    1 S0 R, c' i5 \" b9 f4 S  ~* ]7 h    {& i" R! S) v8 ?( A- N7 D9 a
            tag[v] = 0;
    7 t; [: J9 {5 F+ D0 G  Z& W        vexTable[v].data = es[v];. r2 O! k# c5 P' u; y" P) }
            vexTable[v].firstarc = NULL;) \6 r! O) G: v& ]! e" S
        }
    ) H& K* H. W+ r" S1 K: B6 |}
    . E  z8 X! X/ qtemplate <class ElemType,class WeightType>$ |+ x+ j  O5 j' s1 B" Y4 x
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    4 J0 S3 M! E0 z) F2 c{
    9 Y: \7 F) @% Q2 Y    if (vertexMaxNum < 0)
    ! K: i8 S; y3 H8 ]' Q. z4 a1 L# K- I5 W        throw Error("允许的顶点最大数目不能为负!");
    # A. n5 C7 u: i8 h5 g    vexNum = 0;
    ( N& m' E" P9 a0 g4 C$ n- V    vexMaxNum = vertexMaxNum;3 P8 q8 [3 `( M0 L  @9 ~- @
        arcNum = 0;
    5 D- j  q) o& A% }8 t    infinity = infinit;5 f  x- x; d4 E5 G7 y9 P2 A: G
        tag = new int[vexMaxNum];% o1 a' V; S2 ~
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];. f' }5 q/ Z0 S; t
    }
    3 B1 C5 R9 G0 d0 Y6 c! |# I% Dtemplate<class ElemType, class WeightType>
    4 k6 y/ \, w4 g2 Y1 I! s0 x" rint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const( Z2 {' ?3 B9 s3 H; E& ^) ?
    {5 ?/ Z( Y: a- Q+ ?% q
        if (v < 0 || v >= vexNum)
    " d# r8 w4 ]+ }5 r  H) n- @, @2 C9 o. C        throw Error("v不合法!");
    * ]+ j" B+ a5 a6 |1 J) _    if (vexTable[v].firstarc == NULL)
    & @& `% U& n8 m; e. r        return -1;4 l; C2 v/ H& \# W0 Z% ~
        else- C: a; q, T: g* l/ f3 D
            return vexTable[v].firstarc->adjVex1;
    8 ]2 \8 a6 K2 I9 ]/ E. w}
      s: p7 f" z  b) Z! [$ J
    1 f% e" x, g; W" k& n1 m& Itemplate<class ElemType, class WeightType>5 U/ o% P0 S1 P7 ~( v. u( C; ]
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const$ i! j# ~6 Z. h+ l# Y+ c/ U
    {3 g, Q9 g1 P4 V& w7 M
        MultiAdjListNetworkArc<WeightType>* p;( [8 @+ D0 K+ Z, H7 r8 X6 B0 m: F
        if (v1 < 0 || v1 >= vexNum)1 a" Y- m* @4 {8 N' y+ y( `7 F
            throw Error("v1不合法!");
    4 O/ v; E3 i% _! B+ m    if (v2 < 0 || v2 >= vexNum)- ?! t# b- ~* M! y
            throw Error("v2不合法!");
    * f0 w1 E8 {, l) ?, r    if (v1 == v2)
    4 s! r/ N! D: k# T4 p4 U        throw Error("v1不能等于v2!");
    8 i/ g6 _# c. W' I  H* r: n& G8 D    p = vexTable[v1].firstarc;& J! r* Q) `- h- B' |& n" j* H6 v
        while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)) z2 W4 M% j* K/ \# ]
            p = p->nextarc;
    . ?$ ]# e, ~4 g7 I    if (p == NULL || p->nextarc == NULL)
    3 o8 I. R  q$ E8 Y8 {        return -1;  //不存在下一个邻接点
    3 X$ S/ W0 u+ z5 \9 L    else if(p->adjVex1==v2)
    0 g# C. V5 d6 m& v7 F# L/ |! O9 F        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);0 K. e! h1 \( S) N/ |
        else
    " [* X. g6 x* t* P" C: W        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    # ?' }- A: X8 x% _}; L7 `; r# U' [9 p6 v* I: ~' r% M% O
    template<class ElemType, class WeightType>: b) \2 J3 c, ]1 B: v# i3 K
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()
    3 u$ Q7 i- _3 |% q2 K4 B) V: L{6 ]+ C  @& ?6 F3 i, o: z8 f% a
        if (IsEmpty()) return;4 B" ^. X$ w. ^3 U$ E1 u% K+ Z0 p2 g
        int n = vexNum;
    ' v0 C- b, W/ X/ g# E$ b% l    for (int u = 0; u < n ; u++)+ G+ j# Q: }; Z( ]; k) [
            DeleteVex(vexTable[0].data);
    6 B' m4 |4 A6 u8 f3 t" N9 d3 y    return;& d) a" I/ v1 d8 R, [& G; ~# M5 t
    }
    7 v3 c/ E; ^4 c8 f# f3 Gtemplate<class ElemType, class WeightType>
    7 q/ n3 C9 ^: \& Z. w0 _9 E5 UMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
    # y8 A7 [: i6 u+ ]* z{/ q8 z2 L; w1 V! M% \9 P
        Clear();
    / m; G) \2 P" D% `8 ]}  e' y* v+ B0 S0 |6 B! {
    template<class ElemType, class WeightType>
    0 v% F* G4 [" N) G& V0 @0 XMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    2 _: `; _8 F, E8 k7 ]0 A! N8 I{- P* f7 }5 o  l3 i3 @
        vexMaxNum = copy.vexMaxNum;- X4 G# b: d5 n/ W3 I
        vexNum = copy.vexNum;" X/ L, p2 C8 M, W, a' e1 J
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    ( u7 T$ x) [7 n+ y4 D# T/ E- |    arcNum = 0;
    " H( Z; F$ j. y, u! m7 l    infinity = copy.infinity;
    5 J) |/ i9 a' m3 F    tag = new int[vexMaxNum];
    ) {7 r+ `4 e, H- S. v# Z0 m' F2 O/ U
    ) A6 W) r9 ~: m* n) n" @    for (int v = 0; v < vexNum; v++)
    : V) c; G0 [5 x% M. ~% d9 h    {
    # ~) y- ]6 M( |9 Y$ |* M2 P        tag[v] = 0;6 |" @6 U3 N" I8 {( G8 m
            vexTable[v].data = copy.vexTable[v].data;
    ! A' a" \6 Q  M7 L) {( G; P3 T% \        vexTable[v].firstarc = NULL;
    6 M0 q( h5 |+ W1 y  W! t' }! ^# w    }" W$ h3 o5 \( `+ ]) P
        MultiAdjListNetworkArc<WeightType>* p;
    2 y7 f* U( N# }/ @
    0 h" ]+ J4 v& t" o0 f    for (int u = 0; u < vexNum; u++)
    % O2 B) ]+ J& j; j& j    {
    0 n* i. b$ g* K        p = copy.vexTable.firstarc;
    : G8 w, G, z% D4 {- [1 F        while (p != NULL)" w5 ]& G* e- _3 h
            {, O. y3 e% I, a- [$ C  v
                InsertArc(p->adjVex1, p->adjVex2, p->weight);6 @$ x& K, J+ n  z! b6 [
                p=NextArc(u,p);: ^8 ]* V1 O* Y
            }
    * R9 n% `" D' _7 M  I    }% q7 e. L% A5 R/ q4 T, _3 v1 A
    }/ `/ ^$ S  X. ~- F6 O0 F3 i
    template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
    9 U; }0 z1 E, d' X. tMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)1 ^3 s4 `' ?% h; s) |
    {
    ( R; v! k. [" [  Q( t4 T; H9 i$ z    if (this == &copy) return *this;
    ! }& K  U4 \6 Y1 h' Z  @    Clear();
    " G! @# N& @3 i6 [3 j% b    vexMaxNum = copy.vexMaxNum;# n6 o- k! `% |' N5 H* D
        vexNum = copy.vexNum;
    8 [0 b2 b( W( E2 y0 I$ i1 _5 x% X    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    ; U. y# ?7 S1 @7 q' `    arcNum = 0;
    ; m1 \, I6 K7 j    infinity = copy.infinity;# L) ]4 Y# X1 B% i4 h( q2 a
        tag = new int[vexMaxNum];, g- a& n  u: g6 C
    2 _7 b+ x3 Q; V* b3 {( o% @2 ^( G
        for (int v = 0; v < vexNum; v++)
    3 r& t4 @- L4 z- [  g6 d* q$ l1 o    {8 c* w( X, u0 T! I
            tag[v] = 0;
    2 |' P4 j2 G* s5 i9 h2 `1 Q5 b        vexTable[v].data = copy.vexTable[v].data;2 ?, F# p* H9 _! P
            vexTable[v].firstarc = NULL;
    ! Z2 I  i+ y. g+ B6 P' A7 Q    }" d; @, f& {) S0 j; o
        MultiAdjListNetworkArc<WeightType>* p;4 X2 C3 k% A' D+ c

    ! J) O* C9 b- U    for (int u = 0; u < vexNum; u++)  z; e$ h9 R! L; @( S% o
        {  \3 o; e) U+ ^; }; Y2 r  K# C
            p = copy.vexTable.firstarc;
    + ~. |3 N0 ~! T        while (p != NULL)
    2 x+ K( d. o9 W+ m' s$ P3 H        {
    ( B/ m% o7 ~: k+ V            InsertArc(p->adjVex1, p->adjVex2, p->weight);. Y2 z% l' [( Z% l) a" `) ]4 |7 C+ I
                p=NextArc(u,p);
    4 i. J% @9 d% q" X        }8 }; V3 Y0 C: k9 k" c5 Z8 c6 f
        }
    * ?# C# B; ~! s* e$ \0 A- g    return *this;2 K% r4 [. z% v
    }
    ) q8 |3 h% c4 d4 {* I& M0 Gtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*- l) ]7 h+ q. W! @5 J
    MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const2 z( F( |/ @, ]$ L5 K
    {: L! z2 n+ |- p3 P, A4 |
        if(p==NULL) return NULL;* `/ H% R! t3 I' J, H
        if(p->adjVex1==v1)  s; t3 G! x. s6 a! X+ f; M: N
            return p->nextarc1;* a; @+ [  w9 Q% a
        else: Z- I* k; v7 v% N4 Y6 D% s! R
            return p->nextarc2;  T3 F# }( k9 V) L2 I" A% h! p2 U+ y
    }
    % y) v! H2 ^, J4 Ftemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
      @' ~  J5 G: Z1 XMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    * G- t( h5 P" D{0 K- V+ q! G* Q& {. _% j8 ^
        if(p==NULL)return NULL;
    " R' n  J1 ~2 Q) _& |9 |    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;) V0 [0 Q3 P+ J8 d4 M
        if(q==p)" X: z# i% A0 Z5 @; C  C
            return NULL;
    3 U; o8 ~8 O, \6 [+ T. v: }) {    while(q)
    / j" l3 D1 S4 H+ Z! s) N7 H9 p    {  j5 L6 d1 k/ R, ]  U% s) R
            if(q->nextarc1==p ||q->nextarc2==p)1 j4 x# h$ W# ?: v7 O0 b
                break;
    , [7 Z9 p% q/ ?! t& P/ p        q=NextArc(v1,q);; Q1 y& r8 p" I: a
        }
    1 \9 _2 w2 f( Y" p) k* v3 i    return q;( B) Z" R+ N( w9 C* `: c7 Y
    }  s6 @7 @, t- L. i/ h
    template<class ElemType, class WeightType>" [" ]/ D" a0 P4 t5 {) ?# h
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)8 ]* n6 D% B5 e9 F
    {
    8 h! }5 u5 @) a, p    if (vexNum == vexMaxNum)
    * X8 o( T- j. O- H7 |. u        throw Error("图的顶点数不能超过允许的最大数!");
    ' i, A0 _. e5 r2 ^    vexTable[vexNum].data = d;% I. D$ T! G3 u1 c+ K  b7 h& E
        vexTable[vexNum].firstarc = NULL;
    5 {5 G: _9 w$ f2 F3 ^  O( C    tag[vexNum] = 0;
    ) ]  w. }; [2 f: U    vexNum++;& J$ p% ]) @+ o( W0 q& q  h
    }
    ' _# @+ d  j" wtemplate<class ElemType, class WeightType>- Z; [# Q. W/ @
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
    * s- A' Z0 }" n6 l* I{
    : h& k1 ~" p( f6 Y0 Q7 g/ Q' n    MultiAdjListNetworkArc<WeightType>* p,*q;8 [; V$ b* N+ |
        if (v1 < 0 || v1 >= vexNum)4 ]& q/ J3 N& ]# v2 d
            throw Error("v1不合法!");! q7 I% S3 ~( V9 O
        if (v2 < 0 || v2 >= vexNum)& P% b% Z0 `3 h! o, r1 y
            throw Error("v2不合法!");
    / T. t$ \2 a" T1 P! |    if (v1 == v2)
    ( L( H+ L+ ^7 T5 O        throw Error("v1不能等于v2!");
    0 g" f( j# y- a2 {0 K, n* y. Q5 x    if (w == infinity)5 A- E9 ?. w8 @% I5 O: \. E
            throw Error("w不能为无穷大!");- `) M% `1 Q* ^  ^: c/ @7 c, @

    " R2 A' Z( F9 s+ s
    - G4 E( O/ \" y: c# ], \5 @7 K, I    p = vexTable[v1].firstarc;6 f' e6 C) ~+ ~+ @+ J* k& o& l* y  {
        while(p)! I5 V1 D3 C& }! Z
        {6 X* o: y. C2 L
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中" ^4 `" c/ C3 b/ j3 y7 V& J3 w
            {
    5 c0 ~& I1 l7 h$ y            if(p->weight!=w)
    / l9 Y% G; m2 y7 S                p->weight=w;# m5 e% Q5 W. ~: z2 ?: D
                return;
    1 d- l* L$ c2 r% ^) s0 Y) S' \' I        }
    ' T! H& I; _, G7 K" _8 O8 l! z1 ]# f4 x9 p2 \9 J
            p=NextArc(v1,p);: I' @9 d+ c( [; J1 `
        }3 @' g' N, x* F( l. U4 O
        p = vexTable[v1].firstarc;
    ) V; N; ]) _% r* W5 Z    q = vexTable[v2].firstarc;) O: R4 l1 b1 @# N7 P, K* B
        vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    5 V; ]0 I& d* m7 m- ?! l    vexTable[v2].firstarc =vexTable[v1].firstarc;4 k# H+ [0 H, ~
        arcNum++;8 c: G9 H; F0 i4 D
    }
    1 Y( r$ }  u4 j  ^# I5 E
    * Q* R, e4 I( m4 Ltemplate<class ElemType, class WeightType>
    0 O9 p' r( \) Q( S2 N) Ovoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
    * n+ ^) V9 S) z0 H/ Z8 b' Q{
    2 O& g" B' w; j( f! ~* v8 x$ ]/ u# y  y$ x
        MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    * m+ u1 S5 @* O. P0 @2 z    if (v1 < 0 || v1 >= vexNum)$ |9 P+ v) m# W0 V
            throw Error("v1不合法!");' A8 I4 h2 m) i0 q5 i% O' A
        if (v2 < 0 || v2 >= vexNum)) S7 b) q$ j' Z- B$ V
            throw Error("v2不合法!");
    4 T& P/ M: s' e' T. A    if (v1 == v2)$ B  l& ^: x1 w1 N
            throw Error("v1不能等于v2!");$ f. Z2 J3 I' s( |

    0 ?. {' O) I5 K5 F    p = vexTable[v1].firstarc;0 M& b' D% Z$ i' ^) k4 o3 s
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)" S7 i( s. w' G  O" e' [9 i
        {% M( r# z% i6 T! D! X. c
            q = p;& y0 F& i- V8 `; M$ a) [
            p = NextArc(v1,p);1 q) y" l0 f, ]8 U- {
        }//找到要删除的边结点p及其前一结点q
    . w$ ~1 j- ]- O0 X  y. K9 o8 p" O  R4 g- M- Z* ^2 V! `) u2 X0 I" S4 P/ |
        if (p != NULL)//找到v1-v2的边  Z! N) d2 H" L; ~6 V4 D
        {+ \$ k- e3 ~6 H/ u* t6 W1 Z  j
            r=LastArc(v2,p);
    ) A+ S, D1 R6 j' L6 i. {        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    1 [9 ^6 a3 ?$ V6 x6 O$ s& U, i            if(p->adjVex2==v2)
    ' j! A: h8 m  ~9 z2 P/ F) q( W                vexTable[v1].firstarc = p->nextarc1;
    - _% O& V; u4 X  a0 @* C            else vexTable[v1].firstarc=p->nextarc2;) S/ `& J% e5 k" R
            else//不是第一条边
    4 M- Z7 d- f# Q3 V# E        {7 x. J! a" e2 ?- ?. |/ f: G
                if(q->adjVex1==v1)/ }- w! r- ?/ l( k  u
                    q->nextarc1 = NextArc(v1,p);1 k. V! {9 ?+ C5 {
                else
    + P- j+ M% H7 J) [2 x                q->nextarc2=NextArc(v1,p);
    3 f9 _! V6 l, n2 A7 q! m: b# _; Y2 ]8 g7 ~. O- Y, k9 H
            }$ |% `7 H/ o( n, I7 ]
            if(r==NULL)  n" P5 `$ b$ R' f+ D
                if(p->adjVex2==v2)
    - b5 }2 \# E- j6 E, M' L) M, A5 S                vexTable[v2].firstarc = p->nextarc2;( G  L5 I4 Z5 I) d+ v7 x
                else vexTable[v2].firstarc=p->nextarc1;+ h+ c' R- w- T
            else
    0 e, @0 \& V! g* \2 [* \& R2 N        {
      }4 r- x! r; f            if(r->adjVex2==v2)9 P- i- V8 ^# U; ?
                    r->nextarc2 = NextArc(v2,p);* J5 u- I5 s) W6 f/ C2 n6 `+ J
                else- e7 [  r& H& X. K. P, R8 X1 [! k
                    r->nextarc1=NextArc(v2,p);
    + D  j7 }! Q# O% v        }" Z( @% w5 K+ ]1 `8 e
            delete p;/ g4 L( j( |" {2 x8 R4 S
            arcNum--;
    ( z. `+ P, w0 |9 ~+ y0 n    }
    & K8 I2 i9 R4 B/ o: @* ~/ A( e! {( @: R. {: X7 l" t+ X! E
    }% G1 s8 ^$ ]6 F+ f$ f
    template<class ElemType, class WeightType> void4 X" H, u* _5 S% c
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    1 q# C5 W5 z. i& g  Z; b{
    1 i8 P: O% Z/ g8 L    int v;" T; I" J. J7 G' x! G% z3 ~
        MultiAdjListNetworkArc<WeightType>* p;0 L; S7 V- G2 u6 d: ?* M& A
        for (v = 0; v < vexNum; v++)//找到d对应顶点; M( j( ]1 D' J* ]6 g  }0 S
            if (vexTable[v].data == d)
    4 F3 i* B5 y, L7 ~' \            break;
    8 A: N2 B5 Z8 t6 t9 D( t, d* s    if(v==vexNum)
    - y+ H/ D) J" ?# ?# h" ?& d        throw Error("图中不存在要删除的顶点!");( `, ^" v9 S" m% r4 E: P. `) I
    - s+ _( G# q3 j; D
        for (int u = 0; u < vexNum; u++)//删除与d相连的边2 t% w( Y: R  u9 X  o& N
            if (u != v)
    , g8 d- x# M2 L        {: w: N/ c5 {( e1 [, k* q
                DeleteArc(u, v);3 {1 @6 Z& X! U$ v
            }" p  a9 x9 N* W
        vexTable[v].firstarc=NULL;
    : E# s& R' b; _5 U: S* X6 @4 O8 u: U# E8 l$ C
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    * X4 J$ K. C/ }1 d$ R# Y: Z    vexTable[v].data = vexTable[vexNum].data;) c2 H3 T7 n8 ]2 t' _0 e  \/ \% v* o
        vexTable[v].firstarc = vexTable[vexNum].firstarc;. J" \' [- `5 W8 }. B4 P/ F
        vexTable[vexNum].firstarc = NULL;+ J# p  k, \( h' y. ?7 u
        tag[v] = tag[vexNum];
    - G  Z  t0 f: \/ z$ a6 m( F8 U    //原来与最后一个顶点相连的边改为与v相连6 M& t7 P2 Q; |; {- O4 u5 `# b
        for (int u = 0; u < vexNum; u++)3 d3 h# K& }7 s' }% e
        {
    % m+ s  T4 y3 G. u        if (u != v)1 d! w! E4 J2 I8 ]$ F
            {
    2 w9 B  a. {# @1 G7 x7 e            p = vexTable.firstarc;
    ; H! C% e1 Z4 h0 y7 o, N6 B/ X( m            while (p)
    , ^$ U" Y) Z0 \, E            {
    # z5 x& X* B+ Q                if (p->adjVex1==vexNum)
    # ^- P5 h4 F& v' }/ T                    p->adjVex1= v;
    5 W5 h5 w# U: Q" j6 f* D                else if(p->adjVex2==vexNum)
    & ~& R0 J" @/ N9 I; _                    p->adjVex2=v;; @" U1 [! L+ p. m
                    p = NextArc(u,p);
    ; e. S/ W: k/ _* k2 j* I            }3 X+ A3 E; b5 y& v
            }
    6 J7 u2 b% w8 ]3 y/ X  l! R7 L    }7 J* q8 E( j  R' o
    }( @2 i' w6 y8 O; s
    ///深度优先遍历
    " Q1 o; T+ E  G1 ^6 `5 Ftemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)7 {3 |) y" R3 d+ T0 k" V; Q$ R1 a
    {
    & Y  }! U2 D+ k8 L8 ]4 L) S    tag[v]=1;+ j& ], Q7 r& a# ^% W1 N
        cout<<setw(3)<<vexTable[v].data;
    9 {. V* K8 f, M% Z: t    MultiAdjListNetworkArc<WeightType> *p;
    : d6 u* j6 G* e; `+ X    p=vexTable[v].firstarc;/ l+ O8 {6 `# G3 z( U
        while(p)$ Y) ~/ x) |  t! r* g3 E! k$ R
        {
    6 p5 s6 z3 t! g* s) Q% U        if(tag[p->adjVex1]==0)
    & v9 i- S0 f% _5 Y4 F3 @6 |& ]# X2 {            DFS1(p->adjVex1);" w! ?2 R4 L7 y( j# r
            else if(tag[p->adjVex2]==0)6 l- H6 R2 B. Y. O; y
                DFS1(p->adjVex2);9 t! a4 C) D2 g/ @) e7 A
            p=NextArc(v,p);& ~0 O) |. D! l
        }
    & p7 t4 @  Z  ?* b( L, F3 V}+ b: k4 @( Z" B2 t  r
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()0 B# P; I6 q+ o; D/ z
    {
    # q4 E; @7 T- |3 ]- ?0 y    for(int i=0; i<vexNum; i++)
    6 J. d( n) j+ M        tag=0;
    7 b/ b1 V3 O/ S' z8 x2 @    for(int v=0; v<vexNum; v++)
    4 E: d7 r5 @5 }; J! Q! B    {
    ) ]8 V; ~2 g6 p$ D$ Y2 P        if(tag[v]==0)
    ( i& L: M4 t4 t8 _            DFS1(v);' P6 V/ y7 i( {/ ]
        }
    ; n# R& G/ `1 M* t, R: X}
    % _, r; m  o5 h# n; p5 V: L; stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
    , P5 J+ [' V1 Q1 }6 f. j2 O{
      F$ `5 C0 L/ A    stack<int> s;
    3 m" p. y5 c2 P    int tmp;
    ' i$ R, S0 l1 H$ \: Y9 _    MultiAdjListNetworkArc<WeightType> *p,*q;/ y# j% U4 i5 ?5 c3 I3 v! k! W
        for(int i=0; i<vexNum; i++)
    : X& f5 h2 z" w: w" \) J        tag=0;/ o- \! P; U: d6 V4 t9 d3 R1 w2 u
        for(int i=0; i<vexNum; i++)" `; Q: t  ?! K, w9 E8 f- i
        {
    4 K) Q2 d4 a$ T% w/ z2 ^        tmp=i;; d0 c+ t- m9 k7 Y- J: P
            while(tag[tmp]==0||!s.empty())* v- n4 i. D) R& o! j% e0 N
            {
    & T  C8 I) G3 T  ~3 [            p=vexTable[tmp].firstarc;
    " O/ a% G% y" b! O7 C. Y            while(tag[tmp]==0)6 }2 I9 m2 e# ]8 f
                {  c% Y. I4 }% W' y" }
                    s.push(tmp);
    5 Q0 r( u1 P* D* l) T: X( C                cout<<setw(3)<<vexTable[tmp].data;
    5 u- B" A2 |/ |# ^- v5 F                tag[tmp]=1;+ w9 x' `. K* }; \6 u- {
                    p=vexTable[tmp].firstarc;
    ; }8 ~1 E4 `2 K* M' {& R                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for# }" [, r6 ^- i) r# W" h
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    0 _1 k4 m  H4 P& X2 q9 }& t                //cout<<" 1st     tmp="<<tmp<<endl;
    ) \3 Y1 x/ m0 o* x. v            }
    ' T9 m8 W. a/ s: L; ]1 `            if(!s.empty())
    ! ?/ A6 }% C6 m4 U# s            {
    . `: H" n% A  C$ ^. t7 v7 R* Z                tmp=s.top();
    ! @& ~+ e  {+ |9 c                s.pop();7 }  _8 A3 H) k- u9 t
                    q=vexTable[tmp].firstarc;1 d! W% d- T5 b' ?* A
                    int t=tmp;" y& K) V1 Z9 k4 D
                    while(q&&tag[tmp]!=0)
    $ m% z8 ^' |% }% U& H* S$ R                {
    ) x7 C( A6 ^3 N  h                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
    3 T! j8 s. q) n  a1 @+ N  l                    //cout<<" 2nd     tmp="<<tmp<<endl;- Y1 s4 i& x% T0 |1 X# C$ _' u
                        q=NextArc(t,q);
      p; k$ ?4 _1 L5 _                }
    * R* y) }7 R8 ]. `                if(tag[tmp]==0)
    " u6 T! K  w% a                    s.push(t);# {- u' k# J( P: v) d
                    ///1、对应上面连通分支只有1个点的情况
    ; |) Z# _$ ]/ T' M& \' B& A* {" O' E; H                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
    3 |2 [7 _& S: [' u! C                ///tmp要么等于找到的第一个未访问节点,
    * N* T6 O4 q1 F4 A1 \1 T, Y, |' v' s                ///要么等于与t相连最后一个点(已被访问过): z: ]' S) W7 I
                    ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    ' @. \& O" u, p+ a* o9 L            }% N, Z8 U2 d, Z1 l* ~6 b
            }
    ( h# W2 j7 F6 p% c% X# S    }
    / N, J, ^+ M3 {0 F6 [}
    ( ]" o6 f- a* k2 {. J; s//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    * x. Y" y8 V: e" @3 R8 Mtemplate<class ElemType, class WeightType> int7 }0 ]6 r) x7 ]3 n" O# m" ]
    MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
      q5 c7 h7 C6 }$ b2 h{
    % m& C, W% g& D  D+ ^* Y    if(head==pre)
    1 @- x+ Q+ h, _0 R' p        return -1;
    , [( C2 A5 V  \/ d
    0 t4 @- Z# w1 o4 U    MultiAdjListNetworkArc<WeightType> *p;
    / z( y) _; e. k6 X+ ]7 J    p=vexTable[head].firstarc;7 S9 o; d1 J" j7 G9 |% y9 O, o1 a
        if(pre==-1&&p!=NULL)6 m) c# z5 e8 A
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
    * t1 n# }, |# e' H7 f: ~0 D$ F5 b4 L    //pre!=-1&&p!=NULL& j: v8 n7 n. H1 R$ r) _" I
        while(p!=NULL)
    " l3 ~. A. Q( l. X6 g    {
    0 [4 k" ~' Z5 r3 s& K) n# F) H        if(p->adjVex1==head && p->adjVex2!=pre)
    1 i2 W. N0 |4 n7 Q1 u            p=p->nextarc1;
    - j$ ]" ?4 Q0 @. N5 \/ L8 P        else if(p->adjVex2==head && p->adjVex1!=pre)
    ) {! |0 i1 i, a' ~8 P% s            p=p->nextarc2;
    . i+ O( a2 X. r# I        else if(p->adjVex1==head && p->adjVex2==pre)
    ( o% p9 `: q. c& W+ ^4 y        {# w/ U* G/ q; y! I( }
                p=p->nextarc1;7 X' I3 |+ |$ e$ a
                break;
    ) D4 G" V2 u; L. w$ H8 |* c        }1 R5 a2 X- k. Z! a
            else if(p->adjVex2==head && p->adjVex1==pre)
    0 W5 N% C+ Q6 N$ n9 w( d* v- B        {8 }, O; I+ c2 ]: L% f6 F/ E
                p=p->nextarc2;
    / x' y1 ^: I" w( }            break;3 e, [6 R4 R. ]( O
            }
    4 D& J- q) V. y' _/ g    }& b$ f) u6 G0 o% o: E/ N6 d# d
        if(p!=NULL)4 H4 R4 O! ]( L% c% }$ A4 V9 H; o
        {: H- x1 b- }2 P. N7 X
            return p->adjVex1==head?p->adjVex2:p->adjVex1;0 M- A/ H; ~) b- U# a* w
        }: w# U) V+ l* y, G- X' y
        else" l9 g% s$ M2 j4 ?1 v
            return -1;
    : @( o3 Z( ]; j}# d; I: g1 C; M- X& x
    5 ?! q) P: M. r/ a+ g( Y
    4 V; p7 R" ]$ r  Z- i5 K- a
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    , X- {0 q  w6 M. q7 W  i7 K{
    3 S! _) K+ ^# t    stack<int> s;
    ; q, C' U3 E4 a    int p,cur,pre;
    9 [: H( L9 x9 {% E- `3 B' ~    //MultiAdjListNetworkArc<WeightType> *p,*q;- U; x; \9 C& @" C+ ~' l5 P* }) J5 t
        for(int i=0; i<vexNum; i++) tag=0;//初始化
    / h. c$ E0 v1 t: V4 l! @- t* Z% _6 W
        for(int i=0; i<vexNum; i++)0 u: f4 P; n) _
        {# b2 X7 v4 r, w$ @$ e, x
            cur=i;pre=-1;" S# _2 Z' [7 K5 S
            while(tag[cur]==0||!s.empty())4 q  F* r7 ^% w. P5 ?* c( \
            {3 x  x) L6 M8 ^& q- j
                while(tag[cur]==0)
    , b3 j  m3 M! o0 J$ t2 A            {7 K0 n; H. e) }( p% \
                    cout<<vexTable[cur].data<<"  ";# v3 i- v) q6 k7 `# ^
                    s.push(cur);" k/ F! i+ j$ w: m& _
                    tag[cur]=1;7 j9 ?. \! ?: I% V# s
                   //初次访问,标记入栈
    0 b; {" m, u5 ~- M: }1 `
    ' _# W/ e+ ]2 r2 I' r  z& I               p=GetAdjVex(cur,pre);//p是cur的连通顶点
    $ h6 I6 ?2 H" @) Y- r- \% s+ O               if(p==-1)3 R& _2 n7 D+ A8 Y
                   {
    ! a# v4 a3 s4 k$ ^; c1 [( t0 N                   pre=cur;s.pop();- @$ r+ q4 }) Y4 w# h
                       break;5 I- c# |; ]* O: {- ~- q8 n* |
                   }" o8 D( c4 d8 r- b$ s
                   else: z) ]) H; L1 w
                   {
    4 P/ N1 H: W: g# D" `& B                   pre=cur;
    3 e6 ~- K( ~% ]( r* I                   cur=p;
    ( r7 U& g9 z: L5 t               }
    9 ]& N$ d! n- v1 }9 ?2 {% U
    1 a  u9 I2 G% Q( g& X1 U            }* B" o) Q6 t0 y: V
                while(!s.empty())' F- k- `1 S( J, Z/ R
                {$ ]4 T4 z; ]6 O' X3 N3 U# j
                    cur=s.top();
    & t3 g8 z' y4 ^, |' D5 W                p=GetAdjVex(cur,pre);
    : f- d$ O9 s' F- f8 T                if(tag[p]==0)* i8 L1 }7 A8 o6 [, B) i4 v
                    {
    ; v, D: r+ }+ ]) R                    pre=cur;
    ' x. D! H. D0 D  L! Z                    cur=p;1 ?5 \6 O5 j: t: m$ B& k, L
                        break;3 }0 p4 X3 p. m, R( l3 `% S
                    }( X0 t# |2 N/ f
                    else
    & V, P2 y* ~4 H- a: X                {! C9 q$ ~+ ]0 ^2 h1 i/ F
                        pre=s.top();
    6 l7 f2 a- I; v6 `$ {2 @  _                    s.pop();' L( t9 @( Z4 z
                    }" f( \5 @. H5 Q+ T- w% V6 A1 d: K7 N

    / b/ T* e- D% b" ^8 D7 @0 b$ U- E            }
    " S  Z' W8 W1 R9 e- U! k; W7 x
      l, n. s/ z9 Y; g7 p        }. [) ~. I7 g  Y6 i
        }
    / k- o; G; O" m5 ~" v5 S}' n( w+ v0 v5 j+ }! D5 B
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()7 S' C: y5 |7 l  x8 m  x* h& S
    {; W3 f% o( W+ I" V9 ]
        for(int i=0; i<vexNum; i++)0 Y# m. @# @1 ]8 |
            tag=0;
    $ }: q& d* A* ~: _  H# ^9 c; D    queue<int> q;3 A; d9 x, p. J) z# F. v
        int tmp,t;& ]$ ?, c( o# Y2 |0 C
        MultiAdjListNetworkArc<WeightType> *p;- ^1 L0 \! N! t: A3 E/ c; y$ v" y
        for(int i=0; i<vexNum; i++)
    " M7 J1 @( C9 l" P3 ]' f; ]# ]% e    {2 P5 T: c6 N2 I& ]. y
            if(tag==0)
    : [9 |+ U+ C6 A+ ?6 A/ e% ~        {
    ! [- e$ V% S: v8 R7 H- a% P            tag=1;
      |: J# [2 o0 j6 I. B            q.push(i);6 t, k+ F1 c& g0 K. g0 ~
                cout<<setw(3)<<vexTable.data;
    6 u, o0 D5 j; x  j9 M. `+ |        }
    $ |1 }& A. ^( b3 Y" `; \* C- ?        while(!q.empty())1 |+ O; w; r3 z/ `5 l
            {
    7 \" u% L( U5 y+ i+ M# c/ n; K            tmp=q.front();
    / ~3 l* P# _! `: R: [9 H            q.pop();
    ( O- D4 J, A  z            p=vexTable[tmp].firstarc;
    + U, G. [! G% d            while(p!=NULL)2 I1 i1 b* A  S! s
                {
    + p% y6 ^) a9 E* N+ W                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& u: h; T) }! B& C1 ]+ E7 |2 K
                    if(tag[t]==0)
    0 A% j5 Z. Q; H' [- Q% O; M1 c                {
    5 Z& H/ N( u- F" L" T& ~                    cout<<setw(3)<<vexTable[t].data;4 x$ z2 O+ w! M/ L1 ?0 ~* R" q6 s
                        tag[t]=1;  s3 R3 T! \1 h, C
                        q.push(t);8 _: Z* u" {( `$ s$ k
                    }* f2 u: z' Q4 \; f- M% m/ O
                    p=NextArc(tmp,p);
    8 E5 U$ f$ }* }! @4 k1 {  Y            }
    5 U( Q9 {% I: X        }
    9 q' j+ o  M- e! x! D1 N    }
    & }7 Q/ W2 A5 U% ]; w1 c2 ?- C}" E4 _3 s! N: J
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()' Y; \& Z* y2 G2 |: m5 ^+ G$ g
    {
    0 Z$ O5 P3 U; \    MultiAdjListNetworkArc<WeightType> *p;( z' B2 ?0 y0 i7 ~- N7 c) u( J
        cout << "无向图有" << vexNum << "个点,分别为:";
    4 X/ C" k% M$ ^( k8 N    for (int i = 0; i < vexNum; i++)
    ; R7 i+ \5 O' E7 n3 F4 d        cout << vexTable.data << " ";: Q1 Y5 r# Z" d: Y0 H
        cout << endl;
    ! f, Z) u; r" P) U- A. D  `9 b$ ~    cout << "无向图有" << arcNum << "条边"<<endl;+ M4 c* k, Q, J
        for (int i = 0; i < vexNum; i++)! M: O  `0 f' \7 O+ R
        {4 s9 P: h% a$ ]1 X/ C
            cout<<"和" << vexTable.data << "有关的边:";
    + f1 ^: a6 a: L& y& K5 ~        p = vexTable.firstarc;4 X1 g  T& ~% C
            while (p != NULL). s, B; r* ~( h. }( o2 l
            {
    : I1 X2 A  I" u  s; d            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";! N: O- r9 E% o  G
                p=NextArc(i,p);$ l4 `9 I. Q: j5 X2 ?9 N
            }
    4 F! |* H1 ?9 {8 i: U& j( C        cout << endl;5 S: }6 l* _6 k7 j7 R% R. X4 [6 Y
        }
    * B; p4 [2 X* C4 x$ S0 C}
    6 ^+ R  V. E0 c# U, E: B* t7 ?$ n
    $ j: s/ H6 s/ Y& o2 V, V1 |. L- O- g( R$ z, ?; |
    邻接多重表与邻接表的对比  @/ T9 [+ D6 t- r* o6 i

    9 I+ ]; G8 f0 {5 @邻接表链接; Y3 B# o- `" C
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
    9 p. H: e' V7 w& n1 v' i在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    # M& p+ N/ v7 y  i为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。# q3 ?( J% u; p
    ————————————————
    1 M0 L) U- b' y4 C$ K* ^; L( ?$ u版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。0 z# i/ {! k5 V6 ]% K8 U1 C, x
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    # M+ c3 ^, o6 Y1 h6 u; h& W& b- w$ w
    5 Y6 h6 v% r* g+ o# T2 j* G/ u/ Z

    - e( e$ M9 ?& Z- ?* P2 ^' l% }2 j7 O. u; W
    ————————————————7 _5 |! r' s: }9 P: `  M0 ?3 f4 B
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    ) y6 M8 }2 f( S# s8 Z原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    - R: k0 r& G3 D4 k+ k" S9 I1 V! s

    / [( x8 W9 X/ d# K: ^1 C
    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, 2026-1-3 08:35 , Processed in 1.795248 second(s), 54 queries .

    回顶部