QQ登录

只需要一步,快速开始

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

    8 z/ @; I! h8 [  g" x  ?1 X图的存储结构——邻接多重表(多重邻接表)的实现7 b' `- T! I  c  q7 P& U
    7.2 图的存储结构
    3 A$ v7 {& _3 d$ D& e. t
    3 f5 C8 r+ H! \" n0 {) D) R' i7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
    & C4 F' F: d2 [! M" q邻接多重表的类定义% S. }' r4 o1 \. W$ H& C. x. ?
    邻接多重表的顶点结点类模板9 e3 P( ~$ ]9 q. `
    邻接多重表的边结点类模板, K9 c0 a& ^/ ]! j
    邻接多重表的类模板6 r  J1 y0 w2 B
    邻接多重表与邻接表的对比% w- \0 n8 F6 N0 U# `
    7.2.3 邻接多重表(多重邻接表)Adjacency Multilist" C& e0 x1 p+ a3 X) ?* J
    7 M+ E, n0 a) Q3 Q9 v1 s
    在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。
    + o6 N+ `& ]$ R- E! l在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。) P' |/ Z: p" f" A
    + x4 ~: w* G+ v
    邻接多重表的类定义* k! G6 x+ }. O
    1.png
    - d* u( G( ?9 X* R邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:
    9 K5 h: `* Q. Y/ [; Udata域存储有关顶点的信息;* Y( F" G+ C" _: G
    firstarc域是链接指针,指向第一条依附于该顶点的边。
    % T' \8 `8 G9 p所有的顶点结点组成一个顺序表。

    8 \5 @/ P7 U6 K! I4 ?! |

    - {" c( E5 [# X5 Dtemplate <class ElemType ,class WeightType>
    3 Y# _8 M: {& u% q% sclass MultiAdjListNetworkVex
    9 g, v8 |2 n8 i6 r" W" Q{
    0 i5 J" p0 M" P, a$ S4 R* kpublic:+ I! O0 ]7 G6 S( ~5 f
            ElemType data;; X& h9 d  O0 |- x' ^4 C
            MultiAdjListNetworkArc<WeightType> *firstarc;- p6 z2 E  i' r* a3 W- d" l  A; Q

    - w% F7 I# @$ M2 j/ ?' ]1 m  `        MultiAdjListNetworkVex()
    3 w- u" A2 r# Z1 }; K        {# f  X% F$ F. q; ~
                    firstarc = NULL;
    + m+ }7 J1 ]* |: N+ N3 [        }9 t4 x9 U6 x; W! c3 E+ p; ^/ K
            MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)8 o; w8 t+ i# ~" |0 G9 n/ L
            {8 N: e4 ~. N" q- c; ]: r) b- `8 K
                    data = val;
    & n' e. d4 y% r$ L* m. W                firstarc = adj;4 w* z  b% e' F8 Z2 n; F
            }. z& X$ }" s" h
    };& J  L: {+ V% `6 m6 z2 D3 i
    ( ?, T6 {+ {. n/ T0 ?; x. n9 d3 @: x
    邻接多重表的边结点类模板) d- E6 |6 `* s0 W5 u6 F+ a/ m$ K/ ]& q

    9 Q# S( ?3 _: ?3 P! p0 b' h6 Y在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:% K% k7 c; N8 ~! c- i$ E: `$ F; \
    tag是标记域,标记该边是否被处理或被搜索过;2 y5 h& y/ ?( j1 Q0 B4 |
    weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;3 {; B% m1 q. M0 q7 b8 q0 p
    nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;8 f  C1 h1 [  s" t: m9 J* [) O" t# l
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
    / L( [2 L$ y) E' i$ R9 G0 I0 `: R+ I( Y2 ?- a8 w
    2.png 3 ?! m  P% d% F) {9 y" ^7 k9 I
    template <class WeightType>
    , o. k( [/ I4 @, zclass MultiAdjListNetworkArc
    , |* b5 R% {# ~$ j% l' F9 @{
    2 A* |" L+ _$ V, s8 Rpublic:
    & d' |" u) M4 F8 r( r! c& e    int mark;                                       //标记该边是否被搜索或处理过
    % s4 O2 k" G1 r; t2 u2 y        WeightType weight;                              //边的权重5 V( R- F  J9 q9 ?
            int adjVex1;                                    //边的一个顶点, ^. b4 k* f( S' S+ R7 T, ?
            MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
    , [$ x6 T  m+ ]4 c& M+ l        int adjVex2;
    ! [& {$ J$ Z% z; {, U+ E" m        MultiAdjListNetworkArc<WeightType>* nextarc2;/ e7 \4 z9 C- w: n; d
    9 ]$ J6 S) C1 x" _9 S
            MultiAdjListNetworkArc()
    0 ]8 Q2 `# e. K        {7 @! @, a& ^, O
                    adjVex1= -1;2 \/ h0 v) h! Z
                    adjVex2= -1;7 ]1 ]# j! {( w# e4 k" E
            }/ Z/ @4 n1 Y$ ^* T3 q, W* e
            MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    / v$ J9 y( I6 B& Z- t$ G; \- b        {
    & H0 P$ F6 u. A+ F                adjVex1 = v1;       adjVex2 = v2;
    2 |& |- b$ F4 W$ J/ y; T                weight = w;
    $ S4 h, ?2 u9 y) a+ W. Y& f                nextarc1 = next1;   nextarc2=next2;) t. J0 Q% a2 V$ L
                    mark = 0;           //0表示未被搜索,1表示被搜索过4 ~! b% p* h* K8 g
            }
    1 C6 L3 o; A, m) v6 A7 R2 ~
    & A$ Q( r0 P3 A8 L4 \4 z" w: M& E邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>1 b8 c" y9 h  w7 s$ j/ }: K5 @  y
    class MultiAdjListNetwork
    9 }+ q8 T( ]: p; k3 B/ U' P! I{
    6 M4 a9 H9 J$ b$ uprotected:" f% G  O: G- I' @: L
        int vexNum, vexMaxNum, arcNum;, u: v/ s* D9 n' s- {6 S
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    " T, V  }' E% ?6 F    int* tag;; }- O( i; G/ t( z& w
        WeightType infinity;4 d' ]2 ~2 D% m5 M

    - `) `6 p+ _2 _0 X, K% Npublic:2 }5 R2 i1 O- J6 f& [9 \
        MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    7 O( Q' Y" M9 _' e0 b( V7 f  H6 Q2 C6 E
        MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);3 g, m! |2 D, N$ B2 T% c( J, G6 j

    - ^- v% J; D5 x  k% I' r6 [; ~7 G- O. P    void Clear();
    - Y) z! b# ]. K4 d( w    bool IsEmpty()
    6 _/ Y9 E* C) `: Z- m    {
    5 f) j. `8 n/ O        return vexNum == 0;
    9 k8 h' y* _' U3 C    }
    & t; w# o  ?0 k9 }9 h( m. r    int GetArcNum()const, c! O8 b5 `8 Q6 ?
        {
    * m- T# U4 H  a5 A$ {/ p0 x        return arcNum;) s. }. P2 \5 L( K3 E9 c0 M8 W, R: m
        }2 X. q- p6 H# l0 R% H2 ]
        int GetvexNum()const
    4 d+ @0 r$ @. _4 \; {; ]; _2 n; p0 W    {: |' |* n  H; S6 ?1 T
            return vexNum;. f% F3 W+ C* ?5 O/ \) `0 Y
        }
    , T  I( N# M% k' _2 g, z
    ( q5 D2 l- d' c1 ^
    4 i; Y/ i) h) i4 G    int FirstAdjVex(int v)const;$ S3 Z. c. O) I/ C
        int NextAdjVex(int v1, int v2)const;
    3 N: \6 O! r$ w- {* T0 M* K  g    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    , `- z0 {; Y# k$ I+ H/ |6 ]. u: Z    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;+ ^) J5 f5 b; L4 k9 p  {7 I! _

    4 Y; s5 n$ F+ o6 r    void InsertVex(const ElemType& d);
    9 x% o, V+ I- }# C, d3 W    void InsertArc(int v1, int v2, WeightType w);3 }9 e, Q7 @" z& y' y6 Z1 I
    8 g! K+ v! t- _2 G8 J
        void DeleteVex(const ElemType& d);
    3 Q! D' Z' o2 a8 Y. n. \    void DeleteArc(int v1, int v2);
    8 I- [0 J; {3 _  M/ b: L4 g6 C2 q1 M& J/ F. q; A# v! e/ |
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);$ U/ A& I% g  Q3 c
        MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
    " X" q; b! a0 U- F
    1 w9 B: }" V% Y) `    ///深度优先遍历  C, A/ {; S! V/ U5 {- f4 s
        void DFS1(const int v);
    * c2 M3 B6 M0 V, U* M* [    void DFS1Traverse();
    . v8 _9 M' }5 d2 O    void DFS2();
    3 o4 X0 s0 K4 C- ^' ~/ x
    ! c3 {3 t( g) {0 D8 J9 @1 }6 v    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    5 Z" D4 k5 `  x8 \% R    void DFS3();
    . G/ W6 X4 G# H- M" b/ W4 h- t! s6 p$ d* }+ G/ L
        void BFS();5 `) H. @  F3 X( J: G7 I0 t
        void Show();+ N# W/ Q* E) h, s. I, n
    };
    ; z  P, ]% E/ A) C3 n+ O7 E4 G* E, u! f
    2.函数的实现
    7 w# T! q2 x6 f/ {  c研讨题,能够运行,但是代码不一定是最优的。
    6 O# A8 F) _! z3 }5 q: g2 P' c: n& }  }  f7 K: F
    #include <stack>
    % o) M" b2 X% w$ B' R3 ?; E#include <queue>, P) c  R# P- a8 m/ s+ L

    ' x1 Y8 t6 j, v7 _template <class ElemType,class WeightType>
    2 s+ a; {- x% v% t/ w6 ^5 tMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    7 d/ c' D  H5 [8 z# q{
    7 E8 y9 H: l0 `: S" m7 E    if(vertexMaxNum < 0)
    # N4 c* ^- M0 v! k0 B# \        throw Error("允许的顶点最大数目不能为负!");
    / o# `, c( g- X+ i    if (vertexMaxNum < vertexNum)$ M0 y. g9 G! C
            throw Error("顶点数目不能大于允许的顶点最大数目!");
    - c6 R  \3 v$ m, U% T: B    vexNum = vertexNum;
    2 g% e9 `# p) e: j2 x+ }    vexMaxNum = vertexMaxNum;
    " c* ^6 E. {! ?* u. |6 m, @    arcNum = 0;3 M$ r3 \# L7 c+ L6 H9 M& |
        infinity = infinit;
    . x8 E  L& {; s0 y$ ]3 T    tag = new int[vexMaxNum];' J7 F# \7 I; r* P& d& G
        vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    / d5 D5 D% b0 M+ _- @8 Z2 m, f    for (int v = 0; v < vexNum; v++)
    ) Q4 J- P' H0 Z4 c    {9 B; ~' G+ {" t3 U* l
            tag[v] = 0;
    0 `+ t$ S# |2 C/ I        vexTable[v].data = es[v];  b+ @7 c/ `8 I- r1 F
            vexTable[v].firstarc = NULL;2 s* I# s% v1 e& z, `
        }6 N% `% i; h/ E6 W' K( E1 c* n8 b
    }
    4 o" Z9 T7 {  |template <class ElemType,class WeightType>
    - O; Y! U; A+ j0 `- mMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
    " {5 |' S/ a' v' b* y% C  L{9 Q' K; a8 z9 |5 \+ b/ h8 t2 W
        if (vertexMaxNum < 0)9 H: O1 o! r+ P+ A. b
            throw Error("允许的顶点最大数目不能为负!");1 l" ~8 y" I3 w+ R
        vexNum = 0;6 o0 P6 u& Z3 E1 N8 P
        vexMaxNum = vertexMaxNum;7 j7 i1 e, c3 Z6 Z+ h& P
        arcNum = 0;) J0 S: I  W3 r7 _9 G4 ]
        infinity = infinit;, L. C2 Y! [/ J& B
        tag = new int[vexMaxNum];
    : C1 N1 A1 j" C+ J) }$ B    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];1 \6 h) e) W( [& q
    }3 c: i/ B" R" @) w: k$ A
    template<class ElemType, class WeightType>  r! X' ~8 ~) f
    int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
    * o) F8 X0 K# C7 D- x! ^, G{
    * W6 R! w; y4 e8 ~" s9 x    if (v < 0 || v >= vexNum)
    6 c% F: N, W% u( {, \% H3 W        throw Error("v不合法!");# q' P. G- n# }
        if (vexTable[v].firstarc == NULL)
      ^$ C9 H* @; r        return -1;
    ( K9 P" d* @% w    else
    3 k9 Q9 b2 w3 g. V+ Z  ?! n" o( x0 H        return vexTable[v].firstarc->adjVex1;
    , F$ P: f" e  B+ Q}: g* \" |2 _9 A) f$ o

    , c5 }7 Y, Z' O, otemplate<class ElemType, class WeightType>3 ~9 r7 J' {/ M! [2 G
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
    2 ?4 r% m+ q% L( V9 G# F! A  M{3 s* @7 @" t3 r; E; `! k
        MultiAdjListNetworkArc<WeightType>* p;
    0 M' y4 @# [9 P& f, ?& o    if (v1 < 0 || v1 >= vexNum)# Y" `6 A6 e% X" Y0 x, ]
            throw Error("v1不合法!");/ Z7 a1 A8 M' K3 ?7 S6 L- T3 K9 v# G
        if (v2 < 0 || v2 >= vexNum)
    1 l/ o' {; ~3 M% n7 F        throw Error("v2不合法!");) Q7 Z+ d0 O4 f; P
        if (v1 == v2)
    2 m" T( [1 d1 P1 L3 L        throw Error("v1不能等于v2!");
    ) a7 |0 j: N) Y: i    p = vexTable[v1].firstarc;8 H* o* a$ v. x8 L" H
        while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
    1 b: y* t$ m" E* u' }5 o" N        p = p->nextarc;
    ( G  c# d( k0 H8 P4 }    if (p == NULL || p->nextarc == NULL)6 I1 V; M+ U7 j& P$ S' v: L2 V. g% W" j* R
            return -1;  //不存在下一个邻接点
    , C1 f3 Y1 p1 K4 j    else if(p->adjVex1==v2)/ O8 |" y7 l7 x# W4 Q
            return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);' p; \' R. r9 ]6 e: A
        else" ^0 H+ |; p4 T: ]) u0 q5 X
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
    ! H$ d1 Q$ A1 q3 w# d% r* ^9 N4 c}
    * F4 l: W9 Z0 T: |; U5 v1 ?template<class ElemType, class WeightType>/ p+ v) e- n0 p" t, j
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()/ X9 ^2 _$ B3 K: h2 i2 Q
    {
    & [' }; n& q/ ?7 b$ J    if (IsEmpty()) return;
    4 |! a  r1 E5 w) H6 `- q    int n = vexNum;
    3 k% E5 e& \. Y6 W( P    for (int u = 0; u < n ; u++)
    1 m; N) _0 |9 V" I7 F4 g3 c        DeleteVex(vexTable[0].data);
    , T. x! S5 I4 n/ r: P% l4 w    return;
    ' I; R6 ~5 W# ~$ I  l( ~6 Q}
    0 i. m4 E+ U$ U" g; T1 ?: Wtemplate<class ElemType, class WeightType>/ w( P: |; K' ^( F8 b' u
    MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
    * F  k3 J% P7 K. c{; V3 c* \# x5 o5 T4 y* t# \
        Clear();# Y' a4 ^1 Q$ \$ G( o% I
    }9 S: }+ ~  A- m1 N
    template<class ElemType, class WeightType>! q) v' G) d/ V( X  c- z% S" }9 K
    MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    9 o" g: D# }" [9 _{! |' H- w  Q  v- X4 o
        vexMaxNum = copy.vexMaxNum;7 l2 @/ w9 ~. r' W  C; S
        vexNum = copy.vexNum;
    2 n; m, g; ?+ D* X3 l' n+ H4 r    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    9 ?: P7 ~! K8 v- i! n+ \) E9 {    arcNum = 0;" h3 O7 b6 ~7 {! v8 s0 I& s( u. B( Y- L
        infinity = copy.infinity;
    9 g8 ~; j; d# m0 b    tag = new int[vexMaxNum];" J7 S' e# ~, _; D; ?

    % {8 F) }$ v5 q/ }0 x* R; E8 G7 T8 I    for (int v = 0; v < vexNum; v++)4 @, W1 k+ Y: i9 n
        {( ]( t; N! G7 D# y; ~# J
            tag[v] = 0;8 v" Y2 c0 w- v. o) e
            vexTable[v].data = copy.vexTable[v].data;
    5 \5 F% @% m! K' J/ Q9 K; s/ [        vexTable[v].firstarc = NULL;1 c' I2 P8 h9 M+ N0 }
        }
    1 Y7 F4 {1 H# m    MultiAdjListNetworkArc<WeightType>* p;
    * u' o2 _, R5 Z! U9 n% w; c3 K0 A0 t5 Q
        for (int u = 0; u < vexNum; u++)$ @: @* w1 `9 q1 e( I$ J
        {
    3 [8 b& k1 q0 ~  O2 _" F" h$ d; ?        p = copy.vexTable.firstarc;
    6 G3 g+ S/ Y. ]- _  B+ |) k        while (p != NULL)
    % s+ _3 s6 l1 `) w7 N5 ]        {* @3 w' G- p: p5 _8 W3 _$ x
                InsertArc(p->adjVex1, p->adjVex2, p->weight);
    5 h. z/ l3 T" k/ b            p=NextArc(u,p);3 Q6 f3 r' V) r( h/ }% S' Z& Y
            }4 U4 D0 w( Z7 ]1 i% E
        }
    # H2 L% n  Z% N( _. b4 b; `}
    ) b- A( u6 b& U- g) m$ P) b* Wtemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&+ P# X# |0 H6 Q( e" |
    MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
    # {) X- F$ v# W" x# R5 @8 d{
    + `7 k# [& ?  ^9 J' L) S    if (this == &copy) return *this;
    ( p" y" T2 X5 s! J; i! R. {    Clear();' j' ^0 _) P/ f# @4 r$ U* E, Y
        vexMaxNum = copy.vexMaxNum;
    % f6 {0 j2 m+ x' Z( K    vexNum = copy.vexNum;
    9 }5 O' o( u( n0 d- R    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    6 a( h; _  \+ }2 N    arcNum = 0;* ^* n' ^5 }9 q$ e; ^& A( C/ w
        infinity = copy.infinity;% ^( v1 I! v' j$ f  W
        tag = new int[vexMaxNum];
    ( P5 n1 {* |" e2 Q2 s+ w5 T  y( c- ?" f) r8 S$ q; F# V
        for (int v = 0; v < vexNum; v++), U% C0 C% n' h1 f
        {1 S: L$ L) g% e
            tag[v] = 0;
    7 B% K+ `% i* e/ f, f6 m7 p8 _7 u        vexTable[v].data = copy.vexTable[v].data;
    ) ?% n) @* D5 T2 [6 M        vexTable[v].firstarc = NULL;. u  y7 w* p, V: Y5 q# }" W; N
        }9 h( r$ X; F8 \( j- h" @
        MultiAdjListNetworkArc<WeightType>* p;
    ; t) u/ s: }. i, m% O4 o5 h7 V. `% _$ T8 B! {
        for (int u = 0; u < vexNum; u++)
    + u( ^7 [, ]1 F2 m3 h0 @  d9 ~    {
    5 L. W0 y! t% [& k  M( I! T$ g        p = copy.vexTable.firstarc;* U3 J' x2 r1 y8 m8 H8 i
            while (p != NULL)
    5 c5 v+ }( S( E3 D        {
    6 F" a1 V2 ]9 x2 ^" u# q; G1 Z            InsertArc(p->adjVex1, p->adjVex2, p->weight);' n4 F7 g1 \4 w( D  t; M. ?/ U$ u
                p=NextArc(u,p);  z) E5 c  @9 `8 \% K$ B
            }
    * o0 w) L% l7 u2 K' m: u    }
    7 s) @% u- F9 r7 t( E    return *this;  T8 M2 u! ~. t8 l5 o9 |
    }
    ) u. k7 s8 A, C! ftemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>** Z6 ^* W; F2 k0 i+ y+ l' h3 U4 G
    MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const0 l& B! @/ I& f/ V1 e$ f3 C# V
    {
    ) g2 ~' S, k# q; o& s; i+ Q- L    if(p==NULL) return NULL;: a7 P$ k7 B/ ~( J; J: @1 O
        if(p->adjVex1==v1)
    # Z6 }$ ^  ~( F. u6 O        return p->nextarc1;; u% x' }" q, S5 J. d8 L/ r
        else$ ]4 F) ]8 V- p3 a2 V6 Q
            return p->nextarc2;3 g# ?! ?# P) C! M1 U' m
    }# \( s7 a2 d9 z4 n* K/ Z; V
    template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    ' l9 `. S2 U! ^3 o& b/ M( WMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    + V0 N$ v# M% {  C, P{
    - j, C. L" p0 }2 G. _) T# D) W( j    if(p==NULL)return NULL;6 _6 F1 |8 `) a. `3 K$ Y
        MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    / \3 x& Q& M7 Q0 H* U' V, u    if(q==p)4 M) ^7 \+ X  w* ]
            return NULL;% f2 L9 Z* w& E0 c: }- V
        while(q)
    1 k( f7 @! L: R2 b# B1 Y/ l7 s% m    {
    2 R. C$ x2 v" H% `5 c8 c        if(q->nextarc1==p ||q->nextarc2==p)  J4 o+ k0 B9 g
                break;% t5 b2 _1 ~3 M1 X
            q=NextArc(v1,q);
    ( I' X/ @0 y* Q) F; p" g    }
    - H3 u* u, ?3 Y* Z) q    return q;& _% {( ^: b! L0 {6 I) N% }% }
    }
    1 O9 D9 a4 O. t! x) ptemplate<class ElemType, class WeightType>3 Q% Q; F/ h* O1 a7 G' e3 a6 H$ T
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)4 B1 r' j# b& O/ h
    {+ a  q8 N( n: H. j
        if (vexNum == vexMaxNum)
    ' Y# x+ l- q7 g2 B        throw Error("图的顶点数不能超过允许的最大数!");& I0 C+ M) Z) H; {% v# n+ x
        vexTable[vexNum].data = d;
    + ~( J/ H; `3 T/ f5 ~% I- U    vexTable[vexNum].firstarc = NULL;
    % s! x9 V- t, g4 n1 Q! @1 A9 d    tag[vexNum] = 0;
      I5 I1 @4 x' k& E& @4 E) a    vexNum++;* R& ^+ l0 d& i7 i% P& u
    }" E- o/ k1 X) _8 r9 N( s
    template<class ElemType, class WeightType>7 y) U1 c' \* M2 K
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w). k0 h; @$ X0 p) r+ k$ _1 F
    {8 _9 ?' E( i8 ?4 A$ o8 ~* {
        MultiAdjListNetworkArc<WeightType>* p,*q;
    ' Z" K" I/ h  l6 g5 z  U1 u6 y    if (v1 < 0 || v1 >= vexNum)
      @$ q+ ^2 R$ d        throw Error("v1不合法!");8 y0 X+ i- q1 S( H* G
        if (v2 < 0 || v2 >= vexNum)4 {* ~% C4 C# n' F
            throw Error("v2不合法!");
    , P3 R( R# [& Q* A0 l  S' j    if (v1 == v2)
    , n/ t& W5 f8 L. _1 z        throw Error("v1不能等于v2!");
    % d3 r$ u" {6 z& w$ {    if (w == infinity)
    3 \2 Y% b7 b" R6 F, b$ m, p        throw Error("w不能为无穷大!");. }  v! V9 G0 I+ N9 a9 z

    & x8 ^: ?, h* F: x& p! i  v  K) R( S: q5 X' L; P4 F8 n
        p = vexTable[v1].firstarc;& a' W. u  u3 l" g, a
        while(p)
    % A" G$ z7 |5 c9 q2 {( |! ^: @    {
    4 o3 Q9 V5 @4 l8 }0 `        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
    ' O) g# C  q% o" i6 ?! x        {
    * c& [; N- D) H1 Y# X            if(p->weight!=w)
    ; y( s5 ?: T  M( ^                p->weight=w;" H+ F) u3 Z  j! z
                return;+ t2 u" a1 L8 D  t
            }
    ! h% `( X* W' b! E" U
      I& m2 I/ v3 n- p( w5 O" A        p=NextArc(v1,p);/ S1 f2 q% H* {) Z
        }% P0 Z$ D4 x1 X- }# Y* \
        p = vexTable[v1].firstarc;
    ; b8 ]# ~9 }: n* I3 D  l& g/ `    q = vexTable[v2].firstarc;
      @8 B: q5 ~( N6 G3 Y/ e8 p    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法% ?5 R9 C5 d( T8 P1 e) E
        vexTable[v2].firstarc =vexTable[v1].firstarc;
    ) e+ M5 f- ~1 @5 Z' W    arcNum++;
    4 T5 X  j2 q# c' x4 q}
    . J* k5 v6 l! C3 u" f* y3 k0 f- e: e8 R: N% J$ m
    template<class ElemType, class WeightType>
    * }0 V# z/ u  w' Ovoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
    / X. M5 [- z6 _! |+ Z' g' W  Z{8 T2 }! K/ _* o

    9 R1 p) z3 m( O6 ?5 m: Y! z2 l: m; Z    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    7 r, ]. y4 ~! v9 K* i1 Y" z    if (v1 < 0 || v1 >= vexNum)  N" ?, U: W: r& \$ D
            throw Error("v1不合法!");! h/ ^( s; Q  ^, h6 j0 U; V
        if (v2 < 0 || v2 >= vexNum)+ d: Y, I1 J8 f& ]
            throw Error("v2不合法!");
    - S( m  @8 i, K6 O* `' }! Y. c' V    if (v1 == v2)& W, c8 [3 z/ W: d7 f/ e
            throw Error("v1不能等于v2!");: w! ?6 I2 [! T3 q

    0 k. D  Q5 H, U& f: B$ L& N    p = vexTable[v1].firstarc;8 |$ Z" Q+ y+ B( j/ R
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)0 _2 _: ~5 [# I
        {- _+ N6 T( j2 w! ~% n' E* j
            q = p;. }9 R  K! s! e2 A9 u
            p = NextArc(v1,p);
      o9 D# B& a' L& C! w    }//找到要删除的边结点p及其前一结点q9 d% {1 }! f% p; b, P- z& c( |
    3 _' U7 u! t( E4 d& T( T
        if (p != NULL)//找到v1-v2的边
    ! X+ m, E3 m, t. n    {( Z6 S% q1 k4 \# M$ p7 j: }
            r=LastArc(v2,p);; u& p5 q* y/ ~" d6 F$ `/ L3 b& Q
            if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
    8 q0 ^! W, W* f5 N) Q            if(p->adjVex2==v2). K7 M6 }0 A$ t* F1 \& ?- H
                    vexTable[v1].firstarc = p->nextarc1;
    + S* E6 U: G& n$ t1 W; c  p            else vexTable[v1].firstarc=p->nextarc2;; ]3 I5 C! S: H6 [, o
            else//不是第一条边
    : ^* ^4 Q* F( ^. j* M6 E$ q# o        {
    ' z5 @, K2 E) u! e            if(q->adjVex1==v1)
    % m1 F* G- f" I, ]+ y: Q                q->nextarc1 = NextArc(v1,p);
    7 b+ h# y( i( {, C- Y: e1 ?            else
    7 U2 N7 P: v1 W8 v7 n" `* E" p0 H/ ?                q->nextarc2=NextArc(v1,p);
    5 d' z* w) _9 H- Q; o* l; K
    & ~* W# I# p* E        }) S- ~- d0 I8 G
            if(r==NULL)7 A6 N! _6 C  \' J" R
                if(p->adjVex2==v2)
    * f$ z  ^; M; u7 {- T! A! A                vexTable[v2].firstarc = p->nextarc2;( }" P. d7 u& ]& m
                else vexTable[v2].firstarc=p->nextarc1;* X6 g- g: |4 I+ S9 h" \
            else
    $ K4 s8 A# k+ V- A% P. v        {! y% ~! c: s5 D/ J. c3 Z, E  N
                if(r->adjVex2==v2)4 Q' V9 {$ C2 F
                    r->nextarc2 = NextArc(v2,p);/ B4 |. `' C2 q8 K9 X% q% C
                else
    # h) V) R2 N# V" S( b                r->nextarc1=NextArc(v2,p);) D" G7 \# v) A, T# n, y
            }  ^) n" l$ l7 `7 \: t3 T3 f
            delete p;
    ' \( x2 T( N6 a/ V4 d& `* _        arcNum--;
    1 e- F: }3 f: D! U( V    }& I+ h/ v( v+ S

    2 Y% ~' z3 a- Z6 D( C}
    4 W; {  l1 Q: L8 I; k' }template<class ElemType, class WeightType> void
    7 G$ b% E8 y2 i) R- |1 ZMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    / y6 P; X' r1 }6 ^* S! U; F{" \& l2 j; ~  n6 Z
        int v;- s1 d% S- k/ R
        MultiAdjListNetworkArc<WeightType>* p;
    , @% D2 t0 j9 V% T, F1 E$ t  o* z    for (v = 0; v < vexNum; v++)//找到d对应顶点" T2 o( ~5 I, d
            if (vexTable[v].data == d)8 s" {3 {) r( S) N0 ~
                break;- {0 e5 \, Y+ P% Y, s
        if(v==vexNum)+ B. Q6 ]) J2 N& @7 z8 r
            throw Error("图中不存在要删除的顶点!");
    # B2 K8 }1 V7 y0 J- b5 D" P3 [. L0 @$ a: Z0 v* D5 k* a. r! \% N
        for (int u = 0; u < vexNum; u++)//删除与d相连的边, w2 e3 P* N+ z; G3 A1 \5 |9 q+ t
            if (u != v)6 H- l) L, c! |* M8 w
            {, o; B! C% Q4 G& R( n' G4 r2 L5 {% g
                DeleteArc(u, v);
    9 I# ^9 Y+ x8 ]  ~, ^! h) \/ q        }
    " U; B0 Z  U9 f% S2 J; w  {" H/ ^    vexTable[v].firstarc=NULL;
    : d1 j( g! L  T, W( h2 V, s1 H$ R, q+ ~7 H
        vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    ) V! ^( a" b' n$ P3 e- W    vexTable[v].data = vexTable[vexNum].data;$ }1 t* U) W1 l. ~% ?# \
        vexTable[v].firstarc = vexTable[vexNum].firstarc;
    9 g; `+ L2 T. x8 i    vexTable[vexNum].firstarc = NULL;
    * @+ W, o) f; C    tag[v] = tag[vexNum];$ D. d4 E6 G+ R$ d
        //原来与最后一个顶点相连的边改为与v相连& O; p* G4 I+ K" o1 h3 D/ T3 D8 o
        for (int u = 0; u < vexNum; u++)0 d* B2 `) R" M' O( N& T7 Z
        {0 K( @& C! p) u4 W: W
            if (u != v)# c' ~2 @1 s8 ~! n) ~+ ?9 J
            {
    / a) D+ \) N" O! f+ x            p = vexTable.firstarc;5 {& f7 r; k' n( B5 h6 q& K
                while (p)) I  t9 }& P' p5 M, s" P
                {7 B* Q3 m+ ?( {1 }/ Q4 O& a% E$ a8 v  J
                    if (p->adjVex1==vexNum)
      L, r- n* X# D  K, T                    p->adjVex1= v;
    / v1 h" a2 {4 h' z5 y1 f9 _) c) b                else if(p->adjVex2==vexNum)" J6 A/ K+ `2 X$ X( w; p, s
                        p->adjVex2=v;. Y' @/ `/ w' \
                    p = NextArc(u,p);
    ( j+ ?2 M6 L& n3 d7 U% {            }
    ' y! n7 z7 u# n# L        }( q, t3 F# j: v# E% C
        }
    , [- N; n  u; C6 ~}, X: \7 \  s; S" m
    ///深度优先遍历. K" s. u3 l% ~& Q3 l
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    " O$ c. k  s8 O5 w  |{9 v9 g$ f4 b( i" P& t* G) H
        tag[v]=1;
    ( c* c, `3 ~$ m# J    cout<<setw(3)<<vexTable[v].data;
    : S. S7 n; {4 x* l    MultiAdjListNetworkArc<WeightType> *p;0 r4 I% E. g) |1 }
        p=vexTable[v].firstarc;3 G' ^7 K5 {8 W
        while(p), X- r2 ^( m. D4 G
        {
    # m6 S* K$ ]1 g& p# W. m        if(tag[p->adjVex1]==0)
    # I* U- _2 v$ h# V1 F8 B, t0 h+ T) K            DFS1(p->adjVex1);8 i, ?- J8 b% Q8 T, Q+ E0 H4 h9 B& ]6 ?
            else if(tag[p->adjVex2]==0)
    , P% F' M: d$ g' \9 X- Z            DFS1(p->adjVex2);! d# t  \# B/ `3 P+ M
            p=NextArc(v,p);
    6 r7 }7 v) ]: `9 l" W2 X$ `    }
    ' \5 ?. O+ }8 c}
    . |7 [% u. z- _: g3 O* ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()! R. V2 y. O8 m0 ]3 @
    {
    $ g' b9 ?# J0 g$ w    for(int i=0; i<vexNum; i++)
    * g3 V5 k: w+ T/ X% N" u        tag=0;2 g6 c- B3 w; q
        for(int v=0; v<vexNum; v++)
    % t. M# x3 T, A( t    {" |+ K  T# k6 z; |
            if(tag[v]==0)
    : I0 e0 r: K0 W% @( N6 \* d8 I            DFS1(v);# r9 M! X$ R8 ]! @" B
        }/ W2 U& I: ]/ d% _. m. H, {8 J
    }- o" Z( ^/ v$ p* ?, P
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 T. @8 u$ e% x, W, A
    {* F; G7 z' \: e5 y4 j
        stack<int> s;
    ! Y4 y2 X) ?: \0 h    int tmp;6 n2 {1 b0 C3 C# r% s/ M5 j. w
        MultiAdjListNetworkArc<WeightType> *p,*q;( e% C3 E' b1 N$ k- ]( k
        for(int i=0; i<vexNum; i++)9 I- G" y2 u, }, Z6 |( {: k/ ~
            tag=0;  K0 s+ [1 }  F; J- L9 }
        for(int i=0; i<vexNum; i++)* i) H9 N! }8 Q2 H1 O$ F) H  K" R1 A3 W
        {
    + V& s4 `0 C) X+ }9 D; }9 A" T  a0 f        tmp=i;2 }7 |* y+ K) P( F4 L$ n
            while(tag[tmp]==0||!s.empty())9 y$ L/ H4 ]# `; X8 X
            {! D2 i3 o, I; _" ?
                p=vexTable[tmp].firstarc;5 ~) T7 P( g/ L& x
                while(tag[tmp]==0)
    1 v2 F" b9 r' b/ t# Y            {
    . I2 ]6 Z( F" w5 B4 F9 k                s.push(tmp);
    " A( p) X( {' C1 E, T* y                cout<<setw(3)<<vexTable[tmp].data;$ t4 E* \/ j: @
                    tag[tmp]=1;$ A& @6 A- n7 ~; t$ \1 b. S
                    p=vexTable[tmp].firstarc;& Q% a4 ^. f3 g- @5 d) z4 k
                    if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for9 t4 E: |4 o! `2 r" T
                    tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);, E9 r0 b4 U, c
                    //cout<<" 1st     tmp="<<tmp<<endl;
    # d3 D9 S( B" t            }" B  W: @$ C. d7 ^
                if(!s.empty())0 z' `7 X& h  A4 J
                {0 f0 D; ]5 z4 r& \
                    tmp=s.top();
    + B+ F' n* N7 b4 E( z! h                s.pop();
    ' Q- \( U0 K* y9 `( L* T( \2 e                q=vexTable[tmp].firstarc;; J/ B& R+ t9 o# r
                    int t=tmp;
    8 h) b  x* {3 c% J% t                while(q&&tag[tmp]!=0)
    5 E. E1 Q' A! e                {7 Z+ R. }6 e0 I  A2 C8 H
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);* s9 R, k; B9 L! G, T$ c: R
                        //cout<<" 2nd     tmp="<<tmp<<endl;
    + t. ~- m9 q6 I1 p6 F                    q=NextArc(t,q);
    & B) f9 S+ S5 C" T3 _; f" D                }
    : ]  ]' d! j: W: z9 h                if(tag[tmp]==0)
    9 }8 x# r2 l2 U8 t/ N                    s.push(t);0 g, a+ ^+ B1 W
                    ///1、对应上面连通分支只有1个点的情况8 n( D7 A: g' h- n0 S- @
                    ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
    1 o0 ]8 K7 |) Q+ A5 V% i                ///tmp要么等于找到的第一个未访问节点,/ x  M4 M) B9 P* w  Q
                    ///要么等于与t相连最后一个点(已被访问过)
    1 l* V/ z: O  m                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点- o, b) g  ~1 p! b3 e( h& n( `7 d
                }
    8 |8 q- o# F. |. X4 D, ~; T        }3 `% d) T! X! }  h4 H: ^* @
        }! A; R/ c" j1 F9 Q4 Z  x9 r3 ~8 _
    }
    6 q& T5 q' |9 ]7 h. `//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-13 h7 V9 ^* M. `' J9 Q3 J/ r
    template<class ElemType, class WeightType> int) a7 J5 X6 h9 g9 ^( P5 ~1 Z4 v2 q
    MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)9 B$ E2 p, a& M. X7 ?
    {
    - U$ M! j+ E" \, I    if(head==pre); e, W, f+ A; Q: w" w
            return -1;) f# G8 C3 U2 m3 v$ t8 A. i& _: k

    ( w6 V6 C2 O8 r+ b  u    MultiAdjListNetworkArc<WeightType> *p;# X: j5 u) ~! w( g
        p=vexTable[head].firstarc;
    6 x; m) B8 n2 S$ c    if(pre==-1&&p!=NULL). g# F1 S3 {; s- ]' e9 r2 J8 j9 W
            return p->adjVex1==head?p->adjVex2:p->adjVex1;
      R$ r! L1 I% @8 g5 h$ P4 }    //pre!=-1&&p!=NULL
    % K+ I7 {8 Z1 j( v    while(p!=NULL)
    - L. m3 \0 M! u5 |1 J8 Y. W    {
    : ]) f+ V2 V- b9 g        if(p->adjVex1==head && p->adjVex2!=pre)
    $ R. A& r% v' O4 l' p            p=p->nextarc1;
    5 u) K' O9 I. O3 d( q6 i        else if(p->adjVex2==head && p->adjVex1!=pre)
    5 Y3 x3 i- ?6 ?/ i0 r5 v+ x            p=p->nextarc2;: I6 h8 p4 B$ O; K0 z+ N$ q+ u
            else if(p->adjVex1==head && p->adjVex2==pre)" D4 v8 W7 m: F) p% v% ?" A" Q" ^
            {  c2 F0 S( `9 d4 t" h6 j: G
                p=p->nextarc1;
    : l+ B6 y3 Z0 b* w( J            break;0 x0 `, y% O) Q' O
            }
    % g' g; Q& F6 n        else if(p->adjVex2==head && p->adjVex1==pre)
    2 N; \! k7 r* R5 V1 L        {$ R, _: y7 C" W2 J; ^, F
                p=p->nextarc2;
    , v3 z5 Y; _1 J2 B+ {/ G            break;
    ' P1 R! L* i+ F# R6 F" G        }
    & h9 ^. G4 |8 I    }
    * ~) s" f5 v' z    if(p!=NULL)9 S; a) N) d/ T- m1 ?! n
        {1 x# M6 C, @3 r3 {, x# h& w
            return p->adjVex1==head?p->adjVex2:p->adjVex1;& B# C* q! M0 P1 N# {) s
        }0 ^/ g. X& Q1 J
        else
    : y) j2 V3 H' R# p        return -1;
    5 g- q' R( Q, q- Z' R$ |' c5 F}
    + S: S' C! x+ }. c% D, e- j  W9 T/ E& I4 S( v
    % e7 @! t$ C/ H, t% e5 c- e
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()( @% ?& p, J# m$ o: q. g/ Y
    {
    % W. L2 v) O8 l+ ^0 y. a) [* y    stack<int> s;
    7 p6 V; y: h, o+ A    int p,cur,pre;
    & b/ i  ]2 Q8 p4 y+ X3 l$ e    //MultiAdjListNetworkArc<WeightType> *p,*q;
    0 P6 ~' {+ A1 e% z3 k4 S3 y    for(int i=0; i<vexNum; i++) tag=0;//初始化2 N$ i: w  A' I" I  A6 h5 B
    ' h" D, ?7 ?% l! `! N/ S9 R
        for(int i=0; i<vexNum; i++); H6 Y# _1 V$ T1 k7 A) O% E9 @
        {7 E. p, B4 R0 i. X' g
            cur=i;pre=-1;
      T+ ]  X/ j6 ]        while(tag[cur]==0||!s.empty())
    ( b& l  a" W2 I  \+ f, _        {6 r: t6 i9 G( _- ]) H
                while(tag[cur]==0)/ e/ _/ r! j: m" k0 i/ _) B
                {, R; G3 I, l+ f" R- g  L3 x$ I
                    cout<<vexTable[cur].data<<"  ";" w2 O6 q2 C& ^1 Y$ x" l* ^) o
                    s.push(cur);
    ! B% H1 F; m7 H% j                tag[cur]=1;
    ; ?4 B3 i& |( i0 M5 b' a+ H               //初次访问,标记入栈* _# Z- I/ w( l% j
    : \" O# a7 O( T% q/ @- q
                   p=GetAdjVex(cur,pre);//p是cur的连通顶点
    , Z+ t8 l/ ~- y! l( @$ A& i               if(p==-1)
    & U. ^. t, C' q# ?! v+ _# J; u               {( K. o8 a' }! d3 |
                       pre=cur;s.pop();
    ( P1 w7 I% F: _0 A                   break;  y5 E6 i- }' o% b% F; o
                   }% T9 m  N# ^: Z. B( X
                   else! d0 E5 W) r. W) i
                   {8 i" J- J6 k" S' P' s- f6 \/ i
                       pre=cur;
    # B5 n) c, w8 [" A9 l! p                   cur=p;
    . a- \& X4 b# x& T               }
    . X2 ^4 S! O+ m9 _4 g- C5 N1 `9 r' p" v, e, m
                }
    ; X* X8 U9 `" G- u6 ?( u, M. Z            while(!s.empty())
    8 d6 F2 J  J+ f! M0 n& i            {
    ; Z. @. x% h+ b/ e* i6 X                cur=s.top();" E- n( q3 Q  o% s1 f
                    p=GetAdjVex(cur,pre);
    2 ~1 K( R" Z6 p, z" }; ]" i3 n                if(tag[p]==0)& X1 j2 }5 y. }5 f0 S# D
                    {9 z; G. }6 s+ C$ w1 x
                        pre=cur;7 X) x% @) M0 q+ i  L
                        cur=p;$ E, v" d# c; h/ |
                        break;2 e/ P4 A, }# j1 E& V6 o
                    }0 E+ s/ C$ r8 C
                    else
    ) I2 [: h" s: ~" w7 v/ h$ Z2 L                {# p. a+ p* g: t! r- l' @3 f' W! ^
                        pre=s.top();
    " P3 @2 G* ~. Z1 f. W, T3 }2 M                    s.pop();, G( b* M! n* }, h5 d
                    }
    / ~5 D+ D! E$ C0 u- P4 X9 g: X+ n+ F% C
                }
    ) d* V" u+ t* R1 b: [. T( G, J! f4 B" G7 C4 _4 \! V
            }
    ( `  K5 {5 t4 j9 `9 L% c' R    }2 Z, G' q7 Z8 L2 b
    }
    9 H+ ~2 X( H8 dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
    5 r# ^) }0 t) j6 e! u! x{
    ) R& V+ [# S+ l7 r7 \    for(int i=0; i<vexNum; i++)  _: O9 d4 o% n* z5 g& G. ^
            tag=0;
    ( J) g4 N! T) R  N: C    queue<int> q;2 ~' d; v3 n1 E
        int tmp,t;' L2 ]( a* i. Y0 ]0 S% \4 {
        MultiAdjListNetworkArc<WeightType> *p;
    ! j% G" ~8 ?6 t8 y; |4 r    for(int i=0; i<vexNum; i++)
    4 }8 v# U2 q1 X. U6 Z! s1 W) ?    {
    : I# p0 j3 h8 I        if(tag==0); x% v4 W3 b% @: ?+ Q
            {; d; C# b+ I" r, I. k4 X
                tag=1;3 t. O9 l( g, |0 T% I% q! {% w8 P
                q.push(i);- {2 d8 f8 w9 `* Y; W8 p9 t& X% H
                cout<<setw(3)<<vexTable.data;
    - D( U7 q2 M4 }8 L! M2 J        }7 Y' u1 e9 i# w3 h3 }# r: l! M
            while(!q.empty())4 k3 L4 W+ _# c3 s) |
            {, |1 e+ N$ m+ t8 O, d- k. I
                tmp=q.front();( G+ O% j7 K: x$ ?# Q8 d- A
                q.pop();
    # k( Q4 M- U9 y3 @. ^, P            p=vexTable[tmp].firstarc;" D* _! w7 O1 P) x
                while(p!=NULL)- O9 E, L: m9 S
                {( q8 L. Q2 I" E% h+ ]+ V
                    t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
    $ E3 h8 o, O7 b( e; \2 @0 B4 e                if(tag[t]==0)4 W5 E# [" n* _/ n" S
                    {+ u! w# v; D& K( m+ g
                        cout<<setw(3)<<vexTable[t].data;
    1 ?0 b/ q4 e6 P  V7 o                    tag[t]=1;
    1 a) r6 w9 X, {/ J                    q.push(t);
    0 l2 w+ R) h! A) V* J+ l                }
    ' j, r- P9 r' s/ t4 T5 \7 b) [                p=NextArc(tmp,p);
    6 u( f# R, k1 L8 y& z* r0 _% R8 G2 i            }
    8 @7 F/ Z2 t) f! R        }) A6 Z+ N* K! Q
        }! m* i0 a1 z$ `$ B, q
    }
    + L2 x# ^+ Q8 ]3 g* }1 j% ~) J4 Ltemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
    & ]1 W* c; X, d{
    # [. a' _  k' a' f9 m1 y    MultiAdjListNetworkArc<WeightType> *p;
    , R3 G/ O- W  A$ Q  o    cout << "无向图有" << vexNum << "个点,分别为:";
    - L4 W, t" O! d5 o# ~/ a5 \+ p& k; s8 ]    for (int i = 0; i < vexNum; i++)8 b& S) R( R9 p3 O/ o
            cout << vexTable.data << " ";
    - M: D& I2 G3 b! N    cout << endl;- O; F5 C; F/ A% s! o
        cout << "无向图有" << arcNum << "条边"<<endl;
    8 O/ F6 G  E- s. H9 @( d    for (int i = 0; i < vexNum; i++)) Z+ ~9 e( e7 B, i& Y
        {
    7 y4 E: X. Q2 Z6 ~- E2 ?1 `3 H$ |        cout<<"和" << vexTable.data << "有关的边:";; n% I/ A# W% O, Q# P8 F
            p = vexTable.firstarc;1 K3 l  `) _2 N4 i, B
            while (p != NULL)
    : W- Y4 J2 \& y6 m        {9 J  l+ l! ~0 G% P
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";+ u. V2 f" B3 O0 Z5 ~) \$ h
                p=NextArc(i,p);" Q1 V. Z6 a1 u
            }' r$ I# F2 [6 L4 Z) i* N
            cout << endl;9 X+ _$ z5 `( ?
        }
    & f8 B: J1 x7 n$ V; V$ a! _}! g* p, A3 S! S/ v

    9 q8 @9 \( C' d8 r
    " L1 G/ c( M4 D" L1 a1 _0 S邻接多重表与邻接表的对比. e5 ]0 H: x6 V% W

    0 j3 k& u# r) E9 l8 y1 S邻接表链接
    & [! @5 ^5 Z0 p, n: W8 M在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。0 u2 L8 K1 m0 p- Y- Z8 e* h% A
    在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。+ _* N( x! f# X  G- j
    为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
    $ O6 \9 |* T9 k8 D" o4 E————————————————
    " S5 [7 q  G: w版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。, s- P2 a: D. F3 ^
    原文链接:https://blog.csdn.net/qq_43413403/article/details/1057669585 `5 Q- g9 q1 i1 l. U# X
    ( X- V" N; O7 O; Q
    * M. [; f7 ^2 S2 g& g  a. A
    9 ~+ b: F0 I) i
    3 k3 y& x, l" M+ p8 W
    ————————————————, L9 ~9 m9 |( l0 z
    版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    3 n& Y( f: g2 D( C0 g# t原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958) x0 N' d: |$ T  z
    ' f7 L" L4 L0 L6 Z
    - E* S/ {/ L" Y; \* y+ B% 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, 2025-12-7 12:01 , Processed in 0.685507 second(s), 54 queries .

    回顶部