QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1643|回复: 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
    : s+ M! V4 j5 O7 i5 h8 N; h
    图的存储结构——邻接多重表(多重邻接表)的实现
    7 H9 X/ |# U! O# @3 b1 M5 k7.2 图的存储结构. p; J: M; i1 M8 J

    % l$ W, k/ _/ _/ z8 j# j7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    & f' T) d6 Q- `邻接多重表的类定义
    ) k/ i/ E4 n4 P. G3 h+ b+ ?! E* k7 N邻接多重表的顶点结点类模板
    . V. m) |/ {- @! Q: D4 }邻接多重表的边结点类模板3 `1 K1 G' X/ T. v9 ?
    邻接多重表的类模板  g1 Z) c/ C7 C" M1 z9 |6 ?
    邻接多重表与邻接表的对比; Z- A: Q. V) S) u3 y
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    9 s8 ^! K/ f# |! ]- J9 R6 L& S- Z/ @5 e( r; z, L
    在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。
    6 E; b, [7 N1 J5 b- b在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    / P! N. r8 h% G1 W. m+ T7 C# b. [" A( ?( r( U% d: d
    邻接多重表的类定义
    2 A) v! ]& Y/ \/ P 1.png
    9 q. Q. v7 _; k! g' ?) r7 O1 E% M" e2 A邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:+ d5 M& Q4 B. w4 q. Q
    data域存储有关顶点的信息;5 t5 `+ J7 z. O6 F  }$ \) c
    firstarc域是链接指针,指向第一条依附于该顶点的边。  o% K& i$ y! J3 `) |
    所有的顶点结点组成一个顺序表。

    4 s2 U- i. j& ]  ?1 t* g, S2 V

    2 `6 k2 C* r* I' q% G* vtemplate <class ElemType ,class WeightType>
    ) J6 i7 A% C& s9 b1 N- lclass MultiAdjListNetworkVex
    * q5 u$ d. n" F+ p: ?/ C{
    3 T! l; i5 k: O6 x- l( N; ]  ^public:4 K6 @/ x% s7 O
            ElemType data;2 e9 R) @& v: W: G# n! R5 U; n
            MultiAdjListNetworkArc<WeightType> *firstarc;
    , e# s% V% v" ~7 m. B0 \- {
    3 ?# N5 S4 Y: J, g1 }        MultiAdjListNetworkVex()
    4 A/ f5 O5 C+ T, |" ]$ u" ?0 y        {
    # Z3 A8 G% R  w, a0 C                firstarc = NULL;
    0 H9 ?, q( a$ f: ^) ]* r! q- V6 ]# d        }- s0 B; ^7 o( B  N
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)/ s* v& p: ^1 ^2 o1 X
            {
    4 k7 [9 x) C) a) j                data = val;
    ! p; X  E: Y0 K  m) o7 u- j. t                firstarc = adj;
    4 `- u; ~/ A9 `6 [' K        }+ j, |( k! d6 X; O- T/ e/ n
    };0 K/ j5 R7 ?, ~" f

    9 A' H' c5 z  r8 k4 ?邻接多重表的边结点类模板
    6 `  V! Z4 A. x2 u" S  F  Y5 K7 v7 c! Z3 |
    在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    3 q# q+ V$ f, u) s) B+ E7 \tag是标记域,标记该边是否被处理或被搜索过;7 ^$ w# v0 C0 Y6 o- {
    weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    0 V. E. `. E# `nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;
    & l3 ?+ j9 ~4 U8 A# znextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。+ L2 T7 d: P* N5 P. H" @: z6 Y8 l

    8 p& f; c5 M8 S 2.png
    0 k! C- J+ ]4 e4 ttemplate <class WeightType>
    " Y: [5 N. ]$ J: J7 G6 lclass MultiAdjListNetworkArc
    % V6 x* ]% f4 _3 ?{8 ?0 j' }9 k4 m, h/ Q
    public:4 r! X* {% a* X% w
        int mark;                                       //标记该边是否被搜索或处理过# a8 d* z- x/ z3 k% H
            WeightType weight;                              //边的权重" D; B2 \+ [" F  B1 P5 Z8 |% `
            int adjVex1;                                    //边的一个顶点
    # B  s( h; G" P# y3 Z: q# B) U/ K; C        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1+ o/ x" G/ @5 n7 G8 b5 W. ^
            int adjVex2;$ q3 b7 x! _+ j/ S
            MultiAdjListNetworkArc<WeightType>* nextarc2;) D$ D! q3 h6 B# ^, O1 k

    ( A9 b% o& R9 T        MultiAdjListNetworkArc()! B6 d# _5 W4 v8 K( r4 W3 @
            {/ a5 k# S" ^- R+ K
                    adjVex1= -1;4 z( L, b" B9 ?1 K8 _/ A4 F
                    adjVex2= -1;
    / N) ]6 @1 A2 s4 a/ n* \: d        }
    6 S; m; I4 o* }# K7 u        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)) U' @' f6 Q7 L3 u( _2 U1 ~7 l
            {& U4 D! U& n6 A! q- ]) U9 g
                    adjVex1 = v1;       adjVex2 = v2;/ V1 G7 P* ~4 C- e7 B
                    weight = w;% E* ?0 e  O5 h0 Z2 u4 }
                    nextarc1 = next1;   nextarc2=next2;7 B# }. B  c9 {( M
                    mark = 0;           //0表示未被搜索,1表示被搜索过
    2 W# C$ h$ y% L        }
    0 k7 z/ M: Q) w3 o0 p
    3 f/ _; G+ ~' A! U( l* l/ J! I邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>% f, l. h7 T! n3 C$ b
    class MultiAdjListNetwork$ V, Z* `0 t3 E) s& [6 _
    {
    % ?& {# Z$ \3 oprotected:
    ) R+ x1 j+ f1 V" V3 z2 X# w    int vexNum, vexMaxNum, arcNum;
    ! c6 C) m7 F$ t% M" }    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;- L2 k6 w$ d3 x9 \* b
        int* tag;
    & N9 G. @+ h6 w' h    WeightType infinity;- g) Q$ W% y& S3 G! C
    ! {, c9 d$ J1 u! R. ?* S( J3 Q- D
    public:! M" W1 Q  C* ~5 {; |! e3 Q
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);4 u& P& }9 p3 X: P  a
    / ]& h/ S' ]; v% j; J3 l
        MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    : m0 y6 O8 ~9 ~" v1 _8 c- W6 y) l
        void Clear();
    9 z, C- J; g7 ?; }    bool IsEmpty()- e/ g7 g2 x2 [8 f( F9 _
        {$ G  u3 t# b$ h7 }( g
            return vexNum == 0;/ ]  s) k& L8 h: P, b# t- ~* T
        }
    2 ?: b0 Y' t  M( u- l9 ^) s5 C* W    int GetArcNum()const
    # V0 z% i% a: c# D0 X& e- ^, V5 u/ e, u    {/ p- M7 R: X; c" ]4 [% H  D
            return arcNum;; w% R) L5 w8 T: e
        }' @0 `9 @5 y' ?
        int GetvexNum()const
    * a& s! _' l, q# B; l: A5 P* g    {
    3 X- O& ?2 U7 r0 V        return vexNum;
    ) E2 b9 }. Q+ n( I0 T2 h* b    }
    1 P4 z# g6 P# B  M& I% x! ?  c0 r: }- t
    # u: v; g: y* L7 \
        int FirstAdjVex(int v)const;6 X7 @' e# q6 R9 ]
        int NextAdjVex(int v1, int v2)const;8 ~: v7 B) l& F' i6 v0 L
        MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;1 N1 M4 v$ J7 N% Y
        MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;0 V4 _2 |% W& B" [2 M2 a- v/ m

    # N' T! M9 W: C& F( w5 T2 |    void InsertVex(const ElemType& d);/ ~* X  K; B7 c- m
        void InsertArc(int v1, int v2, WeightType w);
    - a( b- R& t) R  t1 ?2 O7 C. \+ j. A4 l) A0 {  r- T6 Z
        void DeleteVex(const ElemType& d);
    1 V% N8 a5 H% h3 ^$ I8 J" f3 L    void DeleteArc(int v1, int v2);4 k* e. x6 k( [

    2 v2 w8 A4 C* l; N0 `    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);0 U( Y3 b  `; ^
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);! i% P6 G/ f- a4 S9 E3 q

    4 R2 D1 P) O2 a6 j9 O% I  J, E    ///深度优先遍历( v, s1 \  g6 X* l9 r7 a1 D, v4 N! d
        void DFS1(const int v);  q- b, d6 a4 W5 M7 |$ U, T
        void DFS1Traverse();5 Y( G7 ?8 \- D; C9 {! f7 L
        void DFS2();5 v, @# u. w9 s1 q! h

    / R8 W1 [( D- i/ K+ p    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1* v0 \7 b9 b( |, q
        void DFS3();
    4 ]0 S/ f8 \$ w) W
    : d9 I- Y1 }( h# P    void BFS();( z1 [1 r! m4 z8 E- f/ I
        void Show();/ h2 r; }% W1 r4 G* a  e4 s
    };. S( q7 r# W7 D% B
    0 y2 t& n# X) J4 T. B
    2.函数的实现! d, l) w- O9 r6 y8 h- d4 e
    研讨题,能够运行,但是代码不一定是最优的。# p+ I! Y5 |$ H" R
    5 T. R* b+ c1 X; }: `, E
    #include <stack>9 K% v) ?, v. G# u6 w9 k
    #include <queue>, N! Q% g+ |& x7 r

    1 a$ U1 e6 s8 o& vtemplate <class ElemType,class WeightType>: H+ z, R7 b" b7 _; G& n% ~" `
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    + r$ H2 g5 V# s. _* `; ?8 ]{
    5 Z' h4 ]! L  t- [$ k    if(vertexMaxNum < 0)- d8 [; A. M. h  A. ~) N
            throw Error("允许的顶点最大数目不能为负!");
    " \! }5 k0 [: j+ Q0 j2 G    if (vertexMaxNum < vertexNum)
    8 T+ d  [3 g# T" ~( @7 E# K        throw Error("顶点数目不能大于允许的顶点最大数目!");; ~# R* G& ^) T; H( L6 @7 x' O0 k
        vexNum = vertexNum;
    / y  r/ j# r4 p9 R& [* E6 C2 S    vexMaxNum = vertexMaxNum;
    ; J/ ~' {6 a  i# a$ F    arcNum = 0;
    , P% w  ^3 G9 d2 \, \    infinity = infinit;9 B( ~6 P5 D1 h. a% f* L9 m
        tag = new int[vexMaxNum];9 _8 U1 O4 B1 Z% }+ u* a
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    - V; {  j; ]% T9 z2 G    for (int v = 0; v < vexNum; v++)+ x9 \+ |7 W+ W2 f# e# d2 [
        {
    1 \- }% N) r: A$ ?, }9 e& l        tag[v] = 0;
    9 W* T8 Z7 I3 ]& `/ t" X6 t$ j        vexTable[v].data = es[v];
    8 q6 _4 d) V" |( s        vexTable[v].firstarc = NULL;
    * x2 r6 B  d, s4 J: L    }% I' O- `1 }0 U0 b- C4 |
    }
    - a' T* i. F3 r' E% w8 e0 O% x4 P; Atemplate <class ElemType,class WeightType>/ w& E0 E4 Y, a8 x. s9 Y$ X
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    2 s* J9 h8 U! t  P{3 u: b5 n8 H3 H9 ?
        if (vertexMaxNum < 0)! ~2 c2 Y% q) Z0 q" d1 G( W6 V
            throw Error("允许的顶点最大数目不能为负!");5 b# _( H: G. p- x/ x1 ?: Z0 p% m
        vexNum = 0;" H$ R6 e. G% m" i  E2 _$ U
        vexMaxNum = vertexMaxNum;
    " R1 S7 e& h' I' g7 P$ f    arcNum = 0;
    % s: j) R3 q1 ^$ A9 l    infinity = infinit;
    , U+ L' j- p+ C5 {$ L    tag = new int[vexMaxNum];3 X& v  l* ]6 B# ^
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    $ _0 ^% c& I( M1 E; |5 V; F3 Y# K}, `+ i4 F, O4 u, u0 l
    template<class ElemType, class WeightType>
    ! q8 s' o" g+ ?* n/ N" vint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    " p2 S1 C- U3 r% j+ C3 }) s{2 \/ O2 G7 G/ {2 e+ j8 ^# W
        if (v < 0 || v >= vexNum)
    * q2 o8 }) Y( `, P7 @& o3 Y4 M        throw Error("v不合法!");
    & X- C0 f2 }" Q' M    if (vexTable[v].firstarc == NULL)" N5 D( t( i! X
            return -1;7 m2 o3 n* [, D, L* f5 x
        else' n# y. w7 s9 ?
            return vexTable[v].firstarc->adjVex1;" y3 p5 i+ Y8 b
    }( U) j, n( W/ |2 P) W

    3 b4 q) D  f- o7 h* Ztemplate<class ElemType, class WeightType>
    . h# ^2 ~& P6 S3 J6 D6 G3 }5 Bint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    & d% ^. @3 l* y{
    + M2 ^; h& g5 J! C    MultiAdjListNetworkArc<WeightType>* p;
    , v, _& d/ o  q( ^! w' @    if (v1 < 0 || v1 >= vexNum)
    ! m# y* d. j5 P4 [; v1 E        throw Error("v1不合法!");
    . Y* g5 G7 ?: |    if (v2 < 0 || v2 >= vexNum)
    9 p- K" Q2 l+ C6 r: n+ t        throw Error("v2不合法!");/ g0 L! e% h! X) c3 E
        if (v1 == v2)
    ( k% y# X  l. G  Z; {0 Z        throw Error("v1不能等于v2!");
    ; f5 {: T' [1 H2 N    p = vexTable[v1].firstarc;
    1 `% d+ E* n  }1 @; L+ w  A; ?# J    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
    1 O& Z( w8 K4 S7 r9 R        p = p->nextarc;
    # ]/ }2 s+ q, v$ t- ~9 v    if (p == NULL || p->nextarc == NULL)" u1 ?# S' a4 G, _! H
            return -1;  //不存在下一个邻接点
    ; w6 V4 Y# i# O4 D2 t4 t0 Y4 \    else if(p->adjVex1==v2)& q# i* Z% |( l& ~
            return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    - B" ~% S% f7 ?' C- g    else% _8 |* ^. o/ i9 {$ p
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    + C9 C1 X. \; N' \2 k# M}
    3 F9 b* `$ ~* {template<class ElemType, class WeightType>* K3 w" ]/ T% b
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()7 ?, O. ?# H- }+ R
    {
    : E6 A+ ~% r" c7 {5 V: C# A5 v    if (IsEmpty()) return;! Y9 }4 x: Y; v  g& [9 d! I/ k9 r) z
        int n = vexNum;
    / C- N0 ?2 o% H    for (int u = 0; u < n ; u++)7 E0 S8 ^" `. [+ z  E  M
            DeleteVex(vexTable[0].data);
    ) \3 G, w# {2 z; r8 k; Q) d    return;
      q* x- N2 [' A4 T}
    * J; m8 \% E  ~" Ktemplate<class ElemType, class WeightType>+ o7 |0 x+ _- i1 h0 H* m# U; t
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
    0 }7 v( q) _7 \0 p7 `% t8 e1 i: i{+ H$ L2 V  P  u. V" K: |9 ?
        Clear();
    5 z, p5 H. H8 l& J- `* w$ R6 z}1 G6 O' N% m2 V  N. c) r
    template<class ElemType, class WeightType>
    . K) L: G9 \0 h/ M9 wMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    1 p" U( o. G3 g$ O; K{
    2 p0 w/ M. k0 P$ x; W    vexMaxNum = copy.vexMaxNum;1 {9 j% U4 g6 k4 e3 C$ x
        vexNum = copy.vexNum;
    - h- X' ~. @% @2 u  N    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    ; q; C  c0 L' [/ h    arcNum = 0;- v. o4 o7 m7 P! R/ c7 e0 ?
        infinity = copy.infinity;
    $ g% ^' k0 _+ R' {( I( U    tag = new int[vexMaxNum];7 ]  g; R" q" w

    3 O( p- e' j' c" L6 e    for (int v = 0; v < vexNum; v++)
    8 r: d0 e+ }8 s5 t4 K    {
    . _6 W2 d6 {( y3 P& C  L        tag[v] = 0;
    & N8 I& G- U5 N        vexTable[v].data = copy.vexTable[v].data;! ~' m; v% T$ T" I+ k. D
            vexTable[v].firstarc = NULL;: i9 C! l  t' w4 g& ]/ j
        }! w# ~3 {" {2 h+ ?4 Y
        MultiAdjListNetworkArc<WeightType>* p;
    ; h0 G6 J: y$ Q6 C
    & \0 i7 `( h6 v    for (int u = 0; u < vexNum; u++)9 L( s: }# q: O! b& ~! w
        {- S) \9 L9 R+ p; j% A, R; d- {: K
            p = copy.vexTable.firstarc;; j& j4 ]: l$ [0 t6 O4 F( ^
            while (p != NULL)) w3 f5 x# |. P# h6 G1 {8 ?# Q2 W
            {. x/ v6 q  b8 Z2 D; [/ O$ p
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    7 D1 y) W, f  j7 N            p=NextArc(u,p);7 T9 \( q- P0 K" j8 O
            }
    3 X; T5 x  E6 l" P" x/ l4 v    }
    1 o( G$ d9 t0 B; I) f- H2 |* W}
    " p4 U$ ?$ t. d& _9 i! j, Stemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
    $ c+ i' S/ C2 |! C1 \7 fMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)7 \9 F# n  L. N0 {: ?
    {0 S" n! {2 [* M* T' J
        if (this == &copy) return *this;. ^4 r3 M* P7 h; [! D
        Clear();, d! t/ q' b% [& D4 c, Y" ~
        vexMaxNum = copy.vexMaxNum;$ g! b9 z8 ^- I, b
        vexNum = copy.vexNum;# ~! J, g  b; U
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];% t5 \) H* V& U( p0 ^
        arcNum = 0;
    2 [( }7 A7 Y( o    infinity = copy.infinity;1 a* D4 c% P+ C- ?4 E. X3 L, u
        tag = new int[vexMaxNum];' f/ P/ u7 m! p9 x" \# n5 Q
    & v# L5 N1 j0 M+ ]9 i8 o
        for (int v = 0; v < vexNum; v++), R0 ^% B3 ^. H5 Z  W
        {
    7 H, Y, f" `( n* f% C: A4 K        tag[v] = 0;
    , ~0 Y* L6 M0 [9 N: }        vexTable[v].data = copy.vexTable[v].data;+ m1 p3 k# {/ x! _. D! o
            vexTable[v].firstarc = NULL;
    . I* F6 J$ Z6 ^1 o9 H: H4 b    }+ e1 Y, g" N9 W1 U' f) T8 n3 D$ j& ^; E
        MultiAdjListNetworkArc<WeightType>* p;2 w) {( W' ]3 ^; N4 ~9 x3 E( r. e
    . {! R- J. Y' z9 @: V: V
        for (int u = 0; u < vexNum; u++)
    1 ]1 _( J" r, b: G    {& i0 w  _+ W$ V8 I, a4 ]
            p = copy.vexTable.firstarc;
    7 G) i0 i" P2 U5 U+ Z% f5 I        while (p != NULL)
    0 W. {; ^' K  I+ @- z        {( T  T; I' o* e7 {( W- G) {" V$ m
                InsertArc(p->adjVex1, p->adjVex2, p->weight);2 f1 x, ~1 E7 D) r' t
                p=NextArc(u,p);3 V) e, j9 N1 d9 n" X
            }" a4 z' a3 n0 }
        }
    % d4 ^5 ?* t0 a8 v    return *this;
    0 x2 z. n" B0 \( ?}, D: ^! h4 L( U: h& {- D
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*- X3 A3 L. c# k  Q# n/ m
    MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const% d8 \( I7 Y7 r4 _  d
    {
    ! w* \5 Y; E9 e( K2 q: z    if(p==NULL) return NULL;
    3 M" M/ B- u( k, Q; C    if(p->adjVex1==v1)6 W  L, D& N- b1 v" m: v% y2 H
            return p->nextarc1;
    2 M7 R- a' e, C- p1 N7 [+ {    else0 `$ ]% f* ]: q
            return p->nextarc2;
    + J" j. v+ P" R) T. u0 Y}
    & {, `! Y. u: d. b9 }2 t. m& K  N: Vtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>** Z& F+ G0 M2 d' Y- M4 }5 ?/ w
    MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const, T7 r' n+ H' {9 v
    {
    , `( H, O5 r% }9 J' ~3 m- ^& k    if(p==NULL)return NULL;
    ) A$ Y1 S! ^+ o& x' e/ E7 r+ s    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    6 k% r  L, ?# _) t6 @    if(q==p)/ G4 x9 a1 ]- Y% k2 x; a
            return NULL;
    ; g/ m+ h' Q* c# a/ ]" X! W    while(q)
    # G1 K# M) J3 c. W/ r    {! x4 }2 y6 ]$ a& ]( Z
            if(q->nextarc1==p ||q->nextarc2==p)
    ! e0 u) R  ~! X1 o  g- t. u            break;
    $ c4 v( H) V3 G6 F        q=NextArc(v1,q);2 G& D  y4 m+ H; k# X' _& q& J
        }
    8 z4 @6 h3 _* a% c8 ]# D" N    return q;
    ' D) G: J: @0 H+ G" t1 U. O}+ ]8 N9 v1 f' T% J
    template<class ElemType, class WeightType>- n/ _2 \9 m9 n8 C' d$ w
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
      ^! `" y  a+ ^- a- @{  L" i% y+ a2 z, L) w
        if (vexNum == vexMaxNum)
    ( m; r. }* P, C1 y$ p: S        throw Error("图的顶点数不能超过允许的最大数!");, X& f6 v9 }1 k+ R
        vexTable[vexNum].data = d;8 w. w  n9 t* [! D; ?9 J
        vexTable[vexNum].firstarc = NULL;% q0 i3 S+ t4 k' S. ?3 f# j" v
        tag[vexNum] = 0;
    0 t6 L+ G4 `: f$ ^( t) P4 l    vexNum++;
      f. u5 P: b# A. F% x  Z2 x  D* e}, h7 j" z* S7 Z' D7 M
    template<class ElemType, class WeightType>, a' z0 q* [/ d& P/ P
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)3 p6 S# D6 d7 T& c
    {
    8 l. i" L( J2 T( [" F% m    MultiAdjListNetworkArc<WeightType>* p,*q;$ Q+ u; h9 `( [! p* s. F+ ?- S
        if (v1 < 0 || v1 >= vexNum)/ L' h4 _7 T& B' r1 D
            throw Error("v1不合法!");! n& U( {- p/ e& R: G
        if (v2 < 0 || v2 >= vexNum)9 s% |/ k" C+ P+ Q
            throw Error("v2不合法!");; f- r+ L3 _5 E) K! k& i) k" B
        if (v1 == v2)- k( C9 _  b. J
            throw Error("v1不能等于v2!");: q+ l* P: j( W( q6 e- P0 W
        if (w == infinity)
    1 g  H% l- W( I6 m        throw Error("w不能为无穷大!");
    , H  H# y/ Z& @/ ~6 o% u  @" j) \; E+ {& ~- k2 Y: D; M

    " t. L) O3 ^( |- ?2 W1 ^$ n    p = vexTable[v1].firstarc;
    ; s, A" @: D& j" C* _    while(p)
    3 W( |$ B6 `- c0 X+ l+ Y    {
    / c. ]5 ~/ r. [5 O; L3 }8 b        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
    . [- L3 @! e' j$ m0 ^% P        {5 P( H7 c* n- M: D/ U
                if(p->weight!=w)
    7 U% y7 E0 V/ q# A: q                p->weight=w;, @7 n3 z3 g9 j) U6 T( V! p6 b
                return;) G1 F. R5 b2 }3 L4 G
            }) s: W+ W- s4 `

    ! n  }( u9 o! r4 t9 W$ c* T' d        p=NextArc(v1,p);; J! t; d2 {1 g3 i
        }3 j, L1 D, M6 D
        p = vexTable[v1].firstarc;- H2 Q. U- d8 R
        q = vexTable[v2].firstarc;1 x# v* d' y; B9 c" X' z
        vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法5 l2 x8 Z7 T! n, d* ]
        vexTable[v2].firstarc =vexTable[v1].firstarc;3 E; r. _; F6 T6 g+ U& k3 R3 b3 u  ~
        arcNum++;
    & Q* n% Q. q1 l/ v. x2 U! T}& b) i$ R) Y1 g, T* C) H
    - b# N. [* V/ e, S! {
    template<class ElemType, class WeightType>& C% S! r7 z$ C; m( \
    void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)* s6 Z$ |6 G7 A/ C  [. l
    {
    . I' s* G) U; x9 k
    % G" t! C% R1 e/ c7 |6 D    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    ' I/ j5 u& w8 C' d    if (v1 < 0 || v1 >= vexNum)
    2 g$ \$ ~6 z) x. f5 `' _6 }        throw Error("v1不合法!");
    , X2 g& r4 g. C$ L    if (v2 < 0 || v2 >= vexNum)) v# Q" J- ?! s$ n3 c. B5 E$ c* n6 ]
            throw Error("v2不合法!");5 ~4 f1 z6 s3 h
        if (v1 == v2)
    , ?# e3 M0 k( X' C9 p        throw Error("v1不能等于v2!");2 u- m5 Z1 R4 m: l4 N  k

    6 d* O3 X' _6 g( t% K% m    p = vexTable[v1].firstarc;1 m6 D4 z" R$ B; U) |' Y
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)- ?9 z+ g+ u+ F: K
        {1 D5 g" O$ T3 W0 }7 d& e: ^. a
            q = p;
    8 c0 s# Z7 M1 s/ h; D6 {( ^  _        p = NextArc(v1,p);
    / R# V0 v/ E) L; M5 O    }//找到要删除的边结点p及其前一结点q3 J# a0 d' ?6 ?4 X8 D* D

    ) `# H  M) q6 M( x/ a7 Z    if (p != NULL)//找到v1-v2的边
    4 h& U  y$ ^% T/ |- v    {
    ' K  A$ s. C8 @, @# R        r=LastArc(v2,p);
    ; \  }" x, z4 V' }        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    4 c, d* @" L0 W* t& p0 q            if(p->adjVex2==v2)
    7 J5 {, Z& Y# {* h1 O                vexTable[v1].firstarc = p->nextarc1;
    . u' g8 F( D8 k* i; L0 s            else vexTable[v1].firstarc=p->nextarc2;% x2 h$ K. `) F: c7 a/ L
            else//不是第一条边
    9 R7 O9 z8 o6 Q/ q+ v  F  y        {
    : Y  e9 n1 H1 n) `  \4 {            if(q->adjVex1==v1)
    2 d6 r3 h1 G3 d& I! N: E: B                q->nextarc1 = NextArc(v1,p);; Y6 [5 J. e* G
                else% o& A( G4 f& u. k- y9 e
                    q->nextarc2=NextArc(v1,p);
    * ^8 m# A8 f# w8 S- o4 U% q/ p# f+ p  |, m- q7 K/ \
            }
    8 V4 @$ T; i/ L/ y        if(r==NULL)
    5 L3 K' E. Z/ X3 a- K5 A) E            if(p->adjVex2==v2)* R, ~* t4 N6 u) o
                    vexTable[v2].firstarc = p->nextarc2;: f. B# w# T6 X" R7 e' e0 L
                else vexTable[v2].firstarc=p->nextarc1;
    3 B$ ?# e8 G" j* C        else
    ! ~8 b' U; N) n' K/ ~- s        {, O& {$ D3 X# E0 u* E! x
                if(r->adjVex2==v2)% _" K- [3 d9 Z
                    r->nextarc2 = NextArc(v2,p);, A- b5 u7 |' B. |( |* \
                else: u9 E* Y0 P2 z# [, t/ ^0 ?- F4 I# ?
                    r->nextarc1=NextArc(v2,p);
    6 e' W. D+ j9 b; B, n1 E        }1 Q  ?1 |+ F0 R; o' k7 g4 D" z( L3 Z
            delete p;
    " d# y- }; ~5 v: J# D        arcNum--;
    3 `1 z' W4 j( K7 A$ u/ K7 ^    }
    1 ]9 y! S2 [7 W+ X# ^9 \8 {: b" W0 m! t
    }$ h$ C7 ~5 w* D. B
    template<class ElemType, class WeightType> void
    " G! x9 C, {- V) G1 dMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)5 v! L/ L" t, w
    {- h  E5 \$ B( z  r  o
        int v;
    ' ~. n% n4 l( H5 {+ q6 A1 G# j    MultiAdjListNetworkArc<WeightType>* p;
    5 \0 X2 z0 |' J) g0 o+ d    for (v = 0; v < vexNum; v++)//找到d对应顶点& \( }- e; e/ l' z4 Z: T
            if (vexTable[v].data == d)1 u9 K# ]9 R* P8 O
                break;
    9 h' H. T1 w+ X& l2 s' [    if(v==vexNum)6 B) [1 Y6 Z: I: e+ H6 m3 T
            throw Error("图中不存在要删除的顶点!");) G2 e0 j# Q& T# g. O

    ) c) A$ F  o/ y$ b  K6 z    for (int u = 0; u < vexNum; u++)//删除与d相连的边3 e3 o' {  n0 L
            if (u != v)3 Z3 L0 P8 k% {
            {2 n/ G2 Y5 v& }/ N
                DeleteArc(u, v);
    " ~, P% a/ [! b+ J% o% o' G$ J        }
    / c7 I, I& \6 t* T/ \    vexTable[v].firstarc=NULL;
    $ z5 o5 x1 r; O3 ~+ z# \5 J: ~7 s9 Q, }+ n9 v+ Y  g
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置% z% A6 R: m' {! U8 b3 G- o# ~
        vexTable[v].data = vexTable[vexNum].data;
    . X7 {, C# L- E; d6 B8 I& m1 ^. v; b    vexTable[v].firstarc = vexTable[vexNum].firstarc;# Q+ f$ x" o% D- i6 p" E! F, R
        vexTable[vexNum].firstarc = NULL;5 }& i2 p7 ~3 I/ G& R6 l- l1 N' N
        tag[v] = tag[vexNum];* f9 m2 o/ o: o- ]) e! T% Z
        //原来与最后一个顶点相连的边改为与v相连) Z. [% E8 }9 s
        for (int u = 0; u < vexNum; u++)
    ) A2 y# Z+ o3 r# z    {
    5 j' P! I1 }/ D2 G2 ~3 H; T3 }        if (u != v)
    $ }6 u/ I. }6 [- i8 W        {
      G2 Q+ J( V6 @2 Y/ z. E            p = vexTable.firstarc;' N3 w/ g( m! C+ @9 R2 q$ a. z3 d
                while (p)
    4 c9 |# q; Z& t  k9 G            {
    6 p& d, _3 p8 ?8 d                if (p->adjVex1==vexNum)
      P" B% Y! S: @7 n. F) s8 q& G                    p->adjVex1= v;* R" }9 y7 g- o- y7 B- Z- @
                    else if(p->adjVex2==vexNum)
    1 f+ L& x0 I2 L6 h6 Y- {/ I' s                    p->adjVex2=v;  C& b6 R( n9 C! o9 }
                    p = NextArc(u,p);
    . s/ H) ^% H, c5 b$ v" v            }- ]- i. G2 F3 v6 X& P
            }
    2 d- Z8 X% r; U0 [4 J7 y2 K    }
    4 ~; l! v: g, F% M6 m5 V! t6 [}
    . A* O3 c9 k; W- K5 K/ h///深度优先遍历0 d7 {  j/ P0 P  ?8 v
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    * j# i! O6 S( b9 P{
    * U- h" ~/ O9 _0 T5 x* |" O    tag[v]=1;
    1 U. F& s9 Y2 y  x, e0 N" n. W    cout<<setw(3)<<vexTable[v].data;; E' W. ?6 \$ l# K; `9 G# l$ s
        MultiAdjListNetworkArc<WeightType> *p;
    0 u( E! a2 w" J2 P* j+ o( M    p=vexTable[v].firstarc;
    # ?& R7 r' G! }; ?    while(p). l1 `; a1 U+ W
        {
    8 X' S5 |) h" o' C4 g) c        if(tag[p->adjVex1]==0)
    * f% X9 X8 y% x            DFS1(p->adjVex1);* Z  C6 V6 T: A1 H
            else if(tag[p->adjVex2]==0)
    / `9 u2 d1 V$ y2 }            DFS1(p->adjVex2);9 w* I- D: m& Z  q. b9 b( z/ y! v2 i+ Y
            p=NextArc(v,p);
    , `" Z1 U* ~& e& A0 }2 R    }  K& c( d, O* y/ }2 F
    }
    & E& ]9 m6 i9 u& Z% {template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse(); h' U" V8 z! w( |2 U
    {' ]8 n2 z" Q! ^5 z  A0 ^
        for(int i=0; i<vexNum; i++)
    * Q0 C( m# }  ]$ o8 f+ l        tag=0;
    ! g: u2 ]+ C* _    for(int v=0; v<vexNum; v++)
    - ~' M$ J2 j- a3 x3 f; i0 m7 X# W* ~4 p    {
    % e6 m! W0 r* Q        if(tag[v]==0)
    , P! N" f/ r& h. W3 D+ p            DFS1(v);
    % W( X* t* S; F% h' I& x    }
      e3 z+ u% X$ d& b+ Z/ f3 ^}5 Y$ Z. X5 h3 N' X. Z6 \( t/ O: f4 z
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()* K- U5 e& i' e
    {
    ' K, y, L5 M: g$ [% \0 a    stack<int> s;
    6 H# V# A8 L* e- g6 w    int tmp;; C7 ?1 H4 m# g$ x3 [; S
        MultiAdjListNetworkArc<WeightType> *p,*q;
    * E6 e7 _( n" S6 h    for(int i=0; i<vexNum; i++)- l1 x" g! D4 K8 d
            tag=0;
    . j9 F0 V. F- I7 F& x6 I! o    for(int i=0; i<vexNum; i++)" x' X5 q( @6 D+ X2 K& a7 s3 m! N
        {
    8 N3 k9 t" H7 h9 e; Y  `        tmp=i;2 ?7 I! n; x* o: j# g( B
            while(tag[tmp]==0||!s.empty())
    ) D4 J' r7 G0 I9 @3 i        {* R( j: S2 u2 O7 X
                p=vexTable[tmp].firstarc;
    3 _) ]: v5 o  G5 ?, ~6 R            while(tag[tmp]==0)
    6 g! X' [+ e9 V0 b8 J9 M9 k( x            {
    5 L3 P  j: t  r% k% B0 ~                s.push(tmp);
    ( r$ d1 _0 P: F; l" i                cout<<setw(3)<<vexTable[tmp].data;
    % H* Z9 A% Y4 i' Q" T                tag[tmp]=1;4 r/ `5 J" x* ^6 K0 o
                    p=vexTable[tmp].firstarc;2 s0 a9 _! w0 o0 X" r3 H- N: ]
                    if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
    & A( z: C6 L6 H                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);' D- a) \% j, z
                    //cout<<" 1st     tmp="<<tmp<<endl;- c+ Y! G/ F. r4 N3 m
                }1 [1 Y3 ^4 c" T3 q/ X, ?
                if(!s.empty())
    * R/ w) L8 M  D            {
    ) X0 p9 W# ?. @. m& w                tmp=s.top();, C$ B$ d) M  s9 x* Z4 P
                    s.pop();" ]* Y) H0 n+ }0 ]6 ]; j! a
                    q=vexTable[tmp].firstarc;
    ! |9 q! o+ y" u+ L  a/ i                int t=tmp;
    * T3 b, E; u" i. W7 y. T# W7 k( h                while(q&&tag[tmp]!=0)
    5 |, ^9 ]: q1 J; x4 M                {, G6 q+ v+ U2 j# Z4 q5 u
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);9 h6 M) G) ^/ x3 e4 h2 H6 J. W
                        //cout<<" 2nd     tmp="<<tmp<<endl;! X8 `$ Z! M; T1 m1 v% _5 z& H
                        q=NextArc(t,q);3 S1 m' l, d$ e( Y
                    }
    " q, l6 _% e8 u. [1 _( w                if(tag[tmp]==0)
    5 L" L" E& A0 y, X& z+ y* \                    s.push(t);) M4 d% f/ Z. J
                    ///1、对应上面连通分支只有1个点的情况
    + K: i! Z% B; e" Z5 ]& w, X                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈; q4 [' D9 K* |8 J8 Y2 z
                    ///tmp要么等于找到的第一个未访问节点,
    ! g" C, S9 }( l) v8 e0 e                ///要么等于与t相连最后一个点(已被访问过)- t- e! U- H. E
                    ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    5 t4 m5 @: L" w* G4 g" U  A            }& }& ?0 j0 l$ f/ i) I
            }
    / }5 _3 u8 `4 _2 M. H' s! F    }5 x/ t8 w' K# h. m
    }' D8 b" U( w3 ?# P
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1  o4 T& ]8 i& }2 P. T& U$ ?
    template<class ElemType, class WeightType> int# D" J( [! N; H9 P) `5 n) _
    MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)( e2 m& z0 B) x' ]9 D8 p  V$ @  o0 [9 M* @
    {
    , U# @5 M7 K- [    if(head==pre)
    , l: V9 x0 c2 r0 R        return -1;/ _$ J  D6 y0 i* b% |- e- R" U

    . Z$ u6 a: n- L; c" n5 n    MultiAdjListNetworkArc<WeightType> *p;$ `/ v" B/ [# d# s$ t
        p=vexTable[head].firstarc;
    # y# R8 L5 X. ?$ R& p0 G    if(pre==-1&&p!=NULL). ^) R' E8 m2 I/ V- o
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
    1 g5 ]: u( R! A$ l* m    //pre!=-1&&p!=NULL
    1 \1 H" o% T4 E3 @    while(p!=NULL)' L( Y' k$ z- c# x6 Z1 b* }2 ^  M
        {  U2 E; ^  J7 C/ D" L; o1 ~# g
            if(p->adjVex1==head && p->adjVex2!=pre)
    5 ^6 H& v! V; E  k1 @4 R            p=p->nextarc1;: q# N: B3 k# r
            else if(p->adjVex2==head && p->adjVex1!=pre)9 l& r) n$ f0 Z! m
                p=p->nextarc2;6 X+ t& r" i, t3 t# r' q
            else if(p->adjVex1==head && p->adjVex2==pre)% ^$ r, S' g* ]0 u
            {
    $ U# n/ E5 {' }$ S* [7 |3 c& d8 E            p=p->nextarc1;- S2 S/ q0 z0 U1 e) i3 y$ c0 _
                break;
    2 A8 k6 d: K8 z% K        }
    % Q' E' t' [$ H( t8 J1 N        else if(p->adjVex2==head && p->adjVex1==pre)
    3 F4 c3 V4 F" y) k        {
    % t) E8 J- f4 {8 z+ q1 i            p=p->nextarc2;% O0 d7 g8 I$ S) @6 J5 I( w% v
                break;
    # E% O0 S% Q. Y" Y" ]; F% z  A( k        }9 K% v& n9 W* `9 k! ?( \' C
        }( w: R6 _: E5 [, O
        if(p!=NULL)/ o& ]' F; K7 {# Z2 q& _
        {
    . A& k- E2 H! {) i$ `, Q        return p->adjVex1==head?p->adjVex2:p->adjVex1;
      L7 _  F2 v$ P# |3 I    }
    * Y) U2 }7 h& I; z    else- w: t, m& o& n. T; a/ s
            return -1;
    * M- k  r6 T- s% E6 h: ]5 O# {# J}' [5 X( A. L9 V& J. `

    7 F) k4 p4 n' [/ B. X% _8 V
    8 z5 g7 H# P' ]$ J" O  b3 v! J% Rtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    . J- @1 p9 k7 x: m{
    3 X# j  V: i& T7 T/ y$ L    stack<int> s;' o9 X; `! K' F/ [0 ~
        int p,cur,pre;6 }2 ?" E. u- z, e% Q
        //MultiAdjListNetworkArc<WeightType> *p,*q;2 @' S! _& C. a& v$ G# \
        for(int i=0; i<vexNum; i++) tag=0;//初始化3 g  ?$ S# f$ X
    7 ^. U: |# o9 L, p7 `3 L7 s) G8 N7 ^
        for(int i=0; i<vexNum; i++)
    7 E& P" d  `$ Y& |8 H    {
    ) y* j; r- Z% @# z' B  z$ q  j        cur=i;pre=-1;
    $ [* j. O% I( l- P1 \1 J        while(tag[cur]==0||!s.empty())6 P- Y  w' F. f+ W* T+ G; H
            {  X  q8 S* Y" {1 ~9 j7 `  C
                while(tag[cur]==0)
    * a) |1 P* N# s* ~7 z            {
    ; g9 X# E; F9 D5 w- S                cout<<vexTable[cur].data<<"  ";! F6 @) P1 f) [
                    s.push(cur);5 v" k5 c7 i9 f% r- y
                    tag[cur]=1;, x6 [% f' E- A: A: d: Y
                   //初次访问,标记入栈5 `+ f/ |9 g; R6 [0 ^
    8 R( g8 \2 `0 r$ u3 U4 z( n, _+ h- M
                   p=GetAdjVex(cur,pre);//p是cur的连通顶点. x# Q" q2 A* G! a0 [
                   if(p==-1)/ G' ^/ y' i0 \! Y
                   {3 `4 Y% |& @" \" O" p
                       pre=cur;s.pop();- D# ^/ ]$ p2 Y# G
                       break;
    ( N" B$ Y: i( j6 i# G# [               }
    5 H1 o2 J& W1 q1 c0 k               else
    2 x% O6 o. m. j. N, Z9 B/ Q               {
      y  K1 P3 }- r- B- {1 |                   pre=cur;
      ]& {- z6 U: |; Y                   cur=p;* q5 \9 F0 E4 u( S& i+ w# I5 y
                   }9 w5 X; W& P, P

    0 K- [: D. A7 `. @2 a            }
      T5 n) J& @# X  J0 n) r/ p" X            while(!s.empty())
    9 U1 s3 y( Y( \; W3 d, R; u            {8 [# d+ K! N% e
                    cur=s.top();' M. C! P  l: J3 `
                    p=GetAdjVex(cur,pre);* ~: a0 c" D9 Y5 h9 V+ r
                    if(tag[p]==0)
    - g0 P1 r5 M  [3 d                {
    - C) k# g5 m# k; ]% l5 O' K                    pre=cur;$ N, Y+ G5 m; `$ g8 Q( I2 o( n% g
                        cur=p;2 f1 K& z4 {0 y8 j
                        break;
    + o7 d2 L$ L& m/ }) R1 r                }
    ; F: Q' a# b% M* R, j# B/ y* r$ ~0 r& b                else; B1 M% Z% W% A7 M
                    {
    ; u+ D4 F1 L2 W                    pre=s.top();; ]) p. v! |" W! y( a  a: d/ t
                        s.pop();$ N" Q3 f  t4 y0 ]0 S1 P$ a
                    }
    5 R/ U  C/ {: v, s  t, e3 p! h0 A) }9 y  D5 F% B: S6 K
                }
    ' n$ v' D) m; R! Y3 b% k- {' X8 O1 a/ x6 ?/ N6 w
            }9 B+ M2 F5 u# s' X3 m
        }! s1 }) S4 B2 S* y5 `+ P7 e
    }
    / H; X, _9 ]/ G4 @/ p$ n' Y0 etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
    2 z: ^" \2 a$ o; g2 ?$ ?{- y* P8 x6 ~8 a) K$ D
        for(int i=0; i<vexNum; i++)5 l! S# ^' W6 Y
            tag=0;
    : F; S: N; s) `5 l! H& l    queue<int> q;7 u" M, Z* ^8 G0 Q/ e
        int tmp,t;
    / _, L! I  `+ }" H9 B5 ?! A2 `; B$ |    MultiAdjListNetworkArc<WeightType> *p;
    & ?" J+ J' F5 ?6 \8 n    for(int i=0; i<vexNum; i++)
    & v7 V1 O# b$ M9 n    {
    , e) }. W8 M* Z6 H        if(tag==0)8 H$ _# ^% P7 C+ J+ `8 ^5 L& i8 a
            {
    * W+ G' ^5 E& b, H  c            tag=1;0 t# [, G7 b  r/ ?
                q.push(i);; Z3 a! P( P9 U
                cout<<setw(3)<<vexTable.data;0 T5 u% u- P$ k* |
            }
    2 y) M, k2 p  Y2 i, T% z        while(!q.empty())
    * g& q: K2 q) ?. t) ~& E. W        {
    2 ^9 J5 L6 w) r9 B8 {# b) ?            tmp=q.front();; }* e) s0 W3 l1 v5 W
                q.pop();/ G  g: p% z8 [
                p=vexTable[tmp].firstarc;1 O7 C: I5 Y, D: c! |) d
                while(p!=NULL)
    3 t: @  p8 Y2 v+ I; T) A- R            {. p1 M. g$ L% i& L8 c
                    t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);+ U/ g3 r$ L: v
                    if(tag[t]==0)! }& K% R% L: k  h5 |
                    {
    1 C* @7 D0 K1 P- O2 A5 k  p                    cout<<setw(3)<<vexTable[t].data;
    6 x/ c, k2 z6 o                    tag[t]=1;
    * o; |- h, P3 n4 b) e$ q                    q.push(t);- {: y# H7 q# f0 A
                    }% A3 U2 b8 S8 ?9 e$ j
                    p=NextArc(tmp,p);6 M; }5 y  \' [2 n5 J: t
                }
    $ t  @5 s& P4 Q" ^8 o7 H# g/ E# Q! ~        }
    & g, n- B6 ~, V4 N    }
    " N9 d( G  B) f* q' s" f5 q- |}
      n% s" i! d/ s# Y6 u6 Otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()5 P2 f* T- p4 Y6 s+ u
    {
    1 @5 q9 w4 O8 [- f! I    MultiAdjListNetworkArc<WeightType> *p;
    ) s# e4 C" K2 ~; x    cout << "无向图有" << vexNum << "个点,分别为:";
    ) |" z+ c, e, G    for (int i = 0; i < vexNum; i++)
    ! c. M; L* _" w" \5 A+ r  v8 |        cout << vexTable.data << " ";( x, ~& D0 j+ @  j4 d5 D: ?4 C
        cout << endl;/ z: a1 p- s  _
        cout << "无向图有" << arcNum << "条边"<<endl;
    5 p- o9 h2 A: c7 K# b    for (int i = 0; i < vexNum; i++)
    + \# c$ E" G2 E; x4 S    {
    . R# Z2 t0 L/ v% N6 j* c5 z! |+ L        cout<<"和" << vexTable.data << "有关的边:";0 E5 V- ?) K. z( y: P; w
            p = vexTable.firstarc;' x* O  I1 K+ A. A. `, T  q
            while (p != NULL)
    . j, o% q- k+ g0 K% J9 q        {
    $ }8 g& t9 [) a            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";  g: m4 g1 J' F# a" p' p
                p=NextArc(i,p);
    ; _$ k! A2 L- F3 Q; x* l9 p+ s9 x        }0 D! z" [+ U/ L9 A1 C
            cout << endl;
    * n9 o- i  Q0 A    }% q, _& b5 V, m% J& c+ `& d2 I
    }% c; @& T5 O0 O$ Q8 I, T

    + n, G& N4 |1 |& q" W! f
    " R# Y, b$ t. }9 E邻接多重表与邻接表的对比
    ' q7 A+ e$ I4 s9 g) O# i) K- T* Q3 ?; x4 U% S; [
    邻接表链接
    2 K4 l" V2 I* Q$ G7 A在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。* H( {3 R- g+ O% r& H
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
    / @' I: I  q. Y2 E9 K为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。" g! v3 l' u7 N! V  X3 f5 Y$ z
    ————————————————
    8 L# U) s0 r6 i% Z1 J( ~版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。: E) i; }0 j" K1 d
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    : f$ j# T% E- a
    $ @8 J4 d8 p! \* A" ~% p
    * L6 e4 y% Q- D
    " D" j5 R+ z$ p% ~& v! v9 q; u% _: x5 e# M% g8 f* d4 C
    ————————————————
    & i6 m) ?% M$ I0 J版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。( N  R) E. T4 e4 s: a6 I
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    5 `# e# R0 B6 r+ k3 }! t* ]' t1 |) A+ W4 S4 f8 I

    % ^2 F) E& }$ m4 g) k
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-7-25 22:03 , Processed in 0.379369 second(s), 54 queries .

    回顶部