QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1532|回复: 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
    : d5 s! i/ i: E: K8 U' ^- D
    图的存储结构——邻接多重表(多重邻接表)的实现
    , ?% I, v7 f& z) o  i: T$ S4 x  r7.2 图的存储结构) G( q' {+ k+ ^! T

    1 v. r' f0 t% }7.2.3 邻接多重表(多重邻接表)Adjacency Multilist* |. S3 X) ]7 R. M* q
    邻接多重表的类定义$ [6 s; \) b8 I, P/ Q8 a
    邻接多重表的顶点结点类模板0 g9 u! J% N+ \
    邻接多重表的边结点类模板
    * F" h! ]7 T; M' G, U* B邻接多重表的类模板- S$ B8 Y) J5 r; [4 J* @4 Z
    邻接多重表与邻接表的对比
    / ~2 j: O# s1 B6 i# o- i7.2.3 邻接多重表(多重邻接表)Adjacency Multilist  J2 r& e, K" d/ B

    4 J9 f% J3 Z" P3 P在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。
    3 i. v; N3 S  Z- t# q- ]2 _, p; n在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    # n  M7 h# |& c# M/ `3 n& P+ L1 T  i7 D
    邻接多重表的类定义
    1 {( R6 ~  w: }% |. I! v, H. | 1.png 1 ]/ t! Y+ m! Q* B4 I0 C6 |1 |
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:! J) Z- R' V5 a, y8 ]* A/ l
    data域存储有关顶点的信息;$ a2 `- d7 L4 k8 k/ [
    firstarc域是链接指针,指向第一条依附于该顶点的边。
    9 w% q5 j: t/ b7 ?- T' Q+ ]所有的顶点结点组成一个顺序表。

    8 q0 x: m; l9 W8 U
    ; K  e# V1 P/ K( U/ G4 c# Q, s/ |
    template <class ElemType ,class WeightType>
    " e' i3 C; G0 P& l7 S  Iclass MultiAdjListNetworkVex
    ! B- s* B6 h) D' s' Q, M{
    8 v" z$ P8 ?2 n* A9 G1 upublic:# X: k: K& Q% a) {/ F8 X+ k
            ElemType data;
    , y+ S, D7 g& t, j' Y3 s        MultiAdjListNetworkArc<WeightType> *firstarc;
    ! ]: ?; W1 h) Y% S0 M; W7 ]2 x( D9 U* g& i3 G$ x
            MultiAdjListNetworkVex()
    7 z. o' Z) Q0 Y3 m, T. n4 q& n; p- x        {
    9 F% Y  o5 w& S: V  U0 d  L; t                firstarc = NULL;
    * T: c. O! S; X! X1 Z$ Q+ t        }
    ! `' _; f- q4 ~6 x8 E- L  W' q5 X) Y        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)4 k, i) R) [" o
            {5 i; F5 J" @4 L
                    data = val;
    & H# A" _* R. b                firstarc = adj;
    0 }) M  \5 |; K/ f- x4 q        }
    & P- {$ f4 h9 B5 v8 ^- c7 D1 m. n};; v0 N% T. R3 H  ~0 [8 T

    & A( b2 M+ r1 }% ?) m7 ]% y邻接多重表的边结点类模板
      b3 A, p! `' W4 l) V/ {& {# c1 z+ X6 u, Y
    在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    , C1 C  f; d0 Q- v6 G, k+ Atag是标记域,标记该边是否被处理或被搜索过;
    * j0 N; ^) T9 f! r0 e* M+ e: mweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    ( U5 i- A1 I0 e1 i: Xnextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;0 @4 f$ h1 p* L+ V' f; e
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
    3 v7 K" E0 u4 C: K, a! o; H: J) F8 b; d# p% |' E& P
    2.png   {9 R, l: {" K$ v+ |. t
    template <class WeightType>2 g: n3 |% b! ^1 u% Z
    class MultiAdjListNetworkArc
    9 g6 R! J: S3 @( j{
    % v, _) a1 h; c5 Z+ _% {; Hpublic:
    . N3 Q7 f6 \0 o0 Q    int mark;                                       //标记该边是否被搜索或处理过
    4 F8 a3 N5 o3 _/ N( D        WeightType weight;                              //边的权重' F+ S- T$ ]* A) L. i
            int adjVex1;                                    //边的一个顶点' x. Q3 L- h- L% j8 ?" i$ L
            MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1( f# K& t" Z6 O" Y
            int adjVex2;
    ; z3 Z  q1 G+ [. x1 D6 x        MultiAdjListNetworkArc<WeightType>* nextarc2;
      W" K+ s3 P" i8 {+ B1 C7 g. X4 i
    2 Z  v  W3 B" W5 O& `" r6 E        MultiAdjListNetworkArc()
    : r  h' j2 {$ A; i        {
    ' M# n, ^) I, f                adjVex1= -1;
    9 k* o: U& d1 A0 m% t  V                adjVex2= -1;5 }" u8 |8 }- @) z" U) a. ]7 ~
            }" p2 s: U7 q1 S; H, M% p
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)1 v4 B, j+ H5 W1 T
            {
    * d- N8 T, ]' v8 J* X1 G! U; P. g                adjVex1 = v1;       adjVex2 = v2;
    2 ^6 h" g" @6 D/ G/ j6 v                weight = w;
    " Z1 T4 G) G" Q) T) Q/ Y9 z$ a5 P                nextarc1 = next1;   nextarc2=next2;
    6 }/ n% Y3 k0 |; Z                mark = 0;           //0表示未被搜索,1表示被搜索过
    ' p# x. H' K( P        }' e  n3 @3 b' Y$ y( x. ~

    , ~0 g7 m" G1 B  Y0 N邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>
    $ X2 @3 D0 R0 R7 wclass MultiAdjListNetwork
    - q4 ~: S+ |+ U0 Z5 z7 Q. ]{4 y  X  I  J0 E! C2 }$ D& k
    protected:: w$ {6 \3 S. F- d
        int vexNum, vexMaxNum, arcNum;
    5 y) r0 f( f: q    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;/ Q# R4 v1 g7 Q2 H! a$ n
        int* tag;4 X2 K: G) N* M
        WeightType infinity;
    ( k, v# X2 p' e6 j& t1 X
    6 C- \% X  c8 p0 n/ _4 I7 a% Hpublic:
    / a! S* g, O& s! |. d$ i8 v/ m# c1 Y    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);! e! F' v6 A4 |6 }/ `3 M, P

    5 ]& P. a; D! P8 ~    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    * l+ ?( i# B  A1 G. F* U
    " G2 f, }, T/ x* z+ k3 X/ E6 o    void Clear();5 M- ~3 D7 M: Q, G
        bool IsEmpty()' g& v6 R- z7 }$ @, J2 V0 H
        {7 O' S/ Z, h8 ?
            return vexNum == 0;
    3 V; C# o' Y9 E+ D4 l    }9 D. a) |& @2 I! P; Q" @
        int GetArcNum()const
    " D) r% M7 X1 a( X% U+ N, v    {
    ; f/ v6 v* \5 O# W( n) {* |8 X# f        return arcNum;
    4 i- X9 [1 D- F    }/ n! V# X4 |/ ^6 O. N9 Z
        int GetvexNum()const* C: k9 \. h( M3 r3 P( L
        {
    0 A4 N; c$ y3 t  [+ ^        return vexNum;7 U- }; h6 w7 L
        }
    ( _, h4 e$ G6 C) t  `* s  f; c0 x3 P
    # |. [( Q! A' G# ?
        int FirstAdjVex(int v)const;3 Z7 p8 }0 Q0 C8 Y. P! i: w5 K
        int NextAdjVex(int v1, int v2)const;
      m. O& t5 K& M1 c5 [" m3 G" Z( V) v, M    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;. [: P5 ~# x$ T' w$ Z
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;' s3 l5 o  ?4 v9 T8 t4 @: a! }

    " ?5 @! l0 f& t' Z* h    void InsertVex(const ElemType& d);
    / ]7 e9 {8 d- s    void InsertArc(int v1, int v2, WeightType w);
    ( @# z- l, N0 E6 {
    % w: J5 |0 \* ]- z" p2 d5 C    void DeleteVex(const ElemType& d);* f4 G3 ^" z9 f
        void DeleteArc(int v1, int v2);
    $ T) d5 t8 Y. n% @4 c1 Q
    ( `. G/ r( R* [, M4 u    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    ) R+ i  Z; ~2 u; E% h3 M4 }    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);3 ^; Q1 N! {; Z- H
    + P' m8 \1 E. A$ u
        ///深度优先遍历
    1 S* M& i& E/ Z% P8 v5 f    void DFS1(const int v);+ r. {6 q1 }# O, |6 @- A" r) z  C
        void DFS1Traverse();
    ( |4 f# W, G" i    void DFS2();
    8 z* o$ t5 f0 w  z! W
    ; }( c! G6 ]+ T: F( a' O    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-12 {6 }+ ^0 P& w4 _' J7 a
        void DFS3();
    . a* Q" e7 g4 n5 ]% {/ u0 ?$ V/ c' @$ {6 A' C& R
        void BFS();
    : v4 m* F; k% |: N4 \    void Show();& }- W% o. n" u! k  _
    };
    2 [2 m2 r! z4 F6 |8 X$ u% q0 H8 D( n. K, u( A
    2.函数的实现: y( `% e7 n) x0 I0 e* E
    研讨题,能够运行,但是代码不一定是最优的。5 q+ v4 J* G* J( a. L- ~* E7 F+ D
    7 J% a) t+ v6 b/ Y! G, D
    #include <stack>7 p5 l2 O! W$ V+ a$ a* [* F
    #include <queue>9 ^$ ?$ p1 }0 o

    2 j4 f* u2 F4 E, ]% gtemplate <class ElemType,class WeightType>7 Y4 O7 [, v7 D
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)- R" U( O8 x7 m4 a: n8 ^
    {; \* `; n8 \# M3 I
        if(vertexMaxNum < 0)9 e+ X* I/ g4 d! _# A$ G
            throw Error("允许的顶点最大数目不能为负!");
    " m* k4 a7 m5 r9 c. @8 l    if (vertexMaxNum < vertexNum)
      ~  ^. @( _/ {1 O        throw Error("顶点数目不能大于允许的顶点最大数目!");7 Q/ `9 Y8 w+ i" A3 z& E0 ~
        vexNum = vertexNum;
    7 R8 _  c4 g2 P0 W1 ?    vexMaxNum = vertexMaxNum;
    , E( V6 P' A6 K( W& G3 O. r    arcNum = 0;7 y1 U: d0 S2 d& q1 x9 v5 v
        infinity = infinit;1 M" L2 k% Q$ b3 X  ?
        tag = new int[vexMaxNum];1 \, p1 b, F1 ?; s1 d- i
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    ( i% [- p* m8 {0 f1 }6 m    for (int v = 0; v < vexNum; v++)- |& n7 `6 a2 Q) W4 e+ A" s
        {  t. ^! \; p5 v* {5 v5 ~- d, E" w6 @
            tag[v] = 0;
    " r$ Y( i: z) N0 q4 t+ R5 s) \        vexTable[v].data = es[v];
    # O' G( i: g! Y' M$ |) ^: x' ]        vexTable[v].firstarc = NULL;
    + L+ A6 _8 Y2 n- q, g    }" b0 u) t$ K8 P2 j5 F4 M
    }' H+ ]6 A0 J% J) O6 ~) H) A
    template <class ElemType,class WeightType>
    / m, @# S, J9 }; E$ j8 C* gMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)7 ~  [: H, c% ]+ z; X" z
    {
    + p) h3 ?* h4 S% |    if (vertexMaxNum < 0)
    ( o! q  z0 Q; z4 O" V        throw Error("允许的顶点最大数目不能为负!");9 {. y1 u% T  s  ?' i- ~5 X
        vexNum = 0;8 S/ c# L' d2 E+ k+ ?4 j1 R
        vexMaxNum = vertexMaxNum;
    " n6 m/ @5 C2 u5 g$ q. @    arcNum = 0;
    5 C% a$ H( `5 {% Q    infinity = infinit;- U. k" y5 g, N+ H/ w* \' P
        tag = new int[vexMaxNum];
    , z. x0 X; A+ h3 F1 E    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];0 [0 q0 \, _3 r$ E3 o
    }  L- b$ r7 @0 i+ \0 I& B( E0 V
    template<class ElemType, class WeightType>
    2 v, Y2 C9 j# _int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
      q4 L+ h, M8 L, I  a{; f* B! S8 l& I/ B/ J3 r: c
        if (v < 0 || v >= vexNum); R7 L; Q% h9 O+ K
            throw Error("v不合法!");; @6 y, b4 p3 ~" R
        if (vexTable[v].firstarc == NULL)
    . Q# }, R* _" W: A6 Q$ B' o/ _. Z        return -1;
    & t! n2 g$ v7 G/ V    else6 c# [4 D  ~8 b5 b/ c% q
            return vexTable[v].firstarc->adjVex1;
    9 z9 Z3 h, Y7 O  e! K}
    $ a# f/ D7 K& @% F- P) }( V3 z+ c7 X
    template<class ElemType, class WeightType>/ z) u3 u9 T7 v% y6 `
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    & ?$ g$ A3 M/ s  i8 N" S, j{
    ) T: l- o7 y- j  S' g  i# T    MultiAdjListNetworkArc<WeightType>* p;6 U3 L# n' r2 |, U# \: Z
        if (v1 < 0 || v1 >= vexNum)
    & `3 I8 R7 O$ g) O+ ?5 ?! r9 @, ]        throw Error("v1不合法!");+ D" Q+ }2 k% n# a
        if (v2 < 0 || v2 >= vexNum)
    % G8 D4 [4 E" f" a% [        throw Error("v2不合法!");% i; i& F8 u' P  X6 h: V
        if (v1 == v2)4 e- u& B3 X- o0 r
            throw Error("v1不能等于v2!");
    ( Y6 ^. `% }3 k# b5 @: ]1 f    p = vexTable[v1].firstarc;7 X0 k! {) ^" ~
        while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
      E5 r) f, u6 S" `9 Z$ I# R- b        p = p->nextarc;( W9 t7 |0 |( h& |
        if (p == NULL || p->nextarc == NULL)8 f9 m% M& I( S
            return -1;  //不存在下一个邻接点
      ~! D: L  r& X8 \3 P    else if(p->adjVex1==v2)# S5 {7 H  U, I8 \+ T5 u
            return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    * \7 r( r# \( q, W* V: e    else, R+ \+ v% @3 m" S
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);" d! _5 `$ n& x5 `
    }- a: h1 d: E' T. [
    template<class ElemType, class WeightType>
    8 q' J& u/ N* o% Yvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
    3 e( O5 |( h" k2 o4 I{0 O5 f8 \+ m" B8 k+ G# R
        if (IsEmpty()) return;: ~* f/ P/ I, g+ V, I. M5 A
        int n = vexNum;
    ' c* `* d  q* z$ Q1 X; g    for (int u = 0; u < n ; u++)
    4 J" M- |5 n/ k+ g1 _% W        DeleteVex(vexTable[0].data);) P" \+ m1 E& ^' e9 ]( ~
        return;
    0 H) J: ^) T' L7 h/ `; C) D' U}% P' P4 @! H2 s
    template<class ElemType, class WeightType>- U6 B! G& J1 b1 z: Q% K7 ~
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()9 }1 f. k, |% n* C+ \/ v: O6 `# B
    {
    ' e$ o* f8 ]  K9 c& E) m    Clear();; F  X3 y( y2 `2 x0 D# |. f7 J
    }
    ( F, y( z+ ?' K: Ctemplate<class ElemType, class WeightType>
    # [. I3 A( w' {+ A' w- tMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    3 S+ K2 I4 x5 `- x{
    ) F0 }9 f- a8 s: D! `' P* ~    vexMaxNum = copy.vexMaxNum;
    ; G2 n, u# i6 F9 M    vexNum = copy.vexNum;
    / [. a) x8 f; V0 B: B    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];5 k4 v& e) @) ~  D  Q! f
        arcNum = 0;* d0 a& {7 H4 D* _
        infinity = copy.infinity;
    % S% E, P& o5 P3 r- B; Z3 `. G2 F    tag = new int[vexMaxNum];9 F% R) c/ G# L" `3 y, @5 K. S" v
    * e( I: ^3 a( }" Z+ @$ |
        for (int v = 0; v < vexNum; v++)1 U8 C4 q2 w3 N% e3 v3 H( Y
        {  e! y& D3 c. r# I2 A5 ^
            tag[v] = 0;
    7 J: t/ r  t3 H1 V1 ?; A2 i$ E        vexTable[v].data = copy.vexTable[v].data;/ r6 ~" s8 Y, V/ j
            vexTable[v].firstarc = NULL;# V6 ]+ i$ W, K' i, K1 x6 {
        }
    2 p1 Z/ |7 H% g7 I. O1 h1 C    MultiAdjListNetworkArc<WeightType>* p;
    * v: n5 Z5 l- b: B. @: Y  N- W
        for (int u = 0; u < vexNum; u++)
    - d+ ?7 o& b7 b8 C6 y. ]: h    {
    " ?+ q# V/ a; h        p = copy.vexTable.firstarc;
    3 ?' r. x, `: J        while (p != NULL)7 ?5 L& Q) k5 F4 f* Y
            {9 ?  x8 D' q/ `$ F2 H* c2 p
                InsertArc(p->adjVex1, p->adjVex2, p->weight);' v+ \. o3 i+ M5 _
                p=NextArc(u,p);' Q' Y6 I( L8 Q/ ?: g5 d7 z
            }
    8 z, A# X, m. t4 {, ~, F    }
    # ?9 f; `% d0 g9 G3 \}0 [3 p. z0 ]; U$ d
    template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&0 M3 a/ A8 P9 p" X( H
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    7 T% E: q6 r6 J+ J{4 V- n" n8 h/ @6 O" P
        if (this == &copy) return *this;* @5 y$ [# H. o0 n+ j
        Clear();* X& G- L& z& G: @! \
        vexMaxNum = copy.vexMaxNum;
    3 X2 n- H/ o( W& o2 p# {    vexNum = copy.vexNum;
    0 P  [. u- C. J: J9 A- z    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];  Q) K, H6 F% B
        arcNum = 0;
    2 X' M0 M# U& O    infinity = copy.infinity;; o! `8 T, [9 a, d8 O: z7 s4 o
        tag = new int[vexMaxNum];3 n$ U" ~' N! z* m

    # K; k" ]' x4 j- s    for (int v = 0; v < vexNum; v++)) M# p2 {. N- N; s& a( |9 d2 z
        {
    * j% {. `/ q6 Y+ T- t3 a        tag[v] = 0;
    2 J" }. b7 D! U0 y1 |        vexTable[v].data = copy.vexTable[v].data;
    & r! ]. X9 d( K  e1 m* [! I  |        vexTable[v].firstarc = NULL;
    2 V2 {) Z  T. I0 p    }
    / p9 x% A. w, a/ L    MultiAdjListNetworkArc<WeightType>* p;+ Q" B3 n( X5 @" Q8 z3 j$ u
    5 J& }- }. U; \
        for (int u = 0; u < vexNum; u++)" y9 a) G- Y* j: A% F
        {: Z: D( j( z! ^0 n# I
            p = copy.vexTable.firstarc;
    ) l4 A* O( E! N& V3 h) K1 {        while (p != NULL)8 ]1 l4 \" j% [& n1 n- g' ?. V
            {- {4 `7 C7 [) N3 Z  X. l- l
                InsertArc(p->adjVex1, p->adjVex2, p->weight);2 R* j  `6 ]' s8 w* A) q
                p=NextArc(u,p);" u; R: }  [! }+ D0 m: u
            }
    0 v1 M# H, H0 B! S! D    }" [+ ^. K0 T# d
        return *this;
    8 d+ u; ?; Z' y& `' n5 C$ N}5 s+ C, l. g/ Q6 z2 a
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    3 o) w- }& {* FMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    7 D$ |3 A8 N1 h{
    7 M# g4 H, w; g9 i3 y    if(p==NULL) return NULL;
    & j; @/ r6 y0 p9 ?7 r% `    if(p->adjVex1==v1)
    4 q* Q7 q4 Q5 `3 R* \        return p->nextarc1;
    ' x; I5 p# @/ _. k2 e    else9 n$ w# x; o) r: m8 g: A0 f
            return p->nextarc2;
    ( L0 Q/ h* `/ V! X}) u; Z5 r. f. ]3 }* O! }
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    % x7 a+ w  r% Y, z- W  S; `" i: oMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const: I  [$ K, M4 w+ J: Y1 Q
    {2 ~+ U* ?1 u) `# o) w5 C& z4 h
        if(p==NULL)return NULL;; \( a* n& t; {. X
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    / @. k/ N9 o# P+ x; m    if(q==p)
    ' C* a4 B- s% B1 P9 \8 K        return NULL;2 d! \* t5 X  W; [  @' N
        while(q)
    " u4 X, f0 n) l# x    {; s* |& r' E" N7 `* s9 y
            if(q->nextarc1==p ||q->nextarc2==p)
    7 P+ h  B3 l+ k& Z5 Z9 n& r6 V- s            break;. s4 @% N. W/ f/ k
            q=NextArc(v1,q);" Z/ |4 ]2 p# Z3 }" G" U
        }2 q! D, K: N, p) C! W7 ^
        return q;% f2 p% t9 o5 }$ R( c: o
    }! K4 X9 \' \- {' e% ~6 X
    template<class ElemType, class WeightType>! e# M, x8 |7 m3 c2 [
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
    5 g( G) ^  Q& n3 M4 q, [$ a) i{7 }# ^* Q" C; O! x4 u" o
        if (vexNum == vexMaxNum)& X# k1 H6 p% W$ D- e/ y
            throw Error("图的顶点数不能超过允许的最大数!");
      O: u" e, y6 T8 ?9 g- _" q! Y    vexTable[vexNum].data = d;
    * w5 o: x5 D. V" H4 \9 w: W6 _4 V    vexTable[vexNum].firstarc = NULL;
    % t, z& C( o5 D/ J: U1 U4 O; K    tag[vexNum] = 0;
    ; h& H$ m- h, V, a9 n7 u    vexNum++;& L8 s- e' P) A8 }6 R9 d8 N; U
    }( M0 o1 h2 G7 _, M( U
    template<class ElemType, class WeightType>
    : Z( ^* [1 e& i0 tvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
    * v: R- R4 s0 ^) O8 [{& U2 s! B- o9 ?6 b) ^
        MultiAdjListNetworkArc<WeightType>* p,*q;; H7 m7 W, T! `' i( H" v
        if (v1 < 0 || v1 >= vexNum)1 V( G. X7 u! o5 d/ ~5 L
            throw Error("v1不合法!");0 u: i+ a; k8 t9 K' h
        if (v2 < 0 || v2 >= vexNum)
    3 w% J$ B. O( D  V( c) V. K( M        throw Error("v2不合法!");4 v& e* \6 k  P* f4 ?4 A8 H3 N
        if (v1 == v2)
    4 M" F; _( P1 {% q, X! [        throw Error("v1不能等于v2!");/ ^+ h4 v& k/ |
        if (w == infinity)
    / V4 G& g: D8 h3 r9 a& \        throw Error("w不能为无穷大!");
    9 y% d" [) L' V5 h+ ~
    # x( ^( C' Z7 `- z! O$ k0 l. Z: N+ H* K% F  ]
        p = vexTable[v1].firstarc;
    / ^+ `. s1 ]3 B0 T/ W& A    while(p)4 i" x. w0 }+ P5 r# ~9 Q
        {
    / j- ^# w9 `( b1 k7 {# Y        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中7 e+ h$ m6 y% s, r% @) r
            {
    - U2 s* O+ E7 J& O4 @1 s% p            if(p->weight!=w)
    - b; d) T. R* N& A& @6 y                p->weight=w;
    1 l6 }: P8 ^5 ^. b6 q+ n1 P% k& V$ [            return;8 l. @& |8 n1 a5 Z8 \
            }% O# U6 u$ H2 h! H% }0 z' f
    & L. X  [1 o- N4 d) a
            p=NextArc(v1,p);8 I! u8 N% c0 z" `" K! L3 |& m8 v9 [
        }; Y# u$ h5 ~" K9 e
        p = vexTable[v1].firstarc;# h+ ^0 T3 M, V# d
        q = vexTable[v2].firstarc;
    3 e0 r' |) h1 W# Q    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    1 j* h; E: k# B2 l  {    vexTable[v2].firstarc =vexTable[v1].firstarc;
    ) I* P: X$ V  M6 U% p    arcNum++;
    0 e! r! h. R% i/ Z- q$ m- s. J}
    # A9 ]$ c. Z2 u0 L: }  @/ r
    ' k$ X- [7 H) [0 J. N0 Mtemplate<class ElemType, class WeightType>
    8 T% L% V: C& `2 z8 nvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)1 G2 c/ W+ k* Y( R
    {
    ( b$ K) g4 Z: p# v- O6 c7 r6 z' X) J- ^6 W- E: q
        MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    * A1 i7 J5 ~1 `3 y/ M7 v5 u! t    if (v1 < 0 || v1 >= vexNum)
    * U$ p8 W" z/ ~" b% R1 @& S        throw Error("v1不合法!");* N( Q/ i3 _6 i
        if (v2 < 0 || v2 >= vexNum)
    1 l$ f, f# f2 J$ _1 H- z        throw Error("v2不合法!");
    & i- j: N: I# f* ^    if (v1 == v2)6 g2 \3 q+ a* p- i  J
            throw Error("v1不能等于v2!");
    ( \& \, d; M$ I, Y
    3 `# E& _* I8 {    p = vexTable[v1].firstarc;
    8 ^+ J/ v7 [7 p1 n7 [/ J  k! C' f    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    $ g' s$ }7 m# V4 ^8 e! k3 r    {  K$ f0 D6 t- X/ S, D, S
            q = p;
    4 M" P( r. E5 q# T4 {: i        p = NextArc(v1,p);& A+ f# |- K  b4 q7 |1 M
        }//找到要删除的边结点p及其前一结点q
      O4 n) y) q: F/ \9 `
    ( j' E2 q6 J# Z( X    if (p != NULL)//找到v1-v2的边
    / Q' C- O- d' {8 s6 X1 f    {0 H$ }4 I3 v9 g0 j. \9 |% I0 a
            r=LastArc(v2,p);  o2 ?. {" ^  l2 a* A
            if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    9 y( X6 V: }; ?! C" v            if(p->adjVex2==v2)# ?; }! c) ^$ k: C
                    vexTable[v1].firstarc = p->nextarc1;4 i( V2 Y  \; J% M" s( }/ N
                else vexTable[v1].firstarc=p->nextarc2;
    $ S" i/ \: L# n; p$ B" M0 j3 c8 D$ @        else//不是第一条边9 q/ B4 x# s" H9 ~
            {  ~1 {; H" }7 r- K
                if(q->adjVex1==v1)
    $ \4 O3 s. k4 \                q->nextarc1 = NextArc(v1,p);! K( i' F+ C" ?: r! R
                else% a3 g# [* c9 D. j  K. c
                    q->nextarc2=NextArc(v1,p);
    $ M+ _% H) `0 G6 \8 T5 R3 L7 L; t" N+ B. E6 v# l; U! L$ R9 t9 G. L
            }6 F0 U+ h( U9 a: H! x! j
            if(r==NULL)
    + ^$ J7 c" i2 }' R' g4 L            if(p->adjVex2==v2)6 k3 C& ]( }" Q. ~# I4 c" E: x
                    vexTable[v2].firstarc = p->nextarc2;
    ! A* s2 T* ]! P            else vexTable[v2].firstarc=p->nextarc1;
    / V* p* n& n4 w/ t6 B6 h) @: J2 U: N        else% Z* ^& D% y' C% ^, k  S
            {
    3 r) [, p$ \- s( {+ f7 H            if(r->adjVex2==v2)5 J( A, r/ J1 C% Y; I
                    r->nextarc2 = NextArc(v2,p);  G+ P& R5 J2 D
                else
    9 H, `1 ?; y* a$ I3 _% a                r->nextarc1=NextArc(v2,p);
    9 X. S% v- X( x* u7 D: s        }
    ( l% K( Y- M+ T: B8 B        delete p;! d4 \2 @  N( ~  O9 ^" m
            arcNum--;# {9 n" [$ w8 p9 d  t4 p; g
        }& n1 `0 s; H6 N; v) S. M

    ( J5 k  @" n! H" D}/ u8 v9 H* M3 H9 {* |8 X- \
    template<class ElemType, class WeightType> void0 h$ f4 `) D7 p! L+ f
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    9 Y2 q+ b" m# _& @{2 p* x$ q9 _' N5 v7 e
        int v;$ t6 c  F% J. d2 ]0 v5 P' }  ]) ~
        MultiAdjListNetworkArc<WeightType>* p;
    - F4 z; f" A7 p1 b" K; p0 G    for (v = 0; v < vexNum; v++)//找到d对应顶点) S* u5 E8 k9 D6 |# A5 E( N" _
            if (vexTable[v].data == d)
    , a' L9 [. e5 N& [: N3 x0 i( ~            break;
    6 u. y5 _" O% S$ q0 X/ q+ A    if(v==vexNum)
    % z% X# H- @% h/ V9 E/ N/ W( R        throw Error("图中不存在要删除的顶点!");
    ( n1 y/ V' G1 H5 X8 l% t9 }
      F2 l% N0 e: i) t, i# a    for (int u = 0; u < vexNum; u++)//删除与d相连的边# @4 B; T( P. w4 {! Q
            if (u != v), {: A) C2 B/ C. |8 c+ Z
            {+ N4 `6 i% p1 u: l1 ?  O( ^
                DeleteArc(u, v);
    5 N- }, N% ?/ y0 ?; z# Q" ^& _        }
    ' l& y% i, Q4 l    vexTable[v].firstarc=NULL;6 d+ t4 ?. S6 O$ o

    + @- _# e5 V7 A! a    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置- s. `- Z6 G0 ~! ?  [4 w
        vexTable[v].data = vexTable[vexNum].data;
    6 W  V4 ]" ]$ u5 o    vexTable[v].firstarc = vexTable[vexNum].firstarc;+ Q, }- h$ [& J4 U
        vexTable[vexNum].firstarc = NULL;" ]+ I0 X6 m) o# I9 v7 H" d
        tag[v] = tag[vexNum];
    ( @' S4 ~9 \4 K5 ^3 D    //原来与最后一个顶点相连的边改为与v相连
    - ^8 ^# g5 ^/ S9 K! E  g    for (int u = 0; u < vexNum; u++); p* D1 t+ r3 A2 i
        {) V' g; ^; f7 f+ l' T. [% D6 P
            if (u != v)0 u" ?& h; V; x) Z( V" L! s, x
            {" e1 A/ T# p9 O' I2 V0 [
                p = vexTable.firstarc;5 C. v: h7 {$ S7 c) s# E
                while (p)2 Y% O* y7 q& C
                {/ |) C8 m1 N2 K5 k: v
                    if (p->adjVex1==vexNum)" u& m& w. \# T, u: v
                        p->adjVex1= v;
    3 @3 k  Y5 s/ j8 {2 O                else if(p->adjVex2==vexNum)
    ; g  R+ q% u% s+ \                    p->adjVex2=v;) U9 }' |- I5 F& {9 d7 i1 G+ d/ O
                    p = NextArc(u,p);
    # G+ t" O: Y% N  Q0 o! ^* Y            }9 e0 A1 n  C' L. D
            }5 g8 C! O6 d* i' }' K" i
        }! _# b0 s4 q  C# e. H' E- _
    }
    & b/ i4 R1 C8 M///深度优先遍历
    / ]: z7 s6 U3 ~1 I1 T2 [9 @template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    ' c1 _: \6 h9 g. h/ F{
    ' c/ ?$ E. f( W  I5 O0 U    tag[v]=1;
    : i" Y" K# V2 O+ A) o2 q' h1 Z+ y    cout<<setw(3)<<vexTable[v].data;# x- }+ P* s4 o8 w
        MultiAdjListNetworkArc<WeightType> *p;
    % e; G/ b2 X' `1 H" S. y/ ~    p=vexTable[v].firstarc;% D8 l- H( b( @3 I; p! B4 i
        while(p)
    + M. d5 b3 _9 j2 n! z; S/ A    {' h. O+ H- p. ?8 e: Q7 Y/ w
            if(tag[p->adjVex1]==0)
    ' ]. p3 t# z# h+ z5 n            DFS1(p->adjVex1);
    , G% W3 H6 d1 X; l; Z# V        else if(tag[p->adjVex2]==0)% }' n/ Y. ?+ F- L
                DFS1(p->adjVex2);
    + t2 R$ Q2 b' @2 M- z) K        p=NextArc(v,p);
    4 z0 l9 D& @. E, _: I* Z- i7 O1 |    }. z1 A6 V# O" p+ I3 ?4 y1 X5 |8 {
    }) e3 @( u' K4 f
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()4 O3 |6 e- x4 w/ X4 d
    {/ V7 E5 q0 d- h+ m( a5 r% W. ~
        for(int i=0; i<vexNum; i++)
    - `, z& W' ?3 @+ m6 A6 ?        tag=0;' \, P; C3 q, K7 z& C; q- i/ x. o5 D
        for(int v=0; v<vexNum; v++)( r0 G* _! i8 r& l' y( p$ Q
        {
    * h% f8 X1 ?7 \" {7 A        if(tag[v]==0)
    - ^6 ~  x+ }3 I- H( m            DFS1(v);( w; T2 w5 ]: ^  f- U3 Y
        }' M& R7 Y1 ^4 U* n% B/ i+ K8 ]9 f' N
    }: F6 l9 m( x' S4 g! Y% p- k
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
    , e/ C) Z, T! t! M, p+ T0 B{/ }# o" g) c5 N: {6 ?' K
        stack<int> s;
    8 e8 i7 F- x9 d2 x$ c    int tmp;
    3 T: \9 l: r0 o: |/ r: E    MultiAdjListNetworkArc<WeightType> *p,*q;
    ' T8 a  B: v- V: P    for(int i=0; i<vexNum; i++)
    5 P* z* _  y3 ]- l" k9 r7 T$ Z1 }        tag=0;! i+ Y: e' k4 u: C" I
        for(int i=0; i<vexNum; i++)
    + Y# Y0 [3 C1 k( Z4 ?$ V4 b, V    {
    6 W( l% K. a$ `        tmp=i;7 ]2 n; j3 G. e: y  F
            while(tag[tmp]==0||!s.empty())
    5 O! n# ^* E+ Y        {! E5 l  |7 H, }* o- p
                p=vexTable[tmp].firstarc;
    9 K& ?" S7 }' s1 a& Z0 u            while(tag[tmp]==0)
    " U3 P% r! P) @. M            {: g5 Q: N; V) I2 s/ L6 n( h
                    s.push(tmp);
    * W% D4 @' H. X                cout<<setw(3)<<vexTable[tmp].data;' F/ ~8 P& M3 y2 r
                    tag[tmp]=1;$ Q. q2 u! G6 d. e( w% M
                    p=vexTable[tmp].firstarc;
    9 j" k7 L4 U* {4 A7 S9 p8 s3 \! R                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for0 E/ T3 i' B" h% q& S; `% t
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    / t* C7 \/ y* r* X; U) o                //cout<<" 1st     tmp="<<tmp<<endl;& e3 v7 P" H* R# w1 o! q
                }
    6 p* }3 D9 |( M9 C9 B! o/ D            if(!s.empty())
    1 o! g8 Y+ o  n& I            {
    ! E5 |/ u9 _2 j                tmp=s.top();/ [# i2 T, R$ v6 J+ l/ N1 d
                    s.pop();
    ! S8 ~* v% @1 K0 {                q=vexTable[tmp].firstarc;- P# D- E  p- r7 [7 w1 |
                    int t=tmp;
    1 I3 s$ v5 ]4 J7 {( |$ T                while(q&&tag[tmp]!=0)
    / L9 X% \" o  [- X                {
    / e/ ]6 V0 K+ e: }. ^                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
    / ?5 n" E( D; _0 N) u& m" ?3 a/ s                    //cout<<" 2nd     tmp="<<tmp<<endl;
    9 R- _. k& G! n( Q+ m* ]8 d                    q=NextArc(t,q);1 _7 P' D0 q7 T( F, Y! T! K& |
                    }% d% h5 z1 T1 `/ y# A& k
                    if(tag[tmp]==0), \0 A. h5 E6 S, C$ f7 o# ^
                        s.push(t);
    * |6 w6 t/ i" Z, G& ~: P8 m                ///1、对应上面连通分支只有1个点的情况: W4 o- F. p. ^- `+ R0 f
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈/ K  c3 g5 p2 _
                    ///tmp要么等于找到的第一个未访问节点,4 S. r2 i4 a4 z9 O8 l" k' Z( S' K
                    ///要么等于与t相连最后一个点(已被访问过)
    8 R6 f6 E$ Z2 f' c, f                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点& \% D, E$ B7 p8 H9 T/ P7 Y! y0 Z
                }. c2 Z' r$ L$ o. G( Y
            }
    1 X9 X" ]+ ~! P7 j. F6 A: v    }
    ) p, _/ F6 R* |* F; U}/ E3 d6 N% v+ ?  c. i: ]" C. B6 ?, C
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1; x  f0 }. Z. c7 o. d
    template<class ElemType, class WeightType> int
    ' ?$ A5 P+ T4 j: R( S5 M  lMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
    1 U3 L4 b- C! O- ?; i+ u{" u# U8 e3 D; j8 q7 x
        if(head==pre)
      P" ]; @4 `$ [4 R        return -1;( O9 f" v* t: A* c0 J
    & Y# v; i  O( ]5 d
        MultiAdjListNetworkArc<WeightType> *p;- v6 x  Z  w8 V) m
        p=vexTable[head].firstarc;' J) {/ s1 s7 w9 D5 ?) C; R0 I- g
        if(pre==-1&&p!=NULL)  C3 E% B/ T# y  W9 A. {6 \
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
      u. Y9 l' b7 @    //pre!=-1&&p!=NULL
    2 D# V& H6 ~+ h    while(p!=NULL)' c4 O% ?% @! j% I" t- x
        {
    ) H  j% b; C6 l        if(p->adjVex1==head && p->adjVex2!=pre)
    , P7 E8 {, H2 `* u  A            p=p->nextarc1;: Y0 {% E" T- m5 j; d
            else if(p->adjVex2==head && p->adjVex1!=pre)
    9 H7 ^$ a, q1 \            p=p->nextarc2;
    ; }6 ~% z6 @% o        else if(p->adjVex1==head && p->adjVex2==pre)
    # |2 k" _! u  @+ G2 L& v. J        {+ }; ^  E# m: E! E
                p=p->nextarc1;
    2 g: P% S: N4 z" k            break;+ l7 b4 k+ w# B% H) `6 n
            }
    / ?7 L+ g% C3 Z+ m* [: Y  l7 H        else if(p->adjVex2==head && p->adjVex1==pre)
    1 T# v( Q$ Z: l        {
    ! n- B4 l# {9 r: s9 X# ~  W3 P# A            p=p->nextarc2;
    3 n( `, s0 g1 N( h4 @$ ~- e            break;/ `/ }6 O# z  y0 H* m
            }; C; d4 j& b# [" I% |
        }
    & h# _# o, L" o" d: z    if(p!=NULL)
    5 |5 ]1 l: w$ }    {
    + @- v  o8 k5 A( L  v2 Z" n        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    ( r0 N* T% p. V6 \! h    }) I  U8 N  U# l* c: E, _
        else
    5 U% d  p6 {- j+ }% J' v$ E: p/ c6 G        return -1;5 `3 E; s% F% b" O) Z
    }
    0 u( D6 M; K6 o  V+ i- j6 a; e, R* n  y) U3 b' R

    + j$ N& E' M7 B- [template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(). z5 h$ p2 y: k) a
    {
    ( O7 T" @* z( y3 M) A6 N* k5 M+ \) e4 K    stack<int> s;; l8 ^5 {) ~, |  f
        int p,cur,pre;
    + ^/ C2 V/ J# O* O0 p    //MultiAdjListNetworkArc<WeightType> *p,*q;
    1 @. d7 H7 e/ A8 I: R    for(int i=0; i<vexNum; i++) tag=0;//初始化) h7 a  X. n/ q/ }. E

    3 k/ E4 d7 w' z/ f    for(int i=0; i<vexNum; i++)) ?$ U, s% _! n" I4 X- Z
        {
    ; j$ Z1 _  Y: d  u; E" O2 l        cur=i;pre=-1;
    ! K0 o, E" a8 S' g        while(tag[cur]==0||!s.empty())
    , p# o: C2 T0 G3 D% U        {
    8 o; n$ N. E* v# m" K2 o            while(tag[cur]==0)$ _, w  z/ t* p7 l
                {! ]% G. a, u- N
                    cout<<vexTable[cur].data<<"  ";& H) a. t! D- p2 F: i* M
                    s.push(cur);
    5 A( S2 N! t3 [1 z5 C4 A- V+ L5 f9 k. ~& x                tag[cur]=1;
    ; j" R' H( r# Y) @, ?               //初次访问,标记入栈: P7 H* O( d1 d* u& x0 B
    + N) O6 d! Y. a' ^) r
                   p=GetAdjVex(cur,pre);//p是cur的连通顶点  t/ I) a( {. ^5 g
                   if(p==-1)9 C/ B; k/ g* P  S2 o# d
                   {0 Q0 h" `8 K, c& \
                       pre=cur;s.pop();
    $ U$ c: q, q& e, `( X                   break;- ?5 P: |" H9 J/ Z
                   }
    7 x' u2 X! |8 [% L" v. _               else
    & i( W" I+ H6 K               {9 U; `& K2 _4 X4 S
                       pre=cur;
    7 h% p& {6 U0 A6 _                   cur=p;) h7 a1 H1 v; R5 a# f  `# A
                   }
    ' h" ]- A2 u. D$ N; u# w
    ; W1 X- H; s  \+ ^            }) ~/ K3 {* F, ~6 p9 @$ l
                while(!s.empty())
    - }3 G* j0 k  {$ K            {4 G* E0 Q+ ~* |; L& C5 \
                    cur=s.top();3 b3 q3 ?# w& \: T3 g( X6 V
                    p=GetAdjVex(cur,pre);8 x* N" p6 P' n/ m4 q
                    if(tag[p]==0)
    $ I' ]9 m5 c/ }! ]                {0 R4 W5 X6 y) z/ M( s
                        pre=cur;# |. {2 m6 \% A8 }
                        cur=p;& g6 b* u( N& g" w
                        break;
    : V# H' V, i. C/ [& T" E4 C                }
    0 g2 j' ]5 Y  \* x9 [$ l2 I' ^                else
    2 b. o1 D2 [+ o$ x! n                {. d% D5 G2 R- b  P# p7 Y2 a, ^- n
                        pre=s.top();
    ( l9 n+ m1 s! j# P$ k' C                    s.pop();$ J9 S. ]! o6 \
                    }
    5 T. s/ ^7 Y9 X4 s/ ?9 U3 ?1 H/ T
    7 }3 D& y) ^7 M3 Q6 j3 f6 S* F+ I" w            }5 ?3 C' i/ }6 ~

    + x* [7 O# ]0 X' T        }
    ! l4 Q: h% T& |    }
    8 ~- F8 G2 z( S" o" X. g}" ]' y1 h6 @5 \6 A' [* V3 |
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()$ q4 i. N6 @) E6 P+ g5 ^1 x
    {! P1 |3 R! B' r: D; p
        for(int i=0; i<vexNum; i++)
    . e2 a3 K" l' C# @; \' Q& S        tag=0;
    4 @8 U4 z4 }: ~9 i    queue<int> q;
    " |  L" [+ d, c) n) e; _4 y    int tmp,t;6 b2 l+ G# T- l/ Z/ I* s) k
        MultiAdjListNetworkArc<WeightType> *p;
    ! Q$ ^/ L7 u6 W) G8 `1 \7 Y, L    for(int i=0; i<vexNum; i++)' V+ I. ]! w; N2 a% M; n& g
        {
      [2 }9 ]( W6 _1 \$ L' ?        if(tag==0)8 ~6 D6 ~' U  Z# ?
            {
    + L$ O% ]: O1 q4 o            tag=1;& w! y/ x* ?" B$ v; g+ Y6 O
                q.push(i);
    7 k: V9 q+ W/ n. k            cout<<setw(3)<<vexTable.data;! \4 H4 d' j3 a2 S
            }+ t7 M$ a3 _! |" H( k- T
            while(!q.empty()): A7 L# E1 j  p0 F  |6 C
            {
    ) v/ ~1 g  s; |. N/ t. X            tmp=q.front();
    0 h  Z( }6 T3 K# P            q.pop();/ H2 e& B8 g' Z5 m
                p=vexTable[tmp].firstarc;
    7 {3 Z  v  i1 ]            while(p!=NULL)
    ! s! G5 _) L2 z+ T& `. ?3 Y3 N            {: V8 N5 F9 ]0 x5 l# W, U+ J
                    t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    6 f* E3 h. V" g( f                if(tag[t]==0)
    + _  Y9 S, `6 @3 ^+ B                {( p; C; f0 i$ d
                        cout<<setw(3)<<vexTable[t].data;4 q6 l' i; p$ K, P) _: D4 v2 I
                        tag[t]=1;
    % g% W6 J: r2 h6 A( K: J) Y; ~$ v                    q.push(t);
    ! V  \$ D: I* s" o8 l( f' k2 H& R; U1 P                }6 {5 ?; W" s& A$ {7 M
                    p=NextArc(tmp,p);
    ) k' L! r) N, r; Y5 |            }
    " \. B# i0 F) \- K        }
    ' ?1 c+ k; u" R" `# Q    }2 U# X/ c8 t: S4 c
    }3 y9 D: A+ S. q8 T0 a* ~
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
    $ L9 I+ ~8 c/ L/ ?5 }8 J{& p, [5 y6 g" W) @" w
        MultiAdjListNetworkArc<WeightType> *p;* A- n. b7 W7 c* l4 m: Y
        cout << "无向图有" << vexNum << "个点,分别为:";4 z, L. P- Z  e5 `
        for (int i = 0; i < vexNum; i++)3 X2 i+ J9 x1 N1 c$ g: c$ \$ x
            cout << vexTable.data << " ";
    1 [+ M) p, _/ `    cout << endl;6 k4 ^3 Q0 y- U5 E# L$ o
        cout << "无向图有" << arcNum << "条边"<<endl;
    . I! Q( r5 [( E    for (int i = 0; i < vexNum; i++)# p7 o! o) A4 B+ g' `9 @
        {
    / J. q4 I' t! z5 \0 A& T        cout<<"和" << vexTable.data << "有关的边:";- X0 ^( U3 x: s6 v. ?
            p = vexTable.firstarc;
    ( o9 t1 \- R9 e  q2 _        while (p != NULL). T: K5 L3 O& y, t6 x5 j
            {
    3 x: W# H4 x1 q2 U            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
    8 ?' q0 c5 x* f( b# o; }6 n3 q& w! S            p=NextArc(i,p);, f7 x* M& {4 q1 y5 j/ U
            }
    7 w2 H! |3 M2 Z8 J4 y        cout << endl;
    : D+ |4 B* X3 Q/ e8 W! B3 u" {    }. I  G" `, v3 C: D, m0 F* C: k
    }
    % V1 E& ~6 V. u8 N- c0 A$ _, Z/ k
    % _% }5 q4 C/ r0 p- X6 j; F% K+ P5 P) V* h; Q7 P& }2 F# S
    邻接多重表与邻接表的对比5 O: L/ {1 T" ~. f+ X9 W

    7 `  L) G& g; ^- G2 W' Y! ~邻接表链接3 @2 s  x5 Z$ R, g) ^$ }5 Z, c$ `  s
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
    : m  G( \" [1 E4 j! ]! b在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。3 Z( [) W6 p* Q. i3 ^4 z
    为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    4 t' W* N4 V1 z1 ?/ @————————————————8 I/ l1 C0 k3 \( Y) h+ ^
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。" z6 \/ Z0 n1 ^% Y" D% }
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    : s" L" u7 L/ U' i) \: h1 L# m/ a! Z" s$ U& @- n: G- [* N! Z
    6 X! L8 e, W2 {5 a8 @- F1 _

    # V; X7 ~1 i+ t8 C# [4 q! F+ F0 X6 H: i# [2 ?
    ————————————————
    3 C+ K) K: D. _4 |$ c) S版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    5 |& n) n* F: t4 K0 p) K原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    * T$ Z/ C; X  @+ x; r+ v, N, S9 f% F) o4 i7 E* E, B9 `, N

    , E" h1 d: C, R& h1 }
    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-12 06:50 , Processed in 0.442136 second(s), 54 queries .

    回顶部