QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1595|回复: 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
    ! i4 V4 J5 n3 }. k8 m
    图的存储结构——邻接多重表(多重邻接表)的实现
    0 _* D1 ]$ ~. k: w7.2 图的存储结构
    $ K, w: U3 R) A, y0 g4 A  g9 m5 B  f# a( O9 t
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist" F) S" O3 {4 A5 ]
    邻接多重表的类定义
    8 N: F/ e0 V/ b" g5 P邻接多重表的顶点结点类模板! `7 i6 H7 u. y/ B
    邻接多重表的边结点类模板
    / H! `$ s7 Q  S  Y/ u, D/ i4 [邻接多重表的类模板
    $ v& J* r; P3 V0 a/ c; c" o邻接多重表与邻接表的对比
    5 A1 L6 t; z( b0 c7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    7 w" s6 D" A" H, S4 v; N0 n: `/ m" H8 T$ K( T( I0 g9 X
    在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。  F+ F. O/ g$ Q
    在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    $ a% X+ O0 T) M* @/ D1 b# K2 [4 o$ h( t8 r5 f7 U* q/ I
    邻接多重表的类定义7 [0 v' \  k* m( |* O0 P! ~! K. V
    1.png 2 p8 O8 S+ }" u! O
    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:! [, p- M, g# Z& ?, V6 W  d
    data域存储有关顶点的信息;
    0 t" X: u! s$ ~5 a8 i' Pfirstarc域是链接指针,指向第一条依附于该顶点的边。
    ( D+ ?8 F6 D5 |: Z6 s# w所有的顶点结点组成一个顺序表。

      f5 b6 g+ d5 h
    - q3 r; L* v" W" K( x! Y# f- ~9 X9 s
    template <class ElemType ,class WeightType>
    ; p0 S$ H# d! A0 }7 f6 yclass MultiAdjListNetworkVex
    / y( r( j$ g: a( m/ ~- X7 h{
      W5 Q; l  L; v* s1 ?2 q% ?public:2 k8 ~, n% \( i
            ElemType data;
    4 o- X% S% v2 }/ f$ Y        MultiAdjListNetworkArc<WeightType> *firstarc;, _$ c9 T" V" A% k3 O
    6 M6 @# ~5 @2 ~' Z' O6 A4 Q
            MultiAdjListNetworkVex()( J3 w0 _. J: G  h; {
            {
    8 U% g* \, P# r, C6 z% p( F" z                firstarc = NULL;9 u; J7 T8 o& p9 G- n3 c
            }4 y. b+ k' d& I) n4 i
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
    & k5 i" @( ^8 Q5 N# N2 @7 o$ m        {7 d  f) B8 y: o# b. \4 |
                    data = val;& \: J% u1 S1 ?0 ?0 M: E" B6 j2 F
                    firstarc = adj;
    3 E' n. N6 |$ A: e* D& g" S        }6 J2 Q2 n6 K+ y( d1 a
    };) M/ Z/ t9 r9 ?: E3 }

    0 o7 `# q( [  G6 Q& b) W' ^" l* W, ~邻接多重表的边结点类模板& [/ b3 t- @2 a. K
    . J* `% S: P! \% z1 Y
    在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    # h2 _1 w5 w% t6 `; V' |tag是标记域,标记该边是否被处理或被搜索过;
    $ J0 [* u2 o& ~% ^+ Yweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    3 Q: I6 V+ |) D; R8 [nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;0 J- @5 O/ @. V$ L
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
    6 h, D( V# Z5 U2 M1 h
    : ?8 C3 u- O7 p 2.png 2 z- r' `- G5 M% T. [
    template <class WeightType>
    * I$ W5 }) p2 G+ B+ x& ?8 Vclass MultiAdjListNetworkArc# N) [5 x+ o( E0 N
    {* ^6 C8 ?' N3 I) w# C
    public:
    % G( H* O' a% M8 f    int mark;                                       //标记该边是否被搜索或处理过
    / o- w! Y% ~) m9 K5 S# T4 O        WeightType weight;                              //边的权重& K* c' F5 Q% u" l3 ~" C- j
            int adjVex1;                                    //边的一个顶点2 P( Q$ L% G* k8 H
            MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
    5 h1 g0 R- z* |        int adjVex2;
    & Z5 S  s4 u9 V/ O1 x- X        MultiAdjListNetworkArc<WeightType>* nextarc2;
    8 A! ]+ ]7 I4 i2 J& z. I( V. V
    ! K2 j# L+ E6 s        MultiAdjListNetworkArc()
    ) A# i+ ~  P# U  Q        {
    # J% R# M! {1 D                adjVex1= -1;" I. G4 \* f+ Z( A& M
                    adjVex2= -1;, Q& X. y5 k5 B  I
            }* P6 F  i! \) j9 o' P
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    ; M; L% v' a. I& t4 g" W# p        {/ r1 c: g3 g4 b3 F* f$ y
                    adjVex1 = v1;       adjVex2 = v2;
    0 z. v- R( Y6 g: T5 Q2 t9 `3 B                weight = w;; R* V+ M4 d# n$ h& U
                    nextarc1 = next1;   nextarc2=next2;
    2 b% E/ R  `7 l! o& R( N. K                mark = 0;           //0表示未被搜索,1表示被搜索过0 I: D2 z* f/ A6 b% u' r  |
            }
    4 L. p* ^# h5 ^$ \3 o' Q& W6 k
    % n% ~; s2 V, b$ ]+ c1 U9 L邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>; |' n2 o- C# h7 g4 M6 Q
    class MultiAdjListNetwork1 G% a' I) _" |, M; e4 a4 F/ j
    {
    ! W* N# S1 _) O% V) uprotected:
    ( G. f2 {# C5 F+ o    int vexNum, vexMaxNum, arcNum;( m9 }& Y5 K, z, E( j+ O# z# n( Q
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;$ d* `8 h& @/ `% d2 S# j) h
        int* tag;
    9 G: x1 h2 D1 w; F9 r, [5 P/ G    WeightType infinity;; P1 H0 t+ Z" u5 U

    ! C' \. x5 L9 `8 F7 B6 x8 d2 Upublic:  e7 o; N& t7 s5 C: S8 e7 W9 r
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    + t3 b; }" M  @+ y
    / n! _0 b* e' B# u  E- G8 b& f    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    6 C  D0 h- ?: f0 r
    / k- x+ s4 f) z6 b: t" N    void Clear();$ ]: C& B. [, T3 F# Y( C: L
        bool IsEmpty()5 |4 v$ A0 a5 _; Z; {9 Y
        {  a2 Y/ b+ b4 v4 h3 Z" d
            return vexNum == 0;# p0 s' x. k* e, s& U
        }
    / l7 G2 o9 _' x' I  Z- z: B4 W    int GetArcNum()const
    $ S' X( H" D8 u& U$ o: Y) r    {
    , v! P  w6 G* z1 ^& w/ `        return arcNum;
    " ]! e" t$ O  {" A5 Z    }
    2 ^2 m2 @  k6 @7 |    int GetvexNum()const0 j9 _/ \1 Z/ f5 }; l- ?2 y& p
        {% ?1 ^, n0 Z; Z
            return vexNum;
    0 L/ z7 ]; k$ H, D' P    }
    " N2 Q) L! a# \/ J6 F
    & M5 X' {2 K# L! f" h; T- D8 e/ h: u
    : l3 g5 G! r* c4 @2 o$ p    int FirstAdjVex(int v)const;) G/ @; k& e8 r4 z* s" ?! D  T
        int NextAdjVex(int v1, int v2)const;. }3 h4 @2 G) s! U5 q! a
        MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;" r* x4 k- d: {  q& n- m) ~/ a; s
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;2 J) o) ?" ^* w$ e; K* F% ]

    / C2 C; ^% d) q6 V6 m# |4 l    void InsertVex(const ElemType& d);
    6 j  \% C; v# k. q7 t5 G+ a    void InsertArc(int v1, int v2, WeightType w);+ W9 m& I0 K  O: \6 l  @

    # W7 q1 D) i( O. {2 Z) D0 F5 O  O    void DeleteVex(const ElemType& d);! Q$ D- V$ Q8 J3 t
        void DeleteArc(int v1, int v2);
    : S$ v6 R, y; v2 B& ?: z  F
    7 T3 G5 \" d5 p- _, ]: n    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);, y9 Q2 O! L3 N9 ?% x  i
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
      h; ^3 z8 g. t/ r2 L! }  }. a4 `) C' O7 b0 u: a& n
        ///深度优先遍历
    2 J, s" {2 K! J! A3 J    void DFS1(const int v);
    9 }- X( D) }- F/ k1 M1 c; H, f    void DFS1Traverse();) P+ s8 `  @! R$ o, M: g! }
        void DFS2();
    7 x; Y- d4 g* X! N7 B2 q4 o: p: v& `5 e) B$ X; Y6 g
        int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1$ W! w' l2 T5 _& r0 T/ l7 W
        void DFS3();' K$ {3 x/ e% A! e) ?

    6 t' T# N3 w9 `% z+ e    void BFS();& [0 a$ W6 r% `6 Q  ~/ V
        void Show();% i3 G, `8 r( h& ~, Q
    };% B/ j. X3 B! N2 d$ ?1 O5 e) v4 ~
    ( N, G4 E) D: Y% P1 G' N
    2.函数的实现
    7 p* ~* L* l/ r) t研讨题,能够运行,但是代码不一定是最优的。% g; z" S; N9 |1 y' C7 V
    % c) \" G8 f! b! S
    #include <stack>
    0 ~7 w8 U9 x' g#include <queue>
    & z2 _* b: b2 y  b. j. A7 H6 u' Z
    8 m* R) C! j) p, y# C# D1 Xtemplate <class ElemType,class WeightType>7 w3 c% E# w! b( F3 k; X
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    * v1 C* y9 Z+ {: G$ A{7 @  p- z, A# ~$ e, b# e
        if(vertexMaxNum < 0)8 m9 q/ H' P1 J
            throw Error("允许的顶点最大数目不能为负!");
    , {+ U, H" s# _- o% Y    if (vertexMaxNum < vertexNum)1 E: J* o8 y( X9 {1 `
            throw Error("顶点数目不能大于允许的顶点最大数目!");
    ( D: j+ G; }0 F  w" u/ D; F# k    vexNum = vertexNum;0 }; c; j- u2 Y8 [5 ]
        vexMaxNum = vertexMaxNum;. \( f2 u# B2 K& G2 S0 L+ |. {
        arcNum = 0;
    # t/ l+ t) G$ R( V    infinity = infinit;
    # y; t4 c7 s8 K% F* n    tag = new int[vexMaxNum];
    2 e1 J6 T! v7 u$ r9 J1 I    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    ' r+ A1 `& G# A3 t  t    for (int v = 0; v < vexNum; v++)* ?' n- d+ d, x- L9 H& L% m+ I
        {6 u! h% K& ~; G
            tag[v] = 0;
    4 H- {( A1 n5 ~        vexTable[v].data = es[v];! W2 r+ k, z; H- Y
            vexTable[v].firstarc = NULL;( q* u4 B* r! r" k% l! S& Z- v$ ?. ~
        }/ w$ S8 l1 _( Q
    }
    ) O3 d! q5 x. |: E! V" ftemplate <class ElemType,class WeightType>
    1 ~4 e: A* e% C( ]3 P' t. j6 M9 sMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    ; O, m' d) u$ K. R0 O" `{2 H, J* h- t$ H, E5 H7 \8 L6 o( k
        if (vertexMaxNum < 0)1 v7 @% d0 C9 e# v
            throw Error("允许的顶点最大数目不能为负!");3 p$ W' z7 u1 n! s- ~
        vexNum = 0;
    9 W; ~7 J7 s" Z4 |: r& S$ \6 w1 \6 D    vexMaxNum = vertexMaxNum;
    . ]# i. y, ]. Y0 j    arcNum = 0;! W8 b' G1 [# H6 }8 H  [
        infinity = infinit;
    / Z8 B- ~% |; k: y+ ^    tag = new int[vexMaxNum];
    0 l) Q/ b9 Y; [% K5 @    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];8 D7 k) b  I6 _. `
    }
    1 @1 @! f. L1 htemplate<class ElemType, class WeightType>
    7 A1 ~. x: f4 {int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const7 B6 p* p# v: T# Q2 t4 R
    {
    2 r( ]  G9 V8 _  `% B0 B7 ^' a1 Z    if (v < 0 || v >= vexNum)
    # _2 S( J0 d" e5 \        throw Error("v不合法!");
    6 U( y: B) T; X7 a# w2 p    if (vexTable[v].firstarc == NULL)
    5 h6 T6 N' z/ `0 Q        return -1;9 g( }0 ~0 M+ ^2 Y3 I) ]
        else, T, n/ h) j$ s
            return vexTable[v].firstarc->adjVex1;: p/ B, D# b% @% k! U0 B# B0 @) A8 x
    }0 x7 T* J7 w1 e6 m8 J
    / F! s+ _! v9 w+ l1 [8 u
    template<class ElemType, class WeightType>
    ; \+ h6 i+ R" f) R. F5 {) Eint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    1 L7 f; V& k: R{+ M9 e) g% N( H. h, A# d
        MultiAdjListNetworkArc<WeightType>* p;
    9 @- p; {2 Z+ v) k2 B    if (v1 < 0 || v1 >= vexNum)- L; ?( I9 g+ H( w
            throw Error("v1不合法!");3 @1 {+ c! V7 K; |5 q4 y
        if (v2 < 0 || v2 >= vexNum)* H) e6 Z. i* J$ Q: n- t( d) k
            throw Error("v2不合法!");; i6 Y9 a' `9 y
        if (v1 == v2)
    / X* Z# f8 F+ C        throw Error("v1不能等于v2!");
    ! T* i- i' s3 J/ _  E2 p# \$ L    p = vexTable[v1].firstarc;$ y" k4 N$ D$ f
        while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)/ \* W2 D6 q8 _& O5 U& M
            p = p->nextarc;# p$ ]+ i* V$ `; C& E+ |% i; K) X
        if (p == NULL || p->nextarc == NULL)8 z# Z0 I- B( d: @
            return -1;  //不存在下一个邻接点6 J& }5 f( y0 P' y' O& ~8 x
        else if(p->adjVex1==v2)$ w, G" N7 N; C; D/ O2 s
            return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    ! @1 A) O9 Q; _& j. S1 _8 y0 G    else
    / d+ I! ?) v2 a' Q' d        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);% y! _1 j5 b2 n' `: _' M! z
    }  @8 {, D: K. X6 f) i8 ^" V
    template<class ElemType, class WeightType>/ A/ N. E9 B) r9 C( k" {3 m
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()
    ! O  [9 w6 A; {2 s{
    # J0 t' ~+ w4 u    if (IsEmpty()) return;
    ) v/ n6 n9 H) u4 Y' B1 N* {    int n = vexNum;& C- L. O2 n8 E
        for (int u = 0; u < n ; u++)/ N  h% [, z/ K8 R. Y. K3 f2 P- a
            DeleteVex(vexTable[0].data);2 o7 c) N$ }4 P& j, z
        return;9 m- Q& K2 Q! a* p
    }
    + D  d& [5 i# S( Ptemplate<class ElemType, class WeightType>
    5 z( t' L4 u- jMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()& f  I* W! c* }' `9 i5 n8 l9 x+ F3 h
    {. o' L  l7 ^3 h: v$ K3 t
        Clear();
    8 `: p, b+ T3 d! S  b}3 ]. @# {- A! S7 u% ^
    template<class ElemType, class WeightType>
    % Q- u$ L8 N' b' J2 q8 JMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    % h4 E. M" Z7 G9 i* t{4 X0 ^( J7 {+ t2 Y( v# `  a
        vexMaxNum = copy.vexMaxNum;
    ) x6 c  E( m' Y$ P/ c    vexNum = copy.vexNum;
    7 D  s5 J% A# J; Z    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    % U: @; P3 U8 T    arcNum = 0;2 E; y8 F9 ]  t3 P  I
        infinity = copy.infinity;. ?7 A: D  ?7 U9 T
        tag = new int[vexMaxNum];
    * ~. s" D: ]  I2 w; ^
    / f+ k& m) z' i9 Y1 D  D    for (int v = 0; v < vexNum; v++)
    6 j7 e: Y0 F! S9 u1 ]/ W4 I    {
    - N; g) k/ L& J, j( t        tag[v] = 0;9 l4 X' {( I. p: p$ Q. D
            vexTable[v].data = copy.vexTable[v].data;
    ' X" g  e4 |7 _- t: `        vexTable[v].firstarc = NULL;+ g* `$ \% l; d$ C5 R$ m
        }2 R4 l% s6 J' k) G& i7 ]4 C
        MultiAdjListNetworkArc<WeightType>* p;/ N7 W4 N9 @4 |2 |5 z5 R
    4 y. B: o7 d( t- {/ i5 Q' h
        for (int u = 0; u < vexNum; u++)6 R! _4 q5 E9 w2 U8 Z
        {- s* x6 H% S2 r& ^) {) y& J8 v$ }
            p = copy.vexTable.firstarc;
    9 T* T# F( w3 L+ e6 Y8 t. O        while (p != NULL)
    9 N( e) i- Y4 H1 F4 D        {4 t# Q6 g( E# {
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    7 {, N- g7 f. t- C5 S% j6 ?            p=NextArc(u,p);
    ) P; y9 J/ w1 `        }# u) P+ |' ?4 P4 }
        }
    ! G' P  U; K2 J7 }2 @}
    ! H/ _! Q5 [% `) A: etemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&5 q' d4 N1 U; R" l7 D& Q
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    0 {4 i" E/ ~  T" \9 C: c' e; M{
    6 \, s# t3 q9 \* I2 p    if (this == &copy) return *this;
    1 k- q: D1 c3 q3 I! \% V6 u    Clear();! r! w. K" g  Z' E+ J6 |
        vexMaxNum = copy.vexMaxNum;
    " o9 T& P9 V" s" c# Y    vexNum = copy.vexNum;
    3 k/ b, e( I/ {% [    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    , N) [1 ?* _7 h6 P2 W/ `    arcNum = 0;8 }* G0 j$ I- U$ t. i5 c
        infinity = copy.infinity;
    & v+ u) {4 `! }8 l    tag = new int[vexMaxNum];: o% r5 x2 |  m+ s
    7 ^2 z' N1 B8 \- R3 j( g6 Q  M
        for (int v = 0; v < vexNum; v++)
    ( J' i, F5 z0 M* ~/ i' h    {
    % `( ^9 I- H4 Q        tag[v] = 0;
    ) w: c, {; z, E( V9 @& s        vexTable[v].data = copy.vexTable[v].data;- W' \- y% s0 ~$ f2 D: n
            vexTable[v].firstarc = NULL;/ p, {5 S4 [' h/ L1 k4 z  ?  f
        }5 \' p( @  p/ ^
        MultiAdjListNetworkArc<WeightType>* p;3 z# T7 r3 a: i+ X) U2 ?; i

    : p+ J3 g  B0 c    for (int u = 0; u < vexNum; u++): K3 w9 B% f8 Y% R( v
        {( ]6 u/ `! v. v" ]* ~
            p = copy.vexTable.firstarc;
    & M2 j! p( P; L) H        while (p != NULL)
    ; y. u& x$ o2 Y        {
    ) r# W# e$ L$ C) a/ W4 a1 d            InsertArc(p->adjVex1, p->adjVex2, p->weight);
    2 o* W; A6 X1 s- X  z9 u. I8 h            p=NextArc(u,p);; E$ o  w7 @- I7 q
            }
    - c1 n) p2 D7 j/ F( `+ B    }- ]3 M6 U8 B$ l' y; A% g
        return *this;4 j- T" s" J5 a. s! V
    }2 D( z5 e# o; u0 l3 v4 k7 m5 v
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    ! o0 A. x% k% P+ }+ X+ ~8 MMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    # u; m+ l* r0 d* K/ z) s# B{
    * `& t% G8 f* L+ o( M. W( c    if(p==NULL) return NULL;! T* ?$ A  \; }( }! P5 d
        if(p->adjVex1==v1)
    $ V0 P4 f3 `/ ?& l/ w% R        return p->nextarc1;% @6 u/ D; E9 ]+ n0 }  u7 s
        else
    5 i8 k8 h0 T* O# z, S        return p->nextarc2;  U; y/ s0 f& l4 f$ Y0 l
    }
    7 y$ Q# s$ c9 H# L  S# Etemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    . W0 E4 T1 c1 ]  w6 LMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    ' u& `# \: @" b5 C" A; z1 }{
    - G2 {1 [$ Z: P7 Q9 m    if(p==NULL)return NULL;8 ]3 y: }/ X* k1 z/ M* k: \
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    3 q! `+ M' r+ ^* c    if(q==p)
    2 V+ G% j/ ?) B  o+ G8 X. a  L& A        return NULL;6 J5 X6 \! w$ h9 R# t6 u( N
        while(q)$ P: `& R, \& h1 b3 E4 T* [
        {
    + |: A, y2 \8 `9 ^% _# s, p7 @        if(q->nextarc1==p ||q->nextarc2==p)
    2 p" W  ~. M  l# o1 P" M4 C; U            break;9 V) I$ H+ Q8 X6 R  [  c; W; b! Q
            q=NextArc(v1,q);% m) e) i, F4 e- o" u! t- N
        }0 Z" I  _2 e- x; I
        return q;
    4 ~$ R. J  J" c  C}
    3 V2 W* c9 z: j6 g& Rtemplate<class ElemType, class WeightType>
    . j* D8 C) K- @5 _5 s9 C/ e& c2 {void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)% k- N! k+ R: s6 M& H+ z
    {7 B  T  T: C6 V7 ]
        if (vexNum == vexMaxNum)
    4 A5 P1 l! c7 l' I        throw Error("图的顶点数不能超过允许的最大数!");
    5 _: ?. Z! E' P    vexTable[vexNum].data = d;
    : Y; e( H$ `# h/ l    vexTable[vexNum].firstarc = NULL;
    . ?1 g/ [# y* D7 F0 J5 f    tag[vexNum] = 0;
    5 v( r8 L( |6 E. H) {    vexNum++;; r/ ~. P2 u' d
    }
    & s0 o6 B+ x( wtemplate<class ElemType, class WeightType>: A5 M1 `! u% V# P; M' U
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
    ; Q1 e) b! T: j& m5 Z{8 Y( _6 U+ F1 s. W" [$ x* i
        MultiAdjListNetworkArc<WeightType>* p,*q;. i) V7 |# l( G6 s4 h
        if (v1 < 0 || v1 >= vexNum)8 K- b( s0 Q+ m9 `+ Q
            throw Error("v1不合法!");  p6 G0 p' ?7 Y% q9 u9 a3 U
        if (v2 < 0 || v2 >= vexNum)
    $ `5 ^2 m3 w4 x: ^6 z' Z& q% q" V        throw Error("v2不合法!");6 P+ r/ |0 L0 s  j
        if (v1 == v2)
    6 A2 V' W1 {& B0 {. Z/ D, M( |        throw Error("v1不能等于v2!");
    , M; j4 v; o) [5 f) V( @! T    if (w == infinity)* ~3 L% C) t- m" K  w  W
            throw Error("w不能为无穷大!");' k4 X1 r) g3 C: T. W9 r1 `

    ' v6 y3 o8 h: K- d5 G  c
    ( J% V5 t, G  d; n9 T& e    p = vexTable[v1].firstarc;6 f  }  x6 C. S  v8 L- O
        while(p)/ v! P0 U- K. }
        {( Z# _: U! J1 w5 l3 h9 b* g3 s9 e
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中- n$ X/ n1 N+ _4 q* I
            {5 N! y* D1 T; t" V3 s: u% y. ^; k
                if(p->weight!=w)
    $ z- u9 [6 r  \# U# ^                p->weight=w;
    $ D1 G" v$ g! ]- Y* I' }/ I            return;
    # `% J! ]0 ^" c# F% I, r6 G        }1 [. ]1 @0 r) |5 @+ M% T$ ~) B
    " K+ r& Q  c! i+ @9 c
            p=NextArc(v1,p);
    - s, Z1 \$ m. @  k  v    }3 e+ \( e5 V( c  g3 ?$ @
        p = vexTable[v1].firstarc;% E0 z5 ^( L! G; _% v, M% Y! t
        q = vexTable[v2].firstarc;
    . R9 K) M' C( L, I    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法- K/ U6 q) W" j2 k2 n' h  R
        vexTable[v2].firstarc =vexTable[v1].firstarc;5 F, M! v1 y1 m( G' g" T
        arcNum++;6 t) U4 j: X; H! e. h
    }$ u- T7 V3 G4 P/ q1 ]
    ) M9 \) h  q# B- G; @! v0 W' P
    template<class ElemType, class WeightType>
    9 J. ~6 v; w2 ]1 Uvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)# ^  y3 }/ b9 f3 Y, J  j5 [1 K
    {5 n0 q; ]0 X+ S' U4 _

    $ X! }- s8 d0 X7 c. [    MultiAdjListNetworkArc<WeightType>* p, * q,*r;) I' i+ ^5 ?6 l0 l* N4 R
        if (v1 < 0 || v1 >= vexNum)  w# \  _$ ~5 y# e* c
            throw Error("v1不合法!");
    + B- T" D: f2 D8 ?) q    if (v2 < 0 || v2 >= vexNum)
    3 C) ]- |$ Q- ?+ ?        throw Error("v2不合法!");/ M9 ~3 D0 J# R+ W0 C+ x9 X; e% q
        if (v1 == v2)
    " I1 S& ]! q; r" U+ g        throw Error("v1不能等于v2!");! {" \3 h7 ^$ b' f0 r- e+ G( {

    ! U; j. g; r7 o2 J    p = vexTable[v1].firstarc;
    % k" j# s- n1 f/ s' \4 X8 a    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)* j/ d5 e, M7 z9 I
        {
    4 k) V6 J! X) C! ^        q = p;" ?6 K0 u- l4 x0 ~, P! J( b
            p = NextArc(v1,p);' Z3 s, \; A6 v9 |3 ~  T3 E" f
        }//找到要删除的边结点p及其前一结点q5 `+ I& D+ T/ c0 s+ y$ b
    % z2 [, f# ]# [3 n+ f9 N* ]9 ?
        if (p != NULL)//找到v1-v2的边
    # e; P% n% R; G    {9 \/ j+ N4 i# p5 G0 X- `3 a  x
            r=LastArc(v2,p);9 ?. L& g1 J/ f
            if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL" \" Y- t! h9 j' u
                if(p->adjVex2==v2)) z$ x2 b6 ~8 @/ L0 Q* r( ]9 U- Y
                    vexTable[v1].firstarc = p->nextarc1;3 i* o' t3 X! ]: y* E2 L9 E% B
                else vexTable[v1].firstarc=p->nextarc2;9 C7 D2 W2 o) z5 X
            else//不是第一条边
    & W7 k+ H( x0 I! p% g        {
    - w( i$ P0 p# K% P4 T            if(q->adjVex1==v1)0 r7 _+ m! ~, d% k, J3 ]% E9 c
                    q->nextarc1 = NextArc(v1,p);
    : X8 z# v! t2 e. `' z" |            else
    0 g5 n' a- H! |7 D) i                q->nextarc2=NextArc(v1,p);
    ' b& u8 L" y- A1 b2 x7 N1 J0 A* Q8 d
            }
    , c1 c" f. g2 s3 \6 {; [        if(r==NULL)  ~8 I* w( h' h5 e: O
                if(p->adjVex2==v2)
    , o  p; o$ b6 a, H* u* N) p                vexTable[v2].firstarc = p->nextarc2;0 r. H( S" |1 m7 t* [
                else vexTable[v2].firstarc=p->nextarc1;
    2 f+ {0 f, f7 ?# R# a- @        else/ n1 z& h4 D' k9 r, b+ k- c% {
            {
    ; J/ |- W0 U4 z) }, ~6 c            if(r->adjVex2==v2)2 e0 X" d3 j2 x+ P
                    r->nextarc2 = NextArc(v2,p);, q% p( q. V7 q* Y# G9 |, y
                else7 Z' H" H* g: Q" g( a
                    r->nextarc1=NextArc(v2,p);0 m) K( W2 m. q0 A
            }0 T. A' _+ P' T& j+ O
            delete p;6 o! C) U5 ~" @( n0 Z
            arcNum--;  w5 v2 {+ z: x; Z8 j2 h3 }
        }+ V+ f" Y( u# y  u; P, x" \1 x! @

    , v7 W/ D1 r' T( {}9 Q; K% Z" f# |) ?
    template<class ElemType, class WeightType> void. |7 L" U0 D- J3 p6 Q6 V
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    2 O# ~( q& u  l! U! P4 H{
    & O6 J7 [( q( V* A" I/ _    int v;0 n+ b5 j" }; n0 a/ ~! e% h
        MultiAdjListNetworkArc<WeightType>* p;
    , z: l4 g5 Q* i; @" d    for (v = 0; v < vexNum; v++)//找到d对应顶点# l% t$ S, Q9 G( n* w9 {$ t; u
            if (vexTable[v].data == d)( |' p9 j3 u2 e6 e- [* p
                break;
    " c: p: z1 C. Z) t    if(v==vexNum)
    ; m4 e9 c/ s( @, C) n        throw Error("图中不存在要删除的顶点!");
    0 S3 N7 M9 _0 M# c, V& C) p5 v/ ]
        for (int u = 0; u < vexNum; u++)//删除与d相连的边
    9 }8 t% _% y5 N" A( j4 }- [6 F        if (u != v)
    ; E5 V- W, e7 B5 Q: e        {2 o* p( t, {; s* v% l6 b3 M
                DeleteArc(u, v);/ |( s1 `) h! p4 l8 L6 o
            }
    9 V% u& Q- d$ c0 q) m# [    vexTable[v].firstarc=NULL;
    : {' |8 `% q: }4 I$ ]$ L  v# j2 i0 U" i- u$ [
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置  b) K. \. Y5 J" j+ ~. l2 Z
        vexTable[v].data = vexTable[vexNum].data;; O! B+ K+ Y  g! S" x7 f! x
        vexTable[v].firstarc = vexTable[vexNum].firstarc;
    / ?9 K+ \' P. ~! r* ]    vexTable[vexNum].firstarc = NULL;( |& ]& e1 e1 D3 O8 R9 k' Z
        tag[v] = tag[vexNum];
    : R. S6 D& {' v) B) h    //原来与最后一个顶点相连的边改为与v相连; {* b4 K8 N. o  ]- f3 R: ~
        for (int u = 0; u < vexNum; u++)) d' s# J' `9 @& y0 j" o& e1 |# m
        {4 y: ]* r; ]% I8 I
            if (u != v)4 P& R6 A2 K1 K5 `; E7 P+ F$ I% ?
            {
    ( j0 }, s% ]# @            p = vexTable.firstarc;6 v. E" G/ p  d
                while (p)7 w! S, f( r, d8 C* P
                {7 B0 \8 G  O* L4 O( R
                    if (p->adjVex1==vexNum)2 r1 T4 H$ F( s. Q  I! Z/ ~
                        p->adjVex1= v;5 \8 w( D# J2 l$ H7 F3 O; ]6 l
                    else if(p->adjVex2==vexNum)
    ) l  m( s5 V' X% `# }% R                    p->adjVex2=v;
    4 l+ W* l: M  f) n" s8 z                p = NextArc(u,p);; g9 p; N) I5 G3 ]  G
                }
    $ x# O; A" k3 I4 [0 \  i        }
    % \; [/ f8 G! [0 S. K2 H    }
    - w; c9 U, q$ N# h" @& @8 ^}
    2 ]( `+ I- F0 G0 W: n8 P///深度优先遍历
    5 T2 p- j/ }! D% G3 Ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    7 \. d" W# Y2 r) {8 l* v1 l{' T+ W, V2 a# r: p; b) Q9 }: _
        tag[v]=1;( g% T( W7 v: ^0 B
        cout<<setw(3)<<vexTable[v].data;
    4 t- q( m# a0 w3 h; c    MultiAdjListNetworkArc<WeightType> *p;- n* h/ K$ d( U
        p=vexTable[v].firstarc;& b3 I4 F/ A6 f9 ^' h% E% d
        while(p)
    * |# ]- F) J/ j" t: p4 H7 |) [    {3 b* u: G" m, |' g8 W6 K
            if(tag[p->adjVex1]==0)5 S7 F7 H8 h! v. y/ `# A4 S; b
                DFS1(p->adjVex1);
    1 X4 K! n+ L6 O% b$ H6 U        else if(tag[p->adjVex2]==0). F, a& R* ?; _, i2 P) m$ Q
                DFS1(p->adjVex2);
    4 g# e: n7 f: B  ~        p=NextArc(v,p);/ Y% q2 k- d' ?! F4 x( l9 E; U9 P+ J( R
        }
    , }6 u3 }, i' E& Y}* i/ A2 e( n+ `6 V0 w. F, `% X1 B
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()4 }  W5 ~, v; W( ?/ `" ~
    {
    , j, M7 d) ?6 G/ ~/ L- {, ~    for(int i=0; i<vexNum; i++)
    - F2 F/ G5 T" B' _6 \9 g        tag=0;
    6 t9 V+ h7 q2 ~$ ^, X    for(int v=0; v<vexNum; v++)8 U1 e# E; V& ]* p% s. A4 E7 d3 T
        {
    + w: \1 O9 J  [4 N: l        if(tag[v]==0)
    / b' n  P6 S$ B) v! X$ m5 `# m' ^            DFS1(v);  @% W& l1 s! [* Q' u! R+ p7 u
        }( D  E6 s( h7 f0 |
    }0 f4 e! e- V) z0 ]5 @
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()+ V( X/ F8 ?, h  J, t
    {( s' Z- [4 J. r
        stack<int> s;
    ; h( y9 W: H' F; H+ l1 N    int tmp;- @$ A# t4 T5 E5 P; j
        MultiAdjListNetworkArc<WeightType> *p,*q;4 [0 b0 e4 C1 }4 W+ e9 M$ `8 m+ M
        for(int i=0; i<vexNum; i++)
    : a$ {, }4 k" s( @# L        tag=0;/ t# X0 @5 T8 {5 H" D* O
        for(int i=0; i<vexNum; i++)
    . U6 `! O. A* i5 o    {& p) l9 J& k$ `8 d) O, C: y  i; I; W
            tmp=i;+ D  }$ F, ^6 U! @
            while(tag[tmp]==0||!s.empty())
    / A, [) N" L7 t. V& J        {
    1 N7 s! R+ S9 j) q0 H# J3 U            p=vexTable[tmp].firstarc;
    & x2 V0 y, J7 }4 @4 g- v  G4 b( x            while(tag[tmp]==0)
    7 ?1 B& l9 R+ d$ Q& l! `            {; x0 Q! U# d8 L/ ^! y
                    s.push(tmp);, i! }0 a0 m( y5 R8 r# U
                    cout<<setw(3)<<vexTable[tmp].data;
    6 Q( q1 ]+ }- m: P6 a                tag[tmp]=1;
    $ l9 \8 @6 r& J, d8 T+ ~                p=vexTable[tmp].firstarc;
    1 p+ `  h$ [# i$ j" o                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for: M; U' J$ E# y+ x0 A2 M
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    9 T/ {: {; R; P+ h                //cout<<" 1st     tmp="<<tmp<<endl;" d8 S% @" ]9 ^( D
                }$ B. Q. @6 G9 d3 l) `" |
                if(!s.empty())
      b4 p  M+ q* a1 G4 C, m            {
    4 @+ d$ V' N* X1 \0 D1 M# E7 `; N                tmp=s.top();* M; u  X$ W! r; k
                    s.pop();
    8 r( e6 S' t5 F( N3 [. X. ^7 S5 y                q=vexTable[tmp].firstarc;
    0 A& W+ T: d; q' R                int t=tmp;" s+ A9 Q6 {! @
                    while(q&&tag[tmp]!=0)
    ; j# u) g5 j' s8 x4 G) P+ N) G9 T- N                {
    2 Y3 ~$ E& H- _; r+ A  X# G                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);, E6 Q0 z- X* B/ Q( ]3 j7 l
                        //cout<<" 2nd     tmp="<<tmp<<endl;
    # a8 _8 k/ F9 R+ G6 K$ D2 b                    q=NextArc(t,q);# J4 y' `4 K% p9 c2 Z
                    }
    9 f4 u* Y5 |/ O2 m$ L' j4 M0 Q                if(tag[tmp]==0)
    0 w7 V+ _4 z, c                    s.push(t);0 c: l' B, v& |
                    ///1、对应上面连通分支只有1个点的情况
    1 u5 ^1 L( L* a                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈! o  ]# h; I9 U
                    ///tmp要么等于找到的第一个未访问节点,
    , r: \7 m+ B+ C5 Y% r                ///要么等于与t相连最后一个点(已被访问过)
    , c7 o8 F3 C' b) d/ u                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    ' M& k! B  x% |. l            }
    9 v( D! O0 A0 S( }9 n1 n8 ]        }
    . A. _: {" l' z3 D+ `% f) \    }
    + H8 W& D6 C0 ~8 i9 t% s}* ~9 U  t' [. I
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-10 a1 c( |4 p" k4 d
    template<class ElemType, class WeightType> int
    . m* t2 M' |" B6 N8 W0 P" xMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
    0 }5 w& L" q- C0 x. Q: b+ X{, H& ?, r/ S7 \4 Z; T* K5 L9 `
        if(head==pre)
      v* L6 u$ a4 j; ?        return -1;
    & w9 V2 e% }8 O# I' g  n) {' s# B- J3 N! L6 v# l5 Y
        MultiAdjListNetworkArc<WeightType> *p;( Q5 Q5 F: E( q) i: E7 Z
        p=vexTable[head].firstarc;) I9 w' j* N  d. d8 ]7 A; A; E; N0 o, z
        if(pre==-1&&p!=NULL)
    3 r: a4 Z* i9 g7 ?& J9 k0 @        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    ( x) ~' {" L$ s, M! D    //pre!=-1&&p!=NULL0 D1 g* `/ [* J
        while(p!=NULL)
    3 K/ ]9 ?! i3 v  S# s    {
    $ J+ v0 s* P, X: h' G8 v8 ~$ T        if(p->adjVex1==head && p->adjVex2!=pre)
    2 k6 b3 |4 w5 N4 L: N            p=p->nextarc1;
    ) [8 m2 u( n3 x; ~3 z7 {        else if(p->adjVex2==head && p->adjVex1!=pre)
    5 c8 ], i$ U; Y8 I: F4 S            p=p->nextarc2;. ^, t5 f; a" K- e! u
            else if(p->adjVex1==head && p->adjVex2==pre)4 f/ C+ _5 L5 r* c4 S* c
            {
    # s# ], |2 O& J( ^. @5 Y0 A# M5 v3 s            p=p->nextarc1;( L0 C1 u$ u: \
                break;
    5 q& I9 T2 E: w        }
    $ M8 L  ^8 x6 e4 j# }        else if(p->adjVex2==head && p->adjVex1==pre): [- h( {% ^* ]
            {
    2 `% O, }5 E' n            p=p->nextarc2;
    ' q; o: q# r8 y7 Z" @            break;
      Q6 s/ I" U  J' J        }2 M) J5 O, E9 }! y8 a
        }! i; X# U& t. N2 p0 O
        if(p!=NULL)! K& I# L1 |$ X% A* F
        {
    4 k! C3 F$ @1 m& p        return p->adjVex1==head?p->adjVex2:p->adjVex1;. `4 C3 I* b! G, l- \5 a0 x& m
        }
    % q, ?% d" {/ K' J- E7 ?    else5 W* `! N" m5 X, k1 Z8 z( h6 G
            return -1;: |6 N7 r) \/ v( j
    }/ e# B7 l  S5 ]0 W/ Y. l

    4 W7 b# s& w: {% B; L! q$ w7 V* c+ i) H( F# m. Z
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    9 w2 V8 U- m# \0 l# T! F; s{5 h5 b$ s3 Y  z; V3 K
        stack<int> s;
    8 W4 V( r/ {- U! D: Q    int p,cur,pre;7 T" {9 C7 X% Q! x0 X  Y) z1 ~+ l3 o
        //MultiAdjListNetworkArc<WeightType> *p,*q;
    $ z6 E- R: b) S9 f5 U/ P0 u4 x    for(int i=0; i<vexNum; i++) tag=0;//初始化
    ' H! J1 F0 ~" f3 R- p  o; Y1 f5 |' K# K1 s: {# n
        for(int i=0; i<vexNum; i++)
    * p' F( O7 B9 O& d& Y    {* ~: l0 _: ~: O. D' `
            cur=i;pre=-1;( G5 f: v1 H- g& q2 t1 V
            while(tag[cur]==0||!s.empty()). c" V/ e1 u0 {8 |# K
            {, d; G/ G( H: G9 C. U0 V* \
                while(tag[cur]==0)
    : J' V" i# B4 g            {
    % l+ @1 ?$ ^; ]5 v. _& D                cout<<vexTable[cur].data<<"  ";
    , R, s4 i: F& ?& K' B) h5 b                s.push(cur);3 Q+ ?/ G4 b9 P! ^
                    tag[cur]=1;
    1 x& P4 V$ q4 E$ ], s. y               //初次访问,标记入栈
    8 W* }0 U- t4 A( a; _- Q0 M* ]. ~* t1 M7 R
                   p=GetAdjVex(cur,pre);//p是cur的连通顶点# v; ]) q  z8 m6 V5 F( K
                   if(p==-1). w( L9 H+ {+ `1 R5 y' J1 l
                   {$ j: Y" ^8 `% P: k; p: |: O3 o
                       pre=cur;s.pop();2 h) ]& H! ~% z2 w) Q+ @% w" i
                       break;! x5 y, G5 \9 l4 ?5 G, b0 P
                   }
    # K3 M( \: @, \5 m4 j( h! C               else% J: Y' |3 R6 G0 U. C
                   {& ]3 c; L. k! y
                       pre=cur;
    8 v/ d2 o4 P+ y+ Y; A                   cur=p;- P/ S- c# ~$ y; p4 X2 C
                   }/ H' _5 K, a9 k9 [0 c' _. N) E

    : B  t7 k+ m! p2 S! v            }% S+ \/ e+ w" s$ k3 P% \
                while(!s.empty())
    4 {9 F: M  X. K0 q            {! t, x: x; P# n" g$ \4 R5 d; R0 O
                    cur=s.top();
    , D5 n, N: f9 R                p=GetAdjVex(cur,pre);& B2 C7 l  x7 a( W
                    if(tag[p]==0)
    $ a4 m, |1 p0 R6 c4 u                {
    ) [$ C4 n3 J% j2 e8 l                    pre=cur;+ J7 f, Z  M1 j$ h$ @
                        cur=p;. `6 Z& \+ }1 J
                        break;
    ' t7 t+ w4 w; D! }3 V                }
    8 {) N5 f+ ^8 p4 i! a3 _: t                else
    " f+ a* S& A. \) p- g) G$ W' ]                {
    ) J* z3 i' d7 ~3 P$ _. ]                    pre=s.top();3 m( H! ~8 I2 V$ H5 C' h4 e. C
                        s.pop();
    . O# ]  l7 U' U# _1 X% K) O                }
    , ~8 U" e- X$ k0 g: o% I3 v2 k2 p7 `' w1 _, c+ ^4 ?% U
                }  g' U6 I3 W* @* A

    . S4 r5 {( I: h+ V) o; N        }
    0 J% f: k7 c6 o9 C4 a( }    }$ G" p  a( r" z6 `# w
    }
    0 h" {/ p1 w& g) Y- [" |template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()5 X; ^2 Z8 `7 O2 t. i+ b2 L
    {, \  B) R8 F3 h! J+ X; b/ M9 {
        for(int i=0; i<vexNum; i++)0 B5 n5 d5 B# z
            tag=0;) b9 A4 q5 |, {: A5 b7 {
        queue<int> q;
    5 u' E. Z! O7 g; W  @    int tmp,t;2 ]- u3 h( ]- h( y1 _& z
        MultiAdjListNetworkArc<WeightType> *p;
    , m% R- k% y: h5 F' d% j    for(int i=0; i<vexNum; i++)
    : J' d7 h& I. A. E( t    {
    + w$ J' ]8 S0 t3 M$ h4 r        if(tag==0)4 u, z& G0 Y2 e- L3 \! m
            {
    ' ]$ C' {( d7 ^. ?            tag=1;
    1 k$ q; g) {& C5 c            q.push(i);% l" ]% P: W/ m  {
                cout<<setw(3)<<vexTable.data;
    3 D4 ]( K" i8 ]4 F/ |; ?# ]: ?        }
    ) @' M1 b* f" x3 b2 A+ @6 W        while(!q.empty())
    ; Z! W. B) I, F1 G+ O8 w% [5 B7 }        {' U$ }4 T3 I+ ?0 B4 O' I
                tmp=q.front();; K: @9 \2 a2 H7 I3 e9 l
                q.pop();
    6 y) G, t: P4 |0 b# _+ ^            p=vexTable[tmp].firstarc;
    # Q6 I2 W. b0 C5 o            while(p!=NULL): y9 B2 B" X7 H5 v8 w  z
                {
    - ?" ?1 U: y* s( v: ]2 K. \8 F                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    ; T  S  o+ C, Q: H- I) P0 d* ^                if(tag[t]==0)1 f! n$ L9 s# \( Y9 x! k
                    {
    9 U: ], R( s/ K. ^) G& l                    cout<<setw(3)<<vexTable[t].data;
    " v  _. V. M- r0 @/ x" j% o" Q. N                    tag[t]=1;
    / p) J5 B, \& z  W& f( N                    q.push(t);
    - y0 q- _+ G! w/ @                }
    ( I; G, i- \6 m0 g4 V0 t                p=NextArc(tmp,p);2 u, j3 P# {7 y( I" I4 z: t; f% X
                }
    ' P' m" m* W$ p0 w0 Y) Y        }
    & `9 H0 \! v2 ~1 i, R    }8 ^2 E; \0 ~8 W  ^# U1 c6 a  ^
    }4 F& F9 V" r% b& D
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()' }- n, o4 ^3 [
    {
    , V  V( ^0 U, T5 A! m$ O( J    MultiAdjListNetworkArc<WeightType> *p;. |4 d8 G" y( p9 h/ w) {" M
        cout << "无向图有" << vexNum << "个点,分别为:";
    0 H3 j" o. v" e& Q( Q) p    for (int i = 0; i < vexNum; i++)
    " {9 \+ Z# W7 v2 S+ l/ N        cout << vexTable.data << " ";
    3 T( B: [7 \1 y4 V& }8 U$ ^0 d    cout << endl;
    # {6 I$ o  V! y2 a7 [- X0 a6 C    cout << "无向图有" << arcNum << "条边"<<endl;
    3 s! @, d4 z1 G8 y( ~) G! i    for (int i = 0; i < vexNum; i++)2 {. S/ D8 B" C* K
        {" \( }0 r, |. B
            cout<<"和" << vexTable.data << "有关的边:";
    7 D, C8 I6 w( r5 A5 o' a9 k$ r        p = vexTable.firstarc;4 _# H. S/ h& X3 o3 S
            while (p != NULL)4 L- O: z) `+ o  \8 I% |2 ~' [) y
            {, q# R: Z4 ^3 O% k
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
    1 v/ ^' A' c+ D7 ]# ~1 u            p=NextArc(i,p);3 B: F( d# C/ Y2 @/ e8 }$ G. N, Q
            }
    ( J: s+ _4 D7 |        cout << endl;+ y+ q1 t- q. r: c! D
        }
    - v2 R: ^1 A  a0 L2 ^/ q5 e3 i. L}
    , \. k. p! c3 r( _& ]* u2 \  Z3 K  L) d  [
    ( S! n( b( F% l, |6 d
    邻接多重表与邻接表的对比
    + s/ A  \4 i$ Q' M
    + U3 Q$ F0 t2 n7 }; _邻接表链接) W3 X9 q3 m# Q, F
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
    " m$ v& \  u! b% ]) ]在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    3 c3 T' J3 |* y- h& n为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    4 d7 v# W' S5 r: Y3 {# u————————————————
    ' _% t9 {1 i1 D; y* @版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。# A/ X& v, F& g
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    8 x8 i: u0 Z0 _$ l+ W; }9 L. O' p( ^% Y% {; f& A  x
    8 r4 }8 Q  j6 ], ?* Q" f
    : u# ~2 i$ J4 M
    1 i* K$ d* E$ n0 }: `" b' u. t
    ————————————————- U: D9 h' ^$ W/ l- q8 ^
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。4 V2 H: A% `2 f6 s2 e0 _
    原文链接:https://blog.csdn.net/qq_43413403/article/details/1057669581 N* H' t, n9 h  Q9 |5 F

    ! d. G/ ~, C  r0 K! I8 |
    3 l- k8 v+ q7 T* O4 P! M
    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, 2026-1-16 05:18 , Processed in 2.325851 second(s), 54 queries .

    回顶部