QQ登录

只需要一步,快速开始

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

    4 Y' ?# T( G6 U. ~, x+ \' d图的存储结构——邻接多重表(多重邻接表)的实现
    9 t7 g; L( |. d7 e( [7 r7.2 图的存储结构
    9 p; s! e- B- P& E
    $ q; ~: m# V6 R/ p% U5 E( S7.2.3 邻接多重表(多重邻接表)Adjacency Multilist# M+ q% e0 e& X( ]& Y
    邻接多重表的类定义
    1 K' n: d; Z1 L邻接多重表的顶点结点类模板
      O( _5 g" @' E4 j. I邻接多重表的边结点类模板
    $ A& k( I2 T6 ^: d: C. O- S$ d邻接多重表的类模板
    6 K; ]6 t. ^/ a; E邻接多重表与邻接表的对比
    4 v3 h1 U* r, S* X7.2.3 邻接多重表(多重邻接表)Adjacency Multilist" v. j8 J8 v% b# m& f( z
    ) k6 w' P- C+ G& |+ j( d
    在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。  @1 i" r7 ]& n, I& ]
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。4 X3 c. S( `* y8 {" {- a' m1 U0 {8 o

    - a' H; R7 K; L- Y/ t, x邻接多重表的类定义
    * k% w4 S: T0 K" m 1.png % }8 i! g. r9 P1 x2 Y
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:1 z9 }- k2 V- g0 N, |
    data域存储有关顶点的信息;
    & T, }3 X: V# A! Q4 pfirstarc域是链接指针,指向第一条依附于该顶点的边。# s1 ]" G! I' y2 L0 d
    所有的顶点结点组成一个顺序表。

    5 N9 X! m% }# {  K9 N0 ]  J

    - q+ [6 n5 A1 b1 A: W1 ktemplate <class ElemType ,class WeightType>
    - f, M. S0 x7 ^' Aclass MultiAdjListNetworkVex3 Y8 l  N0 I/ H! z* d1 b
    {
    8 k- ^; W0 [! qpublic:3 n7 M' T0 q: u
            ElemType data;
      M6 @9 e* \( L1 A6 ^# g4 X        MultiAdjListNetworkArc<WeightType> *firstarc;3 P% A. F* [1 g( X

      Y; a5 J  {9 y. N. Z8 u1 g: b: D        MultiAdjListNetworkVex()
    % ?1 r; i6 O0 |: T9 z        {4 Z) A. f; X4 z5 f
                    firstarc = NULL;* f6 I0 E+ w- n9 R2 j
            }. C8 v. Q% x! m! i7 R
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL). i6 c6 o1 z) E& r) O. M
            {
    5 \1 t" E  w' j* [* t; Q                data = val;, N* h% {1 c% r/ ~/ t# L% ]& X
                    firstarc = adj;- R* g: r7 p  O- M  j
            }
    ; ?8 ~* G" S( ?};+ P( k% W! D0 M& f  l

    : T  n6 h# G: G; [" t  V( _邻接多重表的边结点类模板2 W+ [$ p  h, k3 q& p: O

    1 x' m/ m0 _; h在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:# D1 {0 g7 T$ f8 d1 g: u  J1 Y
    tag是标记域,标记该边是否被处理或被搜索过;- D# r1 b! t; n3 i- i
    weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    . X7 I) s, l, q, k  s$ pnextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;0 c: v5 d4 Z, [" L4 C
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
    ' H' A! J4 v/ A* J" E4 f6 y! m# I- ]9 Y! F
    2.png
    & ?0 G9 C, k5 q2 O. l+ Rtemplate <class WeightType>
    # f4 E1 J, t- yclass MultiAdjListNetworkArc
    $ ?+ I+ F+ Z$ I! G; {{
    9 S4 T" v# c, _public:
      J5 }/ _- w0 ~; {$ {    int mark;                                       //标记该边是否被搜索或处理过1 R2 @+ j, c: e& A# h' y/ f3 ~
            WeightType weight;                              //边的权重
    / v' W0 g' Y/ d# o! a2 c% @        int adjVex1;                                    //边的一个顶点
    ' w7 ?' z  F- h$ l" `3 O' L        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
    6 ]& s9 J4 G; l4 J- i( x        int adjVex2;. Q3 }9 Z8 \) |) t7 }
            MultiAdjListNetworkArc<WeightType>* nextarc2;/ X* k/ f5 R9 [( |4 b8 f

    , I7 |3 U6 u( z' u        MultiAdjListNetworkArc()
    % |9 x* B5 [6 W" `2 Y8 a* ~        {1 S( {4 }2 k6 J, Y, s3 T$ _, G
                    adjVex1= -1;9 A+ p3 J  ^( ~/ j  M* |3 P
                    adjVex2= -1;1 g* U$ F, X7 I. q. Z
            }
    ) b: o( i$ ~5 P' S5 P6 ?9 f5 G2 `        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    % K# \4 R: w  z        {
    $ M" A5 g& y7 B                adjVex1 = v1;       adjVex2 = v2;  Z& i6 j7 Q' F- W' A0 U2 M( h& e
                    weight = w;# u: o: N5 E& V
                    nextarc1 = next1;   nextarc2=next2;5 f8 U0 L) `6 [% S- {+ ~' [: p
                    mark = 0;           //0表示未被搜索,1表示被搜索过
    : Q3 ^: a& ~3 F5 d  ~% r' z7 P        }; C/ N: W* U7 p8 r/ E# h, }
    9 y6 }; Q1 N  S& S% @' d8 t
    邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>
    % h9 q% T1 x4 {! |class MultiAdjListNetwork
    3 c# r$ h9 B5 Q% R# @6 k' T+ Z# e{8 r7 O& z/ m' `" n$ s6 _
    protected:
    4 k9 Q9 w1 e) G+ e- M1 S  G% q" O    int vexNum, vexMaxNum, arcNum;8 j) P* ~, _- ~. {/ a
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;" N, }' Q: A) k# z& K
        int* tag;
    , Y, y8 C& `6 c6 x    WeightType infinity;# @0 c4 K- g5 O! ~* J) o  }

    $ z3 p. O% _/ N1 n' {public:
    6 I! _. Q5 R) W    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);/ @8 X; k9 U% U$ T( R5 G

    + S: l8 M1 ]0 I) R8 M  ^1 h    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    & R% _. D+ F0 M" n3 d' L" d# c/ n( S9 q; |. s
        void Clear();
    ! F# \& A; c  f, f    bool IsEmpty()
    * M7 @6 J9 @- K/ @    {7 {7 w: M' B. l6 R- V
            return vexNum == 0;
    " W+ X) i7 A. |% J& o9 ?( X- N: e    }
    7 ?9 n9 G, C7 w( F1 i: W# l3 b    int GetArcNum()const' N% L1 D8 H) W1 v; m. C. u- c5 n
        {' y- v- L, p* t5 j8 f+ @
            return arcNum;2 R3 o! x8 K2 I' ^3 u6 v. I
        }
    5 T- d" S/ k% O: w) [3 G    int GetvexNum()const, N4 k, @0 z5 s  h" a, W
        {
    6 M1 I8 ?+ {: B8 k# s/ ~        return vexNum;
    # r' T& M* \0 k1 V8 b    }
    , j* V" r5 y- Q( g" x
    / p' w, A" k" J& a- E5 |. \& G7 \3 m/ O' p2 n
        int FirstAdjVex(int v)const;5 J8 U5 _  z% A+ U0 N" L
        int NextAdjVex(int v1, int v2)const;
    5 Z* ?- s2 U8 r" o& Y    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    : _8 Y9 D7 u* M) ~) {    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;/ ]7 i3 g  _" A$ V+ H

    " z' O( [9 D9 ^    void InsertVex(const ElemType& d);
    9 t, O0 e) W4 l$ a    void InsertArc(int v1, int v2, WeightType w);
    1 q8 E* f7 C6 g' v1 u6 @
    , x1 L% x8 u1 z1 o, I    void DeleteVex(const ElemType& d);
    $ o  g. p7 G7 B    void DeleteArc(int v1, int v2);
    6 T3 b, R; P/ w8 e8 U* K2 r) \: B. v, h0 Q
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);7 Y' d, ~: h% e8 \
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
    : c) G% }7 L" O, R! H* `( z9 s7 y7 V* [  ?
        ///深度优先遍历
    2 t8 P) U$ c4 s/ w/ C    void DFS1(const int v);) V* K5 D5 i7 F7 B6 A4 N0 N
        void DFS1Traverse();
    2 h0 j4 c; W$ u4 c9 ]$ L    void DFS2();1 L8 h' g- {) d% m- v6 w1 u- ^

    * @2 I; R* H( y/ Z$ j    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    / U5 d5 i, G4 p4 V    void DFS3();: M* B6 i& l8 g  ]3 C" \/ V

    * \6 E9 {0 b! d3 P, @7 D    void BFS();
    2 h& v# X0 k! z: C- b3 l- ?& i: N    void Show();
    $ n3 z$ C; a# T. r7 i* a};
    % l8 ]% H+ V1 Z4 T1 t
    + x' q4 X5 l! c+ K( p2.函数的实现
    # b6 Y9 n; m7 L研讨题,能够运行,但是代码不一定是最优的。& Z# H- M2 P$ N' ?! h$ h& O

    : c4 h9 p+ [, S3 v3 z+ K#include <stack>
    8 ]/ W. |, k9 _7 A( @& x0 t) v" E#include <queue>
    2 F' G+ f1 h$ M- y- B
    6 k+ c, _/ [, {6 v! c2 ntemplate <class ElemType,class WeightType>
    3 O+ u, |. r1 C" u! GMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)6 W5 S* f! o5 Q' I3 @7 q, j& G9 d
    {5 ], w" L& v, m. v7 l$ C
        if(vertexMaxNum < 0)
    " y) m8 s! i) s% \' j        throw Error("允许的顶点最大数目不能为负!");
    - a) H/ n8 T! c    if (vertexMaxNum < vertexNum)" K6 D4 G! d0 d! e& Z! \1 k6 t3 k
            throw Error("顶点数目不能大于允许的顶点最大数目!");5 Q  O4 ~& P3 h  W( j- W
        vexNum = vertexNum;
    : {4 l" B$ \6 u    vexMaxNum = vertexMaxNum;  M4 o' G7 }8 r9 x6 u& e9 O  m4 g
        arcNum = 0;( c/ `- l/ b1 ]# h) F
        infinity = infinit;. g; X! A, G# _
        tag = new int[vexMaxNum];/ J1 j4 n4 H# D! K5 e5 s( ?
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    ; I" ?$ I/ _% u2 l    for (int v = 0; v < vexNum; v++)" m! [& W, U+ }- q) D+ K$ I
        {
    * |# d. G+ M# Q- X# A$ t2 l        tag[v] = 0;
    ) R8 _: l; L- L& B+ J3 f        vexTable[v].data = es[v];8 m1 ?5 Z4 t3 B
            vexTable[v].firstarc = NULL;
    6 R+ X7 y7 p0 |6 n8 w; U    }6 X/ C: W2 U6 _  I. R1 ]. s
    }, J- G; z' M" E( Y
    template <class ElemType,class WeightType>
    7 n6 g: u( O0 U# Z9 W# n" rMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    3 R5 q# [3 @  s. I7 x9 M) P{# q. b- X) v3 K* V. W6 B3 I# |  w' I
        if (vertexMaxNum < 0)$ W, S. a$ p( d6 I/ u$ r
            throw Error("允许的顶点最大数目不能为负!");
    / W- z  X5 p" O3 E! F- N: d    vexNum = 0;0 r2 Q4 q0 Y8 B" U( A+ Z
        vexMaxNum = vertexMaxNum;
    ! `" r. H# O. s: p" `/ s2 W$ q    arcNum = 0;& x9 O/ `1 O0 l! d4 B
        infinity = infinit;: c7 S+ G# N# ~1 C
        tag = new int[vexMaxNum];' `0 A+ z5 P$ i- e7 u
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    " K% ~) ]& W( d4 B}
    - F  N7 B/ h. Htemplate<class ElemType, class WeightType>7 D6 f$ p2 v/ h* `, f. b
    int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const: i. d4 _1 d! u
    {% F* [8 C* \* h! Y. a
        if (v < 0 || v >= vexNum)* r) ~" [$ u1 `: @  V3 h
            throw Error("v不合法!");
    & J9 Y8 N2 Z0 @5 ?    if (vexTable[v].firstarc == NULL)3 U4 q/ U/ e4 e1 ?/ [" h" d0 h
            return -1;' S5 Y) F+ O0 I9 |5 P8 Q: o
        else
    ' F/ d) S% T0 y        return vexTable[v].firstarc->adjVex1;
    ! B8 a( s9 Z) p, x0 x7 w4 ~/ P}9 m" N- g. g. x* a+ r

    - `+ X. \5 y6 N0 |template<class ElemType, class WeightType>
    * R, e" n* W' \. o2 Kint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    & V: s+ z0 V8 o{
    9 P: h& S3 Q7 r    MultiAdjListNetworkArc<WeightType>* p;7 |5 y" {1 b  J% M
        if (v1 < 0 || v1 >= vexNum); ]! z) m% @0 q; [, o9 C) s
            throw Error("v1不合法!");
    4 q1 x$ E! g- O! t5 e7 r    if (v2 < 0 || v2 >= vexNum)
    0 h: }, n; c3 X        throw Error("v2不合法!");  @) O8 T" s0 y0 L5 u
        if (v1 == v2)
    ! i% X" S+ f# d        throw Error("v1不能等于v2!");/ k( _% E+ k/ E( _! u
        p = vexTable[v1].firstarc;
    . h9 i' z$ M' ^    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
    / L6 Z! m( H* p        p = p->nextarc;& s0 `* y2 M; n( i3 Y
        if (p == NULL || p->nextarc == NULL)
    4 Q- ]- [6 L  ~* ?        return -1;  //不存在下一个邻接点& G4 a* b; T: P" v- I. e& A
        else if(p->adjVex1==v2)# R9 `% r- ]) S% V2 [8 |
            return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);5 @9 }9 t9 D% r& E& {" l! q
        else& P  \; P. ?- g) i4 h
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    , q) a7 Q) m6 H7 t}* e. j+ P0 o% a+ m! ?1 r
    template<class ElemType, class WeightType>+ f1 H( m2 W' G) w
    void MultiAdjListNetwork<ElemType, WeightType>::Clear(), s# L% |# M' H! {9 ~
    {2 E9 C6 a. d4 Q7 r
        if (IsEmpty()) return;
    $ J) W1 o3 W3 ^$ F1 j8 }* O    int n = vexNum;- q4 r% l1 A! H
        for (int u = 0; u < n ; u++)
    , R# x+ B3 |. p. g        DeleteVex(vexTable[0].data);
    $ b: M* S: ]9 W/ h$ F8 A    return;5 }& Z+ }0 ]1 C7 n2 l
    }2 x: f$ V# F" o
    template<class ElemType, class WeightType>
    $ W6 y  f$ l: |$ KMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()$ b. p: o  e+ C  U4 p
    {
    2 Z8 f" w. \3 z, ?, r3 s% ^    Clear();
    8 j; P7 L( t& N+ H}
    - ]( b1 Z( ?8 ~& m: ltemplate<class ElemType, class WeightType>8 F+ J2 E; ]0 \
    MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    + c7 y: V+ h' u7 B{
    & \3 G3 ?7 T9 k0 Z    vexMaxNum = copy.vexMaxNum;% {' [' q* W) {# Z0 J/ B" H% i
        vexNum = copy.vexNum;
    ' d% Y& Q! p& V$ A7 T    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    8 j% v1 G4 i3 I2 B0 W: Z    arcNum = 0;
    . ^/ E3 d3 ^& H3 g7 S! g& w    infinity = copy.infinity;
    2 U0 B: O1 X% t9 b    tag = new int[vexMaxNum];
    # C. {0 L, I3 F0 \& E
    % Y* B6 }* Y4 k' O    for (int v = 0; v < vexNum; v++)% V# p" u  t$ Y& Z
        {% f  x% `/ I8 n8 [6 A% B& B
            tag[v] = 0;
    1 k. M* Z' o* u% \% I9 ?        vexTable[v].data = copy.vexTable[v].data;9 j5 e, I: {" d4 z3 m
            vexTable[v].firstarc = NULL;! S: [. m$ i6 l+ a/ W! q
        }$ c% ^; M0 D! A: o$ ]) |: y' z
        MultiAdjListNetworkArc<WeightType>* p;
    2 l* P, u9 a4 n/ |7 P; ?7 Z& _  {1 {- J0 A
        for (int u = 0; u < vexNum; u++)5 a" b' H/ S0 P# I5 r
        {
    1 m6 e2 l9 Y5 P        p = copy.vexTable.firstarc;6 W1 Z5 I5 O0 l7 E! i) f
            while (p != NULL)
    " v" \5 ^9 W5 _4 ?+ h3 R        {' ]$ A6 e: V( k5 ?
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    0 [' j, C: w3 J: Y! t  _7 N4 w$ ^& \! s            p=NextArc(u,p);
    $ [; R' U' ^& }, _        }7 S+ \$ R/ ^6 E' C* h6 H: c
        }
    5 f7 }5 g' b0 i! Z) T( x+ |; m}
    6 Y6 q7 g; z, V" e. s" Ntemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
    0 ~- P; k& j8 ?) v( T* @MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    + _0 i. @0 r1 h( `8 S0 U  Y: H{" ~3 Y1 }4 j& {: _, R6 ^
        if (this == &copy) return *this;
    / e* x& Q. i; |$ a5 S& e+ [  j    Clear();
    7 d4 F* ?7 Q4 j& w/ G3 b    vexMaxNum = copy.vexMaxNum;% \8 m3 H( O0 L
        vexNum = copy.vexNum;
    6 R. u1 B' q, S( k+ H    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];1 W$ K3 ]2 P/ n9 G( f& [! l. e
        arcNum = 0;
    - G3 o$ k6 G; @* o8 K& v$ q$ l) G    infinity = copy.infinity;
    2 A' d7 C( @$ r  T    tag = new int[vexMaxNum];
    8 h; D- G! [5 G! ]/ \/ K
    + f/ n% X5 R) i    for (int v = 0; v < vexNum; v++)# f) j9 S. |+ _
        {9 ?; G7 ?4 l7 T0 P1 F3 o- @- ^
            tag[v] = 0;
    # M: k& d& }! G# A$ Z+ ~/ ]        vexTable[v].data = copy.vexTable[v].data;
    8 v3 F2 E' g3 r- w9 M2 h+ w        vexTable[v].firstarc = NULL;( `1 T# k6 Z9 t# h
        }
    # {8 i/ G7 r. I, j6 u    MultiAdjListNetworkArc<WeightType>* p;
    , z6 a! w% h$ c# p; p% V& J
    9 K" n, q* Y# F' d    for (int u = 0; u < vexNum; u++)& W* N* z2 |- @# z# l" w" U4 v& J
        {9 o" q8 D3 Y6 n# D1 l1 P
            p = copy.vexTable.firstarc;& G$ V5 O6 ^% j
            while (p != NULL); L' S& @! p6 y: M9 |
            {
    0 u; P+ d2 ?; H8 k) ^            InsertArc(p->adjVex1, p->adjVex2, p->weight);! ^# |! _) `( h2 [4 K& u' a' Z  Q2 G
                p=NextArc(u,p);) ~) N4 ~, N+ u! d2 ?0 ^' r
            }
    - U9 A4 s! f( S1 X3 r: x# k7 @    }
    2 |: S; Q1 w7 N5 I    return *this;) z/ V* K4 \6 n* p
    }
    ! y$ b6 {9 h8 [* i- L  {template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    6 q. @' p% @2 X" f% rMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const9 C9 N* o7 f7 R4 x1 h( ]# G$ z/ O( ~  }
    {
    , b' Z6 U, N, Q3 f& V    if(p==NULL) return NULL;
    / a. |5 v; f7 O7 p% `; I) H3 x, m  N    if(p->adjVex1==v1). |' I3 j0 k+ _3 _
            return p->nextarc1;+ c# M1 E2 t3 k- e4 @$ M
        else) R( V% v% V5 h5 i, d2 M# W
            return p->nextarc2;- G/ a3 b) w6 d9 \
    }" |0 @7 M) m  f/ f# X
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    : g# m' d: T4 M2 B+ J/ K& {# @/ oMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const% p* l; t2 N3 Y; S! K
    {
    3 w" w- C% e$ d4 q    if(p==NULL)return NULL;7 p' t: v, P" g' N" C! H
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    ! {/ K# b3 ?3 D7 Y9 z+ W+ N    if(q==p)& P' Z* J: s, l! p. S
            return NULL;
    $ V" b& }4 ~& G7 i0 c9 f    while(q)
    3 d, ]3 [# y% {2 p( S) Y9 H    {  ?* V* R- R% O: k) ?
            if(q->nextarc1==p ||q->nextarc2==p)3 J! Z  n# N2 K' x9 V
                break;; a3 D3 a; G* V- V
            q=NextArc(v1,q);( b' T+ [* {; v. J1 v, K
        }4 O1 k/ `2 l6 \6 Y4 b% }
        return q;
    : b# I; q7 N7 S' n. o}
    % D' ~/ J- ?. h' @% W4 A% ttemplate<class ElemType, class WeightType>
    - o$ _) ]# c" A- Fvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)7 ]! S! L4 [, X3 h2 v4 `, n4 n# c
    {6 M1 Y* r( v# L, |0 S  k
        if (vexNum == vexMaxNum)
    1 X" s) H& h2 H# }( f7 a& @; C* D        throw Error("图的顶点数不能超过允许的最大数!");
    6 D3 d0 Y# Y3 n6 t# o    vexTable[vexNum].data = d;1 W$ J. m7 h2 f7 G* F
        vexTable[vexNum].firstarc = NULL;. j6 P, j: v. W3 r. v
        tag[vexNum] = 0;. W0 c( Z! {: x8 |( w& G
        vexNum++;" v' `/ `! j3 n# x
    }8 s/ [0 c0 \) e  a( f, \+ W
    template<class ElemType, class WeightType>
    ) J- W" D3 [  n9 N# [. o- fvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
    2 ]9 F% D) }! u' {  \$ X+ l  E2 W{) Y7 O$ ~) y9 u2 p4 J& X4 \
        MultiAdjListNetworkArc<WeightType>* p,*q;, K- i' c0 e; W6 ^
        if (v1 < 0 || v1 >= vexNum)# L" V4 p( |$ c' I$ O7 c
            throw Error("v1不合法!");
    5 [, }- D) y9 N( H- b' d    if (v2 < 0 || v2 >= vexNum)
    / G$ z; J/ k% I$ ~        throw Error("v2不合法!");
    9 o; ]6 M9 M. v- b% Z    if (v1 == v2)3 n* ], r: W8 v
            throw Error("v1不能等于v2!");
    ' n! C0 }3 b( i& f- {    if (w == infinity). |( V* z: z" G& S
            throw Error("w不能为无穷大!");8 J& h1 O' G& T; ]4 T7 d# J

    , k! \! ^+ Z' y/ [
    ( e* u+ x1 j7 f3 |" E) i3 b2 m4 x    p = vexTable[v1].firstarc;
    ( w+ F, K( h: H5 K6 ^- H    while(p)
    7 R+ F, \) A6 @$ i0 ?    {
    1 j& h5 f% U; g8 z% Q        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中, W5 h( A; x3 |+ W. x0 [
            {
    ; K4 h: X" a  Y5 L% b  b            if(p->weight!=w)" ?9 |! F0 z" _& _. X# x& k
                    p->weight=w;8 F) f7 q# c& E0 p4 C7 i
                return;5 K# \0 e; ^% ^' i" o7 N( k
            }" d& {" _& D1 X- }8 I

    1 h9 [3 E7 k' \5 X* x/ b+ D& |        p=NextArc(v1,p);/ C3 d6 r' u/ B" ]+ F4 l: g! S! N- }
        }
    % L1 y& [- {+ I* p8 X" `$ u    p = vexTable[v1].firstarc;! `7 v% L' I! W& _( g. x3 r( B
        q = vexTable[v2].firstarc;& \; ?* t8 F. o6 a3 {; Q
        vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法* m3 J% q9 x7 x' p( b
        vexTable[v2].firstarc =vexTable[v1].firstarc;
    8 S  H# z# p) ~    arcNum++;
    3 f$ K  f  Z# n3 c: |: ~: y8 r, w}2 {; S7 i/ }" g4 ?  V- b0 V. m. v

    ( U6 Y0 ^3 N' f9 O0 i8 L- Utemplate<class ElemType, class WeightType>
    + a$ t( Z: M* I$ I0 ~% s6 Dvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)7 F4 M4 h, g; ^* F2 |
    {
    + C$ Y# F8 J, k1 y* D( e
    / E1 S: ^8 T$ A1 c. G% F    MultiAdjListNetworkArc<WeightType>* p, * q,*r;. |: t# K0 m+ b
        if (v1 < 0 || v1 >= vexNum)( S3 T8 ], z: c
            throw Error("v1不合法!");5 K* ^" p. ^+ i7 }' p7 O/ i" H
        if (v2 < 0 || v2 >= vexNum)2 g' Q4 _" v  d2 t
            throw Error("v2不合法!");
    3 s5 q% {5 y3 c' q/ q    if (v1 == v2)2 u+ m+ h  W+ I. q8 A3 I
            throw Error("v1不能等于v2!");
    6 K  x  A# M& G/ @2 O+ E5 B4 d& z1 R3 m  C- ^- N  V
        p = vexTable[v1].firstarc;9 x6 e3 o# l1 j
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)) r! C/ n% f' b8 U
        {
    9 S# b) f& N! ~* ]1 ^        q = p;( v+ q4 o& x. ]$ W3 v8 X+ |
            p = NextArc(v1,p);
    & `+ E7 w/ F3 |  }9 F    }//找到要删除的边结点p及其前一结点q
    4 K4 s8 q3 k/ N' X6 }# e! K& c5 ?- u# M6 v5 Y& G# h* d
        if (p != NULL)//找到v1-v2的边% V, C9 d# b, T: X/ R
        {& ]% u/ B' X' Y  @
            r=LastArc(v2,p);: g6 v! {- D) \* z' J3 l  \; P
            if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    % G* T! R; g4 w+ _8 J0 F! m            if(p->adjVex2==v2)6 d0 o  x9 k7 ?! m
                    vexTable[v1].firstarc = p->nextarc1;* q( r7 J& `  t, v* ~
                else vexTable[v1].firstarc=p->nextarc2;' t+ T) K5 l8 e& ~
            else//不是第一条边5 \5 ^) f9 U/ N$ n9 L
            {$ s" ~$ g) z4 u* r0 v
                if(q->adjVex1==v1)2 \4 h/ K. @; K# e/ D2 s
                    q->nextarc1 = NextArc(v1,p);
    # q1 Z) d& f* `4 h# s3 ?5 A            else! J/ t1 n1 C; Y" V2 _; K
                    q->nextarc2=NextArc(v1,p);& Z  L6 L5 e& O$ W

    , C4 P7 B3 p5 h. z# M        }
    7 Q" B! V& z: {% l        if(r==NULL)
    ) o- S/ _) s4 {, a, B            if(p->adjVex2==v2)4 {6 H/ }# ^) C0 k/ N1 Q' @9 j. k
                    vexTable[v2].firstarc = p->nextarc2;; S3 x2 |( o& ?
                else vexTable[v2].firstarc=p->nextarc1;
    ) r- G1 W# j$ Z9 n2 Y; ]        else
    2 b3 U1 F* N& i/ N        {4 V4 x% W4 P0 }# H& ~/ C
                if(r->adjVex2==v2)
    9 {3 o( @9 y  P6 {0 }3 d/ o                r->nextarc2 = NextArc(v2,p);
    5 q/ L3 c6 g. p/ p, \* {            else
    " l8 ?# c# `5 I+ k                r->nextarc1=NextArc(v2,p);
    ; D( [& Y5 \8 ~4 H- X( U        }. s# e4 P! v% b! D
            delete p;
    2 N3 n' P! p& t5 O1 X        arcNum--;
    5 G) m7 G: k- G! p    }5 \% x' U1 t; O* O/ i. M

    & t8 _' R& s5 I}, P$ g) p) z& ~0 m, i
    template<class ElemType, class WeightType> void
    9 q; V& D  `/ i3 @MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)+ _) t' G3 w5 A0 _/ l
    {
    : x, j& _  J3 p    int v;
    ; t" J8 [2 g0 r2 w( P; `    MultiAdjListNetworkArc<WeightType>* p;
    - V2 b2 W# d9 v5 {" g    for (v = 0; v < vexNum; v++)//找到d对应顶点
    ' b2 s+ j- k! U5 p5 g3 }        if (vexTable[v].data == d)
    8 B6 z( I# G: u7 Y4 g            break;+ M0 \7 |: y5 g& E: ^, ~/ ]/ [
        if(v==vexNum)2 @6 P1 g0 {2 P% s* n6 I, \
            throw Error("图中不存在要删除的顶点!");& l- e1 t" t. P1 }% _! `

    6 ~( T8 x3 k& ]    for (int u = 0; u < vexNum; u++)//删除与d相连的边  v  A6 X! H3 T4 L% L
            if (u != v)
    6 b0 j* K- \5 z' D/ P+ `        {  {1 {, x4 o  I" G7 q  A  w/ I
                DeleteArc(u, v);# G" y( }! Z8 X
            }( k) W  h( i# v0 ~% t. k# d+ l
        vexTable[v].firstarc=NULL;
    + a4 `- o) E* }9 B7 B
    9 }5 b- r/ @+ w# f    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置) |. Z; v$ ~4 L# K
        vexTable[v].data = vexTable[vexNum].data;
    ! T2 P0 M: c# z: o4 N    vexTable[v].firstarc = vexTable[vexNum].firstarc;0 o% {; W* b6 |5 o
        vexTable[vexNum].firstarc = NULL;0 m: ^2 h' L5 b; s* M# A7 f
        tag[v] = tag[vexNum];
    ; n% W1 y+ O. I# @+ X    //原来与最后一个顶点相连的边改为与v相连
      e3 q$ y7 B& }# }" z: U    for (int u = 0; u < vexNum; u++)
    5 S. @" P8 M, a- `  }* ]6 |2 a    {0 j: x+ N! a8 Z# c* ^1 ?- C
            if (u != v)9 E4 ~. Y% W9 l3 ^9 _& [
            {
    & j1 T- Y+ @9 G5 U9 u            p = vexTable.firstarc;
    ' u: G  [( N9 b& A4 y% X1 K            while (p)
    $ V* L% i' y5 L" s% C            {
    : f' `; h) [2 f: G                if (p->adjVex1==vexNum), E: U- }" a5 C4 N" q* J
                        p->adjVex1= v;
    , r7 ^) r% y3 }1 f0 @) {" W                else if(p->adjVex2==vexNum)! N6 ?; v& ^* i' t( y- n
                        p->adjVex2=v;( t/ A: _! k' H$ j  U8 k+ o7 ~
                    p = NextArc(u,p);
    4 f( a8 o3 D/ L# D/ A. c            }4 n1 k4 u$ Z7 `$ O
            }) Y9 |& S) r3 q& M; D
        }
    0 `* ]. @& [- G) f0 J}
    ' E2 Q+ ]$ ~' i///深度优先遍历7 z; [! w8 g$ D6 y) w
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)2 F, a8 y4 G4 w# F- J$ p5 |  j( k
    {
    ) g- O2 q# Z9 E& W# T9 m    tag[v]=1;5 F' p  s: [+ f1 X( ~) R
        cout<<setw(3)<<vexTable[v].data;
    9 o' ?& ?$ o/ a- l8 \$ p/ e    MultiAdjListNetworkArc<WeightType> *p;! F# ]: D* s$ E
        p=vexTable[v].firstarc;
    6 A& |! \6 ^: ~+ r    while(p); \) c( |/ W/ {! g* s( M
        {
    : U6 n+ f3 e0 g( }        if(tag[p->adjVex1]==0)( Z+ ~5 A/ C" ?% @* [: ?
                DFS1(p->adjVex1);
    $ J9 s0 S0 I& Y$ {' |9 E$ x0 i  g        else if(tag[p->adjVex2]==0)
    . Q- ]- ?& ?" D+ T            DFS1(p->adjVex2);+ n$ {: i! ?5 a( f) F
            p=NextArc(v,p);
    " @. _; G0 |6 }+ k    }& m% S, T! l  Q2 T4 E: O: |
    }
    * N8 E; D' R; l; vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()- _+ y/ t5 H/ J, X+ `
    {
    ) ]+ I' y; {3 F7 e* j- l% q    for(int i=0; i<vexNum; i++)6 q4 P9 F  ~0 f- m
            tag=0;$ c* c. v  j' X" K$ j
        for(int v=0; v<vexNum; v++)6 C$ D5 _) `( N% y9 V
        {# U5 A) w! v0 K$ x
            if(tag[v]==0): o, @3 m: r; t$ x4 y  ?
                DFS1(v);
    % ~% w! _; G, k6 t& ^: H* T6 [    }
    $ F, Y1 y( H1 |}
    " i1 q( B3 q9 L! n6 g* ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(), ^& K! J: i! m" }% E- R
    {7 t' \- |. P4 ]5 q/ R
        stack<int> s;
    5 |" n: p8 J! \    int tmp;8 t( j6 F  }' m3 p* B4 X
        MultiAdjListNetworkArc<WeightType> *p,*q;
    6 D7 \, z5 ~1 b    for(int i=0; i<vexNum; i++)
    + e1 `( f5 s& I, I2 y+ i( k8 I        tag=0;  N' {" @9 c9 ~/ U' A, m
        for(int i=0; i<vexNum; i++)( v( I* s, V/ D4 i
        {
    8 {% B$ Y6 d4 S8 ]8 q1 N: t* e8 `        tmp=i;
    ; _+ r& M, K" J$ o        while(tag[tmp]==0||!s.empty())
    , {5 o; a# j* I# n        {
    7 d8 x) O# O* ]            p=vexTable[tmp].firstarc;
    % C' [1 R6 N" z/ f0 o: J            while(tag[tmp]==0)4 k8 j2 Y. R4 j) L, w
                {& j4 i3 Q1 m; R3 k; q( P2 U. P5 l3 P
                    s.push(tmp);0 T: r# e& P. r: m# F; p, Q* J& p
                    cout<<setw(3)<<vexTable[tmp].data;" j1 G% d, Y8 H7 W) v
                    tag[tmp]=1;9 g" ~2 Z5 U7 L* }. O
                    p=vexTable[tmp].firstarc;% x. E1 e& [. d7 ]3 q" w
                    if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for+ U) U+ }% {# H
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);3 J) J" Y; D/ a- ?2 h, ~
                    //cout<<" 1st     tmp="<<tmp<<endl;
    - u: \: w; ~% F+ H/ I+ Y5 N            }' H' x4 P) i* P
                if(!s.empty())
    $ Q1 ?& L8 Q" T9 d) z+ O            {) g. Z6 e" w6 F6 _( C* ]
                    tmp=s.top();0 U9 I+ G3 _9 D; |6 s! z
                    s.pop();  l4 d  O2 w) z8 ^5 z
                    q=vexTable[tmp].firstarc;
    5 u3 d  d; D" t                int t=tmp;; I) o% I4 H+ x/ _" t
                    while(q&&tag[tmp]!=0)$ C1 x; }, Q4 b% a( W
                    {
    $ [5 x, k; G' r! M( o$ g                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);0 z: N' U% f5 f  v# v
                        //cout<<" 2nd     tmp="<<tmp<<endl;
    8 l/ L% B  v6 w( S                    q=NextArc(t,q);' G6 j- X) o# [) }: c5 Y& g
                    }
    4 E% |: z0 ~8 }- c                if(tag[tmp]==0)  i1 R$ e! l1 I0 k1 q
                        s.push(t);/ l( Z& X' g# G/ W' `  l
                    ///1、对应上面连通分支只有1个点的情况; [* d& K: W4 p6 L9 N; l0 |
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈0 z7 J! i0 Y3 K, m
                    ///tmp要么等于找到的第一个未访问节点,: s. T7 m- H8 v3 X0 M7 r
                    ///要么等于与t相连最后一个点(已被访问过)
    ; K2 v7 G( s) [1 J+ {                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    + y  z% G- J, l% {# W  ~            }1 x& T% t* s0 h$ b) N) e
            }8 ~, @( O5 Q9 B. B
        }
    8 m' }& N" T2 O# I+ c}. ?# }% \& a# V' {3 M; d4 ?1 s. z
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-11 R; g1 i" @  h: b
    template<class ElemType, class WeightType> int
    # w' Q$ ^/ Y# S6 JMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)# D8 P9 D- {6 o3 W, h2 _; E
    {
    - y& Y/ T' ?9 X* S! B* X9 A; J5 x    if(head==pre)
    . t: {. ?5 t% H        return -1;
    2 n' o' L1 ]- G1 V  b! Y+ I- D
    8 B5 c6 x" j/ `* n1 s/ i    MultiAdjListNetworkArc<WeightType> *p;
    ; T7 M8 F* Y& Z" ?, f    p=vexTable[head].firstarc;
    . s2 }" K/ p! M" x6 `( v1 o    if(pre==-1&&p!=NULL)4 J! r0 @- }: x7 g7 W3 g: G; j! j
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
    8 ], j/ B' W" P% I" P% @( g* i  Y    //pre!=-1&&p!=NULL
    $ l& ~; V3 w% C+ V% g    while(p!=NULL)9 j7 F0 I1 D4 V0 ?
        {
    $ k3 Z# U% B! V. D        if(p->adjVex1==head && p->adjVex2!=pre)
    6 n" @6 M5 r+ U5 ~6 V* K            p=p->nextarc1;
    / Z* c0 B' g$ u- S9 d4 ]6 N        else if(p->adjVex2==head && p->adjVex1!=pre): D$ J  q4 E0 ~( R
                p=p->nextarc2;
    ; j5 J8 Q; A" p! k6 ^        else if(p->adjVex1==head && p->adjVex2==pre)4 E# n9 r5 j' r& q8 {0 m9 j
            {
    & z/ {3 j1 ]2 r. y            p=p->nextarc1;
    + m9 V  V# W# {$ @0 g            break;
    9 g* @! |* q. Q# z- S3 y  C. A  W        }
    - o- A+ m! w0 c" z2 T6 P7 W! R! O        else if(p->adjVex2==head && p->adjVex1==pre)
    0 |$ E  D7 k+ y9 Y6 l( C        {7 Q$ e! Q9 Q* C" E8 S, u* p
                p=p->nextarc2;, A+ w5 `8 U3 U0 e- v  a# P, b6 w
                break;2 z8 t* c2 q1 a+ u9 \
            }* u' M" i2 b# r" D6 x* c
        }3 a9 d9 p& n" d/ f& Q3 b! ]
        if(p!=NULL)
    ( E4 Z& u# I1 s    {
    % I" F" Z  ?7 D( A$ V        return p->adjVex1==head?p->adjVex2:p->adjVex1;! N/ H" ]* X$ Y# b& W3 [9 t: f
        }
    ; V: T8 l) z  y  c    else
    ' _- S. n; x9 u" Z# o; D/ j        return -1;( ^0 M; b) b' ]$ g. @' H
    }
    4 G0 r- q: V+ S2 b. y) O, p$ Z% s* A2 T3 D5 i

    ; |+ M1 S& [3 y7 R2 C% Ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    8 Y' ~+ T& g- u) |0 q! m{; y+ K8 K. l3 D& d. ^0 h
        stack<int> s;
    & I; A# R# M- A; ~( l    int p,cur,pre;
    0 n* H& J* ]3 c    //MultiAdjListNetworkArc<WeightType> *p,*q;
    3 u+ I+ s; P0 [    for(int i=0; i<vexNum; i++) tag=0;//初始化
    * L8 u  o# i1 d# C5 H
    / u9 U" w7 }  F1 z; u. q    for(int i=0; i<vexNum; i++)
    4 T' r8 N9 R6 G! H: k& f8 Q    {
    ) a& ?' v0 F4 Z3 }$ U& C        cur=i;pre=-1;0 ?# b' v+ k& L1 B4 j
            while(tag[cur]==0||!s.empty())& Z9 w) t  N' F8 T5 g( O$ s
            {
    ; U. L8 D6 Y; E2 L& V            while(tag[cur]==0)1 D5 d- U/ K& m0 X6 c' a* C9 W
                {
    ( v* p9 B( g% h/ e( c                cout<<vexTable[cur].data<<"  ";
    6 u# w# r0 }4 J! ^4 [5 W5 Z                s.push(cur);) C$ b1 A$ x1 g+ ]' E" C
                    tag[cur]=1;+ i' Z% J' g2 U; l  i: s/ B4 ^; Y
                   //初次访问,标记入栈
      z8 D5 C* ?- p. }- V) F: [! I
    ( b( ?1 B3 \3 t' Y               p=GetAdjVex(cur,pre);//p是cur的连通顶点% p9 E! t1 T, _: I
                   if(p==-1)' }- E% \& R3 u. `6 k, j
                   {
    ) a: Y6 a( j# _                   pre=cur;s.pop();
    . p2 y9 N/ z+ b) H                   break;
    ) s) c3 u% D, |8 c3 `               }
    / s0 `) ^9 S! h               else5 L4 `/ ~- U, Y5 {% M$ R' ^9 K1 f
                   {
    # U0 ~& U, B- c, f; I                   pre=cur;
    2 e( T* ~0 E- g) M5 L8 o                   cur=p;
    # a  U2 u, I4 g  h3 @0 p               }3 [5 ?- _/ P5 ?. m# j4 p. n

    # q: k, v% O, c& v0 t( F2 Z6 Y            }
    * q% n$ Z9 q( w8 p            while(!s.empty())
    & K+ p: ~5 n/ e* ^            {
    9 t, K$ @2 o2 T6 R                cur=s.top();
    ' J8 C- t' ~& Z$ Q2 J  i                p=GetAdjVex(cur,pre);4 N0 m7 D+ p& k6 F
                    if(tag[p]==0)
    " F1 R! }" r% ?/ |% ^                {
    * I1 G3 Q4 L1 V3 r7 c2 p                    pre=cur;
    5 z) o) D# C+ B6 Z, Y                    cur=p;
    2 d6 b0 L% H) B! D; b8 y                    break;
    $ A8 d6 [7 n5 v. e6 o, A. i                }7 f+ a- I, M, D" u& K
                    else0 C6 v: t( Y1 Z# O# C5 X
                    {
    + L% n4 N$ O! L                    pre=s.top();  k; j0 O( J- ~) u4 ]- j6 [/ s6 _
                        s.pop();
    . \! L1 V! o, E* x2 Q. i                }$ o% q- x+ {' J) M3 @) I* K3 z
    ! _- x. C+ g* ^. N/ Z2 G
                }
    ; F$ Q; T# Z; [7 }3 d" y; C- W" {3 \4 v; Q" f2 ^/ A
            }
    ' J$ e' @0 J' ?' b  T8 i5 ?    }
      _9 ?2 y* Y1 \( m$ E0 b7 B}' E! w6 p8 j1 S: h" Z+ r) ?9 g
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
    ( q8 i  L, O/ w: g- Q# X, ~: ]{* J* `3 H2 G+ ?! A
        for(int i=0; i<vexNum; i++)
    $ Z$ J- \5 T/ j) v$ x        tag=0;/ R. x2 a# g" S" f: H3 U4 A
        queue<int> q;
    6 T; j! W. t+ D% c    int tmp,t;) U, ~; @* J% O, V
        MultiAdjListNetworkArc<WeightType> *p;
      S5 P' O1 w5 H7 c9 }: t9 @    for(int i=0; i<vexNum; i++)* p  j5 N" a  d6 O. M* u/ G4 [7 |1 i
        {. P/ H/ N. f: c4 N/ h4 a+ B  c6 H
            if(tag==0)8 E: K3 P8 |/ c0 i
            {, b6 m! q. W8 e; M6 ~" I
                tag=1;" @! w3 Z; X5 G9 }2 J& @! j2 X! s
                q.push(i);
    ' a8 {4 z$ P: \' E            cout<<setw(3)<<vexTable.data;+ C/ t% ^3 \( c& z8 y- L$ x
            }5 ?* P* B( B5 o
            while(!q.empty())3 ?$ {" Z4 q9 R6 i0 F
            {
    8 d) Q. e/ O# R9 w( ~            tmp=q.front();
    7 r7 U9 j4 n7 F% [            q.pop();
    / G& X  H- }& g! c7 X$ F            p=vexTable[tmp].firstarc;% m8 v6 H7 @$ S! `+ D$ D* r2 e
                while(p!=NULL)
    ) |6 M& Z( `2 K( L; E            {0 `$ _$ ~; w# K( H+ F3 A0 i3 ~/ v
                    t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);4 h3 J+ F, Y) A0 C6 l4 e. t$ L
                    if(tag[t]==0)
    6 [' ~, t1 D7 a' \( o, t) j/ u1 j                {* f# u2 Y: y: r8 y
                        cout<<setw(3)<<vexTable[t].data;
    + H( B8 J  L  s9 N+ y" {                    tag[t]=1;
    3 v( ^$ i7 H, k9 i; K& O- h- K                    q.push(t);
    ; n  \: h, |/ Y/ V* ~: x& ^, n                }
    7 x1 Z0 R1 |7 Q/ A) D  P                p=NextArc(tmp,p);
    & J$ t6 U: y. _0 x: L$ Y# ]            }( C/ u( I* ~) v9 q5 Q7 N% g
            }
    0 C3 A5 J! z* ?$ v$ h- S    }
    . o& [( b, _- Y6 _2 @5 s8 j}6 q+ j7 O% l3 ^# W% K  m/ x
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()4 Q  I& V% _0 ?2 F3 b: `4 ]7 L
    {# l( ?  q. U( `3 z( j, u
        MultiAdjListNetworkArc<WeightType> *p;- S# [  w+ I  h( i
        cout << "无向图有" << vexNum << "个点,分别为:";. @4 _5 V$ ?4 \0 d3 h
        for (int i = 0; i < vexNum; i++)" f3 w" E/ T! }, w- S9 @1 i
            cout << vexTable.data << " ";
    ) ~/ i2 Q% R8 f  q    cout << endl;) o/ N' Z1 P" W* s2 h$ }: N
        cout << "无向图有" << arcNum << "条边"<<endl;
    ) p) ^* u6 U/ X% ?; x( Z" T3 ~    for (int i = 0; i < vexNum; i++)* w8 z* t0 u+ f& O& n2 E. J
        {- N- I- f& z) m" S5 Q# Q& j* a6 O
            cout<<"和" << vexTable.data << "有关的边:";( \3 R& m, J8 C5 c
            p = vexTable.firstarc;* o3 @7 C4 T! o
            while (p != NULL)3 w  a8 t$ z# k" a+ x7 K
            {6 z) o% [" s+ W$ z2 J5 `# z
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";: [) [: ^: j5 d
                p=NextArc(i,p);
    ( j/ d" U$ y8 I' d        }
    8 s8 _2 f" v' K" c- z# s( |  {        cout << endl;3 G  `6 S, ~7 v  F$ ?
        }; q1 O5 \- z2 J
    }
    ' B9 X0 ~1 K9 z& n1 Y' v& H: {7 {5 h9 L+ l2 P: E8 `4 c. z+ E

    6 b3 t8 V- ?% V0 ~1 f& }1 U邻接多重表与邻接表的对比
    6 o% }& k, J% D# p- e- ^8 o
    % L! g- k" c: {0 A* \( h* D+ ^邻接表链接9 ^2 u" w- K8 e5 n+ g
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。) L, S/ o5 w) [- L. B- @4 P! f$ K4 \
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    9 h6 T) [9 K! X, O为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。& x0 R. r& D) c' F+ f1 U* C
    ————————————————
    ; s4 Q, e9 F# n7 C- y版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。* c$ e/ n- H7 k
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958- b" I! r4 }8 _/ b6 P& h
    6 M, R7 s  q/ F* u, o
    ) i4 |; L: Y+ j! f

    8 D8 g" r: X, \+ M, l, L/ l8 v" o* y  [! J5 V
    ————————————————
    1 Z- @5 B: _. U版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。* A) J% c0 U' y4 A  u
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    . z( G' _7 p0 u0 L: x
    7 ~' p; X  I) \% _+ L
    , n' |/ m& g. J  _# U9 x
    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-11 23:08 , Processed in 0.670621 second(s), 54 queries .

    回顶部