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