QQ登录

只需要一步,快速开始

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

    ! H! `# H9 ^5 G# M图的存储结构——邻接多重表(多重邻接表)的实现
    + q, N2 ^6 |9 [& c) f7.2 图的存储结构* z+ d) M/ X$ {5 i( j7 J* t

    3 s$ o3 O8 S) p+ P$ q1 U& o  \8 _7.2.3 邻接多重表(多重邻接表)Adjacency Multilist; }6 h0 l7 w9 G+ k
    邻接多重表的类定义6 U& }% S" E& F: b2 C0 j
    邻接多重表的顶点结点类模板. I7 o1 S- d- f4 M0 b+ x9 ^: D8 ^
    邻接多重表的边结点类模板
    2 Z: C& [+ \- f( E( ~. l邻接多重表的类模板$ J/ f$ U+ {$ W' I
    邻接多重表与邻接表的对比( T$ n# A5 a6 b( l7 J* f
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    ' Q- p9 L4 g0 z( W8 O* [/ v
    & m2 |& u. y- b5 n5 V在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。
    1 y: @9 m) c" z$ R" [* \5 n/ n* U. e在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。9 Y  K5 k) w2 F! j: S
    0 L5 K! F) E2 u& m; e2 Z$ [) H& {
    邻接多重表的类定义# L5 C! x& p3 S
    1.png : X" L( t7 Q1 O2 H  ^' k6 w; x4 a; S. a
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:
    2 Z4 ^8 \4 Y8 U8 b. idata域存储有关顶点的信息;- @; G1 ?' c* _, G
    firstarc域是链接指针,指向第一条依附于该顶点的边。8 [' v& H! f% k" ]; ~4 }
    所有的顶点结点组成一个顺序表。

    2 ^! ]* c3 @* ~6 ~2 J$ Y& |
    8 W/ y- N* H" {  r) N' W. l
    template <class ElemType ,class WeightType>. N- g$ V5 }$ n- y
    class MultiAdjListNetworkVex2 }6 y0 W% Z, L8 z6 x
    {' O( ^  Y# y5 c9 e
    public:
    ) @  _" S0 S6 \+ j6 D        ElemType data;
    ; g' o1 `5 a2 i. `  Y4 F, [  k7 [        MultiAdjListNetworkArc<WeightType> *firstarc;
    8 p# j1 t" Y7 b8 a4 K5 v
    - [4 u4 o, z* U* n$ B        MultiAdjListNetworkVex()
    * {8 G: i2 t" h# a8 O% G        {" T# e. z( D9 t$ L
                    firstarc = NULL;& t8 i& e# ?( {/ }, M" I$ q
            }- s5 c' Z$ C0 n, e& E, N1 W
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
    & d! Y/ y5 o2 U5 P0 |5 e        {
    ( o) B; E# W" S; q. S+ d6 F5 Q                data = val;
    # S/ t# J7 b! X. N9 S: k' v                firstarc = adj;
    ; M5 F; K( L! `3 o( O7 {( k        }+ s' f2 {: j% v6 Q& |  Z/ t
    };
    1 S# q: s2 b2 M& D" Z8 S% K. @9 h: K& r( `* Q9 v2 F
    邻接多重表的边结点类模板3 w0 d5 k3 p+ \
    ! n3 q% {( r' u" d
    在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    ; Q1 S3 l, N( Z. V- @tag是标记域,标记该边是否被处理或被搜索过;- H$ k, C" l5 Q  M: k
    weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;# I; R5 P* D7 n" Q
    nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;
    # W' M3 c* j2 S& L" @nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。% G/ n8 p: \0 K% t4 b  k7 G
    3 F( M) A, y, U/ [; I, N
    2.png : f# a8 c# p" ?: [9 B1 _
    template <class WeightType># F: z& [6 ?5 Y' `* Q
    class MultiAdjListNetworkArc1 Z# b" f0 ~. e% o% P- x
    {
    , o& n2 M9 E5 ]* q8 C- gpublic:5 S3 F% f8 r6 C: Y: j3 k: E" x, z
        int mark;                                       //标记该边是否被搜索或处理过4 M+ V! O  a3 g& [* K9 J6 y. G
            WeightType weight;                              //边的权重
    " [4 U0 I4 ?6 k3 g1 Q6 B  v# Z        int adjVex1;                                    //边的一个顶点
    7 o  E/ w% J% G' `( K; w% E1 w+ {        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
    5 i) X1 t# W" g7 k: O        int adjVex2;3 Q" \# b6 n4 S3 M. h$ Z- @
            MultiAdjListNetworkArc<WeightType>* nextarc2;
    * x( h: A2 |/ A" ?# m5 I& D2 A* k5 C
            MultiAdjListNetworkArc()
    * o; r( C* q5 n5 k        {
    & Y# s- T' k8 I! T2 R, Q! W# T                adjVex1= -1;7 _' V/ o# K. p5 `  w
                    adjVex2= -1;7 E! l& G" {6 s1 I) P
            }
    % y3 I+ {! R' a2 D4 V7 K% \( Z8 o' s        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)6 v5 o3 i. F0 x3 v) [4 J
            {
    4 X2 t% w: x# m- Q% t; V' a                adjVex1 = v1;       adjVex2 = v2;; `( A( [7 @& X3 v+ B( x
                    weight = w;1 U1 w; l# g$ }! ]4 }- Y
                    nextarc1 = next1;   nextarc2=next2;  j, s( R% K4 v
                    mark = 0;           //0表示未被搜索,1表示被搜索过, s3 [2 d$ _3 @1 ?4 x! p
            }; K8 O5 K( h7 Q2 B* z

    + X% G0 J' s- M0 J3 g# |! h邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>1 H* E: v. z  j" l2 g
    class MultiAdjListNetwork
    ! h6 @  z% J: v+ p$ b{
    + o0 y$ d! H: \9 m; r& }protected:6 \8 a5 q8 H9 _1 g  y1 Z
        int vexNum, vexMaxNum, arcNum;/ g% F! P/ J" ]6 `9 c! Y
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    # B9 ?3 I% c/ \: i9 J4 S# _& j/ |    int* tag;+ z6 l8 I$ _& L7 F2 y
        WeightType infinity;
    1 Y9 P3 e. D% |5 W$ M
    % T" T' h, K: |0 spublic:5 _2 [% I4 W' Z/ K+ H' X9 z
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);" h. J( B. X! {3 P9 L* s9 a

    & E0 `+ r4 d/ A2 S7 B    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    0 g, R7 M) @! p
    & o9 O4 c% l  F- z; A    void Clear();- i5 {0 {- |# s
        bool IsEmpty()$ q5 |8 b7 C$ p# [! S) y0 k
        {
    ; {4 ]( }0 i% P+ F        return vexNum == 0;
    ; r! }% x8 d, ~! F' {9 K% ]8 |* k    }# ^8 K1 j+ `2 Z; K! J; l
        int GetArcNum()const& T) T: j3 y% @& ]  @- E
        {! u  ~/ ~0 w7 P, j. }
            return arcNum;3 I3 l+ o& y. _9 u4 F
        }
    ) ^# w- }( o, e# @    int GetvexNum()const
    , F- Q& d9 [; h    {
    9 ^8 ]3 i6 V' \' F5 i        return vexNum;
    " T. A1 r2 W( k7 s7 a% r0 ?. p    }
    9 o  G5 d5 Q5 s2 e$ y) A6 b$ q$ j5 \1 |% t7 l
    $ T$ ^- V# D$ F0 c$ w' ?  L
        int FirstAdjVex(int v)const;
    0 _# W( ]9 T/ I1 o+ y1 A3 G) ~    int NextAdjVex(int v1, int v2)const;8 ~6 k' v6 _8 Y5 \: @
        MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    9 |; d: }8 P5 a, Y( V    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    , t9 O7 {, Q$ t9 N
    + c7 P1 t5 Y  A- b6 A    void InsertVex(const ElemType& d);  }' s5 D3 ]# n
        void InsertArc(int v1, int v2, WeightType w);( E0 \0 j2 g8 t2 Z8 M: u
    1 x( X& {0 x: q1 j
        void DeleteVex(const ElemType& d);
    & y% D" d- }7 x# `; f  f! M    void DeleteArc(int v1, int v2);( P3 Z6 Q, O. S3 a  {3 t
    $ a, [2 K' _8 w% Q5 U) ]% Y
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);5 g! o. A; C) z" H2 d
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
    7 Y# U9 Y% m  n. p, K8 g2 ?7 Y. V8 j
        ///深度优先遍历9 a" Y6 \4 r2 \" ~
        void DFS1(const int v);0 y. T% G4 W! s4 H! [# F9 {
        void DFS1Traverse();
    . }0 }; @. N; r4 b    void DFS2();; O: y1 i6 e" f5 N
    : e5 d  m/ k7 ^( @: V3 q
        int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    ' O6 Y- a, \' W. o/ b/ Z" ?) u" G    void DFS3();! W: B# M& B2 W3 P, ?. h: {, D" J& k% [

    # m' A  m& R$ |6 k    void BFS();- ?! f" {" |* \2 |; g
        void Show();
    $ f( [8 M6 d( t6 A+ \9 m- |# s};
    0 z& H" `) l+ ~% ?
    $ H: _7 R( H0 L2 m, I7 \2 y; L2.函数的实现
    ' B7 W3 g( _: K! S研讨题,能够运行,但是代码不一定是最优的。- J3 S1 g9 C% P+ F) U) u9 z, b

    ' Y$ ~# w, a5 [#include <stack>
    ; k) q$ T) O$ b#include <queue>
    4 h) t: U3 s$ b9 j* t( K1 y
    ! s, X) ?' i3 X8 }- h) H' ]; Z1 p9 l1 btemplate <class ElemType,class WeightType>( a2 _! m# P. i0 p- @. K
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    ! ~! `; `: F3 c, J{
    " L9 H% G5 U6 a2 g! r, F8 P% Z# ]/ q( c( T    if(vertexMaxNum < 0)0 G0 p3 Y; ^( v' o7 E
            throw Error("允许的顶点最大数目不能为负!");6 F1 z/ R  h/ |- A( T! s
        if (vertexMaxNum < vertexNum)
    8 V; M  E2 o5 S3 z2 @( e        throw Error("顶点数目不能大于允许的顶点最大数目!");* T2 u& c5 a  V- ^1 u. I
        vexNum = vertexNum;
    8 O1 G. E$ J6 q$ d- Y2 I    vexMaxNum = vertexMaxNum;
    1 Q2 X/ c! _! ?0 I. q    arcNum = 0;! J$ X, S: r2 l2 f9 T& s/ }8 C
        infinity = infinit;: P8 ?' f+ m+ x7 u' e+ g
        tag = new int[vexMaxNum];2 i: m% K: C* w
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];. G$ }7 ~- k4 N4 _
        for (int v = 0; v < vexNum; v++)4 T& ^8 ]7 j0 M$ O+ r
        {" s8 A! G+ J+ \# G0 C: ?# J5 l! V
            tag[v] = 0;( `+ S" z0 }5 q6 t1 m
            vexTable[v].data = es[v];
    ' g' Z" _$ r- U1 Y        vexTable[v].firstarc = NULL;
    / O" F  i4 Z. Z& Y& F* X    }
    2 J, c$ w. P# w. C; ^5 J}) u; ^$ o. w6 u) c3 L  u
    template <class ElemType,class WeightType>
    ' F5 v+ H9 C/ g! V4 x  IMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    , Z( u0 S3 Y; f% O5 `/ m5 ^{
    6 D' f  N* F/ k3 @4 t* F6 P    if (vertexMaxNum < 0)# a: @7 k! A+ Z1 O1 c; t% D
            throw Error("允许的顶点最大数目不能为负!");# C0 m" K/ {6 G
        vexNum = 0;
    " P  A! C/ p) W; h0 v3 |; T    vexMaxNum = vertexMaxNum;
    0 A$ P" P5 Q$ z4 q    arcNum = 0;
    0 {/ ~* D5 k; @/ k5 s    infinity = infinit;0 m& y  |5 [# }1 W
        tag = new int[vexMaxNum];
    $ F  c  @9 n- X8 B( L9 f9 U8 G( X. w    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];( l- X+ g1 ~! T5 @3 K4 D/ p& p- e
    }2 s8 T$ H  M, }8 T! U% c
    template<class ElemType, class WeightType>* h  d" s" y4 _) z( p+ q1 W
    int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    - n' F; ?8 h: I/ n: j" @& g{" Y% _8 O/ |+ X, _  }" l2 B' C; N  {
        if (v < 0 || v >= vexNum)1 ?+ K! B4 u# U6 y" A
            throw Error("v不合法!");
    % `. W& m9 |; t% i    if (vexTable[v].firstarc == NULL)
    9 y# q, [4 ^' d/ Q" u        return -1;
    2 D3 {) |# ~6 `$ z0 M$ m0 U# j- P    else
    3 s. m. C. e9 K0 E        return vexTable[v].firstarc->adjVex1;* ]. ^; Y7 P8 k0 P1 }
    }
      X( C* _, \8 g* Z+ e, r0 A
    5 i/ z$ s2 N& O- @template<class ElemType, class WeightType>: Q. N9 j$ r: l7 ?3 \9 y. ]
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    ! x8 s# r. j/ x' J; u# G{2 T  [2 T1 @  \) f2 T5 X
        MultiAdjListNetworkArc<WeightType>* p;
    ( ]# d: T9 E/ S# u    if (v1 < 0 || v1 >= vexNum)
    " [+ R( `) A" w' D' ~6 F% \        throw Error("v1不合法!");9 t  i" r+ u3 F, T) d
        if (v2 < 0 || v2 >= vexNum)
    ' {: P5 S4 p+ k3 c. z) y6 N& s- e        throw Error("v2不合法!");
    * g! a6 `$ c0 T. z6 v, p& S    if (v1 == v2)
    ) @+ }! ~" F% I        throw Error("v1不能等于v2!");
      [4 f: M% h2 K# F0 B    p = vexTable[v1].firstarc;/ \) B1 Z: I; J
        while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2): s9 L# B( U+ D
            p = p->nextarc;
    3 g& c2 s, o% s2 g, D2 v" Y6 j    if (p == NULL || p->nextarc == NULL)
    # g; F4 r; X0 T4 [% R( B2 Z        return -1;  //不存在下一个邻接点
    9 N9 Z) y  {+ u1 J5 B- f    else if(p->adjVex1==v2)
    5 V! G+ c1 k3 H5 O  ~2 K$ K        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);8 I5 ~% ]9 x- N& F$ `2 J
        else
    7 D, O2 c, P& a0 X8 n  R        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    , l2 W+ F8 J2 [! k+ F7 F& J9 m}$ J) w1 n  w% w; `3 S6 b5 }
    template<class ElemType, class WeightType>
    6 C1 K/ w6 |) _% z: g! X9 svoid MultiAdjListNetwork<ElemType, WeightType>::Clear()4 f6 g9 V5 a' J3 y  B# E# q7 D
    {
    ) V. N1 q# I. [  r    if (IsEmpty()) return;
    6 p$ `6 r& a) E: r9 M    int n = vexNum;  s; C, T4 H- ^: q7 s5 F
        for (int u = 0; u < n ; u++)  Q7 b( a7 h) Z+ s: ^& d( F. x
            DeleteVex(vexTable[0].data);
    + p$ V7 l; [6 o0 L9 [    return;3 {+ `1 M( x; O7 C
    }
    ! C  F5 o0 b4 w: ktemplate<class ElemType, class WeightType>- g3 i- O+ l# B
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()# U4 i! B( ]) F+ {/ m
    {
    % Q6 h  O+ p3 n2 \- y8 l/ ]% f    Clear();2 L( `* h# C8 q$ N2 |* z4 z
    }
    4 j3 J, B0 ~) X9 K6 G3 d) W: f( s, Rtemplate<class ElemType, class WeightType>. E8 M+ ], k+ Y$ y8 A$ A* H
    MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    ' m5 W% r1 h" o{  A7 r/ |! l9 j- A9 \+ o
        vexMaxNum = copy.vexMaxNum;: r0 ?, ?. V6 N, f8 B
        vexNum = copy.vexNum;- u- u3 J' m6 b
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    1 J* _5 d8 F6 S$ K    arcNum = 0;& S8 P# a, o. O7 [9 }0 y% B/ F+ Z3 q
        infinity = copy.infinity;
    3 m5 h0 s1 O2 m2 p! T1 O4 ^' v    tag = new int[vexMaxNum];0 R- d7 @, J" d0 \8 q" C+ [

    ' ~5 P: v# e3 F+ `& X* O: x" r    for (int v = 0; v < vexNum; v++)
    " a. l# B4 k& ~, o; ^    {
    ; d2 N. \0 v& f( x7 x- o2 Y' {        tag[v] = 0;* I3 ^0 [' d* @, r  g
            vexTable[v].data = copy.vexTable[v].data;* ~% q0 A5 m8 e3 {3 Y4 [$ J
            vexTable[v].firstarc = NULL;! P2 _& ?! |# l: h- s3 X
        }
    : D& i, B, c& r" T9 ^    MultiAdjListNetworkArc<WeightType>* p;
    % `) ^" `4 R* _) q0 B" H. k, i6 V3 c3 l  K+ E& |) _5 _9 \& X  L
        for (int u = 0; u < vexNum; u++)
    9 e! d& v2 U6 c$ F( Z9 t    {7 D1 C# s/ i' _
            p = copy.vexTable.firstarc;, g; T" e, }4 b4 n+ r
            while (p != NULL)6 H1 [0 |% z& V* i! p
            {. v8 ]5 z  s" L( D  O/ N5 v1 X
                InsertArc(p->adjVex1, p->adjVex2, p->weight);8 w& Q+ O+ c8 `" {  s! T' x1 z  @' Z
                p=NextArc(u,p);9 P8 x$ y+ Z# ^: F4 t
            }8 W# S# J; Y3 R; g- _
        }4 a+ W4 T5 B, v; l* {$ |0 M. L
    }
    $ S0 V' S* o/ {! Ytemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&- L* H; w0 x7 J
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    / j  U% g; g: p" s  o7 }{
    2 u' Y- P! q+ S. B: s    if (this == &copy) return *this;
    % @) p, X  @: y0 b( p7 |    Clear();( V5 W4 }# m- r- |. @6 l+ Z
        vexMaxNum = copy.vexMaxNum;4 |: R1 {' Y% [0 h
        vexNum = copy.vexNum;
    $ C# w7 J9 P! N6 m& H* F    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    ( i( H( j1 V. i% }( H6 ~9 R; c    arcNum = 0;- H$ g9 ]7 f, w! M  V3 u" y0 H1 ]
        infinity = copy.infinity;
    4 c# \' R4 F2 C) R    tag = new int[vexMaxNum];  M+ A7 z9 j# r5 N2 x( Q
    # ~5 w/ a, j% B2 e9 E1 v) e
        for (int v = 0; v < vexNum; v++)( z, O3 V, m) y* Z8 w
        {' _+ r  Z2 u  W# x4 O
            tag[v] = 0;
    ! i( z; v/ b- X# h2 M* s$ ^' P        vexTable[v].data = copy.vexTable[v].data;* n/ H9 w7 z7 s% c3 ~7 b
            vexTable[v].firstarc = NULL;
    8 c/ I# e% w0 r; a6 b    }
    ) u8 C' E0 r1 A    MultiAdjListNetworkArc<WeightType>* p;8 s. F$ q8 u. L' K+ n+ y1 X
    0 T) i. N8 E4 o  b
        for (int u = 0; u < vexNum; u++)2 H% x+ y+ a. c# I# W( O/ C
        {
    8 X% c& i4 e# u6 ]! D/ G$ }3 ?        p = copy.vexTable.firstarc;
    5 x, J7 R  x. k# g! y& [9 Z7 d        while (p != NULL)
      O9 V. M# D6 S* d* E7 ?        {6 K4 r1 c6 C, G8 W. X; l
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    # n& d- W0 U  V# |, N6 o! K            p=NextArc(u,p);4 l4 Y; Q) N; A- H7 d6 U$ a
            }7 A. [. w' d9 |; V5 y& ]
        }
    9 ]* ~  H+ W; ]; Z; ^; |2 [    return *this;
    ! k$ `' n) _7 ^1 c+ O}/ J$ K, O" V8 W7 \4 S, _# f% ^
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    , B& j# _- z4 t( D# U( uMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    4 \, [9 l& @3 f( `% B3 b& @! W* h{) s  _' c' P$ _& i% g
        if(p==NULL) return NULL;
    $ f2 y" J  Y2 l, L* R  r$ \7 b    if(p->adjVex1==v1)1 E4 O( ~; g8 _  t4 b) G
            return p->nextarc1;
    , I8 I+ R9 }7 m: p    else
    4 i) o7 a! c$ D        return p->nextarc2;
    6 |) K$ w, A* Z3 N  ~4 t( ]% O5 v5 Y}7 b* k  {# B7 E# R4 u8 ^
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*+ \8 R7 V  t% H3 q
    MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    6 j6 h" V! o* J{
    - k) ]  S5 _0 F, _9 j    if(p==NULL)return NULL;
    ' @& D: Y1 E% ~; T/ c# g/ S/ p    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;& M. g$ }3 v9 q) F0 ^
        if(q==p), M9 I* `+ p4 S
            return NULL;
    : n/ [7 W4 L  c: K& |! k+ R# ?    while(q)
    ) V( U/ M- J, U' z' i3 d" z& B    {5 l! r5 P1 p: ^- x
            if(q->nextarc1==p ||q->nextarc2==p)1 j3 n. N4 |* L4 ?- }
                break;
    & t3 Y4 |, E  w( v        q=NextArc(v1,q);
    3 S/ v- E% `7 A    }
      s" W# w. w) T6 @3 D# Q    return q;
    1 W- o$ Z1 ~; v4 k1 g: I& A6 H! r}
      B" ]) K$ E+ d" |template<class ElemType, class WeightType>
    3 s  P3 H) O3 f( y$ ~+ J5 A! ?1 lvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d); O- c" n8 {8 B8 [+ _' Y0 l
    {! N" ]9 z$ u( j1 M4 @) W' b
        if (vexNum == vexMaxNum)' T, W6 e( ~% @& S( w/ A
            throw Error("图的顶点数不能超过允许的最大数!");# D7 C6 x% p1 Z
        vexTable[vexNum].data = d;# y3 }1 b! y0 }  `& _3 G) Q7 h
        vexTable[vexNum].firstarc = NULL;( d& x7 H  }. m% w/ P5 x2 H
        tag[vexNum] = 0;! o' a1 e* F0 r+ D& N, k
        vexNum++;
    ) L( B6 v0 h7 ~$ _' s' U}/ U* `! h/ m  Q) R8 j
    template<class ElemType, class WeightType>( q# t1 ?/ ]! b. n+ \4 V4 T+ P
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
    1 J. K: F9 b- ~8 B- _. k{" [+ F5 B) k& G5 M( y/ L$ f
        MultiAdjListNetworkArc<WeightType>* p,*q;* o1 l# v. s- @0 d2 w
        if (v1 < 0 || v1 >= vexNum)! l9 m; m. m8 D( s7 l- f: S
            throw Error("v1不合法!");
    ) C8 I! O- G* _  q0 T    if (v2 < 0 || v2 >= vexNum)/ e2 c* v3 S) J  Q5 ^1 y
            throw Error("v2不合法!");' S* f8 ^1 ]; s0 L
        if (v1 == v2)
    9 W6 H. B6 U; K3 @$ z        throw Error("v1不能等于v2!");
    ' q- [) Y6 O4 x. Z7 a    if (w == infinity); {+ m3 Z# L( B& [5 `; `
            throw Error("w不能为无穷大!");  Z. o: J: a% t! e2 s0 @) m0 K( q

    ) T+ x  h' v9 N* a4 k0 O8 ~* l( D- z/ K# ]! b+ _
        p = vexTable[v1].firstarc;
    0 n9 ]9 W- B- ?    while(p)
    3 @& N) \' m: G( [    {
    # n+ Y+ U; ^; P        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中3 @5 d2 \* T4 M7 B
            {: v8 O5 Q3 L7 s' v( k, K: s
                if(p->weight!=w)  ~7 Z/ G3 O8 z( D9 C9 z. T
                    p->weight=w;. b& l9 r( C8 X. k- K9 i
                return;
    $ X1 N2 v" j6 E  O        }% d" F. T* ]6 s! _
    5 C* {# g, e0 K2 y+ K7 e
            p=NextArc(v1,p);
    " m* {) g6 q. i6 L    }
    " G, P" G. P" E2 m    p = vexTable[v1].firstarc;
    5 j/ g! I8 R* R( x- R8 s    q = vexTable[v2].firstarc;* L9 i8 j$ n$ W5 ?8 g( ~  W, d
        vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法5 `( \6 Z; t1 B9 x4 D
        vexTable[v2].firstarc =vexTable[v1].firstarc;
    & d+ U: N" Y# y    arcNum++;
    & P2 t' E% [* A. w+ R! e}
    ' k+ M$ ~9 H0 z7 k8 d7 n$ o* L1 @6 l* K5 @' N+ f$ R
    template<class ElemType, class WeightType>
    & T0 E( N; {$ {- ]- }7 L; y- fvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)% I7 ^7 o- a) Y1 f( Y! W4 Q8 H" P
    {
    % _: H; v0 _/ z2 J; t& H" E/ e: ]+ k$ Q1 e
        MultiAdjListNetworkArc<WeightType>* p, * q,*r;6 a3 V% p5 A$ O7 g8 F
        if (v1 < 0 || v1 >= vexNum)
    0 |. ]: W5 B( M+ K/ l        throw Error("v1不合法!");* I) n; v1 \8 J$ w' a3 {
        if (v2 < 0 || v2 >= vexNum)
    ' p: e" I. _; A# v$ T1 b  H( l        throw Error("v2不合法!");5 c6 ]" p1 s7 `) p. b' x
        if (v1 == v2)  E; D1 Q$ ^4 }4 G- N( D
            throw Error("v1不能等于v2!");% u. J8 G/ ^- r- j  N

    * x# L8 b6 _# h0 ?9 j* d  f5 E    p = vexTable[v1].firstarc;% H) G5 S- f1 e
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)7 L( X: I, ]. e/ J
        {. L$ e  O& H. ^% w. f
            q = p;
    / x" M) K( X8 o6 c        p = NextArc(v1,p);% }4 H: C: r3 b
        }//找到要删除的边结点p及其前一结点q
    + R' d! P' F2 f: L: M+ N9 N/ F* }$ h" K6 o, S! c
        if (p != NULL)//找到v1-v2的边
    3 @% a* @6 Y. n6 ?    {
    0 q6 P8 r4 E9 h5 r: Z- V        r=LastArc(v2,p);
    / A* U6 d8 p* c; S3 m9 W        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    & ^+ t# @% |. O9 Y! l% w/ T/ D            if(p->adjVex2==v2)" X3 g' m  [, @. u9 [3 x; R+ j& d
                    vexTable[v1].firstarc = p->nextarc1;5 R" R! `$ j, s8 T  T
                else vexTable[v1].firstarc=p->nextarc2;
    ' Z/ W1 c& x' x0 \        else//不是第一条边
    2 V7 q4 t, F$ w/ n        {
    7 Q8 ?4 {- I- n8 l8 v) \, h            if(q->adjVex1==v1)
    6 P) v4 ~! b. d" c                q->nextarc1 = NextArc(v1,p);
    % z) k7 n0 Y5 k7 r' z            else
    ' r, q7 E) U# {' |                q->nextarc2=NextArc(v1,p);
    $ ~, ]- u( W' L- t& q' N/ i
    % O+ r7 B) i9 L8 F$ g' v% n        }
    4 H" ?/ R$ g5 z& L- q        if(r==NULL)
    1 L8 {, k7 o% i8 k" x) W4 L            if(p->adjVex2==v2)
    - E# w8 x" d4 [. U3 S                vexTable[v2].firstarc = p->nextarc2;. q% M- s) o9 A, h, W
                else vexTable[v2].firstarc=p->nextarc1;4 ]" e, s( E/ A/ k' R" s
            else
    . N1 M+ c, j/ O) I  l/ F" S, U' x* W        {
    & `: g+ b5 A/ L            if(r->adjVex2==v2)
    ' V2 p5 a& i$ D                r->nextarc2 = NextArc(v2,p);# Z% [" z4 Z( y5 e5 J/ Z
                else
    2 E* T7 @8 \9 o# z7 s                r->nextarc1=NextArc(v2,p);
    7 [8 x' O8 f+ b' T* }        }  ], _& t7 x% }
            delete p;
    . B+ y, ?* A  n9 J        arcNum--;3 s+ }, N9 R4 `3 j  v: U3 L
        }
    ; d+ g1 M/ n- j0 i7 W7 ?
    , P3 H* ^' m0 x4 |}
    7 A. S  i: @+ A7 w4 t% Mtemplate<class ElemType, class WeightType> void; M* v1 p2 T7 G4 Y3 I3 w
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)6 {$ d, G. j* v3 z
    {
    8 ~0 [( M/ V! _3 p* _  z! ^. D    int v;
    : s* q! g! v2 N2 o- d    MultiAdjListNetworkArc<WeightType>* p;
    . L. ?! o6 X1 H9 J- L9 s9 X    for (v = 0; v < vexNum; v++)//找到d对应顶点
    4 I2 v9 |# Y2 T& y2 I3 X# c        if (vexTable[v].data == d)  o# _6 i  C: Q/ ?4 J
                break;
    " {8 l9 g0 t8 q; p) {    if(v==vexNum)
    ( ?% v/ B$ |0 Q. f; A        throw Error("图中不存在要删除的顶点!");
    , u# O6 B1 ^* F6 n0 v; K6 g+ W$ ~" k9 g- ]: `
        for (int u = 0; u < vexNum; u++)//删除与d相连的边" o) A9 G8 [- N( l. d* M7 W
            if (u != v)
    8 ~6 \8 ^# H2 X. ]        {
    + O$ I% M2 F* U            DeleteArc(u, v);. Y% ]& H/ J8 I* V6 _/ I' u& L
            }
    : ~; C. j& p2 g, S( z    vexTable[v].firstarc=NULL;
    + d) D3 D- \2 T7 |" O1 h9 e
    3 `3 m6 r+ U, `" ?    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    5 _$ U; x6 W0 ~  B/ ]$ W    vexTable[v].data = vexTable[vexNum].data;
    + p9 ]# T: B6 r    vexTable[v].firstarc = vexTable[vexNum].firstarc;5 E. M  e7 p2 k9 M; D! g- |2 b2 M
        vexTable[vexNum].firstarc = NULL;" U* p. b; H2 a. j
        tag[v] = tag[vexNum];) I2 S. [, ]6 E% E8 q% [, M
        //原来与最后一个顶点相连的边改为与v相连
    0 a) b' p5 [; P& V  }$ ]. j    for (int u = 0; u < vexNum; u++)+ Q9 j1 p4 t! ]& i/ a9 y
        {  a  k/ x) D6 f. L) S8 p
            if (u != v)$ @9 |5 u  L1 _4 n
            {6 [  P4 |2 d6 e3 ~4 w& M. m
                p = vexTable.firstarc;( g) r- b; y1 [7 k- ?
                while (p)2 f" C) v4 p) J  F" ~0 d% w0 Q
                {
    5 B1 u% @- F. W! p' `                if (p->adjVex1==vexNum)5 Q& {# I% v( j6 h9 F2 u% Y* o! V- ~
                        p->adjVex1= v;* z" M' B8 ]6 O3 h5 `; W
                    else if(p->adjVex2==vexNum)
    0 r  R/ y) g, P) J9 h                    p->adjVex2=v;
    7 _" B, W, W( i. E# I) h& R                p = NextArc(u,p);, \+ r" C0 o# L
                }- I* ^" X; R& T4 v9 s
            }
    # i# [$ }; \- N7 [& A& }$ H7 R    }
    * ^! y! M: r" N7 M+ \" Q1 [! a, X/ Q}
    7 n% b8 }  Z5 H///深度优先遍历
    2 i8 s! Z$ K. I  x- d1 ]template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    4 Z8 r  S6 f9 ~, E5 g{
      {4 P: c% p4 n/ e    tag[v]=1;
    6 h" t' r; v( {+ F4 Q    cout<<setw(3)<<vexTable[v].data;
    4 q7 b+ `( T4 A' \: Y8 Y    MultiAdjListNetworkArc<WeightType> *p;4 O9 ~% k" o! `+ \# ?* Z
        p=vexTable[v].firstarc;' t. V; G, s0 a; e- C5 v
        while(p)8 N% c# B' c! ]' L0 b2 g) Q, F
        {
    - ]/ G$ I' {; ?- e        if(tag[p->adjVex1]==0)
    . o; |& P  B4 \- Z( ?            DFS1(p->adjVex1);9 a8 [7 G1 @  O" T
            else if(tag[p->adjVex2]==0)8 E& `3 r; C+ ^4 x6 F1 K& h- p7 C
                DFS1(p->adjVex2);2 {1 q4 W/ Y: I' G) e
            p=NextArc(v,p);1 w5 q: v0 G, Z( t
        }
    - t# D( e' O) a$ d}
    1 X+ `" D/ @9 A3 J# H) l( f3 Wtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()6 p* s3 Q9 E4 H# _/ R
    {7 P0 b/ T; N- h' j. `" r2 Y1 x
        for(int i=0; i<vexNum; i++)
    ) M9 Z. s* o2 n* l7 C6 t        tag=0;" x8 Z& }; a9 X
        for(int v=0; v<vexNum; v++)
    + ^: [/ ^% e2 i9 o$ j, V    {! s+ o! b9 [# C+ M7 s
            if(tag[v]==0)2 N# p* ?, U9 J' v/ r7 p- g
                DFS1(v);3 S/ x  \1 W7 q+ W8 J2 O9 X
        }
    9 E( u5 U, K( ~  n* O}
    - ]! \3 F, D- X+ \2 Ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()! f6 }& i7 h0 O3 p3 F3 l
    {7 u0 W/ [" u! |. M
        stack<int> s;
    $ ]( k. h  Z- V* J    int tmp;) w/ i4 N! R8 p* C2 j: O  ?# x
        MultiAdjListNetworkArc<WeightType> *p,*q;
    , K# E' p; d7 z    for(int i=0; i<vexNum; i++)* w, E) F( D$ F3 H, ~& S/ E
            tag=0;5 Y9 z: I2 z* X8 p: l! W, h
        for(int i=0; i<vexNum; i++)0 Y) x- Z+ f1 {
        {
    . q1 ?6 s$ k( m, t3 H+ G4 B% A* q        tmp=i;. i% b. Y& j4 Z3 A. L" o; B
            while(tag[tmp]==0||!s.empty())- E9 c0 V8 I, g  T1 t3 q
            {
    4 I0 ^1 u; v/ e; s4 a5 w4 x            p=vexTable[tmp].firstarc;& B. C: Y" c7 \
                while(tag[tmp]==0)* v" a7 V0 F: D, O
                {
    & b, D: A- L9 ~- ^! ]- h                s.push(tmp);$ P5 p6 O, O: H: |4 X" g3 j& G6 _
                    cout<<setw(3)<<vexTable[tmp].data;
    1 l8 n7 x& T8 \, v2 ~0 i                tag[tmp]=1;$ Z$ T9 ~4 S4 Z% g+ j4 X# s, o
                    p=vexTable[tmp].firstarc;
    * f' U0 F" H2 C3 ^) e% U                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
    ! z% s/ z3 I) A0 b3 Z: `1 s                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);* |% m: S# J' P0 M0 F& J- u* b
                    //cout<<" 1st     tmp="<<tmp<<endl;3 i8 Q1 M3 w2 M& N; M+ C1 z
                }
    5 h- c. G- }( D' C# G            if(!s.empty())
    6 J4 J; E6 z- M6 \            {+ Z) R4 s( s0 ~- g* N. _8 }
                    tmp=s.top();" R, u) D5 n6 V
                    s.pop();
    % ?) X* b- \8 V; d5 m1 N0 E                q=vexTable[tmp].firstarc;/ ]2 ~% k; D1 t8 @3 N% F* @
                    int t=tmp;
    , K: _: Y$ @4 I, N0 |. P1 l                while(q&&tag[tmp]!=0), i  c& m) w1 P0 D1 {$ c
                    {( v( N# L/ o6 W2 i% f
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);: h) I! J, ?0 h/ y6 @
                        //cout<<" 2nd     tmp="<<tmp<<endl;
    2 F7 Z  f6 b" G# b                    q=NextArc(t,q);4 v9 I# a6 v% U; `8 E' p3 P' D
                    }3 Y8 ^4 |1 L$ _* I0 u
                    if(tag[tmp]==0)
    . I4 L: ?, }( W! D6 Q. O2 N: l: H                    s.push(t);
    % {, ?6 y( q3 n" b; o                ///1、对应上面连通分支只有1个点的情况2 E! H4 A- K0 K/ f
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈+ A$ [! X# T/ K
                    ///tmp要么等于找到的第一个未访问节点,
    / x0 X: D! ]; V5 m% Y! e& d                ///要么等于与t相连最后一个点(已被访问过)
    ; M5 |5 P4 E$ C                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    ( X- ~/ B* |7 R* P* {+ G- L            }
    7 J6 z6 S. `$ {0 S        }& m& H& h! Z$ R% M7 T9 f! G
        }0 V+ X, d( \: V1 g  }) o
    }, K2 r0 L( l/ e2 f* y* P, A% B( Y$ z1 F
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1$ Y* I( H! [$ t# {% H  g
    template<class ElemType, class WeightType> int
    ' `9 B6 B0 A' F( e' t! _" }3 k' rMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)% f& B, g  [, s2 q
    {, n2 H5 n$ b1 n: ]. _7 E7 l) f- v
        if(head==pre)
    1 i" z' Q. X! `3 I0 Y" v        return -1;0 f6 |; z# m2 p; R" f" b
    * D: M. ]* z# `3 P$ p
        MultiAdjListNetworkArc<WeightType> *p;* _; q; `2 q/ h+ p
        p=vexTable[head].firstarc;0 I) n: }+ X0 U/ P# \/ W
        if(pre==-1&&p!=NULL)5 k8 J5 y5 e1 C/ s) S0 J, {
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
    9 U( p" Q7 E1 B0 }    //pre!=-1&&p!=NULL% I: M. N9 V1 e& C, S0 v9 C
        while(p!=NULL)8 b- Q& o  P1 F) F+ T9 U. |; e% U
        {' i1 R+ z/ h4 d0 I- t- v
            if(p->adjVex1==head && p->adjVex2!=pre)
    : [% b( S) |0 D1 k! \- @            p=p->nextarc1;# o9 `) F% D/ U7 i6 l! A8 P
            else if(p->adjVex2==head && p->adjVex1!=pre)
    8 W. m1 E* F& x0 V3 W            p=p->nextarc2;: ]8 c' l8 Z' k/ P8 X9 X
            else if(p->adjVex1==head && p->adjVex2==pre)
    , ]/ N4 O$ `% t        {$ [3 j( {& }( t% u
                p=p->nextarc1;
    5 n( h& D/ X9 ~! q+ d$ m- z            break;
    : V" ~7 \% u/ O# K/ \  n        }
    / i& p% z0 N# h        else if(p->adjVex2==head && p->adjVex1==pre)
    , @8 H. W$ T' v1 Q# ~- W; e6 w9 N        {
    6 f# u. e& o" x1 [. r  n- U9 P            p=p->nextarc2;8 z* u+ y& _# p% X+ O, ]* U
                break;$ Y7 s, {# s0 h8 ~% c
            }4 L2 Q9 l8 h" _. y2 T# o# W
        }
    & u# i4 b1 }1 S: Y- g    if(p!=NULL)
    1 c) S7 ?. N0 O    {' G& |# [! i/ M
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
    4 Z/ ~$ l1 o$ p7 o) F    }
    - X: C% f& H5 I* l+ e* F    else, {4 v, c" R; c* B$ S/ n( b
            return -1;
    . {+ L* [4 y( F! Z1 m% g8 e}
    4 C! }( I) K% r- O! ?6 R0 j; q) E% o
    ! I8 K' i5 `* Z% S
      \5 b2 |% }9 U/ b6 Jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(): i9 K5 I4 ^' u& l# a
    {: f. a! B' D0 e' Y: t% G7 n
        stack<int> s;
    / T& {* C# K& Z5 n6 F    int p,cur,pre;1 ^9 D+ d" E) {; [; S
        //MultiAdjListNetworkArc<WeightType> *p,*q;
    ) d( g: P7 [+ l; H* e    for(int i=0; i<vexNum; i++) tag=0;//初始化2 E# M- M/ i5 s$ ?( \5 I6 W  }
    ' D8 m7 _$ R2 @
        for(int i=0; i<vexNum; i++)
    3 _8 ]1 O7 T5 h/ a1 z$ I    {
    & J  C9 R/ G4 j. N( X0 b/ B$ `        cur=i;pre=-1;/ C% V  A. |, Q1 ?. D5 m
            while(tag[cur]==0||!s.empty())' @  h% s) R4 S* g5 g
            {/ X' M- N4 }+ d! ]$ o
                while(tag[cur]==0)1 \) x$ J8 B" q* g. V- f
                {2 `9 g; S. t6 ?5 O* H$ D6 l
                    cout<<vexTable[cur].data<<"  ";
    0 t# @+ J& L4 G) K8 I                s.push(cur);, p! I7 C4 {4 T' H
                    tag[cur]=1;
    4 ^  B. L8 z# Y. B! {  B3 ^+ [8 |               //初次访问,标记入栈
    ( `$ f6 {' K: ]$ V
    . v2 W, X* M: M% C               p=GetAdjVex(cur,pre);//p是cur的连通顶点, l; f0 ~* w5 J) o* t0 d
                   if(p==-1)9 V$ ^4 Z( n9 v
                   {+ k5 A2 b) p: u. ]/ _# z& y  l5 r
                       pre=cur;s.pop();7 T5 R1 R" M0 o# z9 l5 A4 ^4 |
                       break;
    * E7 l% z5 c. @               }' z( J" |0 y6 Q; ?. p' d) L
                   else
    5 s' m8 P* ~0 @9 `, S) s" V               {* [0 j, S3 g: D
                       pre=cur;
    / h0 i0 b! @0 |/ C                   cur=p;+ `* ~: I8 \8 E  l
                   }, L* [- i8 z& K8 W
    / l) X$ ^& M, C8 T3 e
                }
    6 E" z/ _& D* M2 ?            while(!s.empty())
    9 z: k8 ^3 ?( n4 p! v            {
    * D0 ?; X5 w1 R- r, P                cur=s.top();* ?8 t4 ~. z! f+ M
                    p=GetAdjVex(cur,pre);
    ( W# c+ |( R1 l- h# b                if(tag[p]==0)
    8 m+ k1 V3 m2 e- b" l$ `4 Y; u                {- |2 E; z9 s) ~. a2 ~
                        pre=cur;
    ) [* |  m& E: F- L# D                    cur=p;  D; g- _. d0 b. e8 V
                        break;# _! ^5 r; S5 t1 I+ ~- ]' ?
                    }; _! j! s& _; ^) c' A" Z3 N- n
                    else
    , u  N. c2 n6 V; P% A8 R                {6 [0 Q2 i4 `6 _
                        pre=s.top();
    ) Z* S6 |+ x1 F+ A6 f4 W+ }+ s! r: Y                    s.pop();2 j! H  A1 @, r* l- N
                    }
    - l: l4 m3 D$ I  {6 z8 X  q; r( ?; a5 j/ V1 V. }# L" E: f
                }
    3 ^' ?" z/ _5 q+ Z; A1 y4 x* l! {, D7 W% ^5 ]
            }" P1 n7 o! D. Z9 R- l3 \* c5 n
        }
    2 l# D+ o8 K' M" g6 v' V$ H; v}
    # g5 p* y# O6 h5 ?+ Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
    & g" z# f5 S+ Y$ r7 y5 y{* T( i0 r/ l- ?/ @- |6 D# V* A
        for(int i=0; i<vexNum; i++), q2 x1 B, C  _5 U4 w$ y. h* X
            tag=0;) I. e7 l, p* [
        queue<int> q;
    : c) v% w+ q( N4 ~    int tmp,t;
    - e" B+ d/ m$ c" U' ~' E    MultiAdjListNetworkArc<WeightType> *p;
    " H3 K4 C- @( G4 p    for(int i=0; i<vexNum; i++)
    ! U- [, w1 h. D" y    {/ o& r3 {) T2 U% X$ \& j% z
            if(tag==0)
    ; I/ U5 J6 A$ c5 S$ W, [        {0 [5 i0 y! C& c; w, J
                tag=1;
    ' |8 b7 b% Z" g* L5 \* J            q.push(i);5 Q1 F0 e, M; T& o
                cout<<setw(3)<<vexTable.data;  h0 U5 s* c4 V: k
            }
    & x! T# K( i3 R9 ?3 r) P8 @        while(!q.empty())! j4 D; g& h" ]" I% A  C2 X
            {( T! ^1 c. f+ d; O3 n4 ]8 z
                tmp=q.front();* G5 ~; M( }5 ~
                q.pop();* S5 ^6 _$ I& z  y9 l' q
                p=vexTable[tmp].firstarc;! c- y* R& @) w3 [! n5 n" y
                while(p!=NULL)
    1 v2 `% B4 c* }5 M            {
    6 h; l; H7 U: L5 v                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    ; }1 B! I- q, L) }- S3 d                if(tag[t]==0); d! f* ^% T. p7 p+ ?
                    {9 V3 S3 ~$ Q* A, o3 {2 k
                        cout<<setw(3)<<vexTable[t].data;$ y' R+ S; L+ h, N: i" S) t
                        tag[t]=1;0 x3 L1 Y$ m3 F# C7 f
                        q.push(t);: g, W5 Z0 U+ A; }) Y5 ?* Y
                    }% c$ `# D" N4 w9 E  [+ ]+ d
                    p=NextArc(tmp,p);1 x/ n/ N8 M: c
                }
    6 e) x- k4 f6 D& r" o$ r        }
    8 l. m1 |& E. i9 q9 k    }
    , K* o3 x$ @- m, f$ |* w0 Q}
    $ ~' m! S) Z! ?" g- ?! ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
    8 G6 ]4 J8 l: a& d{8 Y2 |$ B, C& y% E/ e+ k
        MultiAdjListNetworkArc<WeightType> *p;+ I& v' ^* w" C8 H( x' _1 i
        cout << "无向图有" << vexNum << "个点,分别为:";7 |, I8 c4 ?  P& ]3 P+ M
        for (int i = 0; i < vexNum; i++)9 d- G1 f! ^" V* ^. y! F* e. h
            cout << vexTable.data << " ";/ `4 d  G+ ~$ y% U
        cout << endl;
    ( P% I% T& X; W; t9 u' h3 J    cout << "无向图有" << arcNum << "条边"<<endl;1 {7 `# u- ^0 [1 c0 h2 l
        for (int i = 0; i < vexNum; i++)
    . Y6 {' q( L$ j    {
    3 a! N% S7 I5 v7 i4 C        cout<<"和" << vexTable.data << "有关的边:";1 T& p: [7 ]% {, _" D0 R+ q5 O' t
            p = vexTable.firstarc;
    ! R" u& ^& ^; ~: g+ r7 J        while (p != NULL)
    ( q1 z" p' M8 r2 f$ c        {+ w8 A5 T+ X3 ]6 i7 w
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
    , s2 |) d9 R! [. u+ W            p=NextArc(i,p);
    1 `9 w! M: w$ g8 L5 y' k        }1 d" `! \7 G; c
            cout << endl;
    $ B; b! e- N# p* z: ^8 B    }
    ; B) H. ~& @1 K* p/ D+ T5 m' s" V}
    " L1 K% {% u* B! D' Y
    & Z/ `  w& x2 g
    9 m1 ?$ Z1 U# T) i邻接多重表与邻接表的对比
    2 p$ f0 a. E/ W" J+ V9 J  A" n: e7 L, E2 f  L; l4 I4 Z
    邻接表链接- f/ t4 `5 X, W: i" X+ `) E
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。5 Q, o9 Q" V- A/ s5 d9 E% B
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    1 B# V9 V# W/ y" |( v2 A6 W为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    + v! w! e/ C2 e: Z————————————————- q1 b7 Y' K( a- G
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。1 D& ]# w& E' x+ O3 b# y* {& t
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    1 L( u. Z6 I! B& V$ z% V( h4 Q
    * M1 B) j& x6 k! X+ y! A" F0 m) e+ N' B* ?

    * [4 h4 j8 B5 m4 e2 w' s; N: j; V
    ————————————————
    . J6 g+ m& G% o; K版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。; `8 l. H+ ]) u+ O. ^# M* {+ R; n+ W
    原文链接:https://blog.csdn.net/qq_43413403/article/details/1057669586 G. ?) }4 m! S. W" J
    ; G$ b( h, W5 t; J  |7 r8 a
    7 _/ F# y* P6 p9 x7 S" S. ^' |
    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-7-11 09:51 , Processed in 0.882528 second(s), 53 queries .

    回顶部