数学建模社区-数学中国
标题: 图的存储结构——邻接多重表(多重邻接表)的实现 [打印本页]
作者: 杨利霞 时间: 2020-4-26 15:26
标题: 图的存储结构——邻接多重表(多重邻接表)的实现
4 Z+ I1 k6 G, `& t3 S
图的存储结构——邻接多重表(多重邻接表)的实现
0 D+ h4 _# Z+ _7.2 图的存储结构' u3 G! Q1 E0 X+ F
. N. W) s, a* k2 m2 O. V
7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
W; g# m6 {& D7 D" U邻接多重表的类定义3 D# T' m ], h6 W# J! o
邻接多重表的顶点结点类模板
- i2 H( q T4 d. {2 c1 E, ]" Q+ ^8 G, h邻接多重表的边结点类模板- g$ T0 E" V Q/ O$ a
邻接多重表的类模板3 w: P! e: x9 Y( H) K8 e. R" m
邻接多重表与邻接表的对比) Y& P- E6 ~' P$ a! Y C. Z& O
7.2.3 邻接多重表(多重邻接表)Adjacency Multilist
+ J7 ~- g" S+ R- x6 _4 V) @) Z. K) s, t7 Y- p
在无向图的邻接表中可以看到,每一条边(vi,vj)在邻接表中有两个边结点:一个在顶点vi的边链表中,表示(vi,vj);一个在顶点vj的边链表中,表示(vj,vi)。( @" Y( N* w" ^- X
在较复杂的问题中,有时需要给被处理的边加标记(如访问标志或删除标志等),若用邻接表表示,则需要同时给表示某一条边的两个边结点加标记,而这两个结点又不在同一个边链表中,所以处理会很不方便。若改用邻接多重表作为无向图的存储表示,则可简化上述问题的处理。
/ Y) @) l8 L/ A& v2 ^$ H2 h( a2 a5 M& B$ b1 z7 H* c$ z9 _9 [% W
邻接多重表的类定义; S6 O+ D; a* _3 h4 I
3 t- B7 v d1 P8 v8 @
邻接多重表的顶点结点类模板对图中的每一个顶点用一个顶点结点表示,它有两个域组成,其中:
3 p R/ {7 F0 E- Vdata域存储有关顶点的信息;! i* m3 G( @& a3 F
firstarc域是链接指针,指向第一条依附于该顶点的边。
x9 o4 z3 W/ |& w# z6 ~所有的顶点结点组成一个顺序表。
- G- X5 _3 ~% \0 ?0 {' a; c+ q+ S
' `$ k! A! z4 C7 ~1 q% C
template <class ElemType ,class WeightType>+ l( G6 W8 o* G6 Z$ T3 H$ g* U
class MultiAdjListNetworkVex
" w- }: t- R$ }8 _5 n# N2 N{& i" c2 \* y) ?6 I2 e# W
public:6 k' z6 V1 K7 G/ }/ b
ElemType data;* y) m8 F) }, o! L' G x0 |
MultiAdjListNetworkArc<WeightType> *firstarc;" e0 j, ~, G3 U+ Z5 e4 m. p3 z- A* C
: @: R# s3 F" V0 N" d. B6 \
MultiAdjListNetworkVex()
! n' B6 @! f4 ]: q$ Z7 E {0 j) d2 [( @8 Y- A" n5 |3 e
firstarc = NULL;- j8 s: K/ `$ V( F! h& R/ g
}
, a6 V3 Z* {% o/ q MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
. h& Z7 g P3 u2 D {
b# l( |+ K6 i: q1 O' H: k' u data = val;3 @! z+ a9 m; ~ W
firstarc = adj;
3 i, W1 u6 d9 c; d( U; F6 B( m }0 u5 @6 z G; s3 [% `, V+ A0 O
};* e- u; R$ h7 e! }
+ y3 Y* \. Y" ~& O j8 W' ?3 b& @+ ]邻接多重表的边结点类模板
) M! U5 ~) R) {6 W
, k, |0 Q& y: u! f在无向图的邻接多重表中,图的每一条边用一个边结点表示,它由六个域组成,其中:. q3 U" p5 A2 w+ e Z
tag是标记域,标记该边是否被处理或被搜索过;, j3 o3 q& e/ P# \. m/ W8 g
weight为边的信息域,用于存储边的权值;adjvexl和adjvex2是顶点域,表示该边所依附的两个顶点在图中的序号;& l! H; Q# Y+ q# H$ R/ e
nextarcl1域是链接指针,指向下一条依附于顶点adjvexl的边;
7 o' x7 S/ M5 I9 R& m5 lnextarc2也是链接指针,指向下一条依附于顶点adjvex2的边。
+ v& \$ q* F6 b4 a ~
" h8 |, i! A% r- }' ~4 a* r
; _$ R0 S( t! E/ }) I; Ftemplate <class WeightType>
% S( _* V, g7 {- u- A6 p% p7 G8 mclass MultiAdjListNetworkArc
, M' L# }6 }8 T7 ?$ i' O{! Q8 t" m5 f$ w% y( F4 e
public:
4 ~+ @: P, ^6 g' B7 B int mark; //标记该边是否被搜索或处理过
( `5 a0 a, R" L( T/ l8 C' V WeightType weight; //边的权重
3 S1 ~" b$ g1 H$ T9 I+ W int adjVex1; //边的一个顶点$ @* ?1 c8 o* k+ A& P/ Z; `
MultiAdjListNetworkArc<WeightType>* nextarc1; //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
( X! [$ O0 T' c2 J! W' ]$ A int adjVex2;
' n6 O4 b2 L& s. P MultiAdjListNetworkArc<WeightType>* nextarc2;
# S2 I$ g, R1 a9 X3 j- k
' ~4 W; T" ^* }: q7 i9 h g MultiAdjListNetworkArc()
- M; L( e; W7 o9 B { h7 E$ p( m! s" c, Y, S
adjVex1= -1;
4 h3 p& Q+ W* c! K7 |: Q3 u4 ` adjVex2= -1;
: p6 y- @: n& L0 x }
* N3 V l/ f. M* i2 x6 u MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)% |7 C, C- I6 w2 z. @
{5 b) d8 ?- g5 A0 J+ U
adjVex1 = v1; adjVex2 = v2;
3 o; O) q2 v* k$ [+ q7 f; N weight = w;- Z% ^" p* G8 ]) }
nextarc1 = next1; nextarc2=next2;
" G( E7 a! S8 |. p" F5 C z mark = 0; //0表示未被搜索,1表示被搜索过
2 |, [# ~" o% n* D; h: s6 J6 d }
. Z- u/ c5 r4 H& V- p8 n' K5 C0 ?" i" w$ `; c( K
邻接多重表的类模板1.类定义
template <class ElemType,class WeightType>2 S6 Q0 {# X! r. f2 N: x* c' Q
class MultiAdjListNetwork5 g K$ w% }8 {
{
1 J& E; w8 v+ [# Y3 I& y2 U: Rprotected:) E5 a8 T( {9 f5 e
int vexNum, vexMaxNum, arcNum;) F4 e( T* T7 E# N/ J
MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
8 e% m. _, A& m8 c, G' a1 H int* tag;; O. Q# v( Y4 N2 E4 u4 q7 H
WeightType infinity;
" l) A" a2 j' T' C" j
. ~4 t6 O9 q f5 Ypublic:
6 P4 @, @* F/ a3 B7 \* h1 o MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);+ ] k1 e* x% M5 |& W5 X% J
: d% y0 M5 U. ~# }; e MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
+ s0 Q* R& U$ Y. \ C0 p. J% _1 t/ ?" H
void Clear();, C4 Y# v6 V+ s' H
bool IsEmpty()
5 h C9 y& F7 c/ V {: G5 t/ h' W- m5 X
return vexNum == 0;: e7 M1 f$ W) p. u" D$ S- Q
}
, C, z& M2 h( `" u* |' v2 P, z s int GetArcNum()const
; l! w3 S& X4 c2 g+ i; v {! C. J* h1 z# f# Z2 u4 M
return arcNum;
/ f; ]# |- {/ a( E" o5 f7 D6 D% O }2 }8 S1 ~. P. z6 Z
int GetvexNum()const
3 D1 Z& o' b7 {" n$ r7 J5 T {5 |. b2 {2 l. Z5 @& R$ g- X2 F
return vexNum;3 q0 H. W4 J: R5 m/ V
}7 p' m5 Y" r+ r* h1 U0 m$ O: X
1 D" w" L4 }& }5 Z: n/ w6 l
: v; {3 @5 ?. I$ o8 L: J ?
int FirstAdjVex(int v)const;( t( r0 x# E4 ^6 V5 G0 ]
int NextAdjVex(int v1, int v2)const;9 G+ x0 m0 ~1 g, \9 O6 C
MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
* z; O/ D* D# w MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
% M' v8 J0 i! y: ~
; A* ?$ H. \; R8 V8 p" S2 V& D& l- a void InsertVex(const ElemType& d);$ m0 W$ p, {3 [. d6 f; w7 J
void InsertArc(int v1, int v2, WeightType w);2 |, ^6 m! g7 H3 V' b! r" D
8 q, A6 q8 l1 S) s5 v void DeleteVex(const ElemType& d);
C0 W( j" w, x- y) X8 z+ o5 v void DeleteArc(int v1, int v2);
$ u# |/ u/ O- R
6 S) R7 J% S3 V6 C MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);, D5 ^( @1 s+ k6 B3 S
MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
- E5 R# [& [% W1 s$ \0 K# J4 S! F- r$ f, @4 t. w4 C8 H; t! O# Y9 N( w9 `
///深度优先遍历
4 x* Y! o# ]( l' G$ Y& } void DFS1(const int v);
4 b- A( m6 V. w, }, f* W9 K. ~' y( d4 _3 R void DFS1Traverse();8 y" l/ N: J( V3 a- J
void DFS2();
5 q1 A; a! y" _. H2 E9 w8 ?9 n0 I, K9 T) C6 R$ `( C: R
int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
. {* k7 |7 b$ m! s$ Z void DFS3();
7 _$ B* B, W* X& H2 _2 [: m" k) a7 q3 q/ ?4 v% K4 \
void BFS();1 X1 Y* Q0 z/ K) [# r5 ~
void Show();. D7 T8 F$ S) G- m2 t
};
; B! ^* d; D( H F8 z; c( F1 M3 g& t' v: S/ N4 o {
2.函数的实现4 Y8 T+ E2 p6 n, a
研讨题,能够运行,但是代码不一定是最优的。
: N. H' n5 O/ W% {
: @. @. f4 c7 `. E3 m5 a#include <stack>
: q1 X9 }: w; I O2 _#include <queue>- ~ I7 m& J' ?9 _, q; p
: j. o6 N2 y* _5 t, x* ]template <class ElemType,class WeightType>
0 Z# s, \; K6 j% o# oMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)& G9 i) D; W3 z- Y, i9 c- Z
{
! r- ?* X. i7 N; k2 S if(vertexMaxNum < 0)
3 Z5 }- `, ^2 P& F. I; Z throw Error("允许的顶点最大数目不能为负!");
0 y- _0 m+ X% g& N if (vertexMaxNum < vertexNum)
+ Q# h7 l$ |+ w. G, M7 z" [ throw Error("顶点数目不能大于允许的顶点最大数目!");
+ I% y9 B: W6 U0 V6 r vexNum = vertexNum;* P# B; {1 C* {/ `
vexMaxNum = vertexMaxNum;4 g' {5 w/ t. ^: C" x: T# A8 K
arcNum = 0; M0 q0 t+ `/ k T, F( n# m
infinity = infinit;
+ ]3 U/ I) G1 O2 n& w; f+ K/ d tag = new int[vexMaxNum];
+ p" c+ [# @6 j4 p% f G) k- r# ]5 M vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];0 N4 ^( [7 @! M, ?" {9 |( a6 p
for (int v = 0; v < vexNum; v++)
3 M, B$ t- P6 c {: ]/ ~% R- r9 F, Q
tag[v] = 0;) f4 b' p: A# } C3 y% G0 T
vexTable[v].data = es[v];5 W2 S! C3 Y. u6 _7 ^( {, g% g
vexTable[v].firstarc = NULL;, ?3 N) a6 o4 M& S/ h( P$ o
}
) e- Z3 y5 z# a; H2 v1 K1 Z' f}
+ h) M1 X! o" }template <class ElemType,class WeightType>
/ L" T4 l- }$ A; \5 ?2 H& \MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
$ g) F* {2 u2 W% X{; F6 I w5 M K+ j
if (vertexMaxNum < 0)
: i* h$ J6 `( q& P throw Error("允许的顶点最大数目不能为负!");8 Q2 L; g7 I2 R* E0 p: o' |% K; t! _
vexNum = 0;% c7 t( {1 T7 s
vexMaxNum = vertexMaxNum;
" t0 w \6 @9 S& R% k% H% ? arcNum = 0;8 G/ d1 t, ?! a% b; X
infinity = infinit;3 R: u! ~+ s$ r5 E/ B
tag = new int[vexMaxNum];/ _) L. Q1 ~0 u
vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
* }/ }: m% U# L- m' x/ c1 h6 D) T* S}2 e1 S6 d E1 i
template<class ElemType, class WeightType>
O# N+ J! d9 w! r* l% s0 Aint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const/ Y; o! k) P0 K" V/ k( b
{/ l* q& ]# g0 L# }: \9 N, s
if (v < 0 || v >= vexNum)
% q/ z% F" y5 S) W6 I! A- M throw Error("v不合法!");
2 H$ `( r" g$ t8 e5 _7 m if (vexTable[v].firstarc == NULL)1 b+ J J R1 ?# r5 a
return -1;
) {" ?: X2 m& _ else- I( g" J7 k. x
return vexTable[v].firstarc->adjVex1;% a! W7 ~ _9 P X/ [0 ]' V
}
# f6 o+ b" V! L$ b
) @/ E K8 M) p1 H) Z8 U7 \template<class ElemType, class WeightType>
, \: @! E3 V4 L: zint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
8 f% }3 \9 M% O{
; @. m; G6 ^ m U; ^4 q MultiAdjListNetworkArc<WeightType>* p;/ `1 ^% Y$ B: w( H& O
if (v1 < 0 || v1 >= vexNum) u1 x$ Z/ |5 z' M7 H+ l
throw Error("v1不合法!");( n+ D8 f! C1 @6 Q7 M$ p
if (v2 < 0 || v2 >= vexNum)
, r9 `1 H* S3 q+ Y3 e8 z throw Error("v2不合法!");2 x; t8 E. l% w% l4 c, D
if (v1 == v2)+ I+ I5 f% e" E
throw Error("v1不能等于v2!");
& e4 F! Y- v3 I7 f p = vexTable[v1].firstarc;
y% ]( p- H |) C; [ while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)1 f8 w/ n0 i4 @
p = p->nextarc;
7 ]5 u! O, Z) U4 y if (p == NULL || p->nextarc == NULL)
1 `, i' s) I* J0 [5 [9 p# e return -1; //不存在下一个邻接点4 H- n( s- v' v2 [$ X; x2 B# d: Q
else if(p->adjVex1==v2)3 T7 Q( s" h& C
return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
; P1 k4 P& t3 b) l else
7 D0 j4 g0 i Z; I u return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
% d9 J& G3 Y$ h- s0 E0 S2 `1 f5 f}
2 c! O2 _8 Z+ W! t3 A/ S# }$ Xtemplate<class ElemType, class WeightType>% p0 i( |4 O# F* m
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
3 I6 [5 d, S3 q1 V{3 Q5 h9 G9 J, a& M5 j/ O
if (IsEmpty()) return;
) L8 d4 B% d, y9 m* _, b int n = vexNum;# t, S( d# U( I2 O. J4 \
for (int u = 0; u < n ; u++)
, l0 B. M0 s- G/ Z2 ^- ?2 C. H DeleteVex(vexTable[0].data);
/ J0 e" {% F& l S* x return;: r$ {4 h* g2 q! E8 N3 a! S9 L+ M4 I
}
3 u" W" s( {, k' m. D* T. U+ otemplate<class ElemType, class WeightType>4 F1 {( B2 v! S1 r; c
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork() C% q1 i+ D5 `6 d3 _! `
{
( ?! m" P6 X$ ~' i$ m: N Clear();! t( i- i1 J* c, e9 o! e
}3 k1 \ p: h% s3 l6 E! s" {
template<class ElemType, class WeightType>4 L, j$ F- U) T2 j& T
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)" W; V) x4 ^* Y+ v& R4 x
{2 _) _) `# M/ A! E4 K. R c. j
vexMaxNum = copy.vexMaxNum;8 @; L6 f* v' N) s& x1 ?% s+ p/ |
vexNum = copy.vexNum;
/ g, R; p+ A% \, W7 ]* F3 `& L vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
" T9 x) e- M. T( E6 k arcNum = 0;8 @* P: h. S3 j# A* \5 T2 [$ n
infinity = copy.infinity;4 O) L1 t9 b" k; E1 B
tag = new int[vexMaxNum];1 @: U- y6 x7 }6 T. u
0 [: l0 |& @: n; C4 n
for (int v = 0; v < vexNum; v++)# V) U1 Y) ~8 g6 z
{- ]9 Z: o7 a# y# A$ ?) W
tag[v] = 0;' c7 w/ J* T2 x
vexTable[v].data = copy.vexTable[v].data;. m E% w \; n" a- f6 \
vexTable[v].firstarc = NULL;% _. O) p& b1 o- }1 s% ~% N J
}
4 X l U% l* B- e n6 T MultiAdjListNetworkArc<WeightType>* p;
8 U% ]. |( B9 J6 O6 y, J2 _6 y: C7 _
for (int u = 0; u < vexNum; u++)
, h9 h- m1 o- \* z8 y! S6 n {
/ E2 G/ a: ^, R: ~4 Z p = copy.vexTable.firstarc;5 k; n9 b2 a- n4 {
while (p != NULL)/ z. Z7 o5 L; ~$ Q
{
/ W% ?* E6 k2 `2 j8 R' {3 L InsertArc(p->adjVex1, p->adjVex2, p->weight);
! p- i h: S5 j& i' p p=NextArc(u,p);# m$ R7 G6 s5 F6 Y& d4 y. j0 j, y
}
$ E* H, H9 |/ o6 m! s! M }. X% w! n8 {# }6 ?: X% ?: v/ f
}
* l, K* @" Q/ ?/ F# E0 Ftemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
8 a- Q5 K1 e& F; U/ mMultiAdjListNetwork<ElemType, WeightType>:
perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
( G! |% P5 `) c/ l y2 y{6 T- u4 E' O9 ^ j8 ~7 y% U. L1 p& w
if (this == ©) return *this;
! `. a! X! t0 f& O2 ? Clear();
$ g/ r( T8 E2 V$ x7 n# y vexMaxNum = copy.vexMaxNum;% y/ l; k9 z! l! Z6 w. ~
vexNum = copy.vexNum;# v: k% \/ z( K4 _* {' i- N; N
vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];6 @6 {8 U% K7 B _
arcNum = 0;
1 L2 _& i1 T& {6 ^6 `8 L infinity = copy.infinity;
% G1 a3 F% B) Y [ tag = new int[vexMaxNum];& P. a! T {. d
, S# _6 b9 x$ G2 |
for (int v = 0; v < vexNum; v++); r: F& R* D; ~5 K
{! Q8 ?# }) u2 `# }. M! Q
tag[v] = 0;
' s5 W& i m' P( d5 J5 T vexTable[v].data = copy.vexTable[v].data;7 ?, S* Y T% V8 s( d
vexTable[v].firstarc = NULL;5 c. s) d4 D: G, p2 L
}5 Q; C) L! ^, \6 a4 P- i% ]
MultiAdjListNetworkArc<WeightType>* p;1 |' w. Y( r6 q1 S( U) V
$ }5 B" H4 S/ _ R) L for (int u = 0; u < vexNum; u++); X& T+ V9 s+ C! z$ d
{6 {( ]3 x) p& w) m
p = copy.vexTable.firstarc;
5 } ^% [, z* u; k& b, e. ^ while (p != NULL)% [' {0 B% d7 G6 P4 S
{
, {9 o+ O( I7 I: [9 D+ b: o InsertArc(p->adjVex1, p->adjVex2, p->weight);5 }- Q0 X) _6 W! C q$ W
p=NextArc(u,p);
9 X! \1 ]2 F7 o0 J9 f }7 b3 N7 K2 ~4 V4 S K
}- ?' ~) m; r% P
return *this;6 Z. ^; x1 o, O' }$ e; X
}: Y8 C- J2 F4 n( G' d/ R3 ]* d
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
& y( A! N7 `2 N0 e8 Q/ ?) ?: ~6 wMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
3 [! e# d0 J0 ?6 I{& H# J4 m q! A ~0 ]3 h
if(p==NULL) return NULL;
& ?6 {2 X2 F6 ]* V2 x) e/ \1 A% L if(p->adjVex1==v1)* }) e$ q- {$ N' J: F$ n1 g
return p->nextarc1;8 J* ^) B* o7 f( g
else
& B& ?! O6 {* b& E! C3 [ return p->nextarc2;
1 [/ |* L% C* o5 Z' ^) U/ ?. d}5 K1 v, k! [* X, E: ~
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
# \, X7 S: S" I1 n# Q1 IMultiAdjListNetwork<ElemType, WeightType>:
astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const8 R9 J1 C+ o1 m1 L
{# a# j$ q: a* ~/ e
if(p==NULL)return NULL;
# |' B5 y! a0 q- `) `# s MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;% G1 i. }# i7 X' y, ~/ a
if(q==p), _5 X; Y" ~( N
return NULL;* }! p. J2 [2 _+ |
while(q)
8 f3 u* c% S9 t* P, L {
5 h& P( [* T4 D1 S, L" b- u if(q->nextarc1==p ||q->nextarc2==p)
1 ]5 P7 e8 ?/ e. `) s break;7 w. b0 y- p6 F9 V9 Q: Z
q=NextArc(v1,q);4 ?% ^' p* M. G. t# s1 Q5 Q3 I/ J
}
+ e" i* @! U) T" {8 ? return q;
# q7 n" [5 W# F+ F0 m& f9 B# d}
* Y/ A w2 ]1 n; q1 B1 D J& }template<class ElemType, class WeightType>
9 b; [8 ~. c: `! W' C7 Pvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
. e- Z" X& B% \; y, C: l{
) U0 M' R# c2 x2 A3 i if (vexNum == vexMaxNum)
! N f) Y8 ~3 B% g! ` throw Error("图的顶点数不能超过允许的最大数!");* P5 f. V- c; Z" |" _
vexTable[vexNum].data = d;/ c |) g! ~! m$ W) D+ F W% L
vexTable[vexNum].firstarc = NULL;% Z, z, u# p( D- \
tag[vexNum] = 0;
# i+ P; F( }# g- p; \/ n* k vexNum++;
7 y4 t5 c: u1 E}" j3 ]4 T; A/ L4 O, p# Y# ~& _
template<class ElemType, class WeightType>3 b1 n' Q& ~* R9 K
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
; a. n$ E6 J' d: U! f- D1 _{
: T4 M+ A' Y6 B& b' N. M MultiAdjListNetworkArc<WeightType>* p,*q;/ N$ r4 Z2 X2 q+ Y c. E, J) y
if (v1 < 0 || v1 >= vexNum)& `; x+ E& n, D0 E
throw Error("v1不合法!");6 K% R# o8 ^4 F! h. a: D
if (v2 < 0 || v2 >= vexNum)& q) i* Z) J) m+ W: k: `+ s
throw Error("v2不合法!");
$ g9 A4 k) \3 G, K3 T3 u3 _ if (v1 == v2)( P$ A, `/ }3 }' O6 r |/ J
throw Error("v1不能等于v2!");
. e7 \& s) @: @ if (w == infinity)1 w0 w, r# @9 ~7 F
throw Error("w不能为无穷大!");" j2 c; ?& z( ?! X- {1 C0 |. J
. ~# J( r* h1 F* n2 O/ X
. Q/ K1 f1 y3 D9 w2 S6 e
p = vexTable[v1].firstarc;% Z L- C" h; G) k( T6 K4 E7 Y
while(p)
8 a1 k$ I6 K% ? E {
/ U3 z! w7 H" f( M if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中. H, |& j; s! c, V9 J8 i
{; H6 }- b- t: t) F' J, E( T
if(p->weight!=w)# ~4 n B6 A0 U7 o$ u8 n
p->weight=w;0 B8 s: C1 R w# M3 p" b" [
return;
% f2 n# l4 r3 Y* U- V }3 ^8 B3 q7 P4 I# A( e6 K$ t- }
4 Y( q: f' @0 _! W( |. B
p=NextArc(v1,p);
) H9 h; b3 ?' R; O }7 Y, z* P' [: e. y. u$ C
p = vexTable[v1].firstarc;7 a* D; o; X, X0 S& g
q = vexTable[v2].firstarc;
# e+ b8 b* f6 ?" ?* w vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法9 K9 y% h: W* z/ W3 f
vexTable[v2].firstarc =vexTable[v1].firstarc;
) M5 f8 s- x& V% _' S. |0 [ arcNum++;! R1 W- X2 f3 U7 n3 I: h
}7 t+ o' Z3 x6 P# g- E
/ A! v/ e, g- g: ]% `+ ?! Ltemplate<class ElemType, class WeightType>
7 s; x& m' \; P9 r% L; v1 P1 avoid MultiAdjListNetwork<ElemType, WeightType>:
eleteArc(int v1, int v2)! W1 u! ^2 a& u1 c; R; [, g
{
& ~1 D5 Y. R3 u3 \5 R# x3 s- Y: n5 q+ J7 C+ s8 ]
MultiAdjListNetworkArc<WeightType>* p, * q,*r;
7 L6 n2 U2 T5 S- u: k; O! l/ q if (v1 < 0 || v1 >= vexNum)+ \: y* j3 U: s6 D8 q2 G
throw Error("v1不合法!");. n% v6 J: w# }* v3 U/ ]
if (v2 < 0 || v2 >= vexNum)
8 o! k* n# P t9 z5 z: r. o throw Error("v2不合法!");
% H' x) i4 Q" {8 X if (v1 == v2)
, S0 w+ F2 t9 p0 u+ O( S throw Error("v1不能等于v2!");/ c! x( M$ P2 O F8 N2 U5 m
2 N7 I3 M' c6 j O) S
p = vexTable[v1].firstarc;6 k. x, [% Y8 H, J
while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)2 G2 @# K4 q& w/ G. D% _% n
{+ A" a/ F8 `/ V
q = p;+ B' z; Z o% g
p = NextArc(v1,p);
5 Z8 E* _! O1 E L! v7 ? }//找到要删除的边结点p及其前一结点q
3 N$ n2 o! N. q1 ]4 j" }
! b) R$ t5 |" _) n5 e: \8 r! | if (p != NULL)//找到v1-v2的边
' j& H6 [$ [/ f" \9 m8 s {' s9 E8 H) O! T
r=LastArc(v2,p);
3 n: z0 r9 ~1 L; J if (vexTable[v1].firstarc == p)//第一条边,q此时为NULL
8 u7 L* H" |" U if(p->adjVex2==v2)
. s- D4 K' e, P+ `, ? X6 D. |; r vexTable[v1].firstarc = p->nextarc1;
2 o5 w% f) P/ ? else vexTable[v1].firstarc=p->nextarc2;
+ J; u8 k( g7 I3 `4 F1 U else//不是第一条边' E! U' R) S4 l: C& Z, z. A- y3 Q
{
* s! b6 A6 m; S o if(q->adjVex1==v1)1 u% W& j' L. k* P
q->nextarc1 = NextArc(v1,p);# W. F: p4 t* N
else2 U/ ?: k" ? X7 X; k
q->nextarc2=NextArc(v1,p);
6 N$ n4 _/ A, i- P, {1 s! f0 X [- S' V# W" |" r+ u; z5 c
}: V2 j- I& Z( |+ L. k/ p, c
if(r==NULL)/ g. `0 b" d. z3 g/ F
if(p->adjVex2==v2)8 B$ B" D- \, v9 P
vexTable[v2].firstarc = p->nextarc2;% L6 Z# ?! l: r# M9 t
else vexTable[v2].firstarc=p->nextarc1;
* `" V" z. Q/ G, R/ z7 ? else5 ^8 j' A" ~) J& i
{
; D, ?9 G: K- X# G' }) } y. m4 a- M if(r->adjVex2==v2)
; r8 |3 t4 _3 Y8 V6 \0 i r->nextarc2 = NextArc(v2,p);
, J* l7 D6 G) o% a else% P* P' t1 n4 j& p
r->nextarc1=NextArc(v2,p);
! M3 Z! r; z% B: F: q) c% ^' G, H }1 ?+ r2 _4 m/ i6 Z
delete p;
( D* K: r, d5 Q5 E arcNum--;
/ E/ t8 b t4 {" ~; K }. d( Q( G7 Z5 T4 s, X' {
N" Y/ Y2 x, r3 `( J( g. K% k3 \}
0 q+ B' H4 G& D2 A# H9 dtemplate<class ElemType, class WeightType> void3 t0 D p& t8 i5 V [2 E O
MultiAdjListNetwork<ElemType, WeightType>:
eleteVex(const ElemType& d)& Y5 n! b! [) Z* p) b; `
{
" `1 h# l& r: K( ] int v;: P* [1 G& W0 M. C
MultiAdjListNetworkArc<WeightType>* p;+ O3 H% W' C3 ?0 d1 ^
for (v = 0; v < vexNum; v++)//找到d对应顶点! @! U, t q+ l# N$ N0 v- N( _
if (vexTable[v].data == d)
5 D9 `" y; A* ?' f" b1 I S& X& E break;. `1 Y+ m }0 q5 z H- ]' a
if(v==vexNum)! D6 u* z7 M$ V
throw Error("图中不存在要删除的顶点!");
4 e6 A8 @/ B) e1 ?2 P( v; C9 j) G9 [% s/ K9 h) g. |
for (int u = 0; u < vexNum; u++)//删除与d相连的边" I1 y& t2 ?+ G
if (u != v)4 H: R$ ?3 I0 _+ e" L! n
{
6 [3 s1 P& E% l DeleteArc(u, v);' `4 e( w' J* N# G' {$ C3 g
}
: t! N3 ^& J, a. s6 Y vexTable[v].firstarc=NULL;
" `6 s2 F, b0 ~8 F+ Q6 q5 }
+ }8 D, t$ t p6 i" a( B% ] vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置! \/ p0 m- g( _$ {: y1 A/ L. }) p
vexTable[v].data = vexTable[vexNum].data;
' A5 p6 z3 W% h vexTable[v].firstarc = vexTable[vexNum].firstarc;
5 x7 P b# b7 u) Q$ T6 { vexTable[vexNum].firstarc = NULL;
) V* [. Q h. N8 c tag[v] = tag[vexNum];5 L6 i8 @, D& W1 d
//原来与最后一个顶点相连的边改为与v相连& c6 ^ h" m5 S* g6 V
for (int u = 0; u < vexNum; u++)! E- X) F( c( k* u+ z
{) U5 J; A( G' O+ n+ Z" n' m
if (u != v)$ h3 n+ B8 g j1 s- \; e
{; |! [$ H- J% q% |3 m$ f! W
p = vexTable.firstarc;$ t) k- C, E! D- z+ ]" w
while (p)
6 c$ u* M; t/ E {/ _; D/ c) H* s A( V
if (p->adjVex1==vexNum)8 c, i0 Z9 m* C U9 c, t# ~+ p
p->adjVex1= v;4 X' }0 t4 f9 K
else if(p->adjVex2==vexNum)& E% r q' G( } b8 ]
p->adjVex2=v;7 _- a& g' Y" F2 C( l
p = NextArc(u,p);
* s$ c' C1 u$ Q }8 ?, ? W! m6 d y4 x" N3 }. W
}( s+ ~3 @- m! T z% P
}
, K* R! G2 e+ \}
, K4 e+ E, |2 |+ O, d* P; W: Q///深度优先遍历5 L# O0 z# K- x J0 Z }8 S
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:
FS1(const int v)# h8 d: m% F+ @: [
{! ], j1 X! X0 P1 q- y
tag[v]=1;
/ C9 E* u: v6 E' q8 C7 _" T cout<<setw(3)<<vexTable[v].data;5 e/ v0 P( ~! X7 k+ w$ G) [( r: ^
MultiAdjListNetworkArc<WeightType> *p;! s0 e6 ]: `" h: U( y c3 Y0 W( T8 G
p=vexTable[v].firstarc;* ]$ Y2 k+ p2 ~5 e
while(p)
4 D: e2 ?) w* a. _2 t& b z {; _4 i& Y/ C, y. V
if(tag[p->adjVex1]==0)" m& e6 d6 ]: [& W6 X b5 Q
DFS1(p->adjVex1);
( q9 Z% W0 v5 v" d/ v: N, ` else if(tag[p->adjVex2]==0)
( i' {' _& ] U) \ DFS1(p->adjVex2);
' q z& U+ s2 `( K p=NextArc(v,p);0 r" [* \& b$ g7 G9 ?
}& ~9 ?: C) j0 f3 Q8 G, K
}4 S7 t) V8 `, w( H+ d1 F. J
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:
FS1Traverse()
% O5 x$ H1 \' ?% I5 v- ^{. K% O( V9 z4 ~) d" M
for(int i=0; i<vexNum; i++)& B" m5 D7 z& }/ O
tag=0;
! X: P; E' G# N- E for(int v=0; v<vexNum; v++)* L! d9 _& j) W) {
{
7 P4 m; A6 U' b if(tag[v]==0); n& J/ b2 q, [3 T, f6 b
DFS1(v);
5 G5 Z c& ~1 j. N9 b/ l4 _$ g& m: o }* Z) b' M; O% S; Q, ~
}. p l4 q+ k: N' d6 P ^2 P& @
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:
FS2()
0 Y) ^+ S4 |& j0 `2 G( a" F{: C; P. o$ w" x$ ?; S D$ N
stack<int> s;- u7 H. }9 k; D, G U6 q% y8 ?
int tmp;3 @- g% c2 G; Y6 r9 r: P+ }
MultiAdjListNetworkArc<WeightType> *p,*q;, R$ H$ q& Y, ]" n0 I8 h) y
for(int i=0; i<vexNum; i++)! {3 n1 R, C2 n9 V! d
tag=0;( |1 g( v+ C! ^" p
for(int i=0; i<vexNum; i++)( k3 J, s8 P" @% @0 f* {
{' _9 p3 m+ w% k% |8 M% s6 U& c
tmp=i;
! m4 C( [) ^3 l% S) J- ~ while(tag[tmp]==0||!s.empty())- v( v1 U9 ^9 K4 p' A9 m
{) U! Z! V6 [" g1 x% U m6 t0 A
p=vexTable[tmp].firstarc;
. Z$ Q- w, W7 o- U while(tag[tmp]==0)1 ^( \. b8 A; D' U5 {
{ \# E% u8 |9 V, Z# B/ F
s.push(tmp);
6 n; @9 `3 |" [ cout<<setw(3)<<vexTable[tmp].data;, v# F- N' P" H1 o' Q+ e
tag[tmp]=1;
& \: f6 ~% Q$ B: |, t p=vexTable[tmp].firstarc;: f5 {7 u4 s* V! Z9 T
if(p==NULL) break;///该顶点没有边,连通分支结束(1个点)先出栈再跳出循环进入for
' J6 j5 t( I1 Z0 V+ v2 S2 U/ ~ tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
& h C- B! {5 z8 W" W //cout<<" 1st tmp="<<tmp<<endl;7 z3 f$ @# ]0 s& r2 ^5 p3 a
}. |0 N2 H O; R" r4 S' Q
if(!s.empty())1 z5 G5 E' t8 h( ^" W" [: B
{
9 J6 A4 ]1 u* ` tmp=s.top();1 g& m4 L+ _; T8 W$ y7 j7 }$ i. ?
s.pop();! [$ J, a5 M6 X) Q3 v
q=vexTable[tmp].firstarc;6 C% v2 x! J$ ^$ Y* i* A( }7 r
int t=tmp;( W* G7 R1 ]8 l# l+ {
while(q&&tag[tmp]!=0)
4 j3 Q+ f7 g/ w {
4 m7 r) C2 o* \, p1 D tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1); k0 s& f8 | `9 f4 M
//cout<<" 2nd tmp="<<tmp<<endl;
, s# ?( d+ x0 L# |5 F( P q=NextArc(t,q);3 [# R) D& L( o$ M. k/ b
}+ `& w9 W1 o& I2 ?. S
if(tag[tmp]==0)
, m2 s' z. H- y6 ^ s.push(t);
, J0 d0 Y: I6 T6 x2 [- @ ///1、对应上面连通分支只有1个点的情况5 N: l' V1 i& Q& K% C0 N( e& k6 l9 b
///2、t上的点都被访问过,此时tmp是t相连的最后一个点,用于跳过上面while,再次进行出栈
& Z7 B$ S. p! u) Y& k ///tmp要么等于找到的第一个未访问节点,; \5 }2 Z) ~% U+ N$ [
///要么等于与t相连最后一个点(已被访问过)
5 M8 u) o3 M/ V4 P; [2 H$ @- T ///当连通图只有一个节点时,这时tmp=这个已访问的孤立节点
3 A1 p7 D& f! D- Z( z$ C( b }
3 G6 A/ d, I) z$ l: X, ` }) J* l+ |5 \. R
}
6 i2 g1 c+ w1 Y}
3 X5 l) d2 ?4 y1 b/ b3 G//从顶点v出发的一个顶点u,返回v通往的下一个顶点;如果没有其它分支或者已经是最后一个连通点,返回-1;如果要取第一个顶点传入-1
+ o( t/ J5 I! {; Atemplate<class ElemType, class WeightType> int
8 m& S' Y6 E5 V0 n; U iMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
% E: J- G6 C0 n, {& ?; k{
8 g/ ~9 {2 [- }+ M if(head==pre)) o" o" ^1 D* B1 D( N2 M
return -1;
9 i5 f2 S: r( S1 r% @1 W7 R1 K9 P: m2 u, E' ^
MultiAdjListNetworkArc<WeightType> *p;2 Y! M' `0 K. N! Y8 n
p=vexTable[head].firstarc;
2 \' W) D9 m4 K% Q( { if(pre==-1&&p!=NULL)# ?, p% h V2 l: M1 ]0 H
return p->adjVex1==head?p->adjVex2:p->adjVex1;
$ ~1 G0 D- X. `( E7 O4 ?+ i //pre!=-1&&p!=NULL: P8 ]& \- z6 R; Y5 `! M7 V
while(p!=NULL)
9 }' v: d# V2 |/ h) |/ i {2 l! R( `& A# T s
if(p->adjVex1==head && p->adjVex2!=pre)
7 B4 Y$ x/ y0 J; Q0 p" E! V0 S! m p=p->nextarc1;
! N3 m3 k+ v" g, U( A: ` else if(p->adjVex2==head && p->adjVex1!=pre)
. d Z3 b0 ~$ k# v' G+ c5 u p=p->nextarc2;
0 J( l1 l9 M \* T- l n/ ^ else if(p->adjVex1==head && p->adjVex2==pre)
: X8 A- B- r6 v. {. m1 i) n- x {8 h$ l% \: Q O, d1 V
p=p->nextarc1;
, z4 e+ u( @$ |5 q' X7 I' U: H& X break;$ K! j! |& p, f: a a
}
; B2 O0 m/ \9 j0 u else if(p->adjVex2==head && p->adjVex1==pre)
/ M& x) E' z' k$ x, z {6 h: \, A0 @1 {& t/ s9 C" J& K
p=p->nextarc2;/ v; [& O2 `- ]( U# r/ o6 u
break;8 A8 a. K2 z# e1 j/ Z/ Y7 y5 y
}
9 b% V5 z" i; @. f* P$ Z5 V9 w r' c }0 ` F. I: m3 a" W+ K3 w0 e
if(p!=NULL)6 t6 q" [ v, D' q3 [2 h
{/ ]& ~$ T& a# e
return p->adjVex1==head?p->adjVex2:p->adjVex1;) H1 I/ u# F' c& a: y3 \
}2 P* p2 f# V( U% `- E
else
7 w0 G9 ?1 k$ t. r) L& |, Q return -1;
0 _% E7 S; r7 u o2 c}
. p7 Q# a7 `. |8 `' [: Z3 ^+ A* K% L0 \/ D
' x0 G3 C$ u* M1 Z1 U% Q% q8 Q5 e
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:
FS3()7 T; d. o4 T! Q2 ~) B
{, }: x1 X# m4 d6 @: i# L* e; R7 s0 e
stack<int> s; v8 p+ j4 w6 [9 C/ t
int p,cur,pre;
& w/ x5 U; g/ y //MultiAdjListNetworkArc<WeightType> *p,*q;
w% F. x6 @7 i# S for(int i=0; i<vexNum; i++) tag=0;//初始化; I+ O4 B* K0 Y! E2 O' P
3 T% B/ w% y( b+ L& @" Q
for(int i=0; i<vexNum; i++)
: S! ^4 T9 I) w7 B+ |. b {
2 }1 t9 i0 m( Z cur=i;pre=-1;3 ~7 V* S5 @* Y6 U/ N0 L; K
while(tag[cur]==0||!s.empty())
6 @" j' V. ^9 u6 i" V {
5 B( B$ p0 S K @( |0 _* @: ?: j2 h while(tag[cur]==0)/ B/ W$ V* ~, b6 a( T: V
{
! h+ {" L% w: L; ~3 ]7 @ cout<<vexTable[cur].data<<" ";
" h0 o: o9 n9 e! F" F s.push(cur);! r6 {( r& ?! K; N, w
tag[cur]=1;
* p. |, e) R- f/ p7 c! r2 o9 M( D b //初次访问,标记入栈. t6 x- [0 A1 `- w2 {" Z- X M
1 N% Z* G7 w# d' \/ V p=GetAdjVex(cur,pre);//p是cur的连通顶点. Q; E& W* x& N
if(p==-1)
0 W4 G! B2 U" }! Y& ]) W {' ?# m0 b) W* o4 B$ `) m1 h
pre=cur;s.pop();: v( n$ y, E* Z/ [" }4 z. `/ Z( W1 R* i
break;
# A) y0 p9 H. s- ^, Z( S }
" k0 L2 a! Q5 z. @9 i L- A+ M else' {& j( o0 k" Y8 T) `
{
0 S7 [8 d2 S! H9 n) c* t8 f0 p+ ^ pre=cur;
8 R8 k- f: Q6 {* J% | cur=p;' n9 U- z$ W% D1 K! f& W) g* Y
}
1 u: j+ o, x/ f( P$ R& |/ A" t+ g! M1 T
}% J* ~1 s5 C! G$ q& q4 ^0 n
while(!s.empty())
; Y! O+ K6 l1 I; j {
6 P |6 V$ I+ D cur=s.top();
3 f: D# g; O# }. U4 O p=GetAdjVex(cur,pre);
7 c( U6 z. R- H0 {$ v! t: @ if(tag[p]==0)
& {) Z, z8 T# R6 l4 |7 \ {* |3 I6 K- @2 W, ~3 X( b) S
pre=cur;
! k+ _: a6 `: R/ J- m* R2 k k3 u: t cur=p;
( Q& J1 N9 O0 {3 }* C break;) A4 d' p' m: m: M7 o" _
}
3 @3 T' K$ _# x else+ v; B$ a d6 {6 y% w0 N
{6 m; h6 T7 N$ C. y& \
pre=s.top();
; t' x( n d: R( z) d4 h- ~7 ^ s.pop();( k/ }+ }8 }% L# Z5 w: g' U
}
9 r/ B& Y# Y4 \, G- F: Y
, t1 X$ _ m+ K; ~* [0 k! N0 N }
+ B2 `1 l; m4 R8 s& ~( S2 J
+ k3 ]% Y* G$ ]- c: ]1 J }
( e3 g- G6 Z0 Z, b }& Q" f9 C/ W# r' _
} ?! l. e) {/ G* |
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
! J4 W T& P9 X# ^0 T( C; g* \* k{+ u# U! q1 n( a+ H" F
for(int i=0; i<vexNum; i++)
/ y1 O X6 B7 V1 o. _ tag=0;
3 `4 G! J# d8 M queue<int> q;
+ @7 k4 ] k; S( G% J int tmp,t;
& j6 z- h/ z9 R0 r$ X9 J MultiAdjListNetworkArc<WeightType> *p;# }: v% Y6 }2 l
for(int i=0; i<vexNum; i++)
& l6 @' B7 R5 I% o$ z. b! m1 e {
[/ b5 {% S& z4 U* v if(tag==0)' P9 p# S7 z% K4 W" L( N8 _1 N# d
{
! r& [0 [* U. | @6 Q | tag=1;
: ?6 t0 e9 |; { q' l2 P$ L6 d q.push(i);
( Z6 A* w. J; G/ } cout<<setw(3)<<vexTable.data;
! h2 \* r: u/ `- R5 U5 [2 h }% Z$ `$ P" i( b0 J8 y, q- ~3 Y
while(!q.empty())0 w5 c% e' {; {& X8 f" f
{4 i$ e8 o/ b2 w$ p$ m# q
tmp=q.front();
/ m' _8 c& O C& [ q.pop();
( S* U; q2 Q1 i$ f5 Z p=vexTable[tmp].firstarc;+ i! ~3 v- |, F1 y2 a% ~/ N# R! P
while(p!=NULL)8 |* k% F" B0 p$ O8 O
{1 V3 D0 {/ r4 g
t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% s/ S; [0 K2 h1 E8 {3 w1 c1 O
if(tag[t]==0)& s8 ~# B1 h6 d6 R2 O4 z- F0 H
{
% L' ]9 s# f5 i( I6 P cout<<setw(3)<<vexTable[t].data;$ w) t1 }; O7 y( W2 d7 V
tag[t]=1;
* v$ F& U& S8 x" o) z* m7 w q.push(t);
9 _+ C( A' ^* X: p6 G }
9 M9 B- m: _, U: o, I& F6 d+ Z p=NextArc(tmp,p);
, b9 @- X' x' \3 ]' i }
! `) F% V" g4 Y7 R, G6 \ }
8 |" e% j% v' k- Q }2 Z, y$ `- f! @* @/ Q
}# ] V) N# F( b
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()" e" V# c. n6 ?2 b5 ?' R
{
8 z6 ^5 `5 F5 C, N0 j0 D1 ^ q MultiAdjListNetworkArc<WeightType> *p;
5 k. }9 j/ ?) c: I cout << "无向图有" << vexNum << "个点,分别为:";
4 [: u/ t% F$ G for (int i = 0; i < vexNum; i++)- z) ?7 e$ u! X
cout << vexTable.data << " ";
0 t; c4 i; Y; U% r& Z; j& H, o cout << endl;
7 n, L, L& p+ B cout << "无向图有" << arcNum << "条边"<<endl;1 G" q/ v/ H# r: [5 q" v
for (int i = 0; i < vexNum; i++), I2 }. r) d7 \9 d" m0 \ ?
{. j/ v5 K. t& v/ e) g
cout<<"和" << vexTable.data << "有关的边:";
3 q: d6 ~, F+ u3 k1 E! x$ { p = vexTable.firstarc;
$ M) B N3 ]$ Q8 c while (p != NULL)
3 V' F& }0 j# V: ~+ F {
+ V, c; a* s4 L. B$ x( A/ A( h cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";) A- B6 W# p- ^- n& O' ~
p=NextArc(i,p);- W8 T1 k. e$ V
}* R' V2 |: l' a/ h
cout << endl;/ j4 E3 |0 w+ L$ g- H
}& ]! r' @* X- t- _) j( b
}
$ X3 r4 P" @6 m5 P3 ^6 D, a& K* z5 o0 I# P$ E
6 c& I4 k% F9 R6 D7 ]$ w; ?
邻接多重表与邻接表的对比, @5 f) I/ T4 d
' z: N( ?/ G% E. i, Y邻接表链接
: W( J7 X( G8 G; l0 G0 d: {在无向图的邻接多重表中,所需存储空间与表示无向图的邻接表相同。
0 ?1 [8 N9 p9 j* V6 t% h: q7 t8 h, o在无向图的应用中,如果更加关注图的顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着需要找到这条边的两个边表结点进行操作,若要删除某条边,需要对邻接表结构中相关的两个结点进行删除,显然这是比较繁琐的。& e- g0 @9 I1 d, L7 r9 S
为了提高在无向图中操作顶点的效率,又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于,同一条边,在邻接多重表中要用两个结点表示,而在邻接表中只需要一个结点。此外,邻接多重表中增加了标志域用以标记该条边是否被搜索过,避免了同一条边的重复搜索。
9 J, R) p# a- C1 S————————————————, }' U7 p3 r* r# ~
版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
- H+ v! n6 L3 x, t% A+ M原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958
) c* T4 z$ B0 h T1 g6 t( H: D- ?% X8 N" q# U0 {* _
! m* }( O1 Q3 J" @
1 C4 Z" U' U' h' Q! G& f4 k% y4 V d5 N5 J& S+ D
————————————————
w' R! a3 P( J, K# w* ~版权声明:本文为CSDN博主「lseaJK」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
: e8 Y# n; j, {- {' _2 I) m原文链接:https://blog.csdn.net/qq_43413403/article/details/105766958; H8 A! ~2 |% j; q
1 N5 R9 J4 _- Q; R% J; [; O
8 k- d ?; B, c' Y
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |