数学建模社区-数学中国

标题: 图的存储结构——邻接多重表(多重邻接表)的实现 [打印本页]

作者: 杨利霞    时间: 2020-4-26 15:26
标题: 图的存储结构——邻接多重表(多重邻接表)的实现
( K; u' E3 Y5 H. l5 S
图的存储结构——邻接多重表(多重邻接表)的实现
- q- Y0 c$ R& D$ |; D# o: v+ H7.2 图的存储结构
/ N. X4 E1 p; K, I0 R! E& K, G* {, A1 O: w( d
7.2.3 邻接多重表(多重邻接表)Adjacency Multilist3 m2 K' N) \$ r8 V$ q" G
邻接多重表的类定义& K& z$ c( G3 q  }3 c" A/ P
邻接多重表的顶点结点类模板/ U" @6 u2 W0 R: Y5 q# A- @( G
邻接多重表的边结点类模板
! E, ^5 b5 \6 |) q* W. F9 A5 ?( ]邻接多重表的类模板
& j: N' a7 t( C7 i邻接多重表与邻接表的对比
: |( [" P/ |8 @& g% k7.2.3 邻接多重表(多重邻接表)Adjacency Multilist% h2 S$ F3 J* c9 z3 a# ?5 E

+ k, ~0 U5 p0 v; b+ e在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。$ T% T+ A6 \2 _9 }
在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
- d  K0 }" A* x* S5 r& U
2 I9 U3 i$ @6 o2 ^! l9 E邻接多重表的类定义- C8 _0 f  t. I% L* C$ P; ?
1.png
$ Y/ V) o5 H$ t邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:5 o+ C$ P7 N% I! _; |. @( W& p
data域存储有关顶点的信息;
+ D+ t, @8 g# P2 P, ^4 [firstarc域是链接指针,指向第一条依附于该顶点的边。3 ^5 T9 ^6 a  \$ `' _
所有的顶点结点组成一个顺序表。

# _1 v2 t7 ?3 k3 Z
% _& e3 j! q$ @; u$ C& w! R
template <class ElemType ,class WeightType>
& O  J% S) h% q" `class MultiAdjListNetworkVex( W! E8 N% E3 L1 \) @, e3 m
{3 H7 a9 w; [0 _+ n
public:$ ?, l' {( B) h7 E; s! F
        ElemType data;
. j9 j/ j( _; Q, R- B) z        MultiAdjListNetworkArc<WeightType> *firstarc;4 C7 W! Y7 c- C/ `. c

" p& M* i. [0 a7 E6 S  I        MultiAdjListNetworkVex()
1 m0 ?' P& b8 Z% }. e        {
) f! J* J' v" L: K                firstarc = NULL;; ^5 i3 \3 R: U9 [' m& w  ?( s
        }& D- h8 Y4 m9 ]! ^: a; e7 d+ U
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)- G9 b# w7 T: I3 F0 ]
        {
& J4 l7 A  C) `2 q/ Y9 M                data = val;
) d0 \, V, O3 f# d4 [                firstarc = adj;5 `$ i5 D1 W6 {4 D, k7 @1 ?3 d
        }
) h4 y; @6 s9 J5 Q& H8 P};4 p3 c3 E3 j; \6 E% a4 l% w0 h

* d: \. ^0 z& @邻接多重表的边结点类模板: c1 ?! F+ y' j; A& I- t: x

% z7 q3 F% M0 b0 F在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:0 \* ]7 @# `/ |/ t5 I/ R# d
tag是标记域,标记该边是否被处理或被搜索过;% W9 {! i2 N! O! M9 o0 e' x
weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;6 H9 K% M; z: W- C( r
nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;
0 P0 M9 W" M& p1 n& c  Tnextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。/ `( d, S& i0 w3 c

+ b% R! P- ?! D 2.png
5 N! W. Q8 C$ ?  p& _$ f/ H$ d% Stemplate <class WeightType>5 }1 d# W3 ]7 i4 S- e
class MultiAdjListNetworkArc
; N5 C9 Y" Q5 z- |{
6 P" Z+ F7 \3 x3 x5 f) Ppublic:" Q. `( r& a7 V& E' n. y
    int mark;                                       //标记该边是否被搜索或处理过* o" g- P3 ^1 ]8 a; x; T
        WeightType weight;                              //边的权重
' s: B1 c6 x- A) j/ K8 x        int adjVex1;                                    //边的一个顶点
* p4 t* Q3 w# K1 t; o; J        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1; G  ~8 N2 p: B+ F
        int adjVex2;( C. i" a' n& P* d, }
        MultiAdjListNetworkArc<WeightType>* nextarc2;3 ^3 F% f* R- ~
* F8 z/ z: h7 W3 ~* H( Q* X0 X6 q
        MultiAdjListNetworkArc()( U! s1 I2 e6 x& p& r1 J3 x- h
        {, X* f7 U0 Q5 P
                adjVex1= -1;
: }7 F! l2 d, x' S! [' |6 O                adjVex2= -1;
8 o! k+ J. A9 Q9 }) |& X        }+ l- |$ J; A! b- h8 Y
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)* ~; K) v1 V! |5 c
        {2 B. ]5 h" b: `& U; s" d1 R
                adjVex1 = v1;       adjVex2 = v2;4 \# X: Q3 q0 V( k6 K
                weight = w;7 Z3 y' j$ h% E5 ?, a7 I9 x# H
                nextarc1 = next1;   nextarc2=next2;
) f2 |, t' _4 h; ]) K9 I) Q! {                mark = 0;           //0表示未被搜索,1表示被搜索过: {3 Y0 U& L* g6 ]* z! ?
        }
5 Z7 a& X8 G. l1 L3 H- T. U
! [2 h5 I4 Z4 w, ~# L+ I; [) n邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
# A& x1 k% b) G' F; q; h, Q8 jclass MultiAdjListNetwork9 [5 C' j) h, r* J& z0 j: G
{( p, s' O! P; D/ j$ G4 ^$ e
protected:
' Y+ e9 F! L6 X/ m9 ]* c    int vexNum, vexMaxNum, arcNum;
5 ?4 D9 ?/ g7 n8 j. A4 P    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;. ?( B+ h# P9 h2 z
    int* tag;
8 L+ A: Q* @& P4 ^, _. C( n$ h    WeightType infinity;% M' l2 u$ _; N7 {9 N0 ^

% Z0 v' V* z( U9 f  Kpublic:  f: n! U: S, R9 u- ^  h
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
, C: g4 i" r: X
2 u4 Q5 {4 Z& h9 R8 K    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);5 u6 u! e7 A4 F" q- I
; i/ X: \4 k5 d; B
    void Clear();
! U$ h- K' G; l* x    bool IsEmpty()  d3 S; i8 [, j/ d; o8 |
    {
# k. V- G% |2 c        return vexNum == 0;5 [/ e2 O% H; g3 q. }
    }1 O( m9 {2 j/ j% d; T  }" R$ D# x. R
    int GetArcNum()const
" e% N( [0 j4 t; t! L6 z# `    {, X# Y' A# l0 r& u& V
        return arcNum;0 e6 j. g, b: Y9 x
    }
/ E  k9 ~1 \' i* t1 `    int GetvexNum()const
7 ?  n3 C* K8 S; }* n% q    {
; ?7 k/ ^7 ?6 G. \2 O1 c        return vexNum;6 z- x2 B/ |4 F* b% p8 I4 E" a
    }8 t9 l* u% M' I" i) M, g4 C& i* O

$ M- S" _) T, r! S  }7 ~  Q& ?- e! r+ y+ }$ x8 s
    int FirstAdjVex(int v)const;3 V$ @1 q! u2 u8 A% @3 x; d, ?$ Z
    int NextAdjVex(int v1, int v2)const;
/ Y: V2 h- ]8 N6 e2 g$ P' @    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
" c/ Y( C& u- {( X" |! L! c$ F* w    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
9 Y' T+ S+ h7 d! k) X9 N
" f$ J; b1 e/ t3 U5 n( X    void InsertVex(const ElemType& d);
+ i" v3 w9 f/ ]6 X    void InsertArc(int v1, int v2, WeightType w);
# j) A* r. v- l. L+ L
% W+ t0 x  W$ f! ?7 S+ Q8 k    void DeleteVex(const ElemType& d);5 C" G! g; E! L: _: x
    void DeleteArc(int v1, int v2);8 v+ k6 @/ R- P% ?2 Q* o4 @7 \

/ J5 G) T/ y$ t1 `    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);, K  T0 `+ ]8 z* L! ~% s) V
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
; R: L2 Z" @( n+ Q) c: z: t' C; L
    ///深度优先遍历: m! \/ k/ ^5 Q! _
    void DFS1(const int v);
0 x7 N7 H2 |% m0 ?" L' l% o( ?    void DFS1Traverse();& g0 \" y0 z+ L  a' {8 T
    void DFS2();- B6 O) M4 H0 ^2 R( r

1 b9 U; L( R  Z0 }, C, o5 r: I$ j$ Z    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
* l: d; L: ^+ b( o; K. H& l    void DFS3();) e/ T8 [5 Y& a  a; p& z

3 _) Y1 }. v) x9 ]" B7 c    void BFS();
& i9 K* Z* L  ?    void Show();  c7 o2 l" K0 S& D
};
% [$ q. k8 h" z& r! D
4 V( l+ c7 ]; F6 p2.函数的实现
( g- Y1 x5 @4 @: @+ B6 o9 n研讨题,能够运行,但是代码不一定是最优的。
, P. \  C6 `- V. C% \
* G" X9 q( k8 V0 L2 Q, _#include <stack>, q* P1 `1 \2 X8 S% `$ E; I
#include <queue>5 ?5 Y" U9 i# \# \

& c7 X) r7 M2 K, N2 H% _7 E! btemplate <class ElemType,class WeightType>
! G) m; j: y8 W) B* M$ N5 oMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)9 A- A' h9 G6 |. B& i, r9 @" \" e
{0 \/ d. r$ \" w9 h+ s# b! C1 F2 F
    if(vertexMaxNum < 0)3 d: _9 y- ?+ ]5 J8 u( x! R
        throw Error("允许的顶点最大数目不能为负!");
# Y, r5 f! ^& z    if (vertexMaxNum < vertexNum)
, m# X: c$ w4 w8 g        throw Error("顶点数目不能大于允许的顶点最大数目!");
+ y" `' z, U2 t5 g/ h) S$ H- D    vexNum = vertexNum;7 Z0 ?( U  s) M& j6 q/ `
    vexMaxNum = vertexMaxNum;  r& m; b/ X, Z& x. C2 q
    arcNum = 0;- o6 Z$ V# L& m
    infinity = infinit;
5 b3 d9 w" |+ @6 }6 r. y    tag = new int[vexMaxNum];
9 k8 q3 l- ~: |    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
- |, x- U- C$ t* [    for (int v = 0; v < vexNum; v++)' `0 N7 J- W; M5 ?* ~
    {+ _9 ^4 o$ V* c" [& J
        tag[v] = 0;. o! T2 ]6 q+ i2 n
        vexTable[v].data = es[v];' R, W0 k) ]6 r9 h+ d$ a) n
        vexTable[v].firstarc = NULL;
- _4 M" Z* R( T3 e1 h- U    }
% K, x% V5 F: N! K, g' O}
8 W0 `( a0 s! ttemplate <class ElemType,class WeightType>
; j5 j1 K) w) e: W6 EMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)9 ~) k0 h% ?) Z2 e; C8 k2 S3 q
{4 P# N% r. m( z( ]& X5 p! _
    if (vertexMaxNum < 0)! u9 Q3 `7 ?* i6 X' F1 ^: J
        throw Error("允许的顶点最大数目不能为负!");& d* v$ K' [7 |! V; R
    vexNum = 0;) V+ [: Z/ N! y* ^
    vexMaxNum = vertexMaxNum;
0 y" r1 R, I9 g, l5 i7 y    arcNum = 0;
8 S& Y& t+ @! T3 ?5 x* q  q: _    infinity = infinit;$ R8 `, t& q% I2 l& j  e+ t
    tag = new int[vexMaxNum];" q; I# {: R4 l2 U& b( l- T( m8 T
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];1 _) ?& L8 c2 Z8 m
}4 Q4 C: n, K& ]1 E) R' M7 y
template<class ElemType, class WeightType>
0 `6 P5 ^2 L6 \) @6 U- pint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const8 k& V6 j* S& W. t
{( A$ M  g3 I+ y" e3 ^/ A6 Z. [1 @" h
    if (v < 0 || v >= vexNum)7 I2 L9 O) u; o# k3 D' {
        throw Error("v不合法!");* T2 _- O2 b  V1 J0 Q0 E' w. h
    if (vexTable[v].firstarc == NULL)/ ]) Z& A  F/ I" p! ]3 b
        return -1;
* ^$ c# ]* d, j8 j    else' u% C  [7 I/ y- q' T8 s6 b
        return vexTable[v].firstarc->adjVex1;) A& Z8 w2 [- N( a/ U5 V8 H
}* X9 |  L, F: X9 O2 T

6 E2 ^% h6 U8 n" _  K% m7 Wtemplate<class ElemType, class WeightType>
2 m! c+ u, E8 w* E2 Y% R4 cint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const- q; B! Z) k6 o" T; C$ B
{3 J3 Y  |7 b" {6 ^. b5 V
    MultiAdjListNetworkArc<WeightType>* p;
# o. e" v- ~" O: N, z    if (v1 < 0 || v1 >= vexNum)% p# a6 x' U  \# {3 {
        throw Error("v1不合法!");5 e. i$ M0 E) }0 Z; _, |( N+ |
    if (v2 < 0 || v2 >= vexNum)$ k( i( Z& H" K% g# I: T4 v, }
        throw Error("v2不合法!");
8 L+ A# R: j3 G    if (v1 == v2)
; J9 _6 Z' f6 B# K5 a8 [        throw Error("v1不能等于v2!");+ F! |9 q9 `4 C
    p = vexTable[v1].firstarc;9 w# W8 a5 C6 t0 \
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
/ k+ T1 s* T) |1 n3 [        p = p->nextarc;+ l7 b+ m* |# G8 |9 h
    if (p == NULL || p->nextarc == NULL)
4 u' C' G5 K) U        return -1;  //不存在下一个邻接点
4 r" z' m7 {/ V    else if(p->adjVex1==v2), {0 H  n+ I- T
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);" D% g1 }6 }/ P0 \% v6 u' K- I! {
    else' \8 \9 c. `, c# C, Z" K# g8 w7 U% J
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
1 b3 ~, c6 I6 f0 }& w}
  w# C* h* Z% H& E, r+ ?template<class ElemType, class WeightType>
5 a3 N! }+ P, O. h; F6 H' uvoid MultiAdjListNetwork<ElemType, WeightType>::Clear(); _4 ?- l4 `3 c* Y! Y* J: T( e1 N
{9 H0 X. }) \9 @" [3 v
    if (IsEmpty()) return;$ Y& R5 B; E+ t$ x  {- e$ V/ b5 _: e( j
    int n = vexNum;5 Z" g. p# I/ D( r% a! P
    for (int u = 0; u < n ; u++)
- V. J2 h- v1 s  f; u: ~        DeleteVex(vexTable[0].data);* R2 h) N/ G$ ]. {# Q9 m2 F2 i
    return;' c! [" D  a) a; |& \+ s5 N7 [' G
}% f- s5 g% z" O8 r, ?
template<class ElemType, class WeightType>/ ~5 ~* b; K, \' D3 J! W
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork(): K$ V" s( B+ R$ b8 h
{- L/ g+ n1 H) j5 A6 E# ]
    Clear();
0 I6 F+ F/ X0 _- I}
! u6 P/ B9 Z% H3 J1 T: L$ c7 htemplate<class ElemType, class WeightType>
0 `- B/ V4 {! u$ l1 iMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)! h1 q) S6 `: @) z) n' d$ r2 Z/ T! a
{8 [0 J4 P) g$ i8 w
    vexMaxNum = copy.vexMaxNum;
& N3 U1 A3 z: i/ G    vexNum = copy.vexNum;4 Q: f) i. y" K: u9 g& v7 V
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
9 O/ W/ t  y, J- j, F2 |    arcNum = 0;2 k. b- e9 w1 A$ ~& U
    infinity = copy.infinity;
, ~9 [$ _0 V1 m1 X1 ^+ h8 G    tag = new int[vexMaxNum];
2 U$ J0 C" G1 G  B6 z' \
& u4 p% W( S; i7 ^3 \3 S7 L" d    for (int v = 0; v < vexNum; v++)7 z- m2 J. J- H& H# Q, S- Z7 a( s
    {4 L0 z( O  |' m' Q$ T/ [+ h" D% U- M
        tag[v] = 0;: F3 r4 G1 c, n7 V" u
        vexTable[v].data = copy.vexTable[v].data;8 {$ v3 a- x7 C7 ^8 }. T
        vexTable[v].firstarc = NULL;
+ I- U* w5 @( Z  `& L; a    }# g; r/ R6 }, E$ ^) @
    MultiAdjListNetworkArc<WeightType>* p;- X% o) X! n4 n# a( ~$ s0 Z% h( C

! l& i2 @/ S, K0 N% I( k    for (int u = 0; u < vexNum; u++)8 v7 V# L* ~5 |& P
    {3 V5 Y  W+ Q& f! G9 V; D
        p = copy.vexTable.firstarc;
4 G' i1 d/ b5 C/ Y        while (p != NULL)/ B" X8 v( Q5 e7 P5 F4 S, U
        {" E4 m5 y& M5 ~+ z/ B+ P; B
            InsertArc(p->adjVex1, p->adjVex2, p->weight);* W* M% v9 B+ C9 q( r: m
            p=NextArc(u,p);) h: D7 M% A; M) Y4 h0 o
        }* N  l* W8 l0 L) J0 ^: f
    }" v) O- d& ?- g6 ?
}: H& H* p3 f+ V
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
% l3 Q' k( n$ ?! A2 w3 H1 h, o  r7 wMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)" V: K$ k4 U. G
{
8 h5 h" }$ e  L8 }  u    if (this == &copy) return *this;
6 s& m4 g& o& T, C/ i6 K    Clear();9 X* y0 z5 ~3 C% @# a
    vexMaxNum = copy.vexMaxNum;$ Z, G  \9 G' p. m3 v
    vexNum = copy.vexNum;
! A# ~. M9 w3 T7 E, p& y    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
0 p) X4 t9 m. O' W    arcNum = 0;
( H$ P8 E4 Y+ f( _3 J4 l    infinity = copy.infinity;3 @7 r. I8 k% ?+ |/ l6 n5 m; v8 a
    tag = new int[vexMaxNum];
# P4 b' c. p" Q  \5 O2 y) f2 o" C! m
    for (int v = 0; v < vexNum; v++)
8 p- h; n8 E! b+ J+ L5 F) I    {( L# p; F5 L8 b+ D5 v; h0 |
        tag[v] = 0;3 _& ?- N4 [8 f$ n4 A7 o' u  X
        vexTable[v].data = copy.vexTable[v].data;
8 ^: ^/ w1 `1 i$ t, O        vexTable[v].firstarc = NULL;( {. V. X  s& H5 N8 l
    }
. Y8 y! V+ n4 ^. e( {# P, a    MultiAdjListNetworkArc<WeightType>* p;3 @" b3 x4 n+ W* r
1 S- s' }8 V5 Y3 U( g4 r* t
    for (int u = 0; u < vexNum; u++)7 I. u& A- F3 Z- Q9 l
    {
+ E- s# Z4 Y$ Y0 L1 z  C        p = copy.vexTable.firstarc;. E% ]6 x+ @. X4 b( v5 g3 N+ M
        while (p != NULL)& o1 N' [' y! ^  U  U/ v: v
        {$ P+ Y5 O, p2 b
            InsertArc(p->adjVex1, p->adjVex2, p->weight);3 q( d/ h, y& F6 }6 K
            p=NextArc(u,p);) _4 o) h( {; D1 p2 [( t) ~. t
        }
: S" N7 Z! q, B4 t& v/ M! i- ~' z    }' D3 M% y" h5 X" W2 }+ k+ y! n
    return *this;3 B0 I4 u& F- x/ Q" n
}/ ?$ h1 u0 X) x( E* j- D; ~
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
, b3 n- _6 C" Q2 Q- J2 bMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
( G! h8 T) y/ b- l9 N{
& H4 M* |5 o9 a$ @    if(p==NULL) return NULL;
& }" o7 S' }2 [& t    if(p->adjVex1==v1)
- g  f2 m- @+ l) z: h( O        return p->nextarc1;9 L' N7 V+ c1 ~! P8 p* L. B
    else
- @  V" G3 E" F, \0 l: k        return p->nextarc2;4 a9 V% q9 z6 n6 Z, g4 X
}: n: h9 {/ t! p/ A+ D2 x; [
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*3 \) y. W2 V- [' c7 g  k
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const* c- L; C6 y, e0 L/ B; \
{9 R6 z' J/ R0 ~
    if(p==NULL)return NULL;3 ^' l6 E6 C4 r% s" x
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;: `& U; \2 w1 B6 N  X9 M- r
    if(q==p)
6 P1 p/ n& e7 @  R- A/ w        return NULL;* i2 g- t9 Z+ ?( t: |7 E. \0 X9 z9 L
    while(q)
; P2 s+ N: ^# b    {% `0 j! Y& ^2 z2 y: \
        if(q->nextarc1==p ||q->nextarc2==p)
8 |2 C5 b; \! Z. P/ i& J            break;
" n' i  Q# S+ r% @3 W0 {/ S        q=NextArc(v1,q);
" U, y$ y& X/ C2 G/ C& e$ T% N    }+ E' Z8 W6 X) P: b( f
    return q;
( z2 t' X' E& m. C! o! ^, K}
( n7 o- j* d8 x, @) E  ?template<class ElemType, class WeightType>( V7 |8 q' A# c+ F
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d); s- B+ ?) x% p7 B% C! O
{
# H2 _- `. A( W; L    if (vexNum == vexMaxNum)
% `" O! E0 M1 m7 X% P) y        throw Error("图的顶点数不能超过允许的最大数!");6 y: Q6 \& H( a: H8 L( O" t
    vexTable[vexNum].data = d;& M1 p" d& c' M- d+ k. A
    vexTable[vexNum].firstarc = NULL;$ p2 e# E' {! H+ K1 `, Q
    tag[vexNum] = 0;$ G6 u: r" g2 w2 p1 s- k" f4 i
    vexNum++;+ C- h) D9 u$ }" V8 F$ }# d3 Q
}
: z7 T1 F& |- J8 J% y9 vtemplate<class ElemType, class WeightType>
2 o& P6 [" Z! j: R1 M! Ovoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)5 J, k# Q! a' h  ?
{) Q3 m" o5 `& k( c! x; l$ V
    MultiAdjListNetworkArc<WeightType>* p,*q;6 ?1 Z, O( z! j/ f0 t
    if (v1 < 0 || v1 >= vexNum)9 M& A2 t- b+ R' x
        throw Error("v1不合法!");
- |% N1 @' \3 W0 ?) m    if (v2 < 0 || v2 >= vexNum)
3 P5 f3 J) {) V/ p- d9 {. ^        throw Error("v2不合法!");2 B, G: x2 }9 x3 e) X& n+ d. C
    if (v1 == v2)$ p% i6 d7 ]4 R) `# Q
        throw Error("v1不能等于v2!");
5 G( r/ C3 C( e% G    if (w == infinity)
( K! Y% n) N/ l$ P        throw Error("w不能为无穷大!");
) y# @, f7 F1 H% d: N7 A2 e7 ^+ M, V* _! I5 F$ p

. @, e* K8 u4 B1 F  l7 l    p = vexTable[v1].firstarc;
5 Q5 B1 H+ q4 Q, Q$ B8 F4 S/ ~    while(p)
# M5 I8 W9 P- }; \    {
: o6 n! K2 P: o' O        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
. w. {- d) G1 @7 W& ?        {
0 S$ j$ x$ \) S( U            if(p->weight!=w)- m9 d; b& H4 n; F
                p->weight=w;
& O" ?4 Z1 W* {( z$ U  z5 n            return;+ @& _0 N- F1 {8 \: I0 W: W/ C
        }! {  B; {% Q) Q/ ^2 K9 I8 n9 y

1 U) Q6 b( k% z+ }        p=NextArc(v1,p);/ d( I, W7 w& Q! T* B
    }+ f* `" E7 r( N' G* j" A: p: K8 q
    p = vexTable[v1].firstarc;
6 N( O" H+ p/ v/ M7 r    q = vexTable[v2].firstarc;+ `, u/ t5 q( |2 O5 Q4 I4 I6 c; u
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
0 G- y3 n! t) Y) b7 J: w$ \    vexTable[v2].firstarc =vexTable[v1].firstarc;, a, ~  y0 d9 B7 j7 }8 h& j
    arcNum++;" n' D9 W5 F4 h2 |7 A
}2 {. _7 {8 Y: l' e# ^4 [0 t
% j8 N) V( f" K" c2 D/ V
template<class ElemType, class WeightType>
8 c# P! u* ?) z2 \1 g0 v; h6 ^; ~void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
. \& O" a: z3 z) m" ]" u% N# K{+ V; g+ U+ w5 I/ L9 {6 ?) K) ^

" W7 I  E$ E; `5 _  H3 W0 I    MultiAdjListNetworkArc<WeightType>* p, * q,*r;# A& c4 ^; r# v2 C+ e
    if (v1 < 0 || v1 >= vexNum)3 n% T1 s; W0 b. i* \
        throw Error("v1不合法!");
( e' m6 n; S. Q+ |8 E0 v  q; a    if (v2 < 0 || v2 >= vexNum)" I' A( V; }% w) a1 q# x
        throw Error("v2不合法!");" L4 E0 s* q- y( y3 _4 X. `! g$ [
    if (v1 == v2)& Z7 p3 `& x, w
        throw Error("v1不能等于v2!");: L# d& b& l$ l: d

6 Z; B6 j: Y4 j    p = vexTable[v1].firstarc;
, w) e  [6 |) e1 V0 A" f: j    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
2 q' u* i! @$ J; t! l    {
" q) h1 O4 X' }3 K        q = p;& ^4 p- l( {% v( l( {; P2 K
        p = NextArc(v1,p);
8 Y9 K: f& `' L5 Z# T7 F+ }+ k: T    }//找到要删除的边结点p及其前一结点q6 R* E7 X! t/ U; O! Q

$ W! @" c3 l, m: E" R5 p5 v    if (p != NULL)//找到v1-v2的边
6 s8 `* T8 h2 C, J    {
0 o% R9 S3 z4 y; }+ b& C( T        r=LastArc(v2,p);- x; R# T, q# A. |$ y% O$ _
        if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL  o: H+ o4 f- r. k9 B2 C
            if(p->adjVex2==v2)9 l* T/ O) m4 q) r5 I
                vexTable[v1].firstarc = p->nextarc1;
+ e3 G5 h/ g/ A. x( t4 h            else vexTable[v1].firstarc=p->nextarc2;4 g1 [9 O2 l( K3 |* o- `
        else//不是第一条边
( x7 W- I, V6 y        {+ `1 {, a: Y4 {+ _: D$ p
            if(q->adjVex1==v1)
( U1 q8 p! g3 \! E5 U! W& X                q->nextarc1 = NextArc(v1,p);
( A( W& s# M9 z# d+ T( a            else  v0 T; x$ k. q  C* `' c4 C5 R9 Y
                q->nextarc2=NextArc(v1,p);6 }6 u3 n* Y* j, l* K( z9 K

% b* g& ?  H7 x8 Z8 r7 S0 Z8 {        }
0 d% f- U- @6 W+ g8 a( R3 X. k        if(r==NULL)
- T* x2 H- M) f5 s2 }! s# [# a            if(p->adjVex2==v2)+ F0 A9 z& z- T/ G
                vexTable[v2].firstarc = p->nextarc2;
( m0 k% ^" x4 k/ g& ?! f            else vexTable[v2].firstarc=p->nextarc1;
* f) t5 C- c; a9 E% m% I        else
6 O5 E( w/ X; k. b3 m        {
* b) e) F* i' d5 P0 ]! V            if(r->adjVex2==v2)
, a) c  ^# n% c# [; T                r->nextarc2 = NextArc(v2,p);
% B. q8 q# q4 J( q4 I9 L            else1 q0 w( _4 ~. Z  ]6 r* G
                r->nextarc1=NextArc(v2,p);0 D& {" a6 U8 g+ s( X: i
        }
, c2 T/ c' s1 Q: `) Q        delete p;2 U3 g% \- z( q$ e1 E8 o/ l
        arcNum--;3 i1 n6 x4 s, C7 E+ I+ y
    }: h4 I1 r2 R% i- Z  M
% z4 M! y9 G/ i. W, D  P  @
}6 l, U2 j4 e) }8 `
template<class ElemType, class WeightType> void
6 l  `& f9 a8 T" RMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
8 V# K& j" c# a; D' x/ x{# Y6 m9 c1 ]) w2 x1 j
    int v;
7 q& [: k0 \; \( e/ L* U1 Q% x    MultiAdjListNetworkArc<WeightType>* p;
( ^$ g1 z# O4 y; K5 H" r+ _0 h& R0 \    for (v = 0; v < vexNum; v++)//找到d对应顶点- s' s7 T. ?5 T7 {+ x2 }" x
        if (vexTable[v].data == d)
) z% j; N( x9 {, J9 p, B2 ]            break;9 T, F" p- P$ O) ^/ Q
    if(v==vexNum)
$ G  w/ i6 ~' n/ E0 j6 I& H, Y* P        throw Error("图中不存在要删除的顶点!");2 |1 {1 U" g& H

6 B3 A8 _# X# O2 m    for (int u = 0; u < vexNum; u++)//删除与d相连的边
$ x6 U/ w" a5 N4 Q        if (u != v)
7 B7 z( w! S0 T        {
0 y9 R8 Z0 o" E8 g* ]" d" V            DeleteArc(u, v);& \0 {; }1 e  |; W$ Z" `3 G
        }
( G( B. X* [2 f" s$ d4 R% d    vexTable[v].firstarc=NULL;( p) d  O3 f/ o3 Y& h; b

) u" R: Z7 ^) F2 e. ~- j. T    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置# B+ j) S! b0 m8 d9 L
    vexTable[v].data = vexTable[vexNum].data;
+ K$ q3 c8 t1 y: |/ I6 C( t    vexTable[v].firstarc = vexTable[vexNum].firstarc;' p! u$ s6 P3 ]: r2 ]5 ~
    vexTable[vexNum].firstarc = NULL;
6 m5 t9 j: M  [3 j  t* ^    tag[v] = tag[vexNum];
' G+ @1 q1 F- P: W    //原来与最后一个顶点相连的边改为与v相连  R" C# z" B" {
    for (int u = 0; u < vexNum; u++)
3 |& n2 a, H3 Q% E: f1 O) b* Y    {& I) M1 n  D  ]4 _, ^2 Y  J: {1 K2 z
        if (u != v)
5 L" P; w7 g/ w/ V: ^* x  g2 g        {( y, Y& Z; G, V8 V1 c* H7 v" K
            p = vexTable.firstarc;
$ P$ A; Q5 K5 X0 U  Y; m            while (p)5 b" A+ w0 S' y- |7 j# m* M
            {
) w& |" a% a0 o5 ^2 o! V                if (p->adjVex1==vexNum)
% X* t4 a% G1 G% O                    p->adjVex1= v;; Q  I, o; X& G2 G. A- d& A
                else if(p->adjVex2==vexNum)
& Z: D" `- @( M, H! M" \  }                    p->adjVex2=v;
5 p% }/ Z. u$ s& p                p = NextArc(u,p);
+ @' E* C5 H  |& Y            }% Z! C- K, s5 w" F
        }$ h  g+ Y; Y" j$ c5 p
    }, k' S1 o( X  K. H. [) z
}
; x5 M0 q9 _  }' E# H1 m+ c. @///深度优先遍历
  Z8 d# P5 F& A+ z, p( J! @; Htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v); {3 p6 W" Y& w* o" ~: z
{
% Y6 A' a1 G6 z3 Q    tag[v]=1;0 P0 {$ y/ l4 ]2 L: C
    cout<<setw(3)<<vexTable[v].data;0 J- T5 s% Q) ^/ t5 I. B, i
    MultiAdjListNetworkArc<WeightType> *p;
( m, |0 l& l0 Z8 t    p=vexTable[v].firstarc;
- M) O2 n5 L, R$ ]; H9 g8 \  L    while(p)6 A$ r4 ?( F9 o
    {9 z  \% \; |% u
        if(tag[p->adjVex1]==0)" A$ a( a  L' c. _8 F
            DFS1(p->adjVex1);
/ Q4 O% G* j. @+ a/ e& R# K% [        else if(tag[p->adjVex2]==0)
8 g; ~; k; T9 @% ~8 r( |# O            DFS1(p->adjVex2);
$ I, q- a8 r/ G; F        p=NextArc(v,p);. v6 w& f( k/ X6 S! S# q
    }
! k6 b7 q0 N3 x. F# h: v" L) N  Z: |}
1 K  F7 q4 T9 etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()9 Q3 O" R, P" ?. Q$ m) @, y
{
7 ~& L" |  @& b7 k" z: @    for(int i=0; i<vexNum; i++)
/ g+ o7 g7 i+ P' N1 ~- x; a        tag=0;
, y' c7 i( g! a& i$ ?    for(int v=0; v<vexNum; v++)" p& d( D3 Z) t" Y' O4 j' [  T+ g
    {
: ?# w6 \& ?4 j. P! s        if(tag[v]==0)
$ k# ~7 b) f4 N" t            DFS1(v);' r+ n9 Q! X6 [1 M5 U
    }( _" W. A. w! C/ P/ a
}
9 \- M3 D  T) n  \: L9 {template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 ]1 `' B2 \4 f' ?  U& E3 U( y
{! Z4 [! x' j  O
    stack<int> s;4 F4 o8 @% t5 b! A  P8 [
    int tmp;# m6 L* V0 ]8 D! k% R
    MultiAdjListNetworkArc<WeightType> *p,*q;
3 `2 _$ i+ H8 E6 x    for(int i=0; i<vexNum; i++)& I4 L3 ?, C2 g8 V7 B. R
        tag=0;
8 w+ v# p5 \4 [, m* C9 e; r    for(int i=0; i<vexNum; i++)
" Q+ c* Q) p" ~# ?2 d" z7 y    {
7 K5 O5 H- O4 y* d/ n3 k        tmp=i;
. W- P' Y1 D3 {% l; v9 q8 u        while(tag[tmp]==0||!s.empty())
0 o7 w) \4 p, k7 Y        {
0 Q1 v3 d5 z- n/ r: y) \- a            p=vexTable[tmp].firstarc;3 h; W& A' V* @# P) M- X7 \, b
            while(tag[tmp]==0): G! \* m, ^9 w
            {. x5 F8 v: s5 {) x
                s.push(tmp);$ B& P  H! g& n7 D( r
                cout<<setw(3)<<vexTable[tmp].data;
/ x- W& C- ?& {, ~+ }0 a                tag[tmp]=1;
9 v' q' i0 x/ @                p=vexTable[tmp].firstarc;
6 P/ p% ?" N; e5 ]2 t4 k* X9 l                if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
* R5 Y* @- E/ o1 `' ]# m( i7 `  N                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);/ K0 [) z# D) P+ P, \; C1 H
                //cout<<" 1st     tmp="<<tmp<<endl;
: n! d" i# j" i  E            }
8 F. w. q7 v( F! j2 e% u: x5 p            if(!s.empty())7 D- W2 d. n% s. r0 I7 A7 b& F
            {
9 j% _" f  b5 E! `% A, u                tmp=s.top();
9 X+ z0 b# y5 Q, Q                s.pop();
8 s) `1 d; }4 W6 e! D1 {                q=vexTable[tmp].firstarc;
9 {  g7 A) `- z% v  i                int t=tmp;* l: U2 U+ l, }1 u% O
                while(q&&tag[tmp]!=0)# r. G% Y! r7 g. _( a& r
                {" o; Y8 l) P. d1 l
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);" [. @7 g) u+ Z9 }
                    //cout<<" 2nd     tmp="<<tmp<<endl;% Q8 Z) q  n0 }6 M  }) A
                    q=NextArc(t,q);3 i9 e9 J, H+ O* E
                }# m& W! H7 |1 P' E; O" E
                if(tag[tmp]==0)% I& m6 d: G: W1 X. C
                    s.push(t);
. l3 j3 h1 k- p% I- t                ///1、对应上面连通分支只有1个点的情况
- }2 H: M  j2 @  H0 }                ///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈6 m0 }3 _# S+ \/ [
                ///tmp要么等于找到的第一个未访问节点,
6 U. K' V% L0 o7 |                ///要么等于与t相连最后一个点(已被访问过)
. F. A* g+ x3 D8 N                ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点: Q, P( s% M7 K# N( @
            }. R$ Y/ W9 w( r- p, Q4 M- D8 Z2 V. t
        }
" K7 n; |1 K5 j2 e+ G    }
$ Y: ~$ F( \4 C  m# w# i}9 B! v1 A* c+ j# S8 c0 X, T5 s
//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1* H( Y  K: l, F8 Y
template<class ElemType, class WeightType> int' }; N" N" k* ?1 j7 y( }3 D
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
  K) `- G. ~7 T+ D0 w+ {2 }! `{
* C, O9 l" W) N: I, Y) y4 r( a/ T    if(head==pre)
! l* |& L! n8 _. X6 p# u7 y& x4 i( l  |        return -1;
3 ^" }+ ?/ \. S0 D0 a0 [' d, @% p8 @3 h2 T9 t, w8 {6 F& K$ ~
    MultiAdjListNetworkArc<WeightType> *p;
# h8 b1 v9 ~2 g/ d# m    p=vexTable[head].firstarc;
5 ]: k# V& y2 F  N2 }    if(pre==-1&&p!=NULL)
( G- P, g  [! a) A+ q  ?7 u' D        return p->adjVex1==head?p->adjVex2:p->adjVex1;
4 h$ ^( m- z7 s& j, X4 r& g) P    //pre!=-1&&p!=NULL6 N1 G% v5 x! p1 L$ s' y* G
    while(p!=NULL)
2 V: G. H% n2 f0 g# D    {
1 n! w- w+ m  z# a        if(p->adjVex1==head && p->adjVex2!=pre)
- f2 F# w2 A" G            p=p->nextarc1;
- W4 @! l+ K/ I7 T6 p, H! L' T        else if(p->adjVex2==head && p->adjVex1!=pre)
" T/ z1 C1 u6 k1 `7 l            p=p->nextarc2;/ c! k' K( I( j: t2 K; o/ ]/ z
        else if(p->adjVex1==head && p->adjVex2==pre)) k8 ?" E$ f! d: p, X8 B; W# B
        {& R: N# h: O8 ^" a) _9 @
            p=p->nextarc1;
) ]. }4 U5 r2 B, F1 x" V            break;0 d7 z/ r/ b0 r- W- f& r  M
        }
. I, i! j: p. `8 y& k0 D7 y0 t        else if(p->adjVex2==head && p->adjVex1==pre)
# o! o; P1 z7 i$ z: g2 z        {
. f0 e! K- o, x2 _: F1 _            p=p->nextarc2;
$ k8 o( _: [2 {) }            break;
* ^$ Q* _" @" l; }        }2 Z# v7 ], p8 g- c/ m& ?, F  {& T" P7 i
    }
% r  k8 E/ r- ~4 a  g    if(p!=NULL)5 ~. T( Q; T$ \$ t4 ~
    {
; Z7 I4 l0 r) g* @7 P" h        return p->adjVex1==head?p->adjVex2:p->adjVex1;0 U7 @8 N: R  F7 \6 U; w( \
    }$ F8 K# F' Z' \3 f
    else
/ m0 ]9 x) k7 _3 @5 ]2 O        return -1;$ B9 S, @" Q' y- _+ `( }" c
}4 O9 H# }9 s. a0 @3 z

  ^' d  `+ c: z) F9 @- y# B( n# ^- R$ ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()4 J% K  N7 }4 t4 W
{0 D' q4 h* e. A# c: _. P$ w
    stack<int> s;
2 H& l0 P1 a5 C1 f, X/ @, L    int p,cur,pre;
& ?1 L1 k. L9 ~    //MultiAdjListNetworkArc<WeightType> *p,*q;
6 k; e7 y  W, T7 @" m# _    for(int i=0; i<vexNum; i++) tag=0;//初始化' k$ z" x) m% D- O% Z: ~
4 A7 L: ?- x6 b$ ?: {
    for(int i=0; i<vexNum; i++)0 d' F( m1 K  z5 {& _: @) w
    {
6 _/ F4 d% o4 K$ n/ a        cur=i;pre=-1;
; @+ B, t) F8 ]) L        while(tag[cur]==0||!s.empty())
/ V. q4 s8 i$ g  F- K3 D8 ~( J        {/ t, V6 W' b/ [: G
            while(tag[cur]==0)
; z- D# b% L3 n, u; q            {
! r: |5 v7 Y& {' x8 G                cout<<vexTable[cur].data<<"  ";
7 i' J$ V7 e5 }! j                s.push(cur);
+ K3 c# z# i5 C# M7 V# l* H8 s                tag[cur]=1;
* \8 s) v' R5 N3 l               //初次访问,标记入栈3 x4 A6 a' Q* V& \9 p. t2 ~
4 b; W( ~5 Y! Y, E" H. G
               p=GetAdjVex(cur,pre);//p是cur的连通顶点0 x% |* c7 I1 d& g; b6 P+ t. B
               if(p==-1)/ N- t  M: h& a7 S$ r: T0 {: \0 B2 J" E8 B
               {  S# _6 D  \' G6 W1 E& r( i0 ~
                   pre=cur;s.pop();
* f$ k5 E) [& V1 ^                   break;
; ]5 V3 v& S1 g" |               }
8 u* P1 b, ]2 d* t% h+ S               else$ ~5 z( b5 V+ U! ?- r
               {' {  x+ k' H) G  P* l
                   pre=cur;# ?  M% F) ^& E; q4 s# A
                   cur=p;
2 L6 g- ^, `6 H  t0 F2 ~# u               }
7 J. \; W$ ^. ?* P) |5 O. ~
) y7 C" ?$ {, [1 ]  Q2 P2 j$ h5 u            }6 L1 h" C2 Y; O) \  E& b) i
            while(!s.empty())# P, V6 D, U& Y  d4 [
            {
# H5 Q4 g( l6 e                cur=s.top();
9 y. ~* s/ ~" V  g/ `                p=GetAdjVex(cur,pre);
1 @5 @$ _( I( T7 }' {                if(tag[p]==0)
+ q/ S9 g' X0 ^  X, H) E/ [, p                {3 b" `, T0 n4 q- b' T! g: R/ c# z
                    pre=cur;
: F1 H3 p% A4 D8 }; s- d                    cur=p;$ {" m6 j% |7 j9 U1 s
                    break;
3 [4 b9 m5 o7 P0 B8 I                }
; ?: b& e( ^2 v' X                else0 m( P0 x7 ~* f* i$ b5 [
                {
$ @- M, @$ ^3 v+ e                    pre=s.top();; y+ [+ F" f) ]( q
                    s.pop();
0 p6 G: ?# m& y6 ~6 u                }  w4 A& f, |- z6 T6 r! Z; R, W

! V4 W/ l" ]2 Q% d$ W  c& {            }6 Y- f: ]" K  H. F' X* u
. i  t, U5 e2 d7 U$ r6 `
        }
2 B# P/ {5 r9 g    }
. x  L; ?4 t" w- T, k}# t$ j* O4 z/ p1 C* }9 ~% t
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()& C7 j* R' _$ c
{
2 U& `  ^, w: o3 s4 y    for(int i=0; i<vexNum; i++)2 B$ y. ^  s- P
        tag=0;+ a* ^" Z) y1 Y( z. c! R
    queue<int> q;
9 Q$ R; t8 I' t) C) r1 ]    int tmp,t;
8 o* @' b) W, |, [6 r: \( q( x' U    MultiAdjListNetworkArc<WeightType> *p;
+ v8 s- Y2 Y" p. L( w8 B8 t' D    for(int i=0; i<vexNum; i++)
) J9 [$ K) z" a    {* _; f6 N5 X8 T8 T) v" U
        if(tag==0)& c, d- G1 M- U% c$ M
        {
  S6 l3 P% N/ v0 P! P            tag=1;7 e1 e7 o8 }$ H
            q.push(i);
: t8 k5 R, U& i# w6 M) a            cout<<setw(3)<<vexTable.data;
, f8 L" b7 ]+ L3 h4 ]' L5 s" l        }
( d+ M. ^9 O' H, g        while(!q.empty())
+ I* t7 `( h# s        {7 @# Z) [  ~" ?1 D1 A% y( J- T) f
            tmp=q.front();
% }5 d1 w# I9 A            q.pop();
7 F* _% P/ Y  {3 o) Z. g3 N            p=vexTable[tmp].firstarc;6 i# J" w1 ~& z. V5 R" y% I1 q
            while(p!=NULL)7 G6 m. |% Z/ z! s
            {
* Y5 N& |. O0 _2 N                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
: `4 |9 L" `3 ^, a& @1 [8 q                if(tag[t]==0)
/ I# {6 a0 ?* s8 {5 e; Z                {
, z$ r. [1 J! T4 K% \                    cout<<setw(3)<<vexTable[t].data;
# r* Y1 m2 r* c( u                    tag[t]=1;
& Q: q$ l9 ?( F! k                    q.push(t);$ A) c( G1 k8 d5 L* a1 g% s' {
                }
! T% }0 r# A  b% z- a                p=NextArc(tmp,p);3 m/ M( C* e! K+ `+ A; e5 ?
            }3 t( ]. O2 r! g8 B6 ~6 x
        }
. v( }" @8 I; v6 t( Y    }0 i2 B1 T& P* y0 N1 K: ?: ^3 T
}
: i& t* V0 t' X; V, K4 {0 j6 btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()) r# b9 ^) E4 D' y* _
{
4 R- P% E  f8 B# T- }# r    MultiAdjListNetworkArc<WeightType> *p;/ ^; c5 {" ]- Q
    cout << "无向图有" << vexNum << "个点,分别为:";
  k5 s% I. {# L; O, ^# `5 z- T    for (int i = 0; i < vexNum; i++)4 e: j5 g: ?/ ?" \- f+ z
        cout << vexTable.data << " ";: ~6 x1 y# {' a1 r* K
    cout << endl;' ^/ |! y2 o8 \2 Y
    cout << "无向图有" << arcNum << "条边"<<endl;( c: H* \" y: f: I$ f0 c
    for (int i = 0; i < vexNum; i++)5 }$ @# E7 t; e8 k  f  x* r" b: P
    {; j) S7 {; B/ ^! T
        cout<<"和" << vexTable.data << "有关的边:";8 ^8 }& V' m1 I  U$ v0 T
        p = vexTable.firstarc;
/ W# t' X* x" t5 n! y4 U& t" H( S$ [) e        while (p != NULL)4 h  n& S6 O9 ?$ o
        {
; v/ Q8 k1 \: v  S" S5 h8 q            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";/ v+ S5 ]- n' Q2 z2 Z! h( s2 N
            p=NextArc(i,p);
: Y6 U( _$ X0 ^8 a8 @        }
+ ?2 H9 W& ~$ ~0 a& M4 Q        cout << endl;7 N3 r( S7 @1 {& C1 g9 ?; D
    }: O8 y( D9 V7 b* y
}5 k" P+ \9 K9 y9 S7 Q

) ~( a1 d  o4 e; K7 a+ [' K% D  I+ J: b0 t! v
邻接多重表与邻接表的对比
9 G4 m. {) W; {8 B0 p$ z" a
' o& G$ V. @" z8 Q' S! Q邻接表链接8 C( k5 K9 B0 w7 ^) r
在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
1 |- @, U6 o" `& ?9 X/ a在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。
# K( I) S& q5 g5 H, E! q* y为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
  g: ?& ]; E5 e3 e% |& W————————————————' F0 `4 e6 r8 A" d' D) Y* a2 {
版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。* d0 s) @" r9 `1 Y" e
原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
% d& U! ]" I# \/ O) {, m4 p% p4 J9 d' {& W! ]
7 n+ c  Q5 U1 ~2 z2 k6 l. k

) \& s. \1 r& ^( U/ n% D; F! W
  M3 o' I, Q/ v# [9 m  ]% n————————————————5 {- P7 D# Y3 d  H6 N
版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
& E6 H! ?% b' g) R原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958, ~6 z; M' k7 a/ G/ g/ I; |

( K$ z( q/ m0 x
3 Q3 _$ [% z0 {3 y- _6 z8 h5 w




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5