QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1525|回复: 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
    1 p! m- p' E1 A. E7 x
    图的存储结构——邻接多重表(多重邻接表)的实现; I1 ]$ X# H) |( t2 K8 ~
    7.2 图的存储结构
    * r1 y( V1 [1 F5 l. c# q4 M. b% q% i# N6 w  p
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist$ \' k1 g+ ]) m; ?, Q+ q8 _
    邻接多重表的类定义: |; a% X. M- g7 }$ l$ J2 G0 [
    邻接多重表的顶点结点类模板" c) \+ G2 E) Y& f% ]1 t* O* @
    邻接多重表的边结点类模板
    / g; }1 z! {3 E邻接多重表的类模板- v# A+ b; w4 _* @
    邻接多重表与邻接表的对比
    - V# u0 P. u- D" ]  V! p7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    ) u( I0 D* G7 p  ~8 p- p2 G2 t9 n; M1 m( t
    在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。2 m2 x2 z5 M. Y2 W5 Y7 B
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    ' W+ B1 ^% ~8 \8 Z, \9 T) h& E" Q* p1 G; F: n0 ~! ]
    邻接多重表的类定义
    ( Q" |3 G( s$ a+ Y2 Z. g) y. u% w 1.png ) R1 z8 J" V3 m2 I) ]
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:9 d& f9 `) N7 d. B, d
    data域存储有关顶点的信息;
    - y* u( H4 T: `firstarc域是链接指针,指向第一条依附于该顶点的边。/ g. \1 T5 H6 i7 e) n: T
    所有的顶点结点组成一个顺序表。


    + A2 x( w' E- X& C$ j9 f+ o9 s
    $ x# D5 J7 ^, t  Q* I4 Jtemplate <class ElemType ,class WeightType>! k* K  g* u- b
    class MultiAdjListNetworkVex
    2 A5 g# K1 i: c6 @" A9 y{
    5 Q7 x# L/ G; xpublic:
    " d; t2 p6 @& Q: Q$ j1 t        ElemType data;
    : g+ M  X3 v9 B! t( A8 x4 v* V        MultiAdjListNetworkArc<WeightType> *firstarc;
    3 s5 c0 N* ~9 D5 F* ^9 |
    / e0 d) f/ @8 R4 x8 d* Y7 u        MultiAdjListNetworkVex(): ]; X# U( D% x( g
            {
    - r* l; ]4 _: a6 I$ l6 j                firstarc = NULL;+ \6 f  E+ B1 |. Z9 I% R0 ?' M
            }- X$ s# H& S2 z/ g
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)7 h6 e, D+ h, U0 s* r. l
            {
    + g3 ~) S6 b& P( x: {% e, i                data = val;
    6 ?  @, _; T; M8 D" ]' R                firstarc = adj;
    3 I& z$ F) {$ w- T9 I        }
    ' J3 G6 @- K4 z8 G% A};7 P* w2 H2 Y4 W# ?
    ) @' i, s$ E! f7 z1 [3 I  X
    邻接多重表的边结点类模板) D/ z( a2 T" `9 Y1 J

    $ G+ |8 C: B6 c5 R, }- y在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:7 K1 _9 h$ L' X% L& L# s) L
    tag是标记域,标记该边是否被处理或被搜索过;  n. D/ W9 x0 m# X/ g0 b
    weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    4 z/ j0 z8 o* @1 Snextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;/ T& F' o, n+ P9 f" ^
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。4 g: P" L2 }$ z. N5 |. ?
    0 |5 C+ m8 ~( J4 S' ~( z* {
    2.png
    - {5 w2 e6 E7 Q) N# D. rtemplate <class WeightType>
    + ?+ k2 f+ Y% t: @" s" \4 Eclass MultiAdjListNetworkArc8 G" Z' g) R" h
    {* K# v! ^( Y; U1 k' X# R
    public:5 |' J& Y/ m7 Q& g
        int mark;                                       //标记该边是否被搜索或处理过
    : w# o8 s. ~/ g! |$ @& P4 Q        WeightType weight;                              //边的权重
    1 B+ @0 h$ Y5 `( S        int adjVex1;                                    //边的一个顶点
    9 r. H2 s2 n6 ?: H( E1 g" l        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-18 o$ y5 ]7 \. E* Z9 I* I# _1 T
            int adjVex2;* c& J- V5 l; v0 f2 l) ~& E
            MultiAdjListNetworkArc<WeightType>* nextarc2;
    ! z1 K: }1 m3 Z# }" f
    7 y3 ]: q) C! w0 b/ x( E, R2 A8 s        MultiAdjListNetworkArc()
    / P: ~, K  t6 ~  `! n9 F        {
    ' D7 @% A1 e/ i$ N9 f0 v& J                adjVex1= -1;3 j: A0 r; e7 F* e5 ]9 A1 V
                    adjVex2= -1;! g+ K2 A2 w" F2 K2 I, N8 U# p9 ^5 J
            }
    7 b: Q) J8 x1 d$ s0 g        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)2 J, R5 T5 h2 N3 T3 s5 H: c9 T
            {/ U+ @  V! U) D  e) S
                    adjVex1 = v1;       adjVex2 = v2;
    3 n! [( H1 M1 L6 t4 I$ H( c                weight = w;1 K$ x# \) u) L+ W
                    nextarc1 = next1;   nextarc2=next2;* J3 Y" W; Z' y. @: t8 B" Q- I" `) i
                    mark = 0;           //0表示未被搜索,1表示被搜索过2 |5 z6 r3 R; m( y" `
            }; Z% n. T# |) K$ W

    0 R, a1 a/ J2 Y* c! y5 ?8 w- g邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>+ ~" O8 ]8 M3 q
    class MultiAdjListNetwork
    ( u" D  I$ B0 W2 |3 N- g0 G{0 }- }$ U; B/ I: z: m
    protected:* ~6 |2 [5 A0 v  Q9 z1 f  \
        int vexNum, vexMaxNum, arcNum;
    4 L4 h) ~+ F" c, s/ M. t' A    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;1 `& U' w2 S$ l3 ]9 v* Q/ u
        int* tag;9 a. ?$ P5 P4 b, Y! o( y, S
        WeightType infinity;
    / z8 e: v# ?" j9 _9 p- C" m4 x7 \! ~: x  M, P# a
    public:; t; B4 W. _( T
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);8 _8 R! z0 M& K; Q: Y; y
    8 P7 i2 e7 X2 [$ n# r3 Y# [
        MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    5 T3 Q" ~6 y% J4 g# N" Y6 P( }4 v/ b- M
        void Clear();
    7 \& |3 K0 I' {4 p, M7 ]+ }    bool IsEmpty()3 G3 r2 F  u7 x/ s& x9 K
        {( v7 x/ G% c! D1 z8 N
            return vexNum == 0;
    6 L% k+ A) Y: ^5 e1 }3 l1 J    }
    " J2 m: ~: s) o' d5 P    int GetArcNum()const' o% y8 o0 T4 n. R$ j, N1 I
        {
    0 V0 y4 r6 ^0 |  {( V/ u        return arcNum;
    : h, t5 N1 y( [$ M3 f    }  t( Y/ f1 g% |* N: K% |+ m+ V
        int GetvexNum()const& ?/ N1 u! j! [! Q/ v6 `
        {
    . O- |7 p( |8 j' i, V        return vexNum;
    2 t! _: H* d9 g" Z4 V9 O1 v1 ?    }+ r# m7 Q) u! A" \) W6 l

    * ]. k  g& W9 e" O: q% |; j+ o% f1 t$ z1 G9 B  F( o: l' H' a
        int FirstAdjVex(int v)const;
    ; D6 u: V$ h; s8 e% u/ B    int NextAdjVex(int v1, int v2)const;
    6 j" r0 h/ V4 O' K1 o( s( n" ?    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;& C0 q: F$ ~4 M4 K
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;; C6 N: l8 K8 ?

    ) i9 c/ x( F. d% Q    void InsertVex(const ElemType& d);
    0 v& Q: X. P3 a4 w! N, d. D7 }" T    void InsertArc(int v1, int v2, WeightType w);7 u" R' n  t  q9 L

    6 L! T1 I: @, V1 Y2 Q7 C9 X! W    void DeleteVex(const ElemType& d);
    * \6 q. `$ ~$ s. p# @    void DeleteArc(int v1, int v2);
    3 ^+ Q% ^! \7 {6 q3 R. ]  @3 P* E7 ~8 F* c+ V6 @
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);% N6 a- K6 @* p: r- Y( u& L; ^1 g
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
    8 `4 A2 J) g( J8 a
    2 q1 ]- ]  k$ ?5 q+ ^+ S    ///深度优先遍历: f( ?8 P8 s. V
        void DFS1(const int v);5 r, w; W+ p+ S: p
        void DFS1Traverse();; A1 H( C6 g; [4 \
        void DFS2();* ?& R$ x3 \1 V; a+ ]# p5 S8 ~
    ) Y$ _( \8 c3 O* A+ h
        int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    ' J! a9 q, P2 X! L& d    void DFS3();
    ; P( `* t. k2 \. x" c6 w$ Z4 m0 A: Y! g0 P% P6 ]
        void BFS();
    ; ]1 J7 p8 L& U3 }6 l2 N    void Show();
    ; C7 Y% r/ h* H};" M5 K/ ]/ i, j; t9 K% _" x1 l

    & t( c9 R1 z" W( d2.函数的实现% V% N8 B- x$ K6 p
    研讨题,能够运行,但是代码不一定是最优的。& r% k2 a1 L) t$ @
    ; W: B9 d/ r1 d' C( A% j: P0 n
    #include <stack>
    7 L" l3 F( Q" w; `* ]* j' O#include <queue>
    0 D4 ?% S- P' b- `  o& d+ `7 D, Q6 a3 z2 p0 U9 s$ u
    template <class ElemType,class WeightType>+ D# G3 u8 ^2 `
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    % L- L4 O4 q/ O{4 r2 o) g+ E; m5 O! I
        if(vertexMaxNum < 0)7 L7 N( }" z8 W% k7 ?
            throw Error("允许的顶点最大数目不能为负!");( h$ N" @! l* a, y7 F
        if (vertexMaxNum < vertexNum)0 T& z% `+ ?8 J9 c, g0 O' R7 o
            throw Error("顶点数目不能大于允许的顶点最大数目!");7 H( h1 g5 B, ]& m' ~) t
        vexNum = vertexNum;
    # B+ z7 o- t! \    vexMaxNum = vertexMaxNum;9 v' p, }$ ^8 u0 y* h0 r0 e; V" z
        arcNum = 0;
    ( T% y' h. c4 E( M! j$ b    infinity = infinit;
    3 T' D  _2 s: [    tag = new int[vexMaxNum];6 s# `$ j8 ^/ s" Y/ w: R( v
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];( T9 a6 L4 h1 P) R+ G
        for (int v = 0; v < vexNum; v++)
    " j/ c3 s7 f% k) m3 B6 c    {
    2 o2 t1 B2 ?4 U% w1 `7 D0 @7 e        tag[v] = 0;
    7 _- q2 Y  Q$ b/ J# Y$ W2 J  c( m+ k; N        vexTable[v].data = es[v];4 C/ D3 h, y, |4 s- W
            vexTable[v].firstarc = NULL;! h9 e' K' e. U! ?
        }0 z7 r' c' Z6 F0 ]6 D
    }
    ' W. }( e( g. p. Q* G& dtemplate <class ElemType,class WeightType>
    ' J. H! v$ l, V  h3 O6 {; LMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    & Y& \4 F0 p% p2 a$ k{; _" q  n0 X5 K3 \$ U- R
        if (vertexMaxNum < 0)( j( s8 T: X  M+ c+ C; d9 R' ~( ^
            throw Error("允许的顶点最大数目不能为负!");
    7 G5 Y1 C- M7 t4 j1 X# u, I    vexNum = 0;7 @2 J. T( T7 L6 q( i0 F4 }
        vexMaxNum = vertexMaxNum;, D* b' a& o1 w0 C) H
        arcNum = 0;
    ( K: M2 i( s! J8 F$ X' w% e    infinity = infinit;" q' d8 F4 d, s% Z7 z- N
        tag = new int[vexMaxNum];
    1 X& ^& l1 R+ w7 q0 y" W* P4 n    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];6 F: e" R& d* k" H
    }  H. d" ?2 v. B5 N
    template<class ElemType, class WeightType>
    . p3 D% W" R/ g3 x) ?! s* X, b* xint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    3 [. B$ C" b1 A, P" e8 t{+ L% A: _; x7 v, x# |
        if (v < 0 || v >= vexNum)
    & _7 N. l" v" }- e! \! T        throw Error("v不合法!");
    9 f# t- J/ p2 e" F8 D6 r/ ]    if (vexTable[v].firstarc == NULL). h8 r, U) {+ t. l: i3 p3 h$ u
            return -1;
    ! v! I/ `, _. Z" A* D# h    else
    * I/ j( X! S& u        return vexTable[v].firstarc->adjVex1;. M2 \" w+ o- }, j; \5 r
    }
    ) N4 r$ b) s' v! a0 J- r' G5 P& w+ b# z
    template<class ElemType, class WeightType>
    % l2 g' v& [! ?% W/ eint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    ) ^3 `& b. a' E1 f1 C$ A# v( Y{$ v, `2 R6 }1 C8 d  H1 ^3 {- I
        MultiAdjListNetworkArc<WeightType>* p;
    0 j* Q, m  C7 j8 J) ?3 ^    if (v1 < 0 || v1 >= vexNum)& q: N8 E8 G2 ^) u+ [- u
            throw Error("v1不合法!");* I# Q  S  k' S) Z: Y6 U
        if (v2 < 0 || v2 >= vexNum)
    3 Z, y/ @- h. H        throw Error("v2不合法!");  C! B. [$ e4 V8 L& y1 N. @
        if (v1 == v2)' C' q9 E, A) f2 y5 g7 a2 a" M
            throw Error("v1不能等于v2!");
    + t$ ^) G& Y8 ^5 A    p = vexTable[v1].firstarc;
    ( E( d  z# B2 @1 l) }. f  w3 O    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)! G/ x, l6 _* v$ Q) i
            p = p->nextarc;
    ) u0 R) T. t4 ]5 M+ R+ M& d9 ^    if (p == NULL || p->nextarc == NULL)
    1 T( [% I) Q8 h) j        return -1;  //不存在下一个邻接点. _; z* @' w" d/ C
        else if(p->adjVex1==v2)
    4 l; p& r. @1 Q8 Z( [4 _        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);5 M$ E+ [. H3 M- T% K* a2 e# Q
        else/ {$ z' H. V7 J* |/ z# J7 P( k
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);, J1 |1 `- T, h; S# @1 D( W/ d. w
    }3 l9 ^- i, \* Z! z
    template<class ElemType, class WeightType>
    : I" v0 X6 K: Q7 C# Y$ M" _  b0 n) h0 Zvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
    ! S: v9 l  q9 k0 j, v9 d{& L3 P/ h. Y8 z) C; O% `1 H5 ]
        if (IsEmpty()) return;( A4 B: F. s" Q. U" |! y
        int n = vexNum;
    ' L9 \& c1 i1 U. u1 `8 _    for (int u = 0; u < n ; u++)+ s; r. N% F0 X* H/ z
            DeleteVex(vexTable[0].data);
    ( @6 r7 O9 N2 j+ _1 V+ J4 t* z- S    return;
    & [. ^6 _+ A" k8 e" p6 @( g! h}
    . K4 v$ u* X$ E2 y) ?% c; Btemplate<class ElemType, class WeightType>  I9 O. j. T9 K, I5 e2 x
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()9 {" v& j* A2 z- B% d  L" k+ f
    {0 I# W+ G$ ^7 m; i# d$ w8 J
        Clear();
    2 V& Y0 m" e2 Q9 l* |5 b' I/ Q}
    ; p# M% z3 u5 `: L0 Mtemplate<class ElemType, class WeightType>
    4 D* [1 g) l9 f$ q( kMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    3 ?0 O$ k3 n! v: O5 C{
    3 H, t4 u1 |& b2 J9 ^+ Q( L. M    vexMaxNum = copy.vexMaxNum;9 S. a+ G+ a+ `% ~) \% S8 s
        vexNum = copy.vexNum;
    4 T8 ?6 z& W5 d9 v( c- v& Z/ p    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    / P  e4 F% Z1 \0 r+ e7 j: c: Z    arcNum = 0;
    + \% `# y; ~! G1 J$ R% X3 f: q1 }    infinity = copy.infinity;1 n0 t3 ?7 r& K% ?) c% X9 q. J4 w
        tag = new int[vexMaxNum];
    : {5 G  k. O$ S4 {$ t
    ( n: G( w$ a9 K) v, i+ g7 L* }    for (int v = 0; v < vexNum; v++)
    ! U) ?4 }) Y7 @3 |/ j7 t. s    {
    . L  A% K2 Q7 ?0 w9 `        tag[v] = 0;
    2 j. T# w( Q0 {  d/ }% J6 C; q! b        vexTable[v].data = copy.vexTable[v].data;- e. }0 ]( i4 o. _/ n4 D
            vexTable[v].firstarc = NULL;) h! b1 b3 u1 F$ i* B- E
        }
    & @6 w1 o: ~: K4 y7 h    MultiAdjListNetworkArc<WeightType>* p;
    . r  Q8 G$ w# I+ A7 C6 ~8 F4 Q; ~
    6 K/ I  O& B$ t& D( [    for (int u = 0; u < vexNum; u++)" h5 G' y( j. c- k$ {% P5 V" S! e6 p
        {
    & f7 X2 S- j/ c, a        p = copy.vexTable.firstarc;
    + l: i7 v4 @8 o- _9 Q+ K4 y% ~, j        while (p != NULL), H, z! r$ {5 Y& f0 `% \. m6 B$ Z
            {2 l* C3 q) F: D
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    5 N1 W4 t! N4 }7 ^- f            p=NextArc(u,p);# f" h0 o. F) s* q$ F5 A- o
            }
    4 B( o* r$ _( C" x    }
    ( R, f1 E* C+ J$ K9 D1 b  X}6 Z- H" U& C" y$ M  j3 ]
    template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&' h/ T4 o4 b, |- k2 _/ P6 n
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)/ X* ~/ K; i! a# q5 y% a
    {
    * n. f( W, ?) n0 S4 F    if (this == &copy) return *this;5 J! Q0 v' V" c% Q
        Clear();* `" n& Q# ]+ n* s
        vexMaxNum = copy.vexMaxNum;! n! @' ^8 N* W* ?, \( y# t8 D9 T
        vexNum = copy.vexNum;9 a6 o5 L: k* b  p, o4 Q" g$ M* O
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];* K2 X3 V, p4 v& Q) }" Z% H
        arcNum = 0;
    4 C+ S7 G6 m- g% ]0 T- M2 N: A' g' H    infinity = copy.infinity;
    + F+ F( L0 f+ V. l/ }2 b    tag = new int[vexMaxNum];
    ) t" l9 Y, A& K/ z0 ?& I' W) ]8 C! w2 v% V. S
        for (int v = 0; v < vexNum; v++)
      ]; {6 X/ k& Q    {
    ' h& n5 p! P, n        tag[v] = 0;9 E- Y9 v2 ?0 k) [
            vexTable[v].data = copy.vexTable[v].data;& \) E! ?2 D4 Z7 u$ l5 }
            vexTable[v].firstarc = NULL;4 y3 {% s3 T4 X/ _' o& y
        }
    0 O2 n6 s' U: Q    MultiAdjListNetworkArc<WeightType>* p;/ P) k- |) z. K$ K8 G, f0 B' |

    2 v+ V3 {8 Y7 m$ I# S    for (int u = 0; u < vexNum; u++). I; ]: C# F: S- o# i* b
        {
    + Y2 {) F; x2 x        p = copy.vexTable.firstarc;
    7 t: m) d9 e; d& N7 E5 ?        while (p != NULL)
    2 S4 G' ^- j" Z9 w        {
    , I0 w& s5 e8 A, l, i& n            InsertArc(p->adjVex1, p->adjVex2, p->weight);
    ' A/ I% p3 P- D" `8 K) W* g; t            p=NextArc(u,p);
    ) _; A) p, w0 }! q0 w, u        }3 ~# I  x2 P- ^
        }# O: a  m' L; w! ~5 v: E
        return *this;
    : e% h& {- P' y5 w& `/ h}
    / @7 X5 ~8 l* Y: Ftemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    7 c9 z9 o& }; J( |: H: H0 V- r7 PMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const  r4 |- N" H  D: Z
    {6 s1 w6 \' P! v5 A
        if(p==NULL) return NULL;( d" c6 o; b# s+ q* Y
        if(p->adjVex1==v1)$ E& t  H+ G+ W* M
            return p->nextarc1;
    5 u% b+ i5 B* X& ]    else0 A9 h6 \7 H' T2 ~5 y, T
            return p->nextarc2;6 U. h4 ]$ W  I, U/ ]  t) S  K
    }
    5 f, W7 z4 J9 D% Jtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    ' m+ i: A0 k8 R$ |MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const0 S; n( p5 P' C5 ]  ~* f
    {3 @( y4 A* O7 v
        if(p==NULL)return NULL;5 P5 u" u  f/ S0 m( M
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;8 Y! ]$ f1 T, _* W
        if(q==p)& z! ?; Z8 V4 N  N, b  D
            return NULL;) v0 h) f1 X6 `
        while(q)6 x6 [. x2 S- ]' M9 n! ?0 G
        {! |% [+ [* {1 N$ \; i; E- B0 K
            if(q->nextarc1==p ||q->nextarc2==p)
    % z+ G9 h8 D, e& X9 q            break;3 @+ _' u0 F$ C# I4 H% F
            q=NextArc(v1,q);+ s- V# E& y% \* n+ ~' h' A; O& i8 Z. Q
        }
    $ X/ F# @  P6 ~. H& P9 U    return q;
    6 R  m1 d! g" J& j/ k& a}
    ( h* G% D0 U" F5 X& Itemplate<class ElemType, class WeightType>  ~, o: Q1 n- Y1 B% H
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)- L1 q- K) g1 ~+ {. N
    {# y  O5 ?" X0 f+ K; q7 v1 y
        if (vexNum == vexMaxNum)! c/ k$ A- c3 e5 f6 o, O: c
            throw Error("图的顶点数不能超过允许的最大数!");; A& h; x7 H2 b! r
        vexTable[vexNum].data = d;
    2 a0 X$ Q  [0 Z7 ?9 O    vexTable[vexNum].firstarc = NULL;: p8 P4 `# A0 w  a" [1 Y. [
        tag[vexNum] = 0;, A7 M+ p- \$ c- x* g2 o
        vexNum++;
    # O  I+ \7 Y; T" i& w; ^}
    ( w5 ^# ~; b! z/ o: f5 itemplate<class ElemType, class WeightType>6 V% @9 J% z. o
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w), N  [# N8 n3 A# l
    {
    5 ^# k7 U6 h7 ~: V0 Y    MultiAdjListNetworkArc<WeightType>* p,*q;' s3 x& U* o( v* r+ `
        if (v1 < 0 || v1 >= vexNum)6 z4 R7 d' v1 b4 p
            throw Error("v1不合法!");7 D4 Q7 H" f; }4 _$ w3 ~
        if (v2 < 0 || v2 >= vexNum)" `0 y+ M+ s( y
            throw Error("v2不合法!");
    . C" J) h  S) m1 h/ a/ S    if (v1 == v2)
    0 h  A; P+ ?- J5 z, j  t6 T        throw Error("v1不能等于v2!");
    5 D, i3 q7 T% [# r0 E2 K    if (w == infinity)
    & m  C) U# g9 U        throw Error("w不能为无穷大!");9 y! ~  M2 `/ \: @# C, |0 X0 G7 N8 k
    # V' G  y* T  x- D: H$ u  I7 `4 [
      @. j  f1 U& k8 G  j9 e+ q3 d: d
        p = vexTable[v1].firstarc;, T. d% u5 `8 f- x
        while(p)
    % @. z* ?% c. D* {% l4 a+ K8 W    {! m8 t* y# z8 J
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中$ l8 k: f' G# N
            {1 |" B# W  o3 j" z
                if(p->weight!=w)( o3 J" @( O$ S1 F3 e- s+ X
                    p->weight=w;% q: B' i+ l" p' j5 v0 w9 c
                return;# ]3 _0 h. R6 B+ ^/ q
            }
    4 o- i+ q# M% F( F# N' n# _& s) S3 i- S6 W, O3 C
            p=NextArc(v1,p);
    7 ]. X0 ~+ [& h9 r1 n+ q0 [8 ^    }
    : q: c0 p" ^4 @: R- z1 {5 C    p = vexTable[v1].firstarc;8 y* Z, t% R% ]7 @
        q = vexTable[v2].firstarc;
    * e4 X/ O( U4 B/ B% n1 p( W0 Q    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法/ v0 n: y( _3 S- R, o9 B
        vexTable[v2].firstarc =vexTable[v1].firstarc;
    - q2 R/ h# F4 k, z* n0 i2 x, o2 [* D    arcNum++;
    * b; }- t9 ?. H% z7 l& l}+ e5 b' ^  m) y4 Q
    5 c9 n! a5 O4 ?/ J0 g* l) M
    template<class ElemType, class WeightType>9 N" A" |2 Y! [
    void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
    + m  ?9 x" m, X{5 Q% F1 T. y: {% X7 r

    2 P( K4 Y" c. l- ^% C$ C0 e# P    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    % ?0 a# o. k2 @( A    if (v1 < 0 || v1 >= vexNum)
    0 |6 _) b; J2 i' k* B        throw Error("v1不合法!");. b* x* r, U1 n! N  a1 Y, x
        if (v2 < 0 || v2 >= vexNum)
    - F6 J& l( E. q4 p" A3 U        throw Error("v2不合法!");/ S5 [: X; ]& x, d% U
        if (v1 == v2)5 q  Z4 @- ]) f' @6 p
            throw Error("v1不能等于v2!");
    ; d8 I  f5 b0 ?
    ) [$ @5 O8 {, I# w    p = vexTable[v1].firstarc;) G' M" Y" F- j" X
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    / J( B- x. c, C1 S3 n5 q    {
    2 b7 G" R4 F/ j; E2 h& B- S' J        q = p;
    & D# ^7 v0 O) |        p = NextArc(v1,p);% V$ f! K8 i/ F& }( q- B
        }//找到要删除的边结点p及其前一结点q0 C# r% Y" _1 j9 p4 X# |: J  A
    ; i  D" P* l8 J5 f
        if (p != NULL)//找到v1-v2的边
    " H2 J1 h& X* c, }: ~3 R/ j    {
    $ l# G8 g) h& ~" H        r=LastArc(v2,p);5 s5 |% Y) w0 I7 C% m
            if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL6 [  Q0 q8 h8 R/ X
                if(p->adjVex2==v2)
    $ C8 W7 n4 ^: q/ R  k8 }                vexTable[v1].firstarc = p->nextarc1;) K( Q# h7 O5 U
                else vexTable[v1].firstarc=p->nextarc2;
    0 {8 l1 ^! o4 B+ v# ~$ o  V$ A4 v        else//不是第一条边8 Y) A3 \& k" X2 s
            {" g% t9 J; a! U& ^  N
                if(q->adjVex1==v1)0 R% X! r* j+ A, {: c
                    q->nextarc1 = NextArc(v1,p);/ U3 n9 D7 L0 b; M5 h
                else
    9 }) Z1 s6 U% k9 z6 r                q->nextarc2=NextArc(v1,p);
    * T- G) b/ ~8 H5 ~$ O0 }! r+ u/ _3 _5 F4 |1 U. P
            }% Y! I5 N4 X2 \7 c7 V
            if(r==NULL)
    * h( U6 c: A* i' |8 V/ p            if(p->adjVex2==v2)$ f) W' G' \, ?  g% l3 R# r
                    vexTable[v2].firstarc = p->nextarc2;+ q: q- D0 ^4 W% n6 }9 M  K% e# s$ v
                else vexTable[v2].firstarc=p->nextarc1;, ^( W0 X1 }8 O& N0 ~
            else
    ; j8 ^" j+ [9 z; R) N" X        {/ b( H! Z. y! Q( z
                if(r->adjVex2==v2)
    ) T: e% B( L$ u# F. P1 a8 ]                r->nextarc2 = NextArc(v2,p);' A- G3 Q1 C5 ]
                else. n* U2 X, a' I" P4 k. o1 L" d! H1 \
                    r->nextarc1=NextArc(v2,p);5 v; b! y( n* N+ \( b! x" D
            }2 |- c- R# ~* s+ N: H2 V
            delete p;
    ; o. U( ^3 V- S& g        arcNum--;0 o% e# ]3 q$ C! k
        }7 P/ C% Y+ F8 S% }( A1 F( V4 a
    ; j. N- K  a/ Z3 N/ K+ Y1 v
    }
    ( r6 W3 C/ W8 L3 [# U; wtemplate<class ElemType, class WeightType> void/ K/ \- N7 }6 ]) ~9 Y
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    - A4 ~  Q7 K+ S2 O. n  N{0 x0 h; G: d  w
        int v;% B4 ^% ]. `1 j  X; o9 m$ \8 q* \
        MultiAdjListNetworkArc<WeightType>* p;
    4 T! ]5 X5 ?0 x7 c    for (v = 0; v < vexNum; v++)//找到d对应顶点
    0 t* e$ O4 O2 z) S* D        if (vexTable[v].data == d)0 {* q7 C3 M: L) Y. s4 e) V! ^& D
                break;
      E. i1 s% }; Q( I    if(v==vexNum)
    . F- R. r" m& {& X% D        throw Error("图中不存在要删除的顶点!");
    ! A' L' B1 G- S+ H  X4 Z: F) h9 e% R
        for (int u = 0; u < vexNum; u++)//删除与d相连的边& D: D) o8 r' l  u$ ^$ T% Q9 G
            if (u != v)3 s3 c4 z, H" b  l' d
            {
    1 J- M- ?) q1 F) n; F            DeleteArc(u, v);2 H- h( i9 d+ \/ _
            }
    4 |, x: c; e% D+ U& L: f    vexTable[v].firstarc=NULL;, ^& y4 l) ~! w8 h% [
    / \2 K0 W* T' t% R, f8 T4 q
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    , D7 j" b6 a+ y/ \6 u2 r- F2 {    vexTable[v].data = vexTable[vexNum].data;2 c6 @+ p9 \" M- @! A- T7 B
        vexTable[v].firstarc = vexTable[vexNum].firstarc;; u" M/ N7 U. e" N1 m+ n: H
        vexTable[vexNum].firstarc = NULL;
    # ~: X) L5 G# N    tag[v] = tag[vexNum];
    9 m) h% V+ e: x( A) @& A! N& j2 O% g    //原来与最后一个顶点相连的边改为与v相连/ Z7 M- H3 A1 s  A( b8 Z
        for (int u = 0; u < vexNum; u++)& t# B, m! p3 X) a
        {) H' _+ h- g+ t( @$ L) O7 `( \
            if (u != v)1 ^/ N1 K7 O4 {# K$ J2 y9 E* G
            {
    % g( ~7 S3 j8 Z, Q( Q            p = vexTable.firstarc;
    $ X! T1 r0 g! o# g" f2 y5 v) a6 z            while (p)
    ( n4 k* P% b6 k6 Z: l# H            {
    0 H+ A/ A& g* |  I7 k! S: D: X. a                if (p->adjVex1==vexNum)! _( g% K1 j) }: d' K
                        p->adjVex1= v;
    / }8 F! q- O, Z! D. L                else if(p->adjVex2==vexNum)7 z1 }1 l1 l% d
                        p->adjVex2=v;
    ) l8 o8 v' W9 ]+ r# T4 o                p = NextArc(u,p);% x" |# ?5 H9 k5 m
                }
    $ f1 u% [) v+ v# T        }
    & O: z: V0 [* N1 C9 ^    }
    7 f7 I- ?2 M3 F. x4 C}* Z0 X, k) r5 O1 J& \1 k
    ///深度优先遍历
    ; B2 N6 s( R2 o4 E! ]( @1 a- ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)/ `+ |5 K! T- W- E9 e" I
    {; h+ q, y  z$ i6 r( [, J. h
        tag[v]=1;  r: x/ r: \4 W. l& I6 y( p1 ~7 h
        cout<<setw(3)<<vexTable[v].data;& g# G% D. s9 S8 [' m& }
        MultiAdjListNetworkArc<WeightType> *p;! b8 H  `1 |( z
        p=vexTable[v].firstarc;7 b7 p; p9 {' s! A1 r' n  ~
        while(p)
    5 [5 l4 t; @" ?$ a& h    {! z  n8 I; W8 S9 e
            if(tag[p->adjVex1]==0)% p+ D& m3 h$ L) ~5 r
                DFS1(p->adjVex1);5 Y% D% D* P9 L
            else if(tag[p->adjVex2]==0)
    ) D6 P: Z2 u& L* N0 h- A$ L            DFS1(p->adjVex2);& s. Z: J8 w  j9 ]0 T0 u3 I
            p=NextArc(v,p);/ `* x* Z% w8 ^' t  C& e4 n% O
        }( }: ~* W: D2 \  R& d
    }
    . y: A4 a7 i4 f5 G8 C, f9 utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
    $ K& F4 {: v* o3 Y{
    ) H7 ~: P' b+ y6 R+ m! x    for(int i=0; i<vexNum; i++)
    7 j2 ^( ]" _- L* a4 B        tag=0;! k9 U9 i1 L: t3 J2 G
        for(int v=0; v<vexNum; v++)
    ! x2 F/ p1 M. e    {& ]) K. ?2 X- o4 O7 F  L
            if(tag[v]==0)
    , V( [% A3 U. M" O& h9 y            DFS1(v);9 Q, N2 R$ {, B4 j
        }
    ' n# V: H5 C- n; J- ]}
    3 j! R, v1 P+ T1 _' u# ^) Ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
    ) U/ e7 o5 z& m4 t{
    , c9 Z/ Q" G, {    stack<int> s;9 @" M4 ]$ ?: l/ v
        int tmp;! `0 }# B" O: P+ N8 a
        MultiAdjListNetworkArc<WeightType> *p,*q;- f( O+ Z- C8 G4 ?0 a$ G
        for(int i=0; i<vexNum; i++)6 g# I5 W% `1 o$ r$ e5 `' x- f% J2 J5 R
            tag=0;* w; s1 E& N9 e  J2 Q- ~
        for(int i=0; i<vexNum; i++)) }6 H8 G% P& t, d% W. h! \
        {, k# r' D( k$ O  i' I, D" m; @* G
            tmp=i;2 p( Z- g. C; k2 f
            while(tag[tmp]==0||!s.empty())6 E; s' A! |( J! w
            {0 y2 E* r- v1 _, K# Z9 }* B
                p=vexTable[tmp].firstarc;
    1 G4 R' R% l5 i$ w1 k            while(tag[tmp]==0)1 t$ g& i9 x/ ]' Z$ }
                {) D" X. c. x& G" E5 }. H
                    s.push(tmp);( _1 y9 m* j: b- `3 p4 C
                    cout<<setw(3)<<vexTable[tmp].data;
    ( c. E+ v' i& ?6 B                tag[tmp]=1;% J* w' g, ?: |5 P1 b
                    p=vexTable[tmp].firstarc;) w" z/ G4 [  T; `$ K1 D1 n
                    if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
    9 Q% X9 L& }6 q) M) H                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    ! W+ E3 ^: `: K, D7 W                //cout<<" 1st     tmp="<<tmp<<endl;2 o- p: E. o5 K: m0 u9 t, o
                }4 Z: K3 {8 H6 F: G9 R0 `
                if(!s.empty())
    + `1 `2 T2 F+ o1 `5 |            {
    ! m) ~( P' O( \7 k                tmp=s.top();5 q( @6 O5 r5 P/ O. `
                    s.pop();
    ; \, H4 O( [8 {/ l% X                q=vexTable[tmp].firstarc;
    9 `8 C& W. n# w0 ?6 [; v# D, R                int t=tmp;
    / I  r; R& E  t" T                while(q&&tag[tmp]!=0)
    8 q2 C$ W# e5 I" P                {& {7 g- d: G+ p# t
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
    " H7 `9 q2 x! Z" S/ W  @# ?                    //cout<<" 2nd     tmp="<<tmp<<endl;6 J8 _& i8 c7 Q  l9 j% S
                        q=NextArc(t,q);
    9 b  T: w. h* b& f3 h& T                }
    ! D* e+ m# n; m! n% o                if(tag[tmp]==0)# s- p( f6 s- s; u6 U
                        s.push(t);; l% t0 e9 y7 g% h. b
                    ///1、对应上面连通分支只有1个点的情况3 w. c9 Z- r# b: u9 d2 f' k
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
    7 i$ z. i& C& h9 ]1 R' q' q+ |                ///tmp要么等于找到的第一个未访问节点,
    * U& S7 G) ?0 W/ S3 T& T                ///要么等于与t相连最后一个点(已被访问过)& l% z$ @9 ^+ Y
                    ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    3 r' h( H  n( h1 H% R            }
    : c& \) H: r% `3 m% U3 A! P1 D) O        }) w& |! y4 V  }8 J+ `
        }
    " X# A" M' m; K4 \}
    # d" w# d* A% ^& |# {//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1# e  |/ }7 d5 s1 u6 I
    template<class ElemType, class WeightType> int- j# i0 W8 p- y1 A2 o' _' n0 \
    MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
    6 L% [6 b9 E$ N  f6 M% c% h. B{
    : n1 Z1 Q' n6 `! |, u/ Q4 r" s    if(head==pre)9 y3 O! a0 J: {4 e+ T: }: M( f
            return -1;# `: R6 p6 o' H, b: G. o
    0 n$ O9 M# T9 }* @; u* {
        MultiAdjListNetworkArc<WeightType> *p;3 [! |( Y8 @! f* D4 e  l+ t1 _
        p=vexTable[head].firstarc;; [% S9 V9 _2 I: G/ M
        if(pre==-1&&p!=NULL)
    9 E, G0 T1 m9 d; r0 V        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    1 w, f, Z  n( N& S7 v' W8 h' E    //pre!=-1&&p!=NULL
    7 W% m" {0 D) s7 h- g    while(p!=NULL)* ^8 L3 T; W/ B# b) R5 k
        {# z6 `9 x! ]. `( h
            if(p->adjVex1==head && p->adjVex2!=pre)# {0 M  n. j- ?/ O2 v
                p=p->nextarc1;' B' `* t' `  M. [5 Y! ~
            else if(p->adjVex2==head && p->adjVex1!=pre)
    ( S7 b$ P8 S2 W* E3 H- l" n            p=p->nextarc2;
    ; i" Z3 P1 ]* {3 l, x4 N        else if(p->adjVex1==head && p->adjVex2==pre)/ @9 q# s% M+ o7 M. W
            {
    + u' G; G8 k  O1 m  N: x7 Y            p=p->nextarc1;' q9 S; c& y& @! U5 E. D0 w$ r
                break;
    $ s; n5 Z# j  K- v! l/ \* ^, a        }; J3 Q2 I% k, B
            else if(p->adjVex2==head && p->adjVex1==pre)
    ) X1 P" m! t2 M5 N- Z1 s. H        {
    ! d1 F* g  B# l# S! n/ u            p=p->nextarc2;1 S  F7 x- F/ N4 \# Q
                break;
    2 q6 H, Y8 n0 p, V& ]/ i% U7 S9 _5 }        }
    7 m2 s8 n# p; Z- P* T+ s    }
    * C! L' U9 A. E0 Z  D  `& Y! U    if(p!=NULL)/ s5 K: c) o' f1 X8 o+ q
        {
    4 i8 {7 `& W( a) f/ A- ~, W& e        return p->adjVex1==head?p->adjVex2:p->adjVex1;( {  j3 ^7 R5 u) {! U
        }
    ( S6 y8 h8 N# c) h8 e5 m  a3 A2 D    else
    6 \# q9 w. e$ |  a        return -1;
    : V  u( \% [% ]* ^) k0 ]}
    . b+ g$ {- N7 F- h) A7 k: ~& y( o. I1 Y
    * J0 T5 Z( z( m1 n) ?
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(). W3 T' Y- J& k
    {
    - c0 P$ P  S' m' L1 {. ~    stack<int> s;" l2 d, C! o% N
        int p,cur,pre;  d0 K* J. O1 s% V4 X0 }
        //MultiAdjListNetworkArc<WeightType> *p,*q;
    $ G- P4 \" ^+ T' H* M- K    for(int i=0; i<vexNum; i++) tag=0;//初始化: u1 A4 @3 v0 t: k; c" S

    - {9 y9 J6 w/ c    for(int i=0; i<vexNum; i++)3 `/ |1 n5 e* o' D' S, x# C
        {
    # r- L; r% B* p5 p        cur=i;pre=-1;
    ; D) g% {2 F3 e        while(tag[cur]==0||!s.empty())8 R5 U8 H& B& v# X/ w$ Y
            {' u( S) x* ~& v. p/ ]3 ~0 K  W
                while(tag[cur]==0)/ r8 A* {  Y" n6 E5 Y: S' j! C+ O) }
                {4 Y  }3 g9 H) c7 X
                    cout<<vexTable[cur].data<<"  ";% u9 @/ @* x2 A3 Y/ m
                    s.push(cur);
    / B$ W1 V* m" @0 ?( s: q) r                tag[cur]=1;! h. S4 }- ~3 a" d
                   //初次访问,标记入栈+ y3 Z7 P, D. w2 i3 M. y

    9 w" j' S, o9 u' d5 k) G$ i               p=GetAdjVex(cur,pre);//p是cur的连通顶点
    8 p7 g5 p6 q1 m$ o$ k               if(p==-1)" M, n6 a( i' @2 H! W
                   {& o+ l2 l& D# q* H
                       pre=cur;s.pop();
    . X& x8 n( D. z9 z                   break;: F5 G. |( I/ \5 @: J9 B
                   }! N9 R1 S0 X5 A( q
                   else
    ' N4 f! [. i( q6 q# A1 T* G3 Z               {" G1 W6 B; v3 A2 V
                       pre=cur;
    ' A& A! G. P4 @/ w7 J                   cur=p;
    # ~- o0 E* r- o* C' \               }' C# q  L9 p& ~* W8 P2 l+ _( V% ^

    ( g: l8 {" S% M5 Z2 W1 }            }
      G$ j4 C0 w. B8 [8 Z            while(!s.empty())
    3 l% x  q1 P) D/ Z3 U* ~            {
    # N) E6 K% o) i( O                cur=s.top();
    - K4 Y; q: e9 t$ l# I0 n4 ^; A                p=GetAdjVex(cur,pre);% h. C# d" ?! }8 B( w+ K
                    if(tag[p]==0)
    , @" V2 O8 P8 i5 A, y                {
    7 m* O4 P2 C: x( r" L7 |3 M                    pre=cur;$ l, |7 `, f4 q
                        cur=p;
    9 p+ i) I' I8 E                    break;* R1 d6 T2 z6 U6 @" m  b& U
                    }& n* `5 I6 a7 @; q1 t
                    else
    6 r8 D( r9 M# W! f( o8 E/ r; K# B                {
    + [9 g6 U' i# `: v1 h  Q                    pre=s.top();1 V: J( I& i$ S) X* j
                        s.pop();2 |) N& g( I2 N& M! U# C$ a% R$ `
                    }
    - F! `: ~( @  p+ z5 f- I
    3 Q: x3 B/ M5 x' D            }
    ' l- y. k: j: t2 H3 d6 @. |2 M! S! S0 z% S+ h2 A1 I6 X  C% Q* K/ l
            }# v  N! M( H9 C& G
        }
    9 Q0 Q0 G. F, u' m2 T}
    ( i* k4 z4 G" d. d6 q( e" @+ @' Qtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()- M0 B, C6 A% X
    {+ [1 M+ N5 L  I+ V
        for(int i=0; i<vexNum; i++)
    " f1 @. a; A+ j2 x7 D8 s3 M" _- }% ^        tag=0;# \7 H" J4 g7 x7 R1 ~" |
        queue<int> q;
    + _* y/ |) E0 |    int tmp,t;. g0 Y7 S' h+ F" S1 W
        MultiAdjListNetworkArc<WeightType> *p;
    5 K; t0 q# d' T% W+ s    for(int i=0; i<vexNum; i++)
    " Q* m5 w; k$ g5 O0 h3 s/ m3 [    {0 _  q" T1 C/ ~3 u5 \5 B/ C% E; A
            if(tag==0)
    4 m0 k3 U" Y) |4 y9 L, g. M        {* D% K3 A& e4 U  M5 X; k. E
                tag=1;9 x. [2 P4 k% M) ?9 i
                q.push(i);4 r0 l9 K7 Z8 R. d8 ^  H+ S
                cout<<setw(3)<<vexTable.data;' Q$ o4 L8 ]% X
            }
    5 \( b5 V: G; B& l% n        while(!q.empty())
    4 \3 z+ \' k1 c* d0 L        {2 X( f: c3 e7 t1 Y( Z/ `) R, U, K
                tmp=q.front();
    0 j6 P9 U" ^( \: T% P" f7 E+ I            q.pop();8 I/ E) I" V6 B
                p=vexTable[tmp].firstarc;
    6 z( ]: [/ [9 i; }) P6 A            while(p!=NULL)3 G, e0 v# f$ [+ U
                {
    ) v: A0 G3 X0 F. d4 p                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);8 \& U! [# B+ t( K6 b
                    if(tag[t]==0)
    ) |7 z3 k' r+ ^6 h                {
    2 t* Z% Z& Y9 C! E9 {, ^( ^                    cout<<setw(3)<<vexTable[t].data;4 ^4 Y' Q( H- L0 W
                        tag[t]=1;
    ; \& z; g* R6 H; J: C; b5 \                    q.push(t);% I% w& k9 m! m& X" f8 z9 U
                    }5 ~  N6 h( N- Z& n, s
                    p=NextArc(tmp,p);
    8 }$ Z! D* T' Z: u            }
    9 z2 L6 y6 n2 ~/ Q5 H: R$ _        }; R) Z' ?6 ?- {! s; v, a7 i
        }% k& }* w4 l/ N) V8 w' s
    }9 S" F& L+ H3 {' @0 z' l
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()9 Y" \9 _& P9 T
    {
    7 X2 p* i6 g- a2 g0 }6 T* F- u9 k    MultiAdjListNetworkArc<WeightType> *p;1 n" ?, I! a# `  _8 V( I5 M5 q
        cout << "无向图有" << vexNum << "个点,分别为:";1 d0 k% _- ]0 l3 e- h" I
        for (int i = 0; i < vexNum; i++)$ H3 ^6 R6 [" q
            cout << vexTable.data << " ";
    / {5 z8 T) J3 U( R! F: h$ F1 V0 e: z& ^    cout << endl;7 b/ ]' k' E! ?- Z8 y
        cout << "无向图有" << arcNum << "条边"<<endl;# y" T8 J1 o" a6 I# U7 T  |
        for (int i = 0; i < vexNum; i++)/ H9 |, ^+ c0 ]$ R
        {7 x& E( V: t; P2 Q5 {2 j4 G
            cout<<"和" << vexTable.data << "有关的边:";& c" V- b( P! i* X+ q, }. f* I; d0 Z. m; K
            p = vexTable.firstarc;
    - c: O& w5 F: L        while (p != NULL)
    $ }$ G% h1 E4 a5 x7 S        {$ L4 w$ a3 r% \( f& y
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
    : ]  p8 S- }  G3 R% n            p=NextArc(i,p);0 G* p/ m; r9 K% H, _
            }
    3 O; R* Y5 p+ M/ M        cout << endl;1 T# |5 d0 A- B
        }* E" N/ V% L4 N8 J/ {. C
    }
    . g/ ]* r. O0 e( u- u: b3 I5 L0 S0 t

    ; k9 a; o. M1 x9 Y) t邻接多重表与邻接表的对比
    2 W5 C+ u" V# r+ `8 J- e" d; m0 L) E: T0 Y5 Y; r
    邻接表链接$ P: z: W& D+ T2 A
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。" P$ B) b$ O: P; N
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    " C+ u/ I  {2 h& @1 v% Q7 f* b6 o为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。/ n( O+ R! u+ R! U3 x
    ————————————————2 n, S/ Y& x4 c6 W
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    $ U, [' C; N! K. ?' N原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958' p) a( z% R1 B. H+ v7 ?
    ( ]: j5 r5 A- n+ E) C/ _  \+ }

    & l+ Z5 i3 {0 {1 X( Y; q2 \) V8 X* G8 q
    5 b/ q; d4 M8 k
    ————————————————
    ! x( U2 E3 h! w# F# Y版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    0 a2 v& `- |. v: K: Z原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    * [$ D% E$ n% [+ W8 q4 q, z- z. h
    8 Q/ t# q  F/ ^, |3 J
    ' ?, ~9 S3 x& B& U
    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-9 22:00 , Processed in 0.481365 second(s), 53 queries .

    回顶部