QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1382|回复: 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% m( e# Z& m+ T3 |3 c图的存储结构——邻接多重表(多重邻接表)的实现1 h7 {" D6 z$ ]/ e/ r- w
    7.2 图的存储结构
    ) A' I: n2 p; [+ g7 v$ ?( D/ c6 ?# }
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    : r2 z5 p/ \$ [* b' _  I% T邻接多重表的类定义' v) c% @& H9 D' X
    邻接多重表的顶点结点类模板
    1 ^9 x) t- a4 q7 t, E1 L+ N% a邻接多重表的边结点类模板( M! w1 |; L$ A# c% j4 R+ }, p
    邻接多重表的类模板  \) M' @- }" x$ i+ ?
    邻接多重表与邻接表的对比( V  g" O* r9 I4 O( x" W' t
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    , L1 K; j/ S$ c9 m/ r# d
    / a6 P4 X( W% E& l- k: q6 y! A在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。9 U. d0 g2 [& @  l( Z
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    - D! p% X$ h: _) T
    " J9 B; |6 `3 h4 o邻接多重表的类定义
    / Y+ M2 }) I: P 1.png , q/ A3 [& M3 J5 \7 O
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:" _  }: m5 j0 f% h
    data域存储有关顶点的信息;: g6 z$ l9 n; S) w9 w
    firstarc域是链接指针,指向第一条依附于该顶点的边。
    - y: B* r7 k2 V9 J% m$ w所有的顶点结点组成一个顺序表。

    / |+ s2 Q9 Z+ S+ |# u& O
    8 \: J  k6 D6 J) a+ G
    template <class ElemType ,class WeightType>1 k. G/ {; \; }- P: Z
    class MultiAdjListNetworkVex( N/ y- O( D% W/ g3 E" g
    {
    5 t) p1 o4 k. u! W) q3 lpublic:
    4 E/ _' y, r% J0 L( U" x1 \& w        ElemType data;7 i6 @4 i- |( b" G
            MultiAdjListNetworkArc<WeightType> *firstarc;4 Q  l* B& K3 Z/ N
    : c  [1 u% D: n7 z" Q$ f2 X' q
            MultiAdjListNetworkVex()9 X& {0 S' X6 u* U1 V7 e
            {) |3 c9 k- |% G! b6 c7 p6 @" {
                    firstarc = NULL;
    7 X. S" b& h; H# J) S7 ~% |        }
      S8 \* O) R$ G$ o% P$ i5 C        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)& i; k, [; v5 e( G2 Z( C
            {  S& t6 G- Q+ R
                    data = val;# Q; h  r7 }) l0 m5 `
                    firstarc = adj;: v0 c" D! g0 v+ ]: S6 o% u
            }
    . c; ^( ?9 r; s, V6 ^5 f};
    4 O/ B. @& K) m8 m1 d4 e% b+ p  t/ r
    邻接多重表的边结点类模板
    ; F6 C! I1 P! S0 K6 x
    7 I% M, J/ u! x* M5 F5 _在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:* H2 w' ]- F% x3 G# d- z: M5 h
    tag是标记域,标记该边是否被处理或被搜索过;
    ! z9 K2 F! I) Vweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    $ p, a3 L6 F/ L* _* ^nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;6 D& }( `: l1 E, \
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。$ f& x) H# f1 }4 l+ b
    5 Y; {# a5 ]$ u- q
    2.png ; P- w; B' G- W  ~% a4 S) G
    template <class WeightType>8 |! r. o: t# h- z
    class MultiAdjListNetworkArc
      [5 l4 R  v, f+ L( ]8 x{
    7 f& H! p" k0 X% c8 @public:
    " z" Y! E9 H% i, d5 Q" `  m    int mark;                                       //标记该边是否被搜索或处理过
    4 `9 A! n9 `. r        WeightType weight;                              //边的权重
    0 o+ {* O7 ~4 C+ D. ^        int adjVex1;                                    //边的一个顶点
      F0 Z8 N, w# d) o        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
    $ s! H+ l0 p2 ^6 W. s. l; F3 J        int adjVex2;8 j" h5 z0 k1 k
            MultiAdjListNetworkArc<WeightType>* nextarc2;- o- J* Q0 a, ]& Q
    7 w0 _; V# j: n7 ^# a. U
            MultiAdjListNetworkArc()' {+ s, `. @1 r/ T' h
            {8 o4 a, p1 m: w
                    adjVex1= -1;8 \: G& Q, v2 t* f- i
                    adjVex2= -1;; T; H% N2 _2 ~. |" O5 J
            }6 x2 C' S9 T( S
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    6 B$ o6 \  f; p- s        {
    . Z  J7 w1 M' Q, T                adjVex1 = v1;       adjVex2 = v2;+ M1 z* X8 Q; D# }: M: {: i( ~6 S
                    weight = w;6 @, k9 X4 W" m7 n
                    nextarc1 = next1;   nextarc2=next2;! o5 z. A0 C2 ?1 M
                    mark = 0;           //0表示未被搜索,1表示被搜索过7 R9 y7 T, J9 X  H, n% H
            }
      g5 {$ z4 y  x: `2 D# ^+ N5 U) K" r+ i
    邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>
    : ~( {, k5 O; S6 o) zclass MultiAdjListNetwork
    0 b' k( _/ L9 m{! r7 V: B3 ~! w& z- d  U
    protected:: C- w1 c7 ]& X: J% \
        int vexNum, vexMaxNum, arcNum;: d0 k: c: a8 d  j: j% Q" O, k
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    & X2 X/ [1 @' J    int* tag;1 w* y6 f3 j2 Q/ E: R& K/ P
        WeightType infinity;
    5 J# P% a. c7 J0 J, L: C8 U" {
    3 a# T9 C% ?: {0 V  I! J% R% Opublic:* b5 @3 M& \$ _
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    # i5 }( q: I# W1 D
    ! I- B  y  y6 a1 |    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);: ~& y* }& j; r, r$ J* i
    7 R- T/ a6 n/ q
        void Clear();
    8 X" w0 i. E1 J    bool IsEmpty()
    % l7 t# F; Y4 Q$ {/ X; t" o% }    {
    ; C& v& G& Y$ a* M" p6 v4 Y        return vexNum == 0;
    3 K+ _) X5 J( M8 Q2 {7 Q" h    }4 j: V. ?: R% V/ h
        int GetArcNum()const
    4 l) v2 g' c2 C    {
    , n4 Z) _! Y0 d$ `% r        return arcNum;
    8 ?6 ]4 Z6 U) K    }
    6 m, y1 U3 ^* ~- y    int GetvexNum()const
    + n- l" e$ @1 D    {& x' q8 }4 e2 ?# f
            return vexNum;! \# G8 v1 q+ o3 `7 C/ P
        }. z5 _( n) T. G8 H9 L6 \' N
    2 r% ~4 C1 X3 r# }$ n1 q

    6 y0 ], X) ]3 q1 T9 O9 x    int FirstAdjVex(int v)const;3 }0 i. h$ e3 Y; Z
        int NextAdjVex(int v1, int v2)const;
    0 O' @5 x- y, ], O    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;9 U+ W9 X) |/ d) Q' @& L
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    9 w3 v+ k8 y1 h% \" C- n7 J
    9 |6 v5 [3 H  L6 I$ f" ]" X    void InsertVex(const ElemType& d);) F8 V4 b  G# Q% \
        void InsertArc(int v1, int v2, WeightType w);" J/ ]0 V' B. ^5 \

    9 S1 k% t1 `' K3 h5 O) h4 h    void DeleteVex(const ElemType& d);" }) k* a% Z/ U2 X' {0 ^
        void DeleteArc(int v1, int v2);
    7 y" H( l' M( X+ P
    0 i! s% Z% g) K. O' h! p* c1 o- Z    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    , o6 k# w) N8 F* |# |    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);5 t8 S3 S" d% y# [* O1 O. `7 p

      m0 A' I+ C- t3 W+ N& F    ///深度优先遍历  N- Q7 e# S5 g3 D
        void DFS1(const int v);
    ' H. u4 G4 Q: l+ i7 S! D    void DFS1Traverse();" j2 w$ {& D2 Z1 X5 H8 M1 }: ]
        void DFS2();2 B4 c9 E) U7 Z, O: Z5 `! {/ L  T

    - B  k6 K$ F) z    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1  M- A9 }5 P% c# _
        void DFS3();$ J- y5 ]5 [& N$ A4 X0 y

    9 m$ I- Z) J4 G    void BFS();) Q. y, f( R$ G+ F" \
        void Show();0 V( A$ N) P$ \
    };
    4 k" Q: Z! l& X; `8 G1 M. [! k& ~+ T+ s: D1 K
    2.函数的实现3 h5 F3 Z* v2 r
    研讨题,能够运行,但是代码不一定是最优的。  C% N2 {' i0 ~! W7 o: o0 W

    ; k0 M/ I+ a2 }, B# e0 [- \#include <stack>9 v9 p/ \; w! \% J+ t/ L
    #include <queue>
    9 m/ n, d/ K# \, f8 {; N6 ~. H7 ?8 }# B# O$ y$ |
    template <class ElemType,class WeightType>
    9 \5 X; G1 P$ o0 H# L; L) IMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    / x0 f0 i1 v  C- n" O{
    9 y. K: h  |1 _4 H/ E# d    if(vertexMaxNum < 0)' o+ w) c) p( q4 y3 a& m
            throw Error("允许的顶点最大数目不能为负!");/ ?* M, d" v; L
        if (vertexMaxNum < vertexNum)
    8 y1 _) h) h1 [' F& q2 \1 Y        throw Error("顶点数目不能大于允许的顶点最大数目!");# B7 ^1 M2 @& @/ O
        vexNum = vertexNum;
    5 K: R& K8 P$ j' m1 L    vexMaxNum = vertexMaxNum;
    : n) B$ w0 d3 e1 d% t" C4 {3 s    arcNum = 0;/ ]* T' e) z, R: u
        infinity = infinit;
    & _7 O, |5 [- f! o1 n* Q    tag = new int[vexMaxNum];- T, L1 D3 g3 z4 t" h
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];3 U4 o' s9 ?" S$ J  M& X* f* m
        for (int v = 0; v < vexNum; v++)0 t7 O2 N4 ?. I8 h
        {# ~3 C9 O$ s/ N3 O
            tag[v] = 0;7 R- J# e2 x# r2 z
            vexTable[v].data = es[v];# e1 o: W( D; H6 `4 e) G- J
            vexTable[v].firstarc = NULL;) d; H# E8 ]2 c4 m9 D% J
        }
    0 Q- q5 j- X$ P- p6 F0 r! E}  k( v3 Z# @3 h8 J* D( y( _, `
    template <class ElemType,class WeightType>
    + o2 ]6 @9 K4 w& N/ N  M- c5 DMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    ; r- O8 y( p4 N/ X{
    . S& A$ k; q" S( ^) [: U    if (vertexMaxNum < 0)
    8 N* f' H1 l0 o7 [        throw Error("允许的顶点最大数目不能为负!");5 L9 \- u+ U9 W; t3 t0 |$ @1 e/ T
        vexNum = 0;  }; l% m  u: T+ N1 l5 T
        vexMaxNum = vertexMaxNum;0 G" I0 A% k% W0 f2 |; U
        arcNum = 0;' L" a/ b% m6 j0 |* y
        infinity = infinit;. ^& G  b' C1 E. c: J1 b% Y. n, M$ @
        tag = new int[vexMaxNum];
      Z/ ~" x- W4 [- w: Y    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];$ w1 T& a$ F2 {! _3 M8 W' H2 M) C
    }. H! }9 q- }- E  O1 z" k
    template<class ElemType, class WeightType>: {4 Q; P5 W( E  m& Y
    int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    9 f7 R* F/ j9 x5 j; ^3 _; n{# u3 n% d2 ?# d# C! u; Q
        if (v < 0 || v >= vexNum)
    ( C) h& U* U- E& A( p        throw Error("v不合法!");
    1 d- Q- _& s) x( q# b! l# J% k+ ?    if (vexTable[v].firstarc == NULL)
    9 a; d" i0 P" ?" G& S        return -1;0 U3 M% O( q+ `* d4 \' I, _6 E$ ]
        else2 z/ d' G: c! [( W, q* l+ v
            return vexTable[v].firstarc->adjVex1;
    3 A/ Z) K9 b- f/ Q7 o}* i5 Y) c4 p: h' f* |
    / j; I5 V, L2 c6 d) |0 @
    template<class ElemType, class WeightType>6 _! Y% F- E! v& V. H& K6 e0 e
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const9 \- e" A2 o* R) f- Y0 e
    {* s, E& i1 V0 }& T( S2 [
        MultiAdjListNetworkArc<WeightType>* p;
    & t& D) Q2 }1 s4 R% z5 t    if (v1 < 0 || v1 >= vexNum)
    / w+ w# h  O1 X, w* u2 o        throw Error("v1不合法!");+ m/ W+ z3 t( j7 V/ M" {" p: m; j: Q
        if (v2 < 0 || v2 >= vexNum)) k1 P% W4 |9 B# M4 i
            throw Error("v2不合法!");! X+ ^) ?: Z6 D' H" p+ }
        if (v1 == v2)4 d/ \( {- _- I& W: H
            throw Error("v1不能等于v2!");
    . S4 R6 B  B1 f8 [9 h0 T    p = vexTable[v1].firstarc;
    - B# W# `9 ~! I9 R* E0 `    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
    5 A$ F8 q% K) H        p = p->nextarc;/ ^+ y3 u2 L9 W: n
        if (p == NULL || p->nextarc == NULL)( ]7 C0 _/ u9 V; G, j6 T
            return -1;  //不存在下一个邻接点
    % N  M0 g8 m0 M. H$ ^: |    else if(p->adjVex1==v2)
    ; S* R1 P: R3 \$ X7 o        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);$ y  q9 l( v$ O& P/ ~0 W
        else
    : t( e% a# k3 o6 x& D) U+ W        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);2 D* v$ m2 S* Z0 W. \
    }: z! Z! E2 F: \; \$ C
    template<class ElemType, class WeightType>6 j) B, K( o3 `* u! f
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()4 _) \/ v% g$ `. [, [7 m
    {  y( c. H+ n( u/ S! p
        if (IsEmpty()) return;
    9 Y6 B0 G9 U! v, L0 _% Q5 T' h; V7 p    int n = vexNum;
    + w: q& R3 r% B( ^7 R: j) V    for (int u = 0; u < n ; u++)
    / Q# g7 O, h+ T  @6 Q3 y        DeleteVex(vexTable[0].data);: p8 g9 a6 H* ]9 l2 m
        return;, |' m4 ^( ]7 a* P* C. ^8 x
    }
    ) r: _1 ?8 Q; ]( u! r! d( jtemplate<class ElemType, class WeightType>( F5 W' X) ?7 A9 m0 \  j& }+ K  t
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
    $ R, v$ h4 T, @3 ~! m{6 P: Z" @- Q4 Y5 ^* F4 ?% b
        Clear();5 q, P9 A, p4 ^
    }) x# {0 T- j' n' h; n
    template<class ElemType, class WeightType>
    2 g$ D4 ~* ]$ i% FMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    % z1 n4 T6 ~% B- t$ f/ @/ z{. e* j  L/ ^2 s; |  q1 n7 v: W
        vexMaxNum = copy.vexMaxNum;$ \. K. v3 P- B) ?
        vexNum = copy.vexNum;
    3 S6 u3 E0 ?4 i/ p1 ]    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    ' e4 S4 B) D9 D; w, }5 [    arcNum = 0;
    # C% d( s3 o5 s" N1 Y    infinity = copy.infinity;
    7 T! u! M. t$ w9 Y; R    tag = new int[vexMaxNum];
    * R. H" {2 Q% ~/ d9 u/ s- B5 Z: T8 Q$ U, j3 ?; f( O  b% U
        for (int v = 0; v < vexNum; v++)
    / `* h2 ^0 k9 j5 D5 D  a. H    {7 S4 c$ t, B- f  D9 X  f- w
            tag[v] = 0;
    + y& @# b. n9 R* B# ~9 E9 v        vexTable[v].data = copy.vexTable[v].data;
    # c9 Z& `- v0 z7 K% r: T        vexTable[v].firstarc = NULL;. |% U- m1 z6 W/ I  Z. {
        }8 J3 O  r- ?, D7 b5 f; h
        MultiAdjListNetworkArc<WeightType>* p;
    3 a& s  \7 y8 `. p) E) q/ j0 U" V4 l1 x
        for (int u = 0; u < vexNum; u++)2 I' Z& a5 m" v0 p
        {
    : h6 A, [: B, r( P: E" l        p = copy.vexTable.firstarc;
    $ w; Y1 u: x: r9 \        while (p != NULL)
    0 i/ W; p9 I$ K7 W        {: J& _% s6 Z/ i8 h; j
                InsertArc(p->adjVex1, p->adjVex2, p->weight);8 C  W/ ~8 p/ Z6 R8 r# q* ]9 B7 K
                p=NextArc(u,p);
    7 R$ Q2 a* G7 E  q        }
    $ o* W. {1 P2 t8 c! ^3 E    }
    + {, S5 h. B1 i* D6 Z}
    $ i( q& M( [* l6 etemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
    / Y/ L4 ~, C$ Q7 U& T% G3 p& q) a/ eMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    + y4 I  a6 W5 B, f* p6 l0 D{& T7 c6 Y% y  f# F2 G& g
        if (this == &copy) return *this;
    2 h' H- }9 t. E- b/ W    Clear();
    * h5 ~- p4 T. S: r" C) q# f    vexMaxNum = copy.vexMaxNum;
    " @7 j% G6 _8 J( J2 `    vexNum = copy.vexNum;% C) X% R* r  I# p5 {
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];3 C+ C9 L, b/ v% W2 @0 ?: ?
        arcNum = 0;
    . V8 m- {$ d$ Q6 c* k) P; w5 T    infinity = copy.infinity;* ^, f, N: G8 z" @8 D
        tag = new int[vexMaxNum];) H1 s0 E3 C% H$ P4 Z* c
    1 a7 W0 Q2 u% `& M9 M7 u% F/ G
        for (int v = 0; v < vexNum; v++)! e9 y4 Z  l, S
        {/ N7 e5 h- u, _5 M% G
            tag[v] = 0;9 T4 K  p4 D4 [. L. l4 P( s, \4 v
            vexTable[v].data = copy.vexTable[v].data;4 t' \2 l$ b5 Z
            vexTable[v].firstarc = NULL;
    1 w  J/ A5 N# T7 v2 a! a0 g    }
    7 G4 X) C* m0 X1 p4 y    MultiAdjListNetworkArc<WeightType>* p;
    ) M- y9 p  L' ~% a% y+ Z1 ]8 U+ |+ R1 C6 L2 ~$ U1 q$ _
        for (int u = 0; u < vexNum; u++)$ P/ m; ^, t6 u/ l) L% T4 y
        {/ W# F7 ~0 U# ]# e7 x
            p = copy.vexTable.firstarc;
    ! X) w& n$ b& i) V6 F2 S( |4 Z  U        while (p != NULL)  C" Z" ^' v5 \
            {7 h7 c$ b/ i/ R7 w
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    ' P2 J1 S$ M1 {$ W+ t            p=NextArc(u,p);
    " ?. ]& @' R! ~) d+ a  |- T        }
    6 z0 D4 `7 i, W! M/ S, _    }$ m+ u' i6 ~/ T% i* c3 T
        return *this;, E5 s% ]! _  n4 i" V) @
    }$ f4 `5 Y  ?/ s) ]
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*0 L1 O4 P6 I* k8 o% x6 n6 H
    MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const. Y5 J1 `- ^1 ?& L
    {" j! p4 [- W1 L
        if(p==NULL) return NULL;+ e" J3 C/ O. c8 o$ B2 B
        if(p->adjVex1==v1)
    - E- h# r, x  i* ]/ _  a4 B; Q        return p->nextarc1;
    ( u2 q5 Y) a1 H8 \* \    else
    1 i# `! |& U" K9 f+ p        return p->nextarc2;
    7 D; z" P' @+ ?) C( T}
    ) w4 b- ?6 e/ T+ }# Vtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*; {! l* d& Z! C, E  P5 @& E
    MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const6 e' i* V* N) a6 J$ S! I
    {
    5 @0 t, y9 H$ D" b7 c6 G" F    if(p==NULL)return NULL;
    ' P' @5 x! z( J9 V    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    $ ^3 n1 E5 p, x- y    if(q==p)  z4 i! ]0 Q9 ]2 {' p- h0 k9 v
            return NULL;
    - N& X5 {* t* ]* P# B& J& `8 {    while(q)
    - e' R+ E5 ^% }' @) l    {
    ! z( t2 y; i0 e5 ?5 y2 m+ T0 [" g5 ]        if(q->nextarc1==p ||q->nextarc2==p)
    1 d0 k; d# A( o9 \# d: \: B            break;
    . Y! k9 m6 y- y# z) D( q$ `) ?" }        q=NextArc(v1,q);6 Y9 e( ~! O& d6 S  f
        }. ?* x& H% v8 A8 C+ l7 M
        return q;
    + T' Y. x5 l' v3 k$ h; `( f2 w}
    6 V+ u8 _$ f9 L3 Z7 U% E! etemplate<class ElemType, class WeightType>6 M9 q9 N% L1 J
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)7 k% B1 k( H6 c9 j5 y' _
    {% W/ n9 w  N3 L) n0 _  E
        if (vexNum == vexMaxNum)
    # S' B0 X- p9 B, P3 f2 O1 @, K        throw Error("图的顶点数不能超过允许的最大数!");! c+ L- s) D: E7 W2 z; i
        vexTable[vexNum].data = d;
    . e  {: t8 S4 \    vexTable[vexNum].firstarc = NULL;
    + Z$ r- t+ C* I3 W9 I    tag[vexNum] = 0;
    + H5 w( @6 u6 B1 K" D4 J1 J    vexNum++;4 R$ M1 y# m& a  c8 O
    }( l+ y& ]3 Y$ }; j8 y3 \
    template<class ElemType, class WeightType>
      e$ D% o# s* d% yvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w); |4 d# i6 }/ X$ _
    {
    ' o/ c% H, j/ @, a9 W" d& Z; N! d    MultiAdjListNetworkArc<WeightType>* p,*q;
    2 z0 }: y+ S! R; @: F0 J    if (v1 < 0 || v1 >= vexNum)) h. k! t8 u4 o0 o; ~" X
            throw Error("v1不合法!");
    0 r  P; D% d) a7 c) y    if (v2 < 0 || v2 >= vexNum)4 F) A' Z+ `3 F. A  t1 r
            throw Error("v2不合法!");
    ; E. w3 @7 U1 G; [- V5 q/ F    if (v1 == v2)3 z9 U4 m- e8 A+ y
            throw Error("v1不能等于v2!");/ G; l3 q# n# h8 u) H$ o/ Z7 F
        if (w == infinity)" \. I  ^% @1 F+ R/ H
            throw Error("w不能为无穷大!");0 d, H* u4 C8 m4 C1 v$ i' w

    - ?8 \! f5 {0 z+ _5 t- [4 m  ^
    3 a' s/ G( E2 c, R0 o9 S    p = vexTable[v1].firstarc;
    - S5 Y8 w+ O% O- L    while(p)
    " |  Z# V( ^" i4 L% x    {
    0 W" R! y1 B/ S9 d9 O# @. w        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
    2 s" r$ k# F, ~) h% Z        {) n8 @& \. W' K8 b# w1 r' X# p
                if(p->weight!=w)+ |, U5 L4 \: k% e; V
                    p->weight=w;
    " P# w7 j& @% k2 S6 Q/ q            return;
      X4 G9 N$ h# P2 U' l& @        }
    - i2 j* F2 O% R4 ^3 j
    8 R" i+ y! V/ @        p=NextArc(v1,p);
    # s$ V9 y2 w+ E2 e6 q1 N6 H& ^& T    }* |( i# o  |  H& R
        p = vexTable[v1].firstarc;- Y  \" }( ?" S; z; _0 g
        q = vexTable[v2].firstarc;
      i% Q0 W! ^: U8 S    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法: I4 R4 S5 a; X: T& D% ]
        vexTable[v2].firstarc =vexTable[v1].firstarc;. i! l) j+ `: P. v  X
        arcNum++;
    ; Q0 Y7 G' q5 |4 K& V; O}& r! ?3 U8 N( A7 Z* J0 q" n% ?8 s

      N5 |! S5 @3 s/ A4 x3 ktemplate<class ElemType, class WeightType>
    ) J( g* Y3 N* C7 s  Yvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)# J; ?9 @( Y& n; d+ g/ h5 n
    {
    " H! J. l/ U) z, }0 d
    , K& \7 T2 T6 ~* k! _0 z    MultiAdjListNetworkArc<WeightType>* p, * q,*r;6 T: |( p; E; i( N( s
        if (v1 < 0 || v1 >= vexNum)
    - n$ V$ m: z! u% w; ^" w& x        throw Error("v1不合法!");* Q* x- ]0 D3 y8 E
        if (v2 < 0 || v2 >= vexNum)7 _! y; x1 k$ e+ g) ?; ~$ F" c' ?
            throw Error("v2不合法!");6 [1 v( d) L' o! m; w* v  s/ q' z
        if (v1 == v2)! F+ E+ q7 L% t4 }  ]
            throw Error("v1不能等于v2!");
    , ^3 a4 ~. z6 J' _7 q7 w8 {0 i5 h; i* \8 O: r8 E: i4 \
        p = vexTable[v1].firstarc;% R2 M/ t" I9 H! _2 Y; H, a
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)6 Y9 A; K! o8 _" g. J& T* |  W
        {' Q4 B, Y& H" s7 q; ]3 G
            q = p;
    - s( b! k* P0 h3 L! d; `; u6 w: o        p = NextArc(v1,p);
    ' i2 T$ u1 A$ `6 `: j" h- q    }//找到要删除的边结点p及其前一结点q$ W; ]4 t, \+ p
    3 W5 n' x% V, }- J% t( D: M
        if (p != NULL)//找到v1-v2的边
      U' k0 m. C' {    {
    , A6 Y6 U7 @' l$ Q  o/ a        r=LastArc(v2,p);
    4 I$ I9 G/ Y9 {% n9 i6 ~3 ^% G        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    8 v& n1 x$ h+ X- u* r            if(p->adjVex2==v2)
    , |6 m. K' y& u8 ]4 ?, C                vexTable[v1].firstarc = p->nextarc1;, ~2 ~6 H! G7 L9 |
                else vexTable[v1].firstarc=p->nextarc2;' C0 O5 \. u& z
            else//不是第一条边5 A' q% u6 l" e% b! t& n' H* ?
            {
    $ [0 F2 B( X* B2 k            if(q->adjVex1==v1)" ^5 V0 i. K7 A
                    q->nextarc1 = NextArc(v1,p);* f( B8 c2 `2 z& t* w( I
                else1 ]  X! s0 U9 T
                    q->nextarc2=NextArc(v1,p);! |: \% \" v2 P
    . h3 V. Y( _( u$ b; n! m) K
            }0 ]9 G* y  s1 L8 p' l
            if(r==NULL)
    4 _3 E% l7 V* S. \4 ~            if(p->adjVex2==v2)# z; L$ W: T" V' T9 K- s9 m
                    vexTable[v2].firstarc = p->nextarc2;1 s& c( N& _" V. h4 `, i2 P
                else vexTable[v2].firstarc=p->nextarc1;
    6 E7 X2 G* j9 ?8 r        else
    1 L5 _/ T- P) i; ^3 t        {6 Q6 u' q' z! B! b: W
                if(r->adjVex2==v2)( t/ ~4 C7 Z& W* f" L- X; u
                    r->nextarc2 = NextArc(v2,p);
    8 ~" v+ y% H3 d9 M5 }, N" |            else
    8 [  {$ P& F# [: H" }" r                r->nextarc1=NextArc(v2,p);  ^2 r& x; C: i, w
            }0 E1 `+ G. G6 |/ m  f
            delete p;* j) R. I" ~4 b; I; e- l
            arcNum--;0 J' j8 W$ M( k) \
        }
    ) _% D0 v1 X/ }7 F. u1 Z: K7 b6 s/ h8 ]0 C1 w  `
    }( o' Z% C6 O, P5 j6 s. y
    template<class ElemType, class WeightType> void
    # N5 H' d6 [' J9 M3 r2 ^& {* `* \7 yMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)% \  s% Y% D5 s
    {2 J3 r  p6 e8 U8 J4 p$ j
        int v;
    9 X, r3 A1 @- f1 b* [1 S! [& x    MultiAdjListNetworkArc<WeightType>* p;0 l+ \) \& K1 R  t, V* P7 c
        for (v = 0; v < vexNum; v++)//找到d对应顶点
    1 s$ R  |: g, i/ Q        if (vexTable[v].data == d)9 x9 K6 R# j9 D* K
                break;
    ) ~! `, r1 X8 _7 z9 J) s- b; q    if(v==vexNum)
    - E2 j9 G: F5 H) ?- z4 A        throw Error("图中不存在要删除的顶点!");
    2 m6 B1 m. C; ^0 g2 z* q! {& R
    , q) d6 a' C- ?" ^8 i2 B# u6 t    for (int u = 0; u < vexNum; u++)//删除与d相连的边
    7 q9 S+ t% S6 v" j" {9 y        if (u != v)" r# A$ L4 u7 H, B3 r) O; ~5 C  ?' e
            {4 D3 |* }: P  u# F$ o  }! h
                DeleteArc(u, v);' s/ t- X9 \( M' W' f' v
            }
    ( a7 {: W, V4 X; m2 m    vexTable[v].firstarc=NULL;7 i, l$ v; l5 \
    & t& k  ?+ S+ O5 G/ x/ V- N: y+ h
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    ; F  G% X* P- h) @5 Z! ?5 l    vexTable[v].data = vexTable[vexNum].data;
    8 u1 h8 D& e. [5 ]* l! z    vexTable[v].firstarc = vexTable[vexNum].firstarc;6 F5 u" n9 c4 ]2 f+ G( R
        vexTable[vexNum].firstarc = NULL;1 u  Y7 g+ M4 Z! p& b
        tag[v] = tag[vexNum];
    # F$ k( r' s! T. p6 s    //原来与最后一个顶点相连的边改为与v相连
    ; R5 U  F9 S! N+ p    for (int u = 0; u < vexNum; u++), {$ \0 f$ _6 y: m
        {! q, U% l( i1 h# y+ u+ z
            if (u != v)3 a2 L$ R3 U; h7 V0 }( d3 w
            {+ n0 d6 F& S4 W
                p = vexTable.firstarc;
    6 U, c% F# V  f% @9 h8 ?) X" E% o- {            while (p)
    6 D9 ]  q6 L4 [            {( d9 S; i  o* [0 F! ?+ @
                    if (p->adjVex1==vexNum)
    9 t9 \6 ]5 g" ~4 A+ P                    p->adjVex1= v;
    ' c6 i3 n0 W4 T4 l; u( D, G! r7 t                else if(p->adjVex2==vexNum), G% o. Z7 _2 v, ~) u
                        p->adjVex2=v;% ^4 y% _# L/ ?2 v# K
                    p = NextArc(u,p);$ ]/ k; p! c  w
                }; f/ C5 c& J+ J, R
            }1 @9 A  T! F* x. P
        }
    / Y1 Z  Y9 d( a* t}" F$ Y0 m5 [2 [/ v( V0 m& Q
    ///深度优先遍历* x' m  q9 k$ G8 \; x# c% m
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    . i, C- C- {2 A' c8 c" h{# w  Q( _( L: y( ~
        tag[v]=1;+ J* O4 e. y, `! X$ V, {' d
        cout<<setw(3)<<vexTable[v].data;1 s6 z* W6 E/ Q3 C# R1 E
        MultiAdjListNetworkArc<WeightType> *p;  o+ K( z3 S( S  _6 k' N
        p=vexTable[v].firstarc;
    ' v. y2 @, i% j6 Z* A+ P    while(p)
    . @4 T/ a% ^. K) B    {
    7 W' R# X0 a0 `3 w* ]7 z: V$ ]        if(tag[p->adjVex1]==0)* b( n- S0 F# g$ q1 p
                DFS1(p->adjVex1);
    # p  o0 Z. B* _; G- ?4 Z# S; O        else if(tag[p->adjVex2]==0)5 _) e% e, o# |/ S1 w
                DFS1(p->adjVex2);+ E* r. I6 Q, j/ x  |# {
            p=NextArc(v,p);
    $ a, l: d5 E* z, j    }
    ) s" K7 v, R( p2 a' N}0 {5 Y8 r6 @# E% J
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()- K; d7 t% e4 S/ \& X9 j
    {
    - i$ X6 r6 Z8 D0 w6 U# r    for(int i=0; i<vexNum; i++)
    ( r" I% i7 V" }! x) Q, F8 S        tag=0;8 ^/ k8 ^4 f  b5 h
        for(int v=0; v<vexNum; v++)
    ( B8 q2 o/ C' ]- R; d% l    {5 a8 P! l2 {: L0 P
            if(tag[v]==0)
    6 M4 S/ a1 V% k            DFS1(v);/ ?* D3 m  R  U
        }
    - }4 K# J# B5 W8 o5 l' I2 e}4 i7 ^+ `5 B/ P7 V) @3 E  q8 W' Q
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 ~2 R$ p2 [7 T6 }/ m
    {* p( Y1 t$ X1 I6 k( T5 Y7 p
        stack<int> s;0 U! O  {& k- `* z" A, ]- x
        int tmp;
    , v% f5 C/ Q. [" t; Q( G0 o    MultiAdjListNetworkArc<WeightType> *p,*q;+ Z4 V0 M) y" v; E9 d$ b$ H. D
        for(int i=0; i<vexNum; i++)
    1 O# w2 }8 e$ _5 ^7 }) o        tag=0;4 o' J: H: E" p2 H$ O
        for(int i=0; i<vexNum; i++)/ G6 n/ P0 B- O0 _
        {
    ) z2 f$ [1 ^# g' z        tmp=i;
    * p$ Z% t5 Q( Q9 P6 i        while(tag[tmp]==0||!s.empty())1 [( t& B2 x5 u3 H8 O7 |" g% I
            {
    $ X5 B* ^" q8 ^) A( P3 ^            p=vexTable[tmp].firstarc;9 v+ r$ h" z4 R/ ]2 ?7 M
                while(tag[tmp]==0)
    $ j  K4 K/ b: s6 y3 Y& p$ ?            {
    % n* b: b, i7 R5 y3 y9 T                s.push(tmp);
    . F; w* k2 c8 B  M8 W                cout<<setw(3)<<vexTable[tmp].data;
    % {' h  z$ ~7 T% f% F. x9 L                tag[tmp]=1;# ^/ U+ i1 |  E& C2 Y/ k
                    p=vexTable[tmp].firstarc;+ [9 Q1 k9 Q- ?" \9 S; r! m
                    if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for& z7 f; Y% O# d. E- i
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);8 b2 J* y- q; ~0 {, Y9 Z/ U) U
                    //cout<<" 1st     tmp="<<tmp<<endl;" T& V, m; P! x. z8 A! R( \
                }0 S& U* l! W; N
                if(!s.empty())0 w* k0 f( E) m' G
                {
    & |+ T- C0 s. C% a/ P                tmp=s.top();$ Q6 d: q7 D6 s. r7 R
                    s.pop();
    1 W0 g5 w) g% ~% D: W) x                q=vexTable[tmp].firstarc;
    + _5 l4 y" a  r! Z, n2 q  z3 X) V                int t=tmp;
    . @( [8 O2 P( {1 q6 }                while(q&&tag[tmp]!=0)
    , i& Y* T0 x3 N+ E                {
    & k# D2 N9 `3 D' L                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
    ! g  F4 y7 A& D1 M; u8 @) H                    //cout<<" 2nd     tmp="<<tmp<<endl;
    " o+ Z- V( }' F: y+ Q$ V) ]                    q=NextArc(t,q);9 i0 Q) [9 [3 _# q8 k& G+ o
                    }: Q( k# u# g1 U" h
                    if(tag[tmp]==0)# q+ Z2 p0 q2 w1 V' q) Z2 K& s2 b
                        s.push(t);
    - ?, z: o  x6 x7 P5 h$ B                ///1、对应上面连通分支只有1个点的情况$ r7 Z- F1 ^. c( P
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
    # }4 C+ [# d4 @, j; Y# i6 }' j                ///tmp要么等于找到的第一个未访问节点,
    9 y/ Y4 B0 O; c; q                ///要么等于与t相连最后一个点(已被访问过)
    - M. z9 z+ }1 S! S6 v                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    ) P  {- f& Y* s9 P! D: j            }
    ) ]' B7 u0 C0 k9 w/ N& _, C8 M% ~) D        }
    ( y( u6 I* J: V: G6 w2 |: T% O4 U. X    }' i, _, g# f" K! J5 I
    }
    ' p" o" c+ E, j//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    5 l0 K0 H+ {' x# k* x; itemplate<class ElemType, class WeightType> int
    9 k6 o  r% J& a/ K! Y) EMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
    2 |8 q4 ~+ h- S' {( q2 e{
    ) H5 l4 ]8 n6 r3 {    if(head==pre)! L* \" V5 I  Y
            return -1;
    3 h# F( P" \: f$ E: f2 q, N0 l1 z' b+ {  i: g- ]8 P# r: N
        MultiAdjListNetworkArc<WeightType> *p;
    , `9 O) q- X4 M, X. U# q    p=vexTable[head].firstarc;
    ' }( X3 H1 B- J* ?3 P* v" W% z6 E    if(pre==-1&&p!=NULL)
    ) @& \4 r; @3 ?- {( H$ H0 v        return p->adjVex1==head?p->adjVex2:p->adjVex1;& C/ V; l" A% s, g  i
        //pre!=-1&&p!=NULL
    2 N& o; w0 A: i* J, R1 g3 \+ q    while(p!=NULL)0 M$ o4 m1 _6 C: I3 j( y
        {
    1 f" ?- [5 }+ r1 {        if(p->adjVex1==head && p->adjVex2!=pre)
    % i$ b( l# c* J8 E/ U& @: t            p=p->nextarc1;
    3 h, U4 L  J: ?1 }3 z        else if(p->adjVex2==head && p->adjVex1!=pre)
    0 U! ]- y3 F) ^0 A; c; E            p=p->nextarc2;
    7 q/ L+ w' K- V! W        else if(p->adjVex1==head && p->adjVex2==pre)
    $ {) z( q( m6 Y% }3 w        {# e6 Q8 p3 q% }7 E% B' a
                p=p->nextarc1;
    4 W% J9 K6 r# R- Z+ X            break;
    : K% T# @! l6 H( b8 w- T1 F        }
    * Z4 t8 B  q3 A+ |( p+ o        else if(p->adjVex2==head && p->adjVex1==pre)
      }  I- l7 `4 M8 T        {
    & ?- G' v) J1 F) r" E# e            p=p->nextarc2;
    3 R  t0 e6 G+ B$ y6 Q            break;. x- G& a/ P5 E4 h  f+ }
            }- e$ z, K. O. D) W4 C) A9 M. E
        }  o3 U5 s  \, H, m1 C6 x
        if(p!=NULL)' F- x4 p: o( q6 \
        {& \' J4 A1 L8 j  ?* S  T) N
            return p->adjVex1==head?p->adjVex2:p->adjVex1;1 S  z" \) b7 p* w2 V
        }; R0 _7 ]3 i  f
        else
    6 `5 a  P- e! _        return -1;, S  |' m; f: U* L2 d% z
    }
    * g9 n3 c' [! v) O8 o" K+ O7 _- t% v) R4 ^' c
      X* i& T. i; m( I+ c  C* _+ C& I
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    : v: x9 _4 G- _4 \5 \: U{
    5 E  x, @) O4 Z; f    stack<int> s;
    2 Z- S$ H6 S" b5 P    int p,cur,pre;
    & m2 s: ?& [7 @" Z: t1 e% ~    //MultiAdjListNetworkArc<WeightType> *p,*q;) o! }5 k+ B8 n
        for(int i=0; i<vexNum; i++) tag=0;//初始化
    ' B' l6 p- |: S; Y9 A
    ) ?' P6 r9 l* }) e    for(int i=0; i<vexNum; i++)
    . @) E) v5 Q$ T2 P    {
    ! L3 |  ^) I7 d        cur=i;pre=-1;) v- W6 R6 D$ \) Q5 C. g
            while(tag[cur]==0||!s.empty())( B3 `) P6 L3 |* S
            {
    8 \8 X3 C, A8 l( ~7 X; m% W2 ~            while(tag[cur]==0)
    7 |4 e5 i; B9 e0 S% n0 Q/ o5 F1 ]            {6 q. T, i! ?  p; P
                    cout<<vexTable[cur].data<<"  ";
    9 V1 Q8 d9 X1 n, d0 z: J                s.push(cur);7 R/ C+ @* F5 w+ k/ S* b( n8 M
                    tag[cur]=1;
    ( \; ?  h4 a! g9 E               //初次访问,标记入栈8 ]" o1 y" n" _

    2 s/ s- t) T  f3 {: t& K               p=GetAdjVex(cur,pre);//p是cur的连通顶点* U! f* w( b5 u7 M( _$ {4 u) V
                   if(p==-1)
    ! [2 x. H* [" e9 J1 g6 ~0 d               {
      |8 r# {7 D! k1 S  j                   pre=cur;s.pop();( H! d  m5 G3 m$ L5 E/ S% B
                       break;8 \0 E# }8 l* J% Y- D7 u5 ^1 J7 n
                   }0 ~, G9 T: ^5 M; m- W
                   else
    % K4 ?( w' ]8 Q$ j( B4 d. b$ k               {
    % m( y: J/ H( e                   pre=cur;
    3 ^* \' h( i/ u1 c; i) d6 N' d" d1 O                   cur=p;# U* z0 p( q) K5 L# @  U
                   }
    2 K+ y- U4 O8 s7 _) G: M
    0 }' M9 s: E  `+ d" a            }
    9 a; u) t0 ]4 `- j5 \9 o$ M            while(!s.empty())1 i/ Y. B1 C) j3 R9 ^, q  s/ e7 Y1 ~- \
                {
    9 d- L3 L- w( H" O8 Y0 h& }: T                cur=s.top();
    ( U: n8 q1 @2 J# [1 n4 k( x- J                p=GetAdjVex(cur,pre);; O; _; f, a/ b7 b7 y) @
                    if(tag[p]==0)7 P& k0 s; V4 X4 z/ T4 s
                    {7 f% j) ^$ i4 ~
                        pre=cur;
    ' R5 l' h  G; n# |+ _                    cur=p;
    3 A; q0 ?2 h* I- h+ @: n* _                    break;
    * M1 C7 n6 h! g& j% k                }0 w- {* {$ R6 ]& i/ _
                    else: y* K  }! p) m* x) A
                    {
    3 }! O  v1 _6 W1 ?: U                    pre=s.top();& b/ I# V# e; r. Z( ]( @) P
                        s.pop();
    / ?% K% ?3 d6 G$ ?5 n2 ^                }
    8 x8 R6 @# w1 v! O( U, t9 X* W  U& ^) k2 {
                }
    % C  U: c, G. o$ f  ]7 W, w: @2 M( i9 c+ p8 `, l+ {
            }
    " }+ ~0 e4 v- m3 ?3 W0 A    }; e& o0 L* f: Z$ e$ q
    }
      W4 L) \; }" {, C) D! @template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()5 G3 p# M+ r. k/ j) S* o
    {5 x  x" k: }( [' a
        for(int i=0; i<vexNum; i++)
    % n5 X8 j6 f' v. u9 g% J! Q        tag=0;0 x6 M" f0 i6 ~4 d
        queue<int> q;
    ) [* v0 @7 ?" I2 {8 O1 O    int tmp,t;7 Y% A5 o8 G' z' u) \% Z) w
        MultiAdjListNetworkArc<WeightType> *p;
    1 p/ Y  z8 p# }  j0 A    for(int i=0; i<vexNum; i++)# b( D7 B# W1 x* o6 ^! t
        {# B' A+ `5 ~4 D2 M$ Q3 V$ P0 K
            if(tag==0)
    ; F4 t* p. i- m% w4 H& a        {
    ' x+ Q2 n; S2 A0 M8 E3 g  G            tag=1;3 m$ b& l% O6 P# L* a8 ]
                q.push(i);; g4 Q; u& |5 @
                cout<<setw(3)<<vexTable.data;
    ; K' a0 k% I7 [4 j' }3 Q' m' ~5 l. c        }$ R# Q* j2 m9 R7 s1 V/ C2 U7 j
            while(!q.empty())3 v6 q+ x) h- e9 P
            {
    % l) P: B: w$ X            tmp=q.front();2 O3 p4 o" l  c* H% }3 L; D% ^0 O4 z
                q.pop();4 k. x2 |6 z" ^* P1 l
                p=vexTable[tmp].firstarc;
    ! n! Y7 _$ c# e9 q- s7 O# l8 u- R* N            while(p!=NULL)
    4 G' S+ f9 S4 ?0 s- b            {
    2 C  S; ]& i% m) z0 m$ I                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);" y0 N9 i, v1 j8 f
                    if(tag[t]==0)
    0 I6 J, O% a" \- b& C% D7 U1 \                {
    1 e* [; J: `( F                    cout<<setw(3)<<vexTable[t].data;
    # X# @" N+ a4 ^5 F' g- F4 P9 J                    tag[t]=1;. R, f+ |9 ~( E( t5 H7 |" ~
                        q.push(t);0 x3 d/ x$ E, i0 e8 ^
                    }
    . o0 n$ J7 P1 P% [                p=NextArc(tmp,p);
      Z2 C5 T5 F1 n, C. Q, i            }
    & {) c) i) \. z/ s& c        }
    6 ~- P$ I" T6 a. }( L& a* }    }
    5 N* F& {/ i7 `+ D}( G2 g# z1 U# r
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
    & V$ h3 i( @* T# q" q9 q{! z( Q- F4 H- f! _6 J# L3 P
        MultiAdjListNetworkArc<WeightType> *p;
    % t! m3 Y9 F3 \( l2 C    cout << "无向图有" << vexNum << "个点,分别为:";2 M' Z6 r1 z$ R# `8 E! d  f! ?( ]
        for (int i = 0; i < vexNum; i++)* ?) V/ |- ]  F+ |- V6 l& [
            cout << vexTable.data << " ";
    1 q" u! G5 B1 Q! @* e9 r+ Z    cout << endl;
    $ I, }1 a1 |. S( O$ a: T/ x$ y$ ]- F    cout << "无向图有" << arcNum << "条边"<<endl;
    5 T  a- C$ d1 t1 M    for (int i = 0; i < vexNum; i++)1 |9 y, n( U: U) H; x
        {
    " y0 y& p$ O( [1 x" h# m        cout<<"和" << vexTable.data << "有关的边:";
    ! ?8 K9 p3 n  U; t$ |/ ~        p = vexTable.firstarc;+ Q- {/ m- Z+ r% n+ D, `) i2 u( ~9 |
            while (p != NULL)
    0 E* r' E9 j4 Y: p: D  J  \9 g. N        {; T( u. g# v* A* p; M
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
    " d, Q6 M" n) H2 E5 T! S4 E" P8 h            p=NextArc(i,p);
    ; j; s* T" p; F6 _        }
    ( i- ?: l3 W' a' s# }2 v, v        cout << endl;' @( L; ~  }* C+ I
        }; A2 l5 U4 H9 H% a$ S
    }" I% {7 p: Y; K6 n/ T
    4 q. C0 B3 j8 j2 ~: F& a! q  R9 r

    6 z' f0 ?& G) g, e, |4 }邻接多重表与邻接表的对比
    0 w* i  T' B+ @9 `
    9 F7 ?4 U% j% ~$ E4 |邻接表链接
    4 n1 F; {0 v! M% f$ C  z在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
    & O0 ?( l' b& ]在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。+ @9 `" L1 J# w
    为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    ! w' I2 Z  V# y  g8 h' u+ d————————————————
    6 F% o. o8 t, a+ k" e4 K: B8 S版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。! r# q; a/ U+ D. [3 J. R  E3 N
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    $ K5 K2 b4 C+ q6 k# n
    : B3 t- x1 B8 m3 R( b8 q* }- e8 v# p3 Q( k- h5 Y+ F
    , G% g7 ]' {0 V9 T% @
    ! e$ O" @& U5 t) B5 c
    ————————————————
    5 k) {. @( i! e9 r; c9 @! }版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。7 \& O9 [0 Y) _7 T# J8 p
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    3 _3 i9 O' p# V3 P- H
    7 C( U% g) _3 M) X  g0 E4 Q% k
    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-30 06:42 , Processed in 0.419840 second(s), 53 queries .

    回顶部