QQ登录

只需要一步,快速开始

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

    / w* P) @& n0 k图的存储结构——邻接多重表(多重邻接表)的实现2 F8 @' J! x+ x- A/ p
    7.2 图的存储结构
    / z/ [$ h. q- R
    + F( ~$ G1 S9 X9 w/ M7.2.3 邻接多重表(多重邻接表)Adjacency Multilist2 G2 U  @3 o. F; ^/ q
    邻接多重表的类定义+ W+ B; L$ c! c& `5 X& {5 d
    邻接多重表的顶点结点类模板
    0 f5 E/ j2 k; z4 M+ i9 G邻接多重表的边结点类模板+ f+ J1 c: F1 S3 W4 F/ b# Q
    邻接多重表的类模板
    * z& G& g+ c4 X  m) ]邻接多重表与邻接表的对比
    0 ^0 @4 I! b6 m# B" r( o7.2.3 邻接多重表(多重邻接表)Adjacency Multilist) v3 j: B( G5 f! H. r

    , F+ _0 X% I  I9 v( \在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。
    2 P. r' C$ ?! _# E& K" y在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
    / p+ r" ]  Y# l6 v
    0 {9 n; |) k* ?% ~4 ]* Y+ i. C( {邻接多重表的类定义# x+ y5 a5 N2 U* @
    1.png
      ~3 I1 M4 v% e; _邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:2 q; P4 f" Y+ Q4 P% W. e! ~2 x
    data域存储有关顶点的信息;
    3 Y4 t2 }& a% w. ?2 I* a/ \9 |firstarc域是链接指针,指向第一条依附于该顶点的边。8 t" Z$ F% k. d. T! x
    所有的顶点结点组成一个顺序表。


    # f. ]" q- ?* b4 a6 ^' o" `- ?
    $ e  ^' V' T$ k4 @) R( `% f2 B, @) Xtemplate <class ElemType ,class WeightType>
    5 K5 x! ?/ Y% W8 N' qclass MultiAdjListNetworkVex1 N; c# q+ b; e! f6 K
    {
    ; l6 S) T  G6 w+ S( u; tpublic:
    ( f$ B: D! m- s# G0 {( w" y& _        ElemType data;( ]* k5 s. Z1 o+ d( d( z
            MultiAdjListNetworkArc<WeightType> *firstarc;+ Y4 f: H( J$ y$ b0 |" L  e

    . g( U& x4 T$ J        MultiAdjListNetworkVex()/ H$ V5 Y7 q! a$ q. z/ r& k/ l, l
            {
    " l7 ]! ^  @/ Z9 d; t( O2 h  f                firstarc = NULL;4 P# s$ p8 |  t, u# a5 H# P
            }
    6 {! G! q% X9 ~1 p3 t/ s+ C        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
    3 `" c7 N3 ~) K: `$ S        {$ l9 {3 Y4 C* v" e  A1 r
                    data = val;
    7 z; X$ u7 O4 M9 t                firstarc = adj;8 k) ~$ ~# q7 f, b- B- z
            }
    * A: B7 O1 T& Z& L4 c  ]};
    # M9 ^7 e! f# b
    ' R- T/ K5 w- V. |邻接多重表的边结点类模板5 S/ X1 T' Z8 k( s

    2 Y( d# T) Y3 E( I+ Q3 y% y" G在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:
    - {3 j, }0 q6 u3 htag是标记域,标记该边是否被处理或被搜索过;
    ' d% F4 K- [0 {9 uweight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;
    8 F2 |1 B) F! O" M( N. Vnextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;" V7 r6 e1 \& R2 [  G) {& P
    nextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。# Z% R0 V9 l) H  s
    6 m6 g' Q& F/ z8 W
    2.png   ]( c& ^2 R. R, s/ h5 f
    template <class WeightType>; G- z: Z# k- g
    class MultiAdjListNetworkArc7 K4 T0 ?% Z* s! Q% R
    {, k4 h% J/ g$ [# Q$ G
    public:
    7 h' l2 ?0 F. y7 u  ^& Z* \    int mark;                                       //标记该边是否被搜索或处理过
    6 T/ r0 c) @  M) V4 U  c( X        WeightType weight;                              //边的权重& O8 l* v$ w# X8 C! {* f9 U) {/ U
            int adjVex1;                                    //边的一个顶点) ~% q( I  z0 e
            MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1# |7 w: B/ u2 t( Q4 X7 e; K
            int adjVex2;( l+ R  D% K2 O8 A
            MultiAdjListNetworkArc<WeightType>* nextarc2;
    / I( {5 N8 |. \  D5 i% ?( a2 M1 c, s" i" X
            MultiAdjListNetworkArc()# q2 Y+ P1 K6 b
            {
    ; T0 y3 L! y6 A6 |/ J6 }                adjVex1= -1;
    $ ?0 G: T7 ?8 _                adjVex2= -1;
      g. k: C) e2 r" t9 S8 Y        }
    # `. m1 {# e2 u! a( n1 f        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
    5 ~$ Q) t7 N9 w4 e- w        {
    ' N. y6 Q. o! p6 {, V0 L9 E                adjVex1 = v1;       adjVex2 = v2;
    + J/ L4 A* g, h9 H, e                weight = w;, w" A5 u/ u7 y! q' Y, H# z
                    nextarc1 = next1;   nextarc2=next2;& |3 K9 V" w( f
                    mark = 0;           //0表示未被搜索,1表示被搜索过
    . ]5 d& L: h  t# ]        }
    ( n9 X* b& e4 |8 r* u, L5 O$ S# H, K/ I" Y" X: U0 V' Q
    邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>
    - p1 [& W+ y% o! ^7 u/ S( hclass MultiAdjListNetwork6 p. x: \- V- ~" Q; d0 i' N! [
    {
    9 V* ~1 L! p7 U2 Uprotected:- R( _* X5 P" `- c
        int vexNum, vexMaxNum, arcNum;8 A1 L. e7 I8 G) e
        MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    3 s) Y! x* G9 N- c  K    int* tag;) D, U( p4 u+ V- S6 x" a
        WeightType infinity;$ I9 |1 W( J! z, p

    , u1 ]; T0 b$ |/ Ipublic:
    1 M2 R8 I9 v: u" n7 o% g: ^% d9 B    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
    % _3 J  l' S$ i, E3 \) k
    . S: k. L- U6 }4 p8 u% n. H    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);/ @6 A: G8 Y1 }8 O# Z

    7 p. {1 S! a) F9 \7 }! O    void Clear();- W/ s  a) I7 Q
        bool IsEmpty()) d! Y1 L; W' ]- B9 C
        {# c) z. v! w6 j4 J4 v, ]
            return vexNum == 0;5 f' V9 Q3 K0 P+ S, i+ w
        }3 N0 `. B' e' U+ K$ A- r* L
        int GetArcNum()const
    # H& C: A+ i8 e7 k$ ?; i+ `3 O    {
    $ ~9 q. F0 Q$ ]" `$ h$ q5 l1 P6 t        return arcNum;8 d( I7 |7 s" Q4 V5 ]6 M- p
        }2 c7 r* {; B0 v" S3 l) p8 B
        int GetvexNum()const$ F% C1 z! {* A% W1 x% Z& P
        {( L$ x, _9 M6 ]/ w7 y* J
            return vexNum;
    + n+ h4 [, U2 s! w% q" D    }
    4 ^+ f3 S3 O  ~' G6 o
    ; S$ N* D# r3 [- b8 h1 T- F  E0 ~0 C' ]+ p1 x, N
        int FirstAdjVex(int v)const;
    ( e( p  n- M$ @4 ^# D2 G    int NextAdjVex(int v1, int v2)const;% N. o: [- X, T* q0 W
        MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    8 G2 f7 u* a: D    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;* V  t( o( m2 N4 i' A0 b0 D
    - M. a  V3 E; M
        void InsertVex(const ElemType& d);
    0 ?! X) b& d" g  o: ]1 i    void InsertArc(int v1, int v2, WeightType w);! X7 ?5 L/ v+ ]6 B, s& ?+ I

    7 o1 H% \  @3 o" H0 l    void DeleteVex(const ElemType& d);
    4 S3 B0 i/ a, j5 r    void DeleteArc(int v1, int v2);2 E! X8 }- V/ j, L
    $ Z0 a5 m: I: k4 }& E8 N0 g
        MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    6 }. m( `7 v0 l: u; x; W8 ~    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
    3 f; t1 h7 Y, ^/ q# B8 s5 V4 ~
    6 e/ ^- k, {2 |3 D6 r1 x$ ~    ///深度优先遍历/ m( V3 R: ^; K
        void DFS1(const int v);4 d. J. b1 ]% M/ y
        void DFS1Traverse();, q2 T. S6 N# J0 C  A: X1 e
        void DFS2();
    & o' I" s  Q1 j
    ! I: _" r, t# s; t8 i0 L! t    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
    2 G2 Z7 l- c! h- p7 W# t5 ~# A    void DFS3();
    & G) m6 Y1 T' \" A
    ) D9 x# `% O, \    void BFS();
    9 S. F9 L( R& A( m8 o    void Show();/ t1 [+ f8 I, t" }1 [
    };
    ; v" a; b7 E+ b
    ! I; x# ]7 d  {& Q- l2.函数的实现7 m7 r' i. y( W$ D: v
    研讨题,能够运行,但是代码不一定是最优的。& [1 ~; _( t* x2 F

    % f2 v  q2 j3 N2 e#include <stack>; |4 [- s5 U( ^
    #include <queue>
    9 J" J+ h4 V+ ?5 n7 W) L- _6 @0 z, J& o3 j
    template <class ElemType,class WeightType># t& D7 `, G3 Y( O0 @
    MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
    ' A$ ^, t( m  w  n  h{( y( `% Q2 z, B. N
        if(vertexMaxNum < 0)
    9 |7 F. D! ?( ]! s9 ~/ j        throw Error("允许的顶点最大数目不能为负!");! A: w# }3 z% l; S1 X
        if (vertexMaxNum < vertexNum)
    0 {* D! ]! }& s' c& T: y7 U$ P  n        throw Error("顶点数目不能大于允许的顶点最大数目!");
    4 s% @# t1 ^3 x0 j' p9 L    vexNum = vertexNum;
    # e. e0 d& ?% V( q5 V    vexMaxNum = vertexMaxNum;' |3 d7 a6 _: e/ j% Q. [
        arcNum = 0;# U  i- ]1 b8 k2 N$ q
        infinity = infinit;
    ; U4 n$ S' ~' ]5 w1 Z# m, G    tag = new int[vexMaxNum];
    ( l: {1 B% _6 S- s9 s- }    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];) `; W* K+ x3 z/ R0 D7 R# r
        for (int v = 0; v < vexNum; v++)
    # _/ ~3 m4 q" Y* m    {
    " n, g: ]+ |4 p7 T9 }# J        tag[v] = 0;
    / d, ^$ ~0 d7 z; G/ c        vexTable[v].data = es[v];
    - ]+ ~6 ~( _6 y% i- c        vexTable[v].firstarc = NULL;
    : ^  m, u1 z8 B2 D- f    }
    , o; C  D. f) X* l: d! f% A}
    0 i4 J6 i+ k* |  M9 htemplate <class ElemType,class WeightType>
      g! Z( q% n* d- G, D- PMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit), v# U9 p% K- o2 ~0 z9 S3 p
    {
      q' c4 h) y- q0 N5 E+ \0 q3 Y    if (vertexMaxNum < 0)# }% |0 [: c" L& Q% x* S+ H
            throw Error("允许的顶点最大数目不能为负!");
    + I  [1 m9 }! Q* Z! d8 P    vexNum = 0;' j$ W8 o' U4 a5 Q9 l9 n
        vexMaxNum = vertexMaxNum;
    - g& x0 _1 t  j3 `9 B- c: @! d    arcNum = 0;' p3 i( ?% C, e& q& b
        infinity = infinit;( y$ _& h5 d  s( \
        tag = new int[vexMaxNum];
    . O; i7 S& l) V8 y0 P    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    + L. _. ]2 D# n6 Y}' ]$ I" i$ T- Q* e2 i
    template<class ElemType, class WeightType>: v: f# X& A3 [# H7 F
    int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const) P+ E, K' I% A
    {& Q6 F, e! N6 R# S% t. e( }' Q
        if (v < 0 || v >= vexNum)
    " P: J9 N, ]7 J8 D) r        throw Error("v不合法!");
    9 j, W$ O; K; R    if (vexTable[v].firstarc == NULL)
    , ]% a/ i1 o+ C1 a9 e' R        return -1;8 ~3 E5 a: Z, L1 k4 s' q. C
        else
    . m: x9 e. n! E! d- a6 x# U5 C        return vexTable[v].firstarc->adjVex1;3 `; n/ B! G6 V2 z0 M0 U
    }
    2 |. f; u$ y- ?# K* |9 I' ?/ y1 }
    ; E9 O. }, a5 P% n' ltemplate<class ElemType, class WeightType>& i6 b2 R$ i" a' z& S# F
    int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const. v9 ~/ i' F* Q3 m8 b7 k; m  ?9 N
    {7 t/ G: ~4 L: s
        MultiAdjListNetworkArc<WeightType>* p;
    8 n$ M- Y! S- ^  F/ b    if (v1 < 0 || v1 >= vexNum)4 c; S; n4 t' k& o
            throw Error("v1不合法!");. v$ F! ~; J* h% X2 L
        if (v2 < 0 || v2 >= vexNum)+ ?  |% _, p+ F; @0 x9 Z
            throw Error("v2不合法!");9 ~" W4 h$ z3 t0 U. s
        if (v1 == v2)
    & b" z( `2 _3 n  |( G! M        throw Error("v1不能等于v2!");& @; G7 m9 _+ L1 L2 `
        p = vexTable[v1].firstarc;
    + P6 w# j  K- q6 h0 `    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)  t5 F  Z) A+ t" v
            p = p->nextarc;
    ; _3 ^+ f4 W; J9 r" j# ]    if (p == NULL || p->nextarc == NULL)! Z& G- H& d4 g( @* q( A
            return -1;  //不存在下一个邻接点7 D6 A2 ~3 h: O$ {
        else if(p->adjVex1==v2)
    2 N$ {) Z0 M. G  \6 y        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    * t" ^# g2 }& R* e$ A    else8 n* r! S- |3 @# x! G
            return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);9 T& e9 \+ R  t
    }
    0 ^  ^/ V( \: c& w, W5 {template<class ElemType, class WeightType>  \8 |  ^: {) Q/ Q5 H, U# V
    void MultiAdjListNetwork<ElemType, WeightType>::Clear()
    ' E" i+ ^$ v1 ~- y, E* J{
    " [1 X2 ]; p8 R0 G$ g7 v; M, U    if (IsEmpty()) return;
    . q' D: M; z& A6 _, t* Y    int n = vexNum;
    " |* K, w; F$ u  A9 Z7 t3 |2 Q5 x    for (int u = 0; u < n ; u++)
    4 z0 ~4 R1 R, ^- M. I- I% `        DeleteVex(vexTable[0].data);- h, T- ?5 P6 w& q8 G5 @' d; n
        return;
    7 M, U( n5 m# m  Z' k5 T7 H% N6 J/ O}( J6 E8 B* _( d4 X
    template<class ElemType, class WeightType>
    2 s+ ^; T7 v$ S1 R8 |. ^MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
    0 H% b* T# B$ o% A/ j! j$ h9 b. J{7 E$ u  w/ D' s# b  M# F% {* X
        Clear();
    - u  F# _2 M1 c" n! y5 ?. M9 Z}" p% Y0 \. o' C1 Z9 [- I# {
    template<class ElemType, class WeightType>$ U6 N4 j% S# R- @+ v+ q3 l
    MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
    ; i: c! P, A& V; o" H4 f  d{
      S7 v! E: j" f9 g/ v& q# X+ ?7 l    vexMaxNum = copy.vexMaxNum;
    & l% ?9 R  S' i& N- V: }& v# @    vexNum = copy.vexNum;6 C4 D) v' c, A6 E8 x( p
        vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];! M2 Z8 C* R9 ~- c: u4 n
        arcNum = 0;
    5 h$ E+ S2 r  n& `1 E( j6 `3 ?( X    infinity = copy.infinity;/ {5 z+ p6 w# A: b# {
        tag = new int[vexMaxNum];' ]; q' @  i! C$ N

    1 Z- n8 K) Z5 a' X, C3 I; @    for (int v = 0; v < vexNum; v++)+ u3 b5 T/ W) }
        {
    / X# C' K  M( z* ]5 ^        tag[v] = 0;5 [; T/ G. ?3 {! V
            vexTable[v].data = copy.vexTable[v].data;) ^7 C! {( g7 ^
            vexTable[v].firstarc = NULL;
    4 \3 Y" u, u; z/ s+ \    }
    % Q0 j3 A3 r4 Z* w    MultiAdjListNetworkArc<WeightType>* p;# F1 Z' X  v& d. N* w
    6 t- V; |  J2 w8 C: {% N
        for (int u = 0; u < vexNum; u++)& u9 X6 [" h: B- F: }- |9 Q
        {
    2 [8 c: @/ w! b/ G% I        p = copy.vexTable.firstarc;
    ; ]' x( z# [3 P        while (p != NULL)) _2 k, M" C0 B0 ^* R* b# l5 i
            {* c) H' ?% A. Q. Z8 U+ c+ A" x- h* b
                InsertArc(p->adjVex1, p->adjVex2, p->weight);! v1 F4 e. \, ]  P) ], z" S
                p=NextArc(u,p);
    8 l. E$ N) {. w4 O6 g        }
    1 o0 z* X! K! o: k. F    }
    : D! E; m1 ?+ B6 P}
      i) X0 P; K0 I5 c+ b" ~template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
    . a+ L4 E+ x: B7 D  p, [2 rMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)4 c2 C" M# A% e7 q
    {. d1 r' U: k& U  s" a9 c9 _5 U
        if (this == &copy) return *this;
    ; F# `# o& L8 f- C5 L: G6 N    Clear();/ x$ q- I5 W7 U2 ^& F- q
        vexMaxNum = copy.vexMaxNum;5 n/ N" z7 L' M7 N2 ]
        vexNum = copy.vexNum;
    8 w4 K5 ]+ Z! M  ]( C" t    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];! a7 ~+ S  I+ S; ?
        arcNum = 0;- Q3 Q- N; _( I$ `4 I" C! a2 l
        infinity = copy.infinity;* a; [& j3 O0 z. d) }. W" p1 j" Y+ ?
        tag = new int[vexMaxNum];
    + X; Q/ l7 N( H2 D7 k- g+ _4 X8 A/ P8 h6 `# E, W% z2 O8 M
        for (int v = 0; v < vexNum; v++). e$ ]  S$ ]( F& R6 ^$ O
        {) h$ v5 J" R, w( }# e9 e, m$ x
            tag[v] = 0;/ @* c/ [* L# h: a& h
            vexTable[v].data = copy.vexTable[v].data;$ D; }$ }) l+ k* N* r
            vexTable[v].firstarc = NULL;. x% R' o3 r$ a4 l/ s% P5 K! J5 ]6 T$ G! p
        }
    8 U/ [- k; H  y: t, o: n3 p' s    MultiAdjListNetworkArc<WeightType>* p;4 p/ L: i) c/ P6 K# p

    9 A3 n, i  ?* v. x! X    for (int u = 0; u < vexNum; u++)
    4 q4 A4 `* _1 g0 w; l    {
    : b  k, @. {9 J3 x. e; R        p = copy.vexTable.firstarc;8 f& n$ n0 x( _6 H9 n6 C9 Z, P
            while (p != NULL)
    8 @0 c8 a2 m- h9 U        {7 n+ O( [; A# V/ c
                InsertArc(p->adjVex1, p->adjVex2, p->weight);  s; i5 _! m  H
                p=NextArc(u,p);, a$ m+ W% Y5 C8 Z9 p% K
            }3 h$ G2 I* `9 U+ H, Q5 T
        }- P; P$ S1 P* e
        return *this;! q7 T/ W9 g  j/ S1 z' N
    }
    0 P2 A& y6 _9 L1 C% N: X; Ytemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    . H. F( m- D" F0 I1 Z3 oMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const0 q9 z/ T+ u( A  T$ K
    {
    : n! e: j, p3 ~    if(p==NULL) return NULL;2 n5 T5 F6 x* b; i1 h4 E
        if(p->adjVex1==v1)' a$ ?- k* T6 D% i
            return p->nextarc1;& b+ _& U, g0 V9 A' ]% M3 K
        else& @2 |5 w  M+ K% h
            return p->nextarc2;  p% x. k( A, |, f
    }
    ; z- ]( T" M4 Z4 ^/ @" v9 ^template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
    ! K7 d- ~  d" ~% V0 wMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
    3 P% ^" @$ {+ K7 L. Y& A8 D( r{
    , X' A+ C% u! C% ~    if(p==NULL)return NULL;
    5 L1 I( G7 J, g/ H8 B    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    9 z9 Z. K' M+ l7 u1 F0 S    if(q==p)
    8 ]; V/ D% k7 J# w6 \! A        return NULL;. o$ j1 o$ |1 {$ {) v. E) O8 t, |
        while(q)/ {& z; @. ]. Z7 T; M
        {- ]6 U8 y5 m6 Q9 |. s3 P5 x
            if(q->nextarc1==p ||q->nextarc2==p)$ x& W+ n# K1 i; {* [+ @
                break;
    . A& S' @& _/ M2 a  @        q=NextArc(v1,q);6 e- [9 d0 F7 }* m) ]# n
        }' `3 h3 C3 S& I& j; O
        return q;
    + F9 [5 I/ L+ E* }  i  d}
    7 y5 W+ ~7 h) o- b+ |8 P. Jtemplate<class ElemType, class WeightType>; `- R5 u% y/ |5 H
    void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
    # U( E' S' f& z' v1 M7 f5 \{8 L2 d. l2 n% U  X9 E" N' G2 |
        if (vexNum == vexMaxNum); ~) i7 F, F& E/ N2 t
            throw Error("图的顶点数不能超过允许的最大数!");# p5 y) i5 s9 u7 G
        vexTable[vexNum].data = d;! V! ]! A" k9 o8 A1 ]" V: E
        vexTable[vexNum].firstarc = NULL;& u+ U. Q5 x1 d6 |5 d  g5 d/ n+ a
        tag[vexNum] = 0;# |; n% O, J, k( E0 s, e- t
        vexNum++;* o( m2 e7 s. e# i# u
    }0 H, u' h  Y& H2 J3 S2 Q, I
    template<class ElemType, class WeightType>5 l8 m+ V' y3 p
    void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)9 R& F" N- G3 v3 k, A0 f% a$ Z
    {7 P+ I6 {+ G8 {: I5 `. L  a
        MultiAdjListNetworkArc<WeightType>* p,*q;+ ^/ i" B8 l' k# U: G: }& I
        if (v1 < 0 || v1 >= vexNum)
    , o( Q  s8 N) q1 s$ V5 s* d, r        throw Error("v1不合法!");8 _& A# @1 |5 M9 n; G5 y5 C
        if (v2 < 0 || v2 >= vexNum)( x3 G( I  C. ?( y8 c+ h2 K
            throw Error("v2不合法!");
    9 n& E; \+ D& `3 h4 p9 e3 l    if (v1 == v2)
    , [2 Z! ?+ n3 b4 K5 R6 q        throw Error("v1不能等于v2!");/ c9 U  u! I& v' Y, k: h5 w
        if (w == infinity)& v9 y" J2 v% t
            throw Error("w不能为无穷大!");: a% ?+ K0 E- z! J; I! D
    8 ~8 `0 B. P9 {

    ; j# r# _4 h2 m+ Z    p = vexTable[v1].firstarc;
    7 d/ `! {6 W1 \: _/ P    while(p)
    ' R" N+ u2 A8 U7 d+ E4 k    {8 a. s% Z) H" d
            if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中9 B2 R+ f& v- h/ b" C' b" ]. l
            {
    7 q' Y8 w) D( H3 B  X& i! p            if(p->weight!=w)
    ( J$ X  E; W2 j, `! A                p->weight=w;
    " M& D0 Y3 R* J* u7 G2 Q% m; t            return;
    # E* S6 \7 L& k( s4 j/ S1 }" D* j        }8 K1 g# e; B0 y( Q5 I  S& O

    : T4 _' z2 W* D# P        p=NextArc(v1,p);
    & f. ^' i7 i% A7 i) Z    }
    . m# V" f% L, Q8 S4 Y4 R    p = vexTable[v1].firstarc;$ \, e5 T# {% L$ e" y3 e. [
        q = vexTable[v2].firstarc;
    2 }3 |" {6 T0 }3 }* g    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    / f5 `* m$ l' F0 y( [  M3 v% ^    vexTable[v2].firstarc =vexTable[v1].firstarc;
    + l4 s+ x; O5 a1 v3 D! J    arcNum++;
    ! S: i0 ]7 M3 B: L4 J: i4 S' J}6 v/ \5 E: v$ U3 ]% O3 i

    / `/ n6 J7 ~+ O6 P$ A4 g9 X4 mtemplate<class ElemType, class WeightType>
    ( C8 [( I  v$ r7 m& H3 k$ tvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)/ U$ D" w" E' O, `* {
    {
    . a& k) D2 P5 W% l0 N; Z4 l" _, n' N; l+ H' B3 n
        MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    4 `6 f7 k( V$ o$ z    if (v1 < 0 || v1 >= vexNum)
    ( Y& m, h/ p! x+ {! J        throw Error("v1不合法!");3 `7 P! L& {. C) \3 V, Y/ C
        if (v2 < 0 || v2 >= vexNum)
    2 ^: c. s7 @6 @; |5 f. ?        throw Error("v2不合法!");
    " B" u9 b& i2 G' `" b    if (v1 == v2)! {, x" O" f' D2 e& c7 F
            throw Error("v1不能等于v2!");' z" b. z5 U( M0 B* B; h

    & a# x* N  E( `5 S  N: ]- B    p = vexTable[v1].firstarc;* G2 J/ @3 Z, h+ f& E  c. h
        while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    2 Z) U5 R! O9 E" x( v8 R    {5 q  h, b2 k/ d6 L$ a9 H
            q = p;
    3 K" S7 X4 j! N: `2 Y        p = NextArc(v1,p);, p# L6 b' `) g9 d- Q
        }//找到要删除的边结点p及其前一结点q
    5 P$ g1 \. [; b5 u' K* q6 `7 E
    & ^' `1 {7 l2 _8 S    if (p != NULL)//找到v1-v2的边
    * D; }# b! @! L1 U: i7 X    {* d3 ]+ C5 L% M+ J9 p, a$ P
            r=LastArc(v2,p);
    5 m( C+ G. J2 c- B! I: W8 k1 p) l        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL  @$ Z, G( w# @3 r: `6 A' i: H
                if(p->adjVex2==v2)# `2 @& n# M  q; _7 ?4 ?
                    vexTable[v1].firstarc = p->nextarc1;- Q* `0 t. B" [5 a
                else vexTable[v1].firstarc=p->nextarc2;1 }" c! \1 v' b+ i: {# J
            else//不是第一条边% a& C# o1 i! I! j1 M/ S
            {( M9 x4 P/ C$ x* ?- g& |
                if(q->adjVex1==v1)6 F! a3 _5 i! m* ^
                    q->nextarc1 = NextArc(v1,p);% l4 o8 J( V4 u
                else
    6 C" ]! f: @9 L5 z6 m  Y                q->nextarc2=NextArc(v1,p);
    4 D) d5 ^5 T& Z7 j& B+ T; Q# g7 u3 S0 r1 y5 J0 B5 j% \" K
            }
    & s4 z, \. d6 D1 G  }! b2 C- {        if(r==NULL)' E; T, s. c6 a, |3 X
                if(p->adjVex2==v2)) ]& J$ [- u0 V- h9 Y) g* I% Y
                    vexTable[v2].firstarc = p->nextarc2;$ R+ u7 z2 U8 K- o# B
                else vexTable[v2].firstarc=p->nextarc1;9 E* h/ p( `! Q9 D% e, O4 R: q
            else
    5 B* Q0 W" S2 A        {
    * A  V* R! A7 ~            if(r->adjVex2==v2)2 E3 h% _$ {' X
                    r->nextarc2 = NextArc(v2,p);
    7 @: x/ p* g1 Q9 L5 @9 W! g' V            else5 X0 r( S% t" l! }
                    r->nextarc1=NextArc(v2,p);( ~# P5 h: o' A4 [1 c
            }& C& S4 O1 Q5 U. i9 w5 p4 O
            delete p;% j* k: F& M& P5 Z3 }0 Z: i2 I9 j
            arcNum--;; \6 f* D9 V& p3 k8 ]$ k
        }$ K( n# X+ l9 X; \1 I. E
    ! A. i9 z* _; @" i/ U! O' B
    }% t$ K% v9 J/ O
    template<class ElemType, class WeightType> void, }! A6 S* `& _( {( j2 v9 ?
    MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
    $ Q" M2 P* z* }# _$ x{
    9 J. t$ v9 _% O( X7 M7 C    int v;& {% u) |& ^1 T% {% T( E' Z4 O
        MultiAdjListNetworkArc<WeightType>* p;
    / i( k7 \( \. s! Z5 f! T: x    for (v = 0; v < vexNum; v++)//找到d对应顶点7 r# K5 `/ }( V6 r$ H; H
            if (vexTable[v].data == d), K2 l$ c6 G: s- ^
                break;
    ) e4 q& J9 {) u: x1 i  B    if(v==vexNum)
    . e$ }0 Z" |. L' t+ x% g; Z3 B& U9 A        throw Error("图中不存在要删除的顶点!");
    & d0 ^1 b  F# a7 W* I1 g$ Q5 w) m
        for (int u = 0; u < vexNum; u++)//删除与d相连的边
    0 L0 s9 e+ i2 y        if (u != v)
    + c  N# W+ V! x* c        {5 F4 g/ S% p# s, P
                DeleteArc(u, v);
    + `) Y! {5 W9 W, T5 [0 i        }5 `. d# Y' n$ r; s5 A
        vexTable[v].firstarc=NULL;/ b, T8 V2 S( f/ l5 ~

    . h  S# i$ n7 x- u4 b& V    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    1 A; Q6 \/ Y$ B8 A# y    vexTable[v].data = vexTable[vexNum].data;& g. B. t! S3 o3 x# @
        vexTable[v].firstarc = vexTable[vexNum].firstarc;
    6 M/ L: C, C2 s' [' J7 i    vexTable[vexNum].firstarc = NULL;: Y, `7 N) k( e1 W- q+ k: d8 v6 c
        tag[v] = tag[vexNum];7 ?! W& J: l0 V  N9 v
        //原来与最后一个顶点相连的边改为与v相连
    - S% w& a1 b. B* s& F    for (int u = 0; u < vexNum; u++)! Z8 S+ g* N. [" l7 w* X% r
        {
    ; B" h/ M0 J9 V# G% r# ]        if (u != v); I8 r) ~0 {2 M
            {/ B3 X% F2 X4 F7 A! K
                p = vexTable.firstarc;
    * z: f6 x+ C; j6 P            while (p)! Z. G' |3 \' s
                {
    0 [1 w1 I% u5 |& I! M2 z; _7 b4 u/ F                if (p->adjVex1==vexNum)
    2 d# t# O7 e5 ?$ \3 `                    p->adjVex1= v;# d. a) l: x& l5 F7 i. E( H
                    else if(p->adjVex2==vexNum)
    9 O0 D  f$ J0 y; U- ^0 I                    p->adjVex2=v;
    + D, R* G# c2 P  t: t3 \. a) }                p = NextArc(u,p);0 l2 R7 {* T% Y+ ?1 Y) n# p5 u1 J
                }* h: _) ]( P+ n1 y
            }" {3 G) O( M0 M4 k
        }7 T/ _( G# J- F1 V- ^+ U, m
    }
    $ F/ C8 ~% `+ j2 R% n/ Y7 A9 R///深度优先遍历
    / d3 p2 W& F3 o, ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
    9 I, M- A  [8 Q( D7 A{
    - N4 P3 a0 r) W    tag[v]=1;
    / M* j) s9 n8 _6 U4 d    cout<<setw(3)<<vexTable[v].data;& P3 \, \! s! Z' P) J
        MultiAdjListNetworkArc<WeightType> *p;
    ) M/ S( t& N# n9 U0 `    p=vexTable[v].firstarc;5 A) {1 U$ {" x* R2 G
        while(p)5 D. b9 }1 D9 H
        {
    " }& t& a! }: z2 N8 X& ?, V0 J        if(tag[p->adjVex1]==0)4 L! n  I7 r0 R  |. {+ d# F7 g
                DFS1(p->adjVex1);
    ) ]& }* @' a5 C        else if(tag[p->adjVex2]==0)
    ' F2 P, N8 g8 P            DFS1(p->adjVex2);
    " N) ^! W7 z# X! o, ^! V; p        p=NextArc(v,p);
    2 Y2 m& Q# c  t1 B! c: |( N& C    }
    % ~! V% H8 v3 Q" W  y}1 h# X1 c& E5 p
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()- w# r: P% o' Q/ D
    {4 w$ g8 F. A* _
        for(int i=0; i<vexNum; i++)6 D6 K" Q3 i5 L; F! O
            tag=0;% f# W  j8 A  A9 d" G9 f
        for(int v=0; v<vexNum; v++)
    8 }% S6 }9 B- t8 d; `! m$ O$ V- U    {& f# W' y8 L( m, E. K1 a
            if(tag[v]==0)% d9 H+ i5 N3 `+ Z$ m: @
                DFS1(v);* `: L3 S2 N3 E8 M' z! l( H, m. B5 F
        }3 F; N' Z7 i2 t' R
    }
    ) B4 G0 v" u% Ltemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(): Z, J. }( j2 d6 }* V4 I
    {2 U: @. T- y' \
        stack<int> s;
    ( p9 _- z+ }: J' ]    int tmp;' C# v  K7 i0 F7 r5 G9 }
        MultiAdjListNetworkArc<WeightType> *p,*q;2 D, r, P! C* |1 Z
        for(int i=0; i<vexNum; i++)
    + r8 M1 ^$ c0 b; ^        tag=0;% ?+ N/ x5 e- o
        for(int i=0; i<vexNum; i++); s) W% k, f* d+ a* n
        {$ Y* H9 R4 f) x
            tmp=i;6 [  P. b# j. n! p. q
            while(tag[tmp]==0||!s.empty())
    % U$ B; S1 o' j( o: {( q        {0 q# |. S6 q0 \( U  c, `: i- o3 Z
                p=vexTable[tmp].firstarc;
    9 ~; ]5 d9 r% c! D) i  b7 C% g            while(tag[tmp]==0)+ _- v3 h6 c, [; g) ]/ `
                {0 m4 V. u) Q$ _5 ]6 O% P
                    s.push(tmp);
    : X+ `9 u) G: b# i                cout<<setw(3)<<vexTable[tmp].data;
    3 v& W) c: w) |1 n; v8 ?! U; G5 n  y                tag[tmp]=1;
    . q3 f* b0 O8 Y                p=vexTable[tmp].firstarc;
    / @* s4 S0 I# j1 c+ H3 X; z                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
    5 b  x3 D, Y9 P$ h8 C# Q% q                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);9 b  |) l6 p7 L
                    //cout<<" 1st     tmp="<<tmp<<endl;& N7 b8 M+ ?! z5 |, V4 U! Q
                }: o  c5 B$ `, ?% B
                if(!s.empty()), q" X9 _/ \2 t6 J8 F& b8 M3 e, N
                {
    : m7 k9 n4 k! j5 L1 I, l                tmp=s.top();5 K$ d* d+ v! s$ I6 W
                    s.pop();4 `9 I5 Z) P4 k+ H
                    q=vexTable[tmp].firstarc;! g: \1 @8 F, _5 K4 t" S  s9 }
                    int t=tmp;% C% J& D8 G) Q: u+ G& ?; m* g1 h
                    while(q&&tag[tmp]!=0)
    $ N/ K7 Q2 m: `) \                {. E4 a: m# W: C* Y, Y/ C5 p+ b2 [
                        tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
    + R2 [: e7 A' F( [! L. z                    //cout<<" 2nd     tmp="<<tmp<<endl;
    . O  ~; T# a2 d9 a/ s! Q8 m                    q=NextArc(t,q);
    5 \! }1 p# x! W                }" N3 M" L! G# Y8 x0 \7 ?8 j2 T9 T
                    if(tag[tmp]==0)' k9 m* I' B$ H8 m2 i/ c: {
                        s.push(t);
    9 C( \7 b, X! t" d: @                ///1、对应上面连通分支只有1个点的情况
    . ^: F4 N. C% s2 S+ o8 a                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
    ( C( ^. C; Y" d! j( q9 p  j                ///tmp要么等于找到的第一个未访问节点,
    # t5 i$ x' o6 J' m                ///要么等于与t相连最后一个点(已被访问过)
    ' h6 H) M" V3 V                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
    5 M' u3 E, r" e; \5 c& t            }
    ( W! p7 Y& C* b  h% O( _7 E        }
    # E8 W3 Y! F/ s9 w) \    }1 m9 [/ \& Y) A+ i# a. r
    }5 C, `" k' F' E0 T) K% e) X
    //从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1: r0 V" u  E8 x  a- w2 [& x/ h
    template<class ElemType, class WeightType> int  Z' P! Q9 _$ q" V) ~
    MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
    , ]9 a# N/ |9 N5 {7 Y1 c' m{
    7 U/ Z9 c' j# B! e) i2 ~    if(head==pre)
    0 w7 [/ r2 B0 n3 f$ P, V        return -1;
    ! w, x3 e$ S. R& |* i
    , U$ I8 E- H% a3 Q. E% R3 W. l( f    MultiAdjListNetworkArc<WeightType> *p;
    / G3 ~5 F, k' y6 n* A    p=vexTable[head].firstarc;
    6 {2 M( w: t1 [2 \! L! m* ?    if(pre==-1&&p!=NULL)
    % A% m' I$ _  q1 X& |) t$ G! z        return p->adjVex1==head?p->adjVex2:p->adjVex1;  x; O1 ^$ D# m8 f8 c
        //pre!=-1&&p!=NULL4 @/ Q. g+ `: e- K/ R- u; D
        while(p!=NULL)' j* t$ Q& R. ]& ~3 M( @
        {$ K+ H: L7 i+ d) m( P# f& A; z
            if(p->adjVex1==head && p->adjVex2!=pre)
    ) `/ c$ x- T4 q* l8 G            p=p->nextarc1;
    ; s$ W3 @' n; H% h, M+ w* L  y4 n        else if(p->adjVex2==head && p->adjVex1!=pre)7 Q( @5 e8 v9 L/ a# V: U
                p=p->nextarc2;
    ' Z1 h' o# S* I7 G$ O' G        else if(p->adjVex1==head && p->adjVex2==pre)
    $ O% I+ z9 o$ M) Y  w0 L& @6 e        {
    3 M" @( h6 r1 x% @( f" h9 J            p=p->nextarc1;( X1 D' W+ p( G: X! {9 |( X
                break;
    " r* b( [  o! ?) m9 H, P        }
    2 n; ~! ^3 p8 B0 Z2 r        else if(p->adjVex2==head && p->adjVex1==pre)
    - @3 N" S" J0 d2 p* S4 c3 u/ U3 d0 l2 S        {
    * {+ b! R7 r, L* \( X# S- P3 a            p=p->nextarc2;, r8 s! ~2 U+ N3 i5 i
                break;
    6 U% K# m6 v0 g. J- R2 {# y* u        }
    ! }% }7 B. l4 ]) @+ q    }" {4 W/ x- g6 V1 O, l
        if(p!=NULL)
    & a% ]9 D& P( C  {6 h$ }3 D* R    {
    + J) a7 e: S% f7 p3 y. s        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    # f* Y& O/ H1 P) o! F    }
    $ m" H8 _! I3 m+ I- M3 w! y& e    else
    2 \4 n+ A" Z" e+ V        return -1;
    0 d3 U* d& ~- E! a% U}8 ]% o+ j1 ?4 q9 |% o( z
    : o" D& y6 Z; z4 P

    1 s6 Z% g) ~6 g& U2 G3 k0 _& n8 ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
    5 e, R, F8 o. m{
    5 v6 ]0 b) E- l" ^4 U1 i) g    stack<int> s;8 k0 d- J4 r% t1 F9 q7 F
        int p,cur,pre;
    0 J4 ^3 j! B, l. l  G5 I$ C$ F% w! Y    //MultiAdjListNetworkArc<WeightType> *p,*q;/ v9 H; J" @! r
        for(int i=0; i<vexNum; i++) tag=0;//初始化
    / q+ M4 O8 h6 i8 f2 u: X! A$ P: ~! ~$ q6 @8 m; L
        for(int i=0; i<vexNum; i++)
    ; r5 t% K" {! g    {
    / Z) F! h8 W" q' s5 T0 V        cur=i;pre=-1;
    & M/ N# L5 m2 U: |5 A        while(tag[cur]==0||!s.empty())9 j9 v/ U3 [9 V9 w% H- N+ }
            {6 A. J: z- @3 G( ~7 r
                while(tag[cur]==0)
    * l& B2 B4 g7 x( c9 O/ _) k            {* }4 x0 E  `* g4 o6 t, q
                    cout<<vexTable[cur].data<<"  ";
    3 E; Z  y% }9 s" a* V                s.push(cur);- @( q. y2 a9 B
                    tag[cur]=1;  P: y# [0 G  H) z
                   //初次访问,标记入栈- z9 E6 B; G$ X" X& z  O, k

    ! w+ M$ W/ B3 o4 j               p=GetAdjVex(cur,pre);//p是cur的连通顶点8 g7 `/ @+ b% X8 w  V8 I
                   if(p==-1)
    & N. \" `" z/ }6 f               {: N2 `# u1 g& I7 S
                       pre=cur;s.pop();
    5 a3 c6 ]! e+ m! i+ i. ^                   break;
      q! Q: S$ M# H6 {+ w               }+ M5 q+ C) j" Q* V
                   else
    0 D' C) d) N+ v6 P               {
    5 ~, U, Q/ Q2 @1 G$ x                   pre=cur;
    5 L; M8 o; x7 F4 g/ ?  L; R/ {                   cur=p;( F$ H! Z2 v/ t5 H; w7 L* B
                   }" a0 y6 S2 T! }0 P  r: }
    2 U# s, o8 ~" ]) [( F- D9 i/ J
                }1 [) w- D/ K9 X
                while(!s.empty())
    / p( I% q" `2 E! _, F) d4 K, t2 r5 K            {, p. f* d/ d! I6 Z9 G
                    cur=s.top();6 j, b# X3 F7 @5 k. t0 y
                    p=GetAdjVex(cur,pre);2 A& `1 L# n7 d9 s' d1 j7 |/ \
                    if(tag[p]==0)
    ( P% s5 s8 m( A& S6 \                {; h% z+ y  p' v& V3 Z7 u$ J
                        pre=cur;7 G0 ]6 w1 e% J( U( E
                        cur=p;
    $ \: v  \3 e, Y: ^# ]                    break;# L+ P/ |6 s" `" ~
                    }
    2 w- u& V: _4 ^* Y" }9 h8 I; G% _                else" @+ ]  u" A) f1 H, B
                    {
    9 Z( [/ h  ?& S                    pre=s.top();7 m  H  ?: t6 S) {. A
                        s.pop();, W( [$ z* z0 w+ C
                    }8 H; x5 Q. U; E

    # B1 d# B! ~* `            }
    ! A2 V2 L5 v1 m2 }) {& H- h9 t- G* o. Z( P. [8 T9 j1 x
            }8 e5 V8 o- H3 w5 K& i5 y& [
        }) j- d6 ]4 }. Z2 K5 q& R7 ]
    }
    . v! }( @. a! r- n  a! xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()' x1 L8 Y7 y$ @% L# y
    {
    3 M: X+ h" Z' r  m2 a    for(int i=0; i<vexNum; i++)
    3 f8 U/ `1 _! e- a: R        tag=0;
    9 x. l7 C) r# {  z6 a1 H" c6 V    queue<int> q;
    2 ~) ?9 t  G0 \: @# ^: R& M    int tmp,t;
    ' d! d7 |7 k( p3 N    MultiAdjListNetworkArc<WeightType> *p;
    $ `/ t+ v' C: |* U1 j5 |3 _    for(int i=0; i<vexNum; i++)% J: [6 o3 v7 T/ v
        {
    % Y+ B+ i+ l& Z        if(tag==0)
    / r0 x8 w8 c& W! [$ u  C" Y        {$ R( ~- D0 `/ m5 Y, A# p  z9 f8 y
                tag=1;
    % _) t5 V+ Y# G4 a3 x2 q, c- n            q.push(i);
    % H9 \1 z2 S2 _! \" o8 V            cout<<setw(3)<<vexTable.data;
    # [3 }( z/ b. U' {% }0 f7 s8 n! t        }( G  F- x( n7 j' G) j+ o
            while(!q.empty())
    - k9 f! R( B& h9 C8 ~        {- {$ Y5 Q3 y0 {7 v" P
                tmp=q.front();
    1 a# d. R; y. `1 j: f& z% O" ]            q.pop();7 Z$ J; R7 J) ~0 G. p
                p=vexTable[tmp].firstarc;8 t+ j! q8 k* u6 Z0 P1 \
                while(p!=NULL)
    ; w5 i7 m4 c3 m$ P1 H% U0 ^0 U0 I            {
    $ T- m' c2 U. p0 O6 Z% V) g                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);; _$ d! N8 ~1 j/ M' h% Y
                    if(tag[t]==0)1 p: e" n& w9 k/ w$ i
                    {
    ( g% v% G' d; z1 I2 E% a1 D                    cout<<setw(3)<<vexTable[t].data;8 e+ ]! Z: k  v5 I
                        tag[t]=1;
    : M! Z' Y$ l  Y* H                    q.push(t);& V  j% G% m. C6 k) V
                    }( u  R* ~# d6 X# }* C6 i
                    p=NextArc(tmp,p);
    5 s+ O' ~: [6 q5 `            }
    , j2 V9 l2 n2 ]. c9 S, o$ d. [1 [        }
    6 o/ O( X- P$ D$ d& C+ X+ M    }
    ( t2 H( G& L& Q' o0 L- M; r}7 y2 Y: p4 s) A: t5 ]
    template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show(); ]* ~  V. [. m2 I, v& \
    {
    3 u( [8 W* j5 `1 b% n* v    MultiAdjListNetworkArc<WeightType> *p;
    ( Z9 p) f) e" Z4 N3 f    cout << "无向图有" << vexNum << "个点,分别为:";) H1 ?, E! v  O6 {& y, a0 n+ N! V
        for (int i = 0; i < vexNum; i++)7 I+ F/ [7 k/ g" @9 v( S3 o
            cout << vexTable.data << " ";( f1 m, i% N" q$ T  D
        cout << endl;
    3 k+ `9 G0 K1 |- t/ i  a    cout << "无向图有" << arcNum << "条边"<<endl;
    3 \% C, Z$ m$ a2 M+ p9 q5 s& n    for (int i = 0; i < vexNum; i++)- X. {& B* X6 D  C8 [
        {+ R9 z1 S3 k4 w" l. d3 J  r
            cout<<"和" << vexTable.data << "有关的边:";
    ! F1 E1 z5 y1 |; V( I        p = vexTable.firstarc;6 d% V/ V- T$ @9 M6 S# d1 u& M- N
            while (p != NULL)/ \0 R6 B( l* X. L1 ^
            {: ^  W2 ]- K, _2 w7 k( M$ [7 t
                cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
    # H3 G' X1 n- V# T2 q            p=NextArc(i,p);
    . S6 O# A$ W' H* q) ~- g: [- ~        }& l) R* p: C5 H- B2 Q
            cout << endl;
    . U: Q7 H& U/ P. x  W8 {    }/ A: F9 K, N7 }5 Z' I; {( a2 X
    }1 o$ e6 P3 e& Y2 U
    2 a& ]$ ^1 D. ?) u  ~  g
    ; C9 h% n" j1 d8 y0 @
    邻接多重表与邻接表的对比0 e$ h6 J, a) O0 R, j, t3 r
    2 A& s) X- V5 Y8 V
    邻接表链接
    5 g& B+ s' A( k在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
    7 {" H8 J3 v8 @2 }7 B在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。! Y: o/ S& \% M
    为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。+ @  V! [& _0 E. j+ X! I0 o
    ————————————————
    ; _3 ^- U3 k1 y5 R4 o版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。: U1 {6 _1 @- l
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
    ( ^1 d7 j6 j& P- n; x% L5 }
    6 w; `5 E. \& {% L, |  R# }: v2 @2 w; K5 S! @
    ' Z8 O/ z" S$ j* O2 f- ?% Y, f! ]

    % p# r0 J4 c& ]( ?, s) Z7 ]————————————————
    6 C0 A0 \( j. \. O1 t; E6 b& ?版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。& S0 }& e6 C& ~: [
    原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958. s4 O  E9 S- n

    ; b/ ^, g* \0 N& Y1 p; ~& K* m8 T8 R
    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-9-10 10:56 , Processed in 0.536974 second(s), 54 queries .

    回顶部