请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 840|回复: 0

图的存储结构——邻接多重表(多重邻接表)的实现

[复制链接]
字体大小: 正常 放大
杨利霞        

5250

主题

81

听众

16万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    发表于 2020-4-26 15:26 |显示全部楼层
    |招呼Ta 关注Ta

    9 |/ ]0 [  F7 J* f图的存储结构——邻接多重表(多重邻接表)的实现
    5 [) F6 j: q5 Y7 R% E7.2 图的存储结构
    7 u, Q; {, i+ e; E- ?1 s# j! ]! p( c
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist$ T$ l7 A& Y  d
    邻接多重表的类定义7 y( w3 X( Z7 j; l
    邻接多重表的顶点结点类模板
    4 T  S0 e- `1 W5 E. J. }% X邻接多重表的边结点类模板3 l& ?, U7 x, Z% v  f* B- ^# o
    邻接多重表的类模板% U' A5 |$ ]2 R5 t1 c
    邻接多重表与邻接表的对比  {4 `) V- W2 d  G- \3 c0 N
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist0 `, q9 ^6 d: S$ K$ N) I3 \

    3 a5 b. g6 R5 T6 m6 `& g: V在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。
    ! c$ m8 U) l$ d$ _: ~在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    5 _+ d$ e: V) k7 _% Z( E% `+ t8 K0 s. q* f4 w1 J1 i
    邻接多重表的类定义' O+ W* {2 }4 A
    1.png

    4 u1 N" \, ~' a邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:% G$ F0 c" g. U1 _1 G* F8 P
    data域存储有关顶点的信息;
      K8 z) O+ d9 h+ b. G  Q6 ]firstarc域是链接指针,指向第一条依附于该顶点的边。2 p7 d' r: e: V5 Y- k3 O( V; q
    所有的顶点结点组成一个顺序表。

    6 Q" t& y. ^8 Y; y" U3 F' g
    4 i- r* C1 Q- s4 _2 t6 v) D
    template <class ElemType ,class WeightType># S7 s4 s# m  L0 B  h
    class MultiAdjListNetworkVex- w# t. \" k$ b$ s+ {
    {2 V2 r; ^7 z6 T+ X& ^3 |+ _/ z
    public:% {' j# z& f' e0 p& G  E- p% r9 C- ?
            ElemType data;  T) ]. A( j0 i- _+ m* y2 M2 y
            MultiAdjListNetworkArc<WeightType> *firstarc;5 M2 Q4 M5 f; V- U+ N: F

    6 X% N4 ]- Y* x" o) N2 |        MultiAdjListNetworkVex()5 Z& A  N; }* J$ i( J
            {
    0 x, k1 @5 h8 n" c                firstarc = NULL;
    . H: S7 @# c" u% E1 V& [* Y( E        }" W5 W! R) d+ I5 V
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
    ' G5 ]8 T: x" }+ A7 N7 r7 |+ k. @        {9 w$ f& N5 K( l" l4 x
                    data = val;
    ! r9 S: z; s# P6 j                firstarc = adj;
    1 y8 ~) v  U( @7 I/ E        }$ [0 R4 I# r4 J1 v6 i4 V
    };
    + }- O0 i; l8 t+ j& B7 n, A( @. w1 l, o9 e) ^  |; u) X; U, E5 K0 K8 y6 X
    邻接多重表的边结点类模板
    3 m8 y$ H- u4 x
    7 I8 |5 i2 |# D, v) A, Q在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    ) l$ b% P4 W7 M* d- utag是标记域,标记该边是否被处理或被搜索过;
    4 {) O! c) X9 ?' T, T4 Eweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    : {% A! u" [* i4 _6 \- Tnextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;- P  e$ r) Z7 j* W
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
    9 G- Y6 T  L3 h5 {8 y5 C  u% s3 ?& J: v
    2.png

    & d, x8 v" \% M+ F4 g" Btemplate <class WeightType>
    ! w" F/ ?, r/ o) c( s- H8 k" G$ Qclass MultiAdjListNetworkArc8 o5 Z7 H4 I7 h/ X# S
    {
      F6 S  n! s3 h" M- v/ Q7 M' r1 vpublic:
    . F; N: r) o. R! Y5 N5 A    int mark;                                       //标记该边是否被搜索或处理过: g3 }! R  \8 L& f# d
            WeightType weight;                              //边的权重
    ; x- ?" \' @7 |; L        int adjVex1;                                    //边的一个顶点* O% i0 J) B0 u- R
            MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-13 f$ Y  G% s# p  a7 S; c
            int adjVex2;' j. v6 B' ?6 h% S
            MultiAdjListNetworkArc<WeightType>* nextarc2;
    - c" Q* B1 K' n" T- g! V
    4 z4 Q# Y. e6 W        MultiAdjListNetworkArc()
    6 ]. Q" r9 ^9 M        {  x$ o0 R, A% X: t7 M2 C: V# g
                    adjVex1= -1;
    7 X( p" a* u) ^, Z                adjVex2= -1;
    * o0 y( Y" O: M( k! y6 T        }6 A) H7 A& ^: v( N7 |* m
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)$ G( B7 E" B& v8 ^9 k. G
            {9 g) C5 {5 V/ J4 l1 }
                    adjVex1 = v1;       adjVex2 = v2;
    & c- S+ U6 ~( T" {. @$ O: z                weight = w;5 e# R* F  [9 a+ D
                    nextarc1 = next1;   nextarc2=next2;( j8 F! F7 G. S4 j6 N- E+ I" j
                    mark = 0;           //0表示未被搜索,1表示被搜索过& A' W6 {8 k( d* d, g# X
            }9 W  ~4 D( H2 I8 O: G- }- ?" f

    . ?/ s( y% D. H邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>2 P8 [8 p. }: P/ n5 B" q  _
    class MultiAdjListNetwork$ D; L6 f) O/ n" P
    {2 M* B! M- ?; d0 u+ x
    protected:! V, V/ d! l: |$ A5 p* l
        int vexNum, vexMaxNum, arcNum;
    & @& b# V( q$ h7 v% T* u    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    5 Y( K* n  M: Q. H- f: I    int* tag;
    7 h8 _* U; u0 b2 h) {) e    WeightType infinity;# ]: Y, ]% l) ~* ^% b, s  v- W% R5 l
    - `$ \4 ^4 x$ V1 }
    public:% g) R/ ]3 A5 m8 s6 y. I& C
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    : b  D7 ?3 Z: l2 M' e
    & o) H* {8 p% K% J/ q& n' p    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    9 r$ E2 T% }. x: Z) U5 Y. E, ]5 A) ]
        void Clear();
    % k8 `. j* S8 @0 r9 P    bool IsEmpty()
    : e, N" m% Z+ g- H4 Y$ w# y    {' _" M8 @, z% g: K# Z
            return vexNum == 0;  e4 i: i$ g' P
        }( f$ b/ S4 @1 J" P! A
        int GetArcNum()const3 r8 V. W2 `1 ]0 d
        {
    , T: Z' @3 X4 F7 ^2 t7 ~        return arcNum;
    ( B( s. E* {, y& m  k: P9 Q    }
    : @" r, @7 x" m; z/ }    int GetvexNum()const
    3 L% ^* j4 {. ]4 m    {
    8 S$ t. G3 k$ X% o4 ^        return vexNum;* ]0 _( S9 h; x+ |
        }  h) M1 {4 {8 `0 _! R
    4 f( U" @& _# Z6 r, b8 Y! w
    + @1 E( R" {: ?- A3 X
        int FirstAdjVex(int v)const;
    ; w. J, P8 }7 X" U* e    int NextAdjVex(int v1, int v2)const;
    % I. [- X' t, a* U) i+ \# ^2 e7 v    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;( Y5 F# w/ T6 Y5 Z
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    . X* U/ g: A0 x- |) b
    , M8 }" e2 C) n& l! L. O- s    void InsertVex(const ElemType& d);' U9 @6 [% i' h8 G4 {
        void InsertArc(int v1, int v2, WeightType w);4 ?! m- G9 `" Z* s  X

    5 q+ B  b% |$ s2 W$ u' j+ X- ^    void DeleteVex(const ElemType& d);( j% _& `% x; e# J! c! K( q
        void DeleteArc(int v1, int v2);
    . r9 V+ B) n  |5 z& S( ]7 z+ g6 `' b. G# K
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    ' M2 h4 r* H. }8 \# c8 B    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);4 e) ]- j# K/ p. [7 @9 ~- H0 ~6 {

    4 P8 ?1 h& ~# D2 @! H, ?) F/ v* v    ///深度优先遍历1 O2 ], e  I# t4 n% ~, X6 s
        void DFS1(const int v);
    & D2 g4 b' d+ O/ @/ y2 p    void DFS1Traverse();+ J$ S9 j$ j& J( u8 V
        void DFS2();. x5 U& B( q1 n9 h* ~
    ( j& \1 x' d  @/ L0 b$ ?
        int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
      |0 t% A- f! c" F2 @    void DFS3();
    - k$ O9 \: |/ f. S* Y* I' i
    8 d; q$ {0 ?. ~6 R3 G3 Z# w1 K: q    void BFS();
    # u8 t- Y* h& k    void Show();
    ' @0 z4 E5 U7 c% Q5 p};
    " z2 d" n. d* a' B! V1 |) M0 A0 j9 s  {( B& o
    2.函数的实现
    ! [& p: B" T9 a研讨题,能够运行,但是代码不一定是最优的。+ p) `) c/ ^$ v  S2 f

    1 [( M  {$ g0 ]9 W, L/ L5 v; A' U#include <stack>
    ' `9 Q- U- o. _: [' h#include <queue>
      {# _& B- l% m7 Z" d! @. Q* O: W& c0 x
    template <class ElemType,class WeightType>
    / v1 A1 g4 ?5 A1 AMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)- R( i4 t! `  y) T4 }* h5 z' a
    {2 f) a4 u& H1 b! Q2 z2 S7 ^7 o
        if(vertexMaxNum < 0)
    " _" A! o/ ]" a0 y2 \        throw Error("允许的顶点最大数目不能为负!");
    $ ?' ?* P. n+ q' A6 f. M. u0 O    if (vertexMaxNum < vertexNum)3 }4 x3 W1 [3 m' \9 w" _
            throw Error("顶点数目不能大于允许的顶点最大数目!");
    , A6 k! i4 f0 n! ?3 R    vexNum = vertexNum;9 U4 _5 l# F3 g- w) I3 q. d9 O
        vexMaxNum = vertexMaxNum;  t2 K) b# J6 A( w3 [* E( _, f0 t6 X
        arcNum = 0;
    # k, w2 [  f4 _* P, I! J) \    infinity = infinit;8 t3 \" y0 y$ Z' N
        tag = new int[vexMaxNum];2 k* l- ?  C- d  i# d9 v
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];" ?/ h) J+ F+ \' D0 ~) n0 ~2 e  ~
        for (int v = 0; v < vexNum; v++)
    : W& t7 c+ k# \    {
    2 \! d8 w1 q* N* _5 g& x, t        tag[v] = 0;
    8 U) D' v$ _$ v. z' g        vexTable[v].data = es[v];& I# {+ P" Z$ Y0 M; s& _
            vexTable[v].firstarc = NULL;
    3 |6 a/ K& X8 f    }2 b" x9 H$ `  @+ p
    }- N( N! r9 L" ?, p2 N: @
    template <class ElemType,class WeightType>7 X8 k. f$ ]. J8 i
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    * T/ D) @# z* _5 k{
    1 `2 V* `  |% B/ Y6 L$ O    if (vertexMaxNum < 0)
    6 A- r1 ~0 L, V1 L1 @        throw Error("允许的顶点最大数目不能为负!");
    6 T8 M$ s% `9 f3 D) [7 d    vexNum = 0;
    ) B1 c9 O/ X! v5 t, P6 v    vexMaxNum = vertexMaxNum;/ Y& R- s4 O) d" b  [& E
        arcNum = 0;, x! b% s3 ^4 _, I4 b
        infinity = infinit;3 ]  r/ R& x. _* v+ C" T
        tag = new int[vexMaxNum];. K( R& H6 t; n  T# J' q" t0 H, v! T
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    5 I" g- k0 _. F1 l; Q. F}9 `# L' Q% R/ Q' `) p6 k
    template<class ElemType, class WeightType>
    2 ^) {9 Q* w2 a4 zint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    1 i1 Y5 y5 ^+ z: D9 u; Q$ L7 M{! w. c  Z( E: ^5 `4 p
        if (v < 0 || v >= vexNum). \& d# G' E5 Z. t4 k) N$ A
            throw Error("v不合法!");6 D$ D8 E8 E$ i9 H3 M; G) b
        if (vexTable[v].firstarc == NULL)/ X7 K6 ~$ w# I5 j5 s0 W9 S
            return -1;: D" r# N2 H  O) T
        else7 f/ q# k- p! M- G
            return vexTable[v].firstarc->adjVex1;( T! ?/ [% L" N3 x5 h6 g- s! i
    }
    6 @. d: T8 z* n- v; c5 H! j3 F+ p- ^1 P+ P- I
    template<class ElemType, class WeightType>
    ' P6 ?3 z7 e0 j4 h$ m; sint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const+ K5 K1 X+ V4 e# j3 T
    {; w) U, V& ^0 N9 Z" s3 G2 v# O
        MultiAdjListNetworkArc<WeightType>* p;/ m/ D5 i# V3 S% T( e1 u
        if (v1 < 0 || v1 >= vexNum). i7 o9 R9 q& j) r% C
            throw Error("v1不合法!");
    : l9 C( e% T/ O5 t# E$ y0 @* j    if (v2 < 0 || v2 >= vexNum)
    5 Y/ K3 K2 N' D4 n' Q# C        throw Error("v2不合法!");
    $ P" b) X( A. J7 W7 J    if (v1 == v2)! z6 g! o  @) R2 \
            throw Error("v1不能等于v2!");% }- K. e! \1 G( H
        p = vexTable[v1].firstarc;
    0 b( H, i( l) b$ w" E+ |  n    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
    3 [6 A; n2 h% W2 k+ A9 d9 s2 O        p = p->nextarc;% l. }) O6 w; r" F8 ]  b$ ]- v
        if (p == NULL || p->nextarc == NULL); P1 M; p+ ?: l
            return -1;  //不存在下一个邻接点
    # C6 @1 k4 @9 n# Q1 R+ B2 k    else if(p->adjVex1==v2)
    % J/ J7 N( I  Z        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    ! f' U) a7 t& ~    else3 J' O  t5 ~2 p( ?- F# }
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);- b; V/ a: F6 `9 z6 `) {
    }
    0 j  }' Q# k2 K, Y" @1 m' Btemplate<class ElemType, class WeightType>( I- ]+ r) q& N6 E
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()& y+ M% L& e. ]! |# W# N6 ]
    {
    8 I2 u9 A2 e  t$ _$ z3 q" u; v# @    if (IsEmpty()) return;
    3 p, S9 w% ^# E) u/ h; i0 W  S& {    int n = vexNum;
    ' _' a  |6 v+ T; J2 b! g4 E2 V    for (int u = 0; u < n ; u++)0 W5 `+ w8 y/ \0 r
            DeleteVex(vexTable[0].data);0 v. f6 S: T7 L+ b
        return;
    / `1 {* @5 U- c* j! k; B0 G* L7 b  Q. P}
    6 J  E. O; ?4 E. Y. H0 a, t4 dtemplate<class ElemType, class WeightType>
    8 I1 d, d! b5 x' j8 H7 ^0 {MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()7 z- {4 X: k- l9 [8 `5 f- O
    {
    7 O0 i7 n+ E4 b! s3 i    Clear();) u% P4 T0 r5 g4 }' _
    }; {! W, s8 t( [8 Y3 I7 J
    template<class ElemType, class WeightType>
    - u8 m( h# W$ z, q( b" ]MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    1 P6 S6 T2 F/ r1 W. F{4 q) ]. e$ ]" o- |, a
        vexMaxNum = copy.vexMaxNum;
    8 @* y* D( o# S4 d    vexNum = copy.vexNum;
    % A0 ~& T7 @3 L  A& Z    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];2 C" r8 |4 A4 r, }) g
        arcNum = 0;' W) e+ c# }; [7 {& F
        infinity = copy.infinity;4 r. N/ c3 q' T. v
        tag = new int[vexMaxNum];% h; T+ {" o4 s2 _5 J$ ^2 P

    1 O3 W+ u+ I4 z  B0 l3 R  C    for (int v = 0; v < vexNum; v++); B  m, j( s8 z) t/ i) o. }
        {
    % i. M  a- r( I! Q- c        tag[v] = 0;
    7 W  `6 Y' T1 t/ j# ~1 s        vexTable[v].data = copy.vexTable[v].data;  k2 d0 K2 a, j5 o7 ~
            vexTable[v].firstarc = NULL;
    + g" L5 g+ U7 W    }! c6 y$ `6 p, D! l& L# L' t
        MultiAdjListNetworkArc<WeightType>* p;& N3 R/ l' ~% E8 U
    # Z: A4 r3 s, W
        for (int u = 0; u < vexNum; u++)
    / m5 \" L  K! u0 t6 l) W    {- y' l4 G8 c4 Z  ?
            p = copy.vexTable.firstarc;! [/ ^4 T% U' x* c' q
            while (p != NULL)
    ) X& B4 r% x! u# K        {" o; l' A3 B7 x0 W' [
                InsertArc(p->adjVex1, p->adjVex2, p->weight);+ M& b% _  y( A3 u
                p=NextArc(u,p);
    ( v8 f7 W+ `5 D% F% W5 R        }; I, v2 M$ }  x4 N) |+ l5 P4 `4 r7 h
        }' ]& Z6 ?; _$ J- ?9 [
    }
    : z1 W! a$ c  b  v$ g2 w& D- ~) d2 T  t5 Itemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&, ]; T" V6 I: J  E
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)( t7 N9 f- ~! L8 x3 ?) Z
    {% H7 ^) `7 K6 f, h- o" [' Z* @# g
        if (this == &copy) return *this;% Y4 Y5 z. j9 D. w+ h1 E: m
        Clear();3 S( h! C  d: t6 Q9 C
        vexMaxNum = copy.vexMaxNum;
    & ?# I) w" X; m* p: o" K    vexNum = copy.vexNum;
    ( t& J) a: p8 t. B; Y8 T! i    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];" I  S" Y+ V# o
        arcNum = 0;  W# P& A8 [* r& t4 ?
        infinity = copy.infinity;& L# k$ v: ?" v; P6 d' V+ I( Q
        tag = new int[vexMaxNum];
    ) [8 _$ t* x7 L9 U& u: C" p' t' |$ W
        for (int v = 0; v < vexNum; v++)+ e" l6 F, R% K7 G: D
        {% Q7 |7 I, y# m. {& v. Z+ P" b
            tag[v] = 0;
    & w6 Z) E% l; A1 U        vexTable[v].data = copy.vexTable[v].data;
    5 b) m1 B- E6 o* Z) O( L! {5 {        vexTable[v].firstarc = NULL;7 B) K1 g: K% N" T
        }
    + s6 k8 }  p' X( M/ Q$ y    MultiAdjListNetworkArc<WeightType>* p;  X. A0 O2 b' W& [4 p: o: K+ ~

    + |9 L" C0 _# p1 f& y; ]    for (int u = 0; u < vexNum; u++)
    / o& R6 v9 W& `; k/ H  a8 }5 y    {6 U7 u; v" Z# X
            p = copy.vexTable.firstarc;9 S' \1 k$ N. Z$ f1 t1 e
            while (p != NULL)
    4 i! \0 ^! v- O2 d        {
    9 I5 @/ e3 l# n3 w1 Q8 [! T            InsertArc(p->adjVex1, p->adjVex2, p->weight);
    9 y! F( N  ]+ Y- I            p=NextArc(u,p);
    ( z3 Z, o$ F" h! M% K        }5 L4 Y6 p4 K0 ]! p
        }) S6 b. c% o2 l+ O2 v" D4 Q/ n8 ^! c% C
        return *this;7 T; K3 ?2 z# |- R% U1 p* c
    }
    : E) r  v0 `: m. xtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    5 S& i3 T* e6 f5 DMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    - V) k& E- U$ a+ h{) |" Y* I! G! l; m. K
        if(p==NULL) return NULL;
    : e: V0 ]$ E$ a) F6 U- @    if(p->adjVex1==v1)
    - ^1 g+ f, M* a6 A/ ?        return p->nextarc1;
      M" R' l& Z- k* s( O: G* L    else/ K" t# \$ C! B+ b' ?
            return p->nextarc2;6 Z  f, z. b0 M/ b' t- W. j* Q: a# j
    }# N* t' F/ G" k4 y
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    + c  b% G' B, v1 ]  v; ?& f% EMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    ) B1 R$ w5 I2 \{* u% }0 k$ _2 O0 C
        if(p==NULL)return NULL;8 @9 E; [' Z& B) V3 \! O7 X
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;" a* S# i7 K' T, A% R
        if(q==p)
    / P/ N3 H: e( F; @4 B7 A3 C        return NULL;7 L# \$ f& o! ]" W  R
        while(q)) C5 v8 O' s. w: Z! C+ R' y
        {
    $ T8 S/ w. h* T, ]4 C1 P4 V6 u        if(q->nextarc1==p ||q->nextarc2==p)
    ) c1 U+ S2 [" q1 W            break;$ N. S3 {+ @; _- O2 n
            q=NextArc(v1,q);
    6 O$ x+ Q! d& g, J2 a    }$ ]% U+ _- h5 E4 b- |3 A' K* c
        return q;9 Q0 u# f3 C6 {7 m( R" K
    }7 p" H# X- E9 L9 q
    template<class ElemType, class WeightType>
    ' Z$ f7 N  \( ]5 o& ^# W6 p* g9 B5 pvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
    " X% l/ [6 c1 R& f+ J{1 d' G( T. C3 c4 u6 p
        if (vexNum == vexMaxNum)1 U- A7 C8 P' [+ s6 H  H- j7 ~2 U
            throw Error("图的顶点数不能超过允许的最大数!");! H/ ?2 K6 j, G. j' `4 G5 Y5 Y
        vexTable[vexNum].data = d;
    - ~6 I% l3 f) C# u5 C9 k; I    vexTable[vexNum].firstarc = NULL;
    ) p/ P0 {5 c2 S" N. N. Y    tag[vexNum] = 0;6 f1 s$ ^/ R6 f  h
        vexNum++;/ W4 w; }( d) n" \9 e7 ~
    }
    0 I0 ?. z( z3 C% Itemplate<class ElemType, class WeightType>
    ( w/ o3 |+ \7 k% xvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
    6 j% _. [( M& s( Q9 G8 }6 ]; I% @{$ j  e! U/ z/ Y- L
        MultiAdjListNetworkArc<WeightType>* p,*q;
    ; ^6 D1 ]9 i: t# o) w" B/ E    if (v1 < 0 || v1 >= vexNum)) S. i% N. [1 d* m4 w
            throw Error("v1不合法!");$ _1 X! g. W  U, }0 g! `3 @: C% I: j
        if (v2 < 0 || v2 >= vexNum)
    # S' l# H) R5 ]: t1 U        throw Error("v2不合法!");& w% a6 F7 R/ N' m( c1 G1 S2 W
        if (v1 == v2)  }1 o( W, Z/ I& u* L9 Y' F0 A
            throw Error("v1不能等于v2!");9 t  H" _" N: ]. e
        if (w == infinity)
    + U$ F# a* r5 j; p- O; d        throw Error("w不能为无穷大!");+ q/ ]+ e. o/ G) }% {0 d
    4 q6 F( B( ?* N

      d& |5 ~( T. i, D    p = vexTable[v1].firstarc;
    ; c  E5 R+ Y2 I    while(p)
    0 v3 {) [9 D* H4 K3 ?. i  |    {* o$ i7 s# V$ \
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
    6 x) x; T7 d- j( l1 Y: F: j+ ^3 k" N        {5 l. r# Z' \; |' I4 }. I
                if(p->weight!=w)
    & [) ~" }. t) [" U4 H                p->weight=w;+ F+ {- }3 N. O4 x4 o0 K/ Q
                return;
    9 K3 b) Y) ?% o( p- t1 w# P        }
    6 m; i$ C7 I5 [1 e- I. {5 t' F; S4 P, a1 C1 N" b2 u9 R1 I
            p=NextArc(v1,p);
    5 R4 z9 e$ n) ~& e: d9 I    }8 |- w3 Z8 `4 k7 \* i8 T
        p = vexTable[v1].firstarc;" r" ?8 x3 T% C3 c3 }* M, p  Z) d
        q = vexTable[v2].firstarc;
    6 K% [3 s0 l9 L% z. |9 S. i    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    / C- r) |; B4 S8 d$ y    vexTable[v2].firstarc =vexTable[v1].firstarc;
    / g; a" W, T7 o1 B! k) Z    arcNum++;
    $ A1 s8 y* V, c# r' s* s$ A# O}6 g! N% [# x3 s2 p# H
    ) p! M" }/ y* S8 ^
    template<class ElemType, class WeightType>
    1 s  ^+ W/ E: X' g1 \* {* q" n- xvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
    4 Y( e, \1 J( ?% a, g/ \{5 W4 M5 T* z$ V! @' b; @

    4 B6 U+ J9 K& V6 e3 l    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    # Q2 T) @. X& h& ]3 {3 x    if (v1 < 0 || v1 >= vexNum)  w8 X, N4 s6 b3 w2 O, T4 c. g
            throw Error("v1不合法!");
    : b% s# e* k; m    if (v2 < 0 || v2 >= vexNum): o- w. S1 {  E2 n
            throw Error("v2不合法!");
    7 a# D7 d* p( _( n    if (v1 == v2)
    7 e& n$ q. m  J) b# e$ V. S* `4 l        throw Error("v1不能等于v2!");
    1 Y- {. T; j5 `2 Q: H" O* |2 r. y$ \% v5 c6 Q& I
        p = vexTable[v1].firstarc;5 }' ^$ f. Q6 k
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)3 P% e/ G( G) f5 g- r: u1 W" }
        {
    ( N) v7 I# {! N& O. y8 ^, w5 _        q = p;$ Y7 A2 W2 @. i- N
            p = NextArc(v1,p);
    4 s: S5 c8 T8 d/ @" @% O2 q+ w    }//找到要删除的边结点p及其前一结点q
    5 i2 ?5 O. @- k: b
    0 j8 S( B! B6 W" \  M( N3 }    if (p != NULL)//找到v1-v2的边2 m/ A) l% Q: w1 c/ t- i- a
        {
    2 s* P# r2 a& T- L$ R* u        r=LastArc(v2,p);' X& {. }* N, |6 i  k5 Q8 V
            if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
      J7 D, R0 _3 j+ n8 a) F            if(p->adjVex2==v2)
    1 ?( u" q2 ~* D" _$ O4 ~4 R                vexTable[v1].firstarc = p->nextarc1;2 z3 Y% ^% P  ?/ m
                else vexTable[v1].firstarc=p->nextarc2;
    2 s, A) v( Q' ~# ?# v' o2 J- P% B        else//不是第一条边
    . `/ \, c% l9 P* f: Q0 G; ?5 ^, }, d: p        {
    4 I. U* Z2 k) p9 t9 V% z! I            if(q->adjVex1==v1)
    * p2 N+ c- a3 p4 g) E' r                q->nextarc1 = NextArc(v1,p);
    6 {+ u$ p+ K7 D            else, r: F* _) T3 P( I
                    q->nextarc2=NextArc(v1,p);
    ; d: z7 M6 ~& }! ?5 ], Y% _. ?9 T# ~& o- @" L
            }
    9 ]+ [2 F1 x: Y5 W) |        if(r==NULL)
      s) K. T/ ?7 e% N% C1 R9 _            if(p->adjVex2==v2)- `6 l1 W$ L. F2 p1 Q& K, r( R
                    vexTable[v2].firstarc = p->nextarc2;
    1 \( ?3 X% ^* Y  B( e/ G2 Q            else vexTable[v2].firstarc=p->nextarc1;. D1 [" d" g7 ^& s
            else) X; R* V5 A6 B
            {) Z( |: b" \! [8 y: N! n
                if(r->adjVex2==v2)
    1 U5 r5 h9 Z! W: w. J6 y7 \                r->nextarc2 = NextArc(v2,p);
    + [5 z) C2 I% z8 M/ F4 X, k            else
    , g0 z7 n# o( o3 z                r->nextarc1=NextArc(v2,p);
    , @, _# b- _) k& z        }
    : u. N- w+ h- h: A$ E* ^- F! T        delete p;! r/ [/ k0 j, L: t1 t
            arcNum--;3 w8 e. w# W0 {2 E5 v
        }9 \  E3 ]0 g" R- g9 U. h
    " ^8 I% X# B) _0 R+ N) y7 n
    }
    + L) t$ @0 R( Q% a9 V+ Htemplate<class ElemType, class WeightType> void! c- l! Q$ _" z( A
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)$ o( j, i$ `2 U; O2 a+ V4 U
    {
    & m) Z5 I: s8 L% ?$ [    int v;. D) s1 p! l% r( ?# k: i; j
        MultiAdjListNetworkArc<WeightType>* p;
    " r, ~, f/ J2 z( R9 W; @5 q    for (v = 0; v < vexNum; v++)//找到d对应顶点+ a" g! ?8 t' }" ^; {
            if (vexTable[v].data == d)7 l7 m* z  O% h% h% M" h/ }
                break;& `4 E8 ~( a. M/ j1 `+ s# W
        if(v==vexNum)' k/ q( m( ^' f% {0 ]/ [& A* V7 T
            throw Error("图中不存在要删除的顶点!");2 ?, a. w& |& Y7 ]1 b
    3 {' E! S+ i- V1 ]# T- _
        for (int u = 0; u < vexNum; u++)//删除与d相连的边2 z0 h# e' i" I5 Z4 U. P  O
            if (u != v); r2 k4 Y# X6 Y! k# y0 g
            {! V4 Z" ?+ Y8 Y  R6 z
                DeleteArc(u, v);
    # L  P0 `, b, v- B        }
    & z3 Z& m0 w' t9 I" j4 _5 j9 i% n) ?    vexTable[v].firstarc=NULL;
    " H0 d2 q) x9 U& Q2 _: q3 O+ P$ Q
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置" R1 C5 a( L1 O# R1 I4 Z
        vexTable[v].data = vexTable[vexNum].data;
    9 g  N+ p' L; j2 r    vexTable[v].firstarc = vexTable[vexNum].firstarc;
      z& _( f1 u6 T4 S( I. D: l. c    vexTable[vexNum].firstarc = NULL;/ \% B. Q7 K; A" h4 r- k
        tag[v] = tag[vexNum];
      q+ S! T9 v7 Q' t) u, E    //原来与最后一个顶点相连的边改为与v相连
    / ]. l6 ^3 z" V; f) N    for (int u = 0; u < vexNum; u++)
    ' v/ o6 J+ {) ~$ {& T8 Z" ^- i" V    {
    8 k- n$ Y2 {# B8 E9 d( {        if (u != v)
    / `( M3 k- z0 d        {
    5 H+ B: w& h6 C0 w6 z( E2 d            p = vexTable.firstarc;
    3 Q$ N! ?( R5 Q  C, @) Q            while (p)
    8 I1 u& b, M9 }8 R            {
    . _1 b6 T% p1 J+ l                if (p->adjVex1==vexNum)
    + K/ x+ z9 c) y3 p1 j                    p->adjVex1= v;- {: Y3 A& ~5 A, _9 _" W
                    else if(p->adjVex2==vexNum)1 u! S) q& r5 X: Z* _, _
                        p->adjVex2=v;
    - D: U' K7 G! O3 R2 A                p = NextArc(u,p);4 h6 }; r6 M8 s' ^2 u
                }
    $ q- N* ~; r! @: Q8 h8 {  v        }# m$ L! c$ F+ k, r: N
        }5 i6 R! ?% i' G1 a9 W+ b4 j0 h2 Q
    }0 L; }& P# M3 i" h9 d) _1 W) h7 A, r
    ///深度优先遍历2 {7 ]# G! G& Q9 x4 v
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    ' I" n( K4 q6 h{- s6 c+ X3 _4 g6 K
        tag[v]=1;# S; o6 B: b* i' Z  P8 W  e1 t
        cout<<setw(3)<<vexTable[v].data;' \1 }- k! i; e( |  y' p
        MultiAdjListNetworkArc<WeightType> *p;
    8 f3 [4 F. I0 w0 u4 K+ @3 G9 G    p=vexTable[v].firstarc;
    9 a* J* l* A1 x; W1 Q0 f    while(p)
    * A0 V% _- [2 V! q0 r# `! H/ a6 s    {
    ! S. a- @  U9 \9 P1 N* c$ ?, R        if(tag[p->adjVex1]==0)4 E4 n. ~4 P1 K! E
                DFS1(p->adjVex1);
    % E# F$ H/ K/ W) `        else if(tag[p->adjVex2]==0)
    7 K8 _! r3 R2 ~# J" ?: d( x            DFS1(p->adjVex2);9 R2 U7 m+ H: j4 V2 _# A
            p=NextArc(v,p);  S+ i/ H0 i# T, C% i6 o  ^
        }1 D- Z5 K' F& N+ g( c: ]
    }
    4 M9 M$ x. m6 h& z( }1 Y2 Xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
    - i+ P6 C0 _5 h  L6 `& }* k& q' A{& ~; ^3 _1 G- ^* m+ {0 b. I
        for(int i=0; i<vexNum; i++)
    . S2 X9 P  `+ g. [        tag=0;
    ( V) u" i: A9 g, S: n2 A  I    for(int v=0; v<vexNum; v++)  O2 Q4 y' \  Z0 ~- [1 Z
        {% [/ i1 j$ J; p# h7 x) ]
            if(tag[v]==0)4 c) x* d' w$ _# G  o- z5 V6 {
                DFS1(v);' P# y) u9 }9 I. z( i, C
        }6 P2 U. Q! ]' ?1 D% x6 o; ^
    }
    % E( N9 A1 {6 y  H7 G- A8 htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()0 B- O% X" q9 }
    {/ U6 u- O8 P# p
        stack<int> s;. U( I, f; T- I
        int tmp;
    2 [* T: j) y$ B    MultiAdjListNetworkArc<WeightType> *p,*q;. v. m$ O" r# B! Y6 }
        for(int i=0; i<vexNum; i++)( @0 G. m8 Q: y, ~) R$ _( M
            tag=0;
    - E  ~2 s/ {1 w/ P    for(int i=0; i<vexNum; i++)9 J! f% C' m4 a6 f- I! a! k
        {
    * O: f3 C5 u( Q+ p4 x3 D        tmp=i;
    + U; r0 O, g7 k3 m        while(tag[tmp]==0||!s.empty())9 z% x3 q, Y, `2 x: X7 ^
            {
    & @3 W- ~) n9 n" @7 L3 w% k6 W7 F            p=vexTable[tmp].firstarc;3 b0 ]5 _: I# c! Q- S- O
                while(tag[tmp]==0)6 X( V7 R* J" [( C+ ]
                {0 r' o1 ^* S1 r. |2 x
                    s.push(tmp);
    5 J1 C; O% X6 p                cout<<setw(3)<<vexTable[tmp].data;: C' A$ m- I3 {2 }+ J
                    tag[tmp]=1;3 A' D1 p9 H7 n7 i8 Y: t7 c
                    p=vexTable[tmp].firstarc;
    & I7 `" L! u$ ?' f4 k* u: s                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for1 [' Q. U2 D6 }
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    8 D& d3 Q$ J% C  _0 a! u) C                //cout<<" 1st     tmp="<<tmp<<endl;
    8 N$ U; j7 z" z4 N# v            }5 r6 f% V5 R- j+ {- e0 U/ i  m
                if(!s.empty())
    / f* @0 w2 _, C2 T$ L- D; g# p            {
    ' d/ q" t! z0 y6 s4 O- f  O7 A2 y                tmp=s.top();
    $ z1 ^! n# W% B* {                s.pop();! R( F4 P- t1 f7 ]! O5 j
                    q=vexTable[tmp].firstarc;  k9 b" N6 b7 _
                    int t=tmp;; @; D' Q' A: a: h
                    while(q&&tag[tmp]!=0)
    $ \7 Y* \5 C8 [& o5 t                {$ M4 S8 _8 I8 y
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);4 Q) r& E( h. u  H& B
                        //cout<<" 2nd     tmp="<<tmp<<endl;% H) c  X, j( O# Y' e( B7 K
                        q=NextArc(t,q);2 z+ a9 U6 x6 z, P2 i' k4 k! X5 `& p$ S
                    }) O: h  e2 {) n: t% @
                    if(tag[tmp]==0)4 e# J& F5 o7 A* v. `8 N1 V% r
                        s.push(t);% K: E* E! V( \+ T* l9 W
                    ///1、对应上面连通分支只有1个点的情况* W5 V4 i9 K- T7 P
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
    8 ]7 i% o+ ?% r9 U& m4 n5 ^                ///tmp要么等于找到的第一个未访问节点,
    2 s8 [8 e$ C2 ~, @6 [! M                ///要么等于与t相连最后一个点(已被访问过)) K2 F) p' w# l! e+ O
                    ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点  [6 i! w* w/ _+ |! J+ [: Y
                }
    $ }- t  l3 X8 Q7 @/ f3 Q1 ~! K9 m        }
    7 j: x& L: ]0 U: X    }
    . A0 `9 A5 S" T5 W  I$ o}0 X% L& Y' ]5 Q9 d' O
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    # ?* ], t' a! |template<class ElemType, class WeightType> int
    ! w( y4 m% s5 G; B2 sMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)4 d1 p! Y+ t3 [9 j% n" t3 t
    {
    2 Q, u6 d% e2 t0 E7 _( H    if(head==pre)
    4 r  I) _. _$ p7 \+ |        return -1;
    5 S$ r# v5 D6 g. \; O
    ) J+ E' ]6 P8 K+ _7 J  B. S    MultiAdjListNetworkArc<WeightType> *p;, r2 n3 _( M$ u8 q# r
        p=vexTable[head].firstarc;1 K) w: ^4 o9 x$ A0 B# @
        if(pre==-1&&p!=NULL)
    8 x& U6 E7 t( @: Z$ ~2 T) p        return p->adjVex1==head?p->adjVex2:p->adjVex1;5 X# N1 G4 }1 {5 h
        //pre!=-1&&p!=NULL
    & \, Z3 U1 X! C; {. }    while(p!=NULL)) l' d1 Q' ^1 {4 {! z
        {
    ( u7 b2 c8 h! j2 e% T        if(p->adjVex1==head && p->adjVex2!=pre)  _& g& I# G& t
                p=p->nextarc1;& p+ `8 q2 I3 v: d4 u7 M+ Z& C
            else if(p->adjVex2==head && p->adjVex1!=pre)
    : g& @( A9 k: r0 n, n4 T            p=p->nextarc2;; C% A/ {9 k1 \1 C; Z
            else if(p->adjVex1==head && p->adjVex2==pre)0 `+ z3 V# k. _& z) N
            {
    9 V; S$ G8 ~9 R1 {; P5 @9 v4 ~            p=p->nextarc1;" [" |/ P7 E9 \0 _0 r
                break;
    6 z* a% c9 M. M# U* U        }+ T# f) o$ H7 x) i+ }
            else if(p->adjVex2==head && p->adjVex1==pre)3 ]* D) L8 G- f; g0 C1 C3 ]- I  n
            {
    ; z" S5 S& q9 w            p=p->nextarc2;
    # |1 V8 O" ^+ H& S* z, [0 I            break;
    5 R) o* b+ M% G/ h& ^+ n        }$ A4 T& f  X2 m# ?% n
        }6 F2 ~& i% S4 q
        if(p!=NULL)
    : e/ z0 ~5 R2 |3 F2 ?5 @    {5 l, y: {# _* A) J, a# j
            return p->adjVex1==head?p->adjVex2:p->adjVex1;# d2 T8 J; Z+ n% b& T
        }- c! J5 o4 Q0 o3 g* Y; Z
        else3 b& C# b$ r6 d$ b( j
            return -1;
    - ?5 M# {) \* ]$ \; G}
    % {& ]6 ^. O5 _) z# B( F: P, P% D: X8 P  l
    ( C# u0 |- r1 w1 b- d1 ~
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    8 i# F% R* w( u2 y{) T& U9 }" l9 r5 e
        stack<int> s;" L4 K# {7 x) E/ c  ~2 @
        int p,cur,pre;
    $ w  v- T' Q3 ?8 W: Z! |    //MultiAdjListNetworkArc<WeightType> *p,*q;
    : A  h- w0 _: I9 X8 I* ]    for(int i=0; i<vexNum; i++) tag=0;//初始化
    / e$ }- z3 \1 E9 l  E# r/ {, L( I, _! D( k
        for(int i=0; i<vexNum; i++)1 x9 L) c, Y; d/ f8 s( `
        {% e0 U& R  ?2 }& Y* ?. d
            cur=i;pre=-1;* A, R. k6 }6 Q5 ^
            while(tag[cur]==0||!s.empty())
    ) W  y( v3 O) Y! n( y7 _2 ]        {; I  |* v/ \. \$ E
                while(tag[cur]==0)
      P4 y) g8 B  ?            {
    1 r; P5 C0 F% X- z; Z+ }) Q! r                cout<<vexTable[cur].data<<"  ";9 T4 [& m- ~4 s: D" Q
                    s.push(cur);
    * c6 G3 ]4 G. d4 i, C. C                tag[cur]=1;% ]' H$ K# O/ y0 l5 _6 Q; v$ E/ y
                   //初次访问,标记入栈
    % s0 ]" N0 h- p+ a/ W6 f: @; [4 ]/ A2 q) @& @$ B9 ]* z; G
                   p=GetAdjVex(cur,pre);//p是cur的连通顶点
    , @* @7 |, ]* @/ \( t: c% H1 ~               if(p==-1)
    ' z; u( W9 ]5 g! ]! {  i$ {( Y2 K               {' z% z* [/ s& R1 u% B3 p
                       pre=cur;s.pop();
    / u2 }/ o1 A" x! s                   break;
    6 f: R9 D  }" d0 g. z: {               }9 a- Z: X  i8 e0 F+ K
                   else! X# j* i: n; E  |5 \6 V
                   {% E) u& S! z3 S$ Y
                       pre=cur;0 i2 }$ Z$ t1 D! H
                       cur=p;
    8 L- [: K  S5 z5 }! z; a1 K1 {4 u               }
    # t; x' D7 b/ O7 v" {
    * I& e! z: i  J9 \            }
    & V9 q3 r, u  {8 F" z            while(!s.empty())' }' }/ ]# E7 ]7 w1 a" f
                {4 d3 J* b  z; I
                    cur=s.top();
    : G, o! A8 M' ~, l3 P                p=GetAdjVex(cur,pre);; [+ ?3 t: L( T& W4 K; Y  L
                    if(tag[p]==0). I$ V/ G8 |4 r0 q2 P' h. X5 y
                    {% P+ i( W% N, X# T6 s9 o! f
                        pre=cur;4 Z+ R6 n/ w$ n3 l3 [
                        cur=p;  }- U6 O# o( K0 _6 }
                        break;$ n5 x# G7 m! ]4 \
                    }
    + ?- ?% U' C, i+ V# K. V6 E+ e4 T                else
    2 ^# T+ ]+ `, c" ?" F$ m' H' q                {* P( Y% w0 N* A$ D2 K& ?* g: a1 E
                        pre=s.top();5 \% g5 J( g1 G8 J2 H9 z) _
                        s.pop();
      g8 A4 x; A! f4 L5 H                }
    ) {  A0 b" ^2 w. g2 x- V9 s
      x  x7 F9 g& A" l3 M            }. w+ Z  s% [* c7 D8 Z. K- `- r  P' I

    / Q! P) w  J- h  r9 ]: ?/ s        }
    , Y, a# d: @  s2 p  ~7 @    }
    4 D/ q" ~" K2 j6 [$ G0 s6 [}1 }' f) D2 P3 I% n4 R$ E
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(), `7 e: A2 c% T5 }4 l
    {/ s- ]% n/ X" L4 b. x) o+ T; F
        for(int i=0; i<vexNum; i++)3 I1 `" i* E% C' M
            tag=0;  C; D/ i2 N- k1 w% ]0 S% i: X, l
        queue<int> q;: h7 B: C5 T6 n1 M
        int tmp,t;0 c" [1 @( f  c1 l5 K/ D
        MultiAdjListNetworkArc<WeightType> *p;$ C: y* Q. M( s
        for(int i=0; i<vexNum; i++)
    4 H% H- X6 U5 `3 A/ J( a% A* P    {
    & y+ o9 ^" Z: L! \        if(tag==0)
    7 A1 J) b* c4 S6 I5 T" S        {5 F2 c% j  ^0 {" I# F% K, |
                tag=1;( \: ?; J7 L# o6 S& ]+ ?8 d* p
                q.push(i);
    : |" u! N+ A: O" a            cout<<setw(3)<<vexTable.data;6 e8 ^; ]) E# y/ N
            }
    " u7 D& d" R4 f- Q( r        while(!q.empty())$ R, a8 Y8 V7 x/ |
            {
    9 J7 s1 ]! e+ x; Z            tmp=q.front();
    * g* @1 I9 t* p! x  |* K- \            q.pop();% M) o& x7 ]$ [" s2 {9 i$ K$ w4 b
                p=vexTable[tmp].firstarc;6 H' f2 O) t# i7 j( i
                while(p!=NULL)
    " r5 E# q- R" c/ l            {
    * u9 v1 N% V7 j( v  a, H% \                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);# U1 p/ Z7 @8 V
                    if(tag[t]==0)
    " F" X2 n  }! G% m! H  _                {
    ! @; {* s$ J4 e# I* c6 ?                    cout<<setw(3)<<vexTable[t].data;
    ' r7 d' j6 y/ r4 K' \$ B                    tag[t]=1;
    " V4 D+ f+ n6 J7 C+ a                    q.push(t);
    0 ?; `) A/ I: ~' r& ]                }. K, f+ E* R, ]' E$ U3 d! R. K
                    p=NextArc(tmp,p);, B* i0 [8 e: o& F. U9 T
                }
    - @' u% i/ |+ A5 ?        }  r/ d7 f3 [% V2 C0 s5 L% }
        }
    1 C; o0 O* @7 p6 t- _" E% ^/ W}) f- F. ~2 N& {
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
    + J! g6 k6 r5 v; B0 y0 c{* P/ I: i) i& ]. |3 P0 b2 q
        MultiAdjListNetworkArc<WeightType> *p;
    9 T: k3 a& h/ H: W% x0 q/ d    cout << "无向图有" << vexNum << "个点,分别为:";$ E# q: K& ]+ Z5 w
        for (int i = 0; i < vexNum; i++): C' T& ]$ J! c; K2 G* B
            cout << vexTable.data << " ";, g. m$ J, A/ W" E/ t4 C  Y# W
        cout << endl;
    & i0 u7 M# j4 J# P% m% F0 q    cout << "无向图有" << arcNum << "条边"<<endl;
    8 @/ ^" o7 k. X0 T4 f& ~    for (int i = 0; i < vexNum; i++)
    4 f+ o0 D. Q3 x0 ~& M+ e    {3 U$ v9 ]7 p. Z/ O4 T
            cout<<"和" << vexTable.data << "有关的边:";
    ; B/ f% j: a; `' e7 N3 S/ w* A& r6 g        p = vexTable.firstarc;
    & {2 P/ \9 [0 V( ]9 T3 g        while (p != NULL)0 I9 ~. D' @* G( {7 u- j
            {
    # ^# F, ~; @8 b3 j: m; `" C            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";% s6 `2 [: S1 K7 v3 V
                p=NextArc(i,p);0 n. j2 r4 t$ K. J$ \/ K
            }
    " i/ j) y, x( H        cout << endl;- k* W/ z  A  d3 N& x
        }9 g, A7 I! ^9 E  P" h
    }
    ! u& i' ^# w- G5 H' E: S
    3 U/ @, D0 d. Q0 Z! l
    , [, \( \9 h* D: y& |2 a/ ^邻接多重表与邻接表的对比* ^# O0 s; v6 H, c$ e- a. |
    . [- K: g3 T( }) v& u
    邻接表链接3 J( U" [) e4 p6 {$ b) n# ^
    在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。- T2 G1 I8 W2 R: J
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    ! |0 [1 s$ Q9 w' }& F/ Q& G为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    9 H9 _1 ~% H% m* q/ M% i————————————————1 a$ j1 A( b, ?) \1 {! c% _( k8 S1 l
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。$ V9 `* g# k, i% T0 l" }
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    7 C4 }1 f. m+ S& ^
    ( m$ F+ S( Z% L% [- c4 N
    $ J6 i& ^/ i) Y% H, v' |" ^  u; `1 l3 K, u- ^4 Y

    / ?! {' [( p( d  o+ U! l2 [5 y————————————————
    8 X, u! j- K& k" k$ b* K, f) Q& P版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    ) T, }7 z' e, t- q3 g原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    6 M5 y+ \9 g0 j; w/ M) v: w& f
    7 A- x% Q. B; N- E$ O8 c( R0 G$ q- u/ z! V4 ?0 q8 b
    zan
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-29 16:37 , Processed in 0.299132 second(s), 54 queries .

    回顶部