图的存储结构——邻接多重表（多重邻接表）的实现

杨利霞

图的存储结构——邻接多重表（多重邻接表）的实现
: n8 v  D8 C  U0 R) T: {/ [8 k! G7.2 图的存储结构
& M# a5 X* T& m& `& q8 B
$ h2 G% z' d% s7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
! t& @8 X& y! Z' n6 _邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
( M( H' e) c0 ]7 R邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

2 D2 A  a( P  o+ k. s6 l  L在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
. Q9 G8 i" F4 _在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

; P. f( ~5 k/ z7 W$ k邻接多重表的类定义

4 ^7 C; ]# k. }3 J/ z* I3 t邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
, r) {  U3 Q7 X! c- E所有的顶点结点组成一个顺序表。

: d& v+ U- V: t  z$ V4 c
template <class ElemType ,class WeightType>
- Z; m: d* A5 E; R' z" ]+ ^  [! d. iclass MultiAdjListNetworkVex
{
public:
        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;

5 q2 m  X% O) V5 \& w- c) x        MultiAdjListNetworkVex()
        {
                firstarc = NULL;
. W: E7 A0 F, [. O        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
        {
                data = val;
                firstarc = adj;
        }
};
: x9 P# g& ]& q9 q6 r$ Q
邻接多重表的边结点类模板

3 p$ E9 @/ I& b  b, I在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
4 I% P$ B+ l: _; etag是标记域，标记该边是否被处理或被搜索过；
) X& v7 G1 A. S! R/ @' I9 {4 vweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
4 ^7 j% ?, G8 w+ x5 q  o8 [nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
5 J1 T' O; m) S: A3 p7 Q% m

+ Q+ b5 U7 {& rtemplate <class WeightType>
class MultiAdjListNetworkArc
* \( p6 u  |: H{
: p2 A, X+ t7 {public:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
/ |% n, C* Q- ]  h        int adjVex1;                                    //边的一个顶点
- E9 g. ^* ?0 ^; ~$ e6 R; s) F        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
, H" E6 x" o+ ?3 k8 h        MultiAdjListNetworkArc<WeightType>* nextarc2;
7 {9 L8 E( w, [" c/ B
        MultiAdjListNetworkArc()
* K6 w' k: W+ l  X; D: B5 Q        {
- A3 o# a) L4 Q$ H: L                adjVex1= -1;
- M4 Y, |, m, ?( ^                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
                adjVex1 = v1;       adjVex2 = v2;
0 |+ ^0 \+ f/ M2 A+ ~                weight = w;
                nextarc1 = next1;   nextarc2=next2;
+ T  e9 {* m% p$ J: U  U                mark = 0;           //0表示未被搜索，1表示被搜索过
        }
# f9 I2 H* b3 h( A
邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
protected:
    int vexNum, vexMaxNum, arcNum;
9 a9 i. r* |* |6 H- n7 j    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
/ U7 L' ^9 [* A    WeightType infinity;

5 p  \+ _& S- t) E6 h" ~public:
+ \6 s) h4 B4 \) i+ Q# g2 C    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
# F5 K0 C  L1 [3 o7 u; A. |
2 B, U# U. T, ~, r( h    void Clear();
. \' [- Z# Q  k: P7 r1 h1 O( V    bool IsEmpty()
    {
4 C  n, k/ v% J, p/ P6 `0 o        return vexNum == 0;
5 K  U9 A) U  z) r; o    }
. ~' `6 U. F$ R/ J. H    int GetArcNum()const
; k( g. K4 H: B) \( ~2 a    {
$ H5 j: H8 [) X4 u0 K3 D# E) G        return arcNum;
    }
    int GetvexNum()const
  i  v$ g! S! A. W' m. G1 q3 V    {
; t* x6 }! K3 w6 v: f8 `( M        return vexNum;
    }
3 J7 H' V; i$ d; N
5 A: ?% m( A. B! u- I+ u6 X. y2 t
( L5 b: N+ S3 B2 N) Q2 p    int FirstAdjVex(int v)const;
+ s& t; v+ u% x) ]    int NextAdjVex(int v1, int v2)const;
  g$ O. o1 E7 c5 @7 W8 u  Z    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
, f8 k. t0 P, `: G5 w- @8 x  q    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
9 W) B8 ?- N( u0 a" A* P
8 S, _5 f; |& d" x; R  z* s    void InsertVex(const ElemType& d);
  y  d$ r3 I% c6 ^6 s    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
# @) e! B* `+ b% T! a2 L    void DeleteArc(int v1, int v2);

5 h& T8 b$ Q+ e* a) ?7 R    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
2 k: Q2 W" ^' j; q" ]
& U% }6 t: U: K4 z2 ]! g    ///深度优先遍历
( Q1 h6 r; a! e% K$ U8 @: ]) k    void DFS1(const int v);
8 I7 l2 d3 E5 D    void DFS1Traverse();
    void DFS2();
7 o9 D: R7 Y2 F- X4 B. t
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
% T$ ?( G6 K) k1 O- F& t    void DFS3();
6 Q& F* T# R$ s, h
    void BFS();
    void Show();
$ w" {, ~1 z" Z) L8 Z$ {! Y};
; c) v# _) }" ]
, V* \. g2 v' V+ i0 h4 t" Z2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

/ |2 k' ~1 z+ C0 S#include <stack>
2 n7 R. [0 B. y; O#include <queue>
  @; O- D# {) \: S4 I
0 X5 S9 F3 n2 j6 M) `7 Ktemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
5 y6 D- v3 W8 d& d6 s" N  |    if(vertexMaxNum < 0)
( a) Q4 s# N: T7 K/ T3 y        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
! \0 G" w, S% Q( P( ?  R' W; w    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
$ }& D( O6 |+ M: G    arcNum = 0;
4 l) L. i; N2 U9 s. X0 V$ A    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
# o" C6 z* h2 l& @; s7 g, y( T: ~" `    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = es[v];
: r: \, r/ e! C2 s9 u* N        vexTable[v].firstarc = NULL;
3 H: o& _  G8 R    }
}
% {: X# F5 t  g- [' Y3 Ctemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
+ ~! C# T1 K1 B/ |: s" Z2 @- }. k6 a9 H    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
1 l9 P% M4 k' {3 P    arcNum = 0;
    infinity = infinit;
% }" F& G" Y1 T  @    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
! E; j9 L# p3 r5 ~& R8 l}
9 u3 ^/ ^( ^. A2 Ktemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
    if (v < 0 || v >= vexNum)
  e7 v6 I! {; p5 ~4 h; ?0 F        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
  h6 s0 w. t7 u- n, v" e    else
        return vexTable[v].firstarc->adjVex1;
}
8 |, q% ?8 L) D$ L3 v
template<class ElemType, class WeightType>
8 S  n9 g7 q5 l$ I* fint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
5 o0 ~/ D9 F; G, e8 K  r6 ]{
/ `. z" j3 c, g    MultiAdjListNetworkArc<WeightType>* p;
, U7 V& F$ k; ~    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
1 @7 O0 R# ~8 H# x    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
* x: x* A4 W: s; z; u2 f$ g    if (v1 == v2)
& I* T  G! B) ^3 ]  q( x2 \; D        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
; q7 Y$ r0 ], W- k    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
0 T+ L+ P$ b& g7 ~9 j        return -1;  //不存在下一个邻接点
6 e' U, r& C! u/ @    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
0 o8 x1 J, [2 T# \        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
/ ~, f' ^: Y- ~% J; c}
/ ?$ ?( s6 M0 j# U1 C- Wtemplate<class ElemType, class WeightType>
' z7 r5 O$ o7 C$ Jvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
4 [  \  X6 l+ J5 ]. x{
    if (IsEmpty()) return;
    int n = vexNum;
    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
    return;
% u1 C/ }& f4 c3 x( W  s. D! l: J}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
6 T0 D  D- d1 P9 D* l( W}
! g. K9 I: g2 i% H. w1 \template<class ElemType, class WeightType>
2 E1 V& U) x# Q/ k/ j( q7 }; zMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
) S) \, P' k6 \) o+ K/ q    arcNum = 0;
  j( s$ A- @/ b: W6 S    infinity = copy.infinity;
    tag = new int[vexMaxNum];
) G; t) t% d# F6 Y! I6 H* l
    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
  _$ r" s* N% m  W! j    }
    MultiAdjListNetworkArc<WeightType>* p;
+ o, A# W" ~8 j6 S
    for (int u = 0; u < vexNum; u++)
    {
: `0 c) t. f6 w        p = copy.vexTable.firstarc;
& P0 {& R& ?8 B" _        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
; V: C/ ?, b/ o; n            p=NextArc(u,p);
% f4 Y- y8 ?- X4 J# C- _        }
    }
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
, k$ q- S8 [, H( z  b* |{
- B7 U. ?( {* W/ J( a1 Y4 N    if (this == &copy) return *this;
0 W4 e. p' K% x+ b    Clear();
. p7 ~$ y- P5 S# s    vexMaxNum = copy.vexMaxNum;
( H/ N5 s( Q- |& p    vexNum = copy.vexNum;
* L* ?3 S9 ?8 W, B# r# i+ a    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
+ I; V/ v, c, ^    arcNum = 0;
: ^3 i0 A9 J4 B    infinity = copy.infinity;
- l& Y7 w1 j0 f) X' T* Z" z4 a    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
$ P0 P3 |& x* D% w) T+ J. A) e    {
7 \4 s  l. w3 Q* ?+ q% ?9 n        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
4 s6 m* R5 C+ p, D; h& F        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;
1 V5 A" Y  V0 J0 K' Y
1 V9 z3 M6 T, S) D    for (int u = 0; u < vexNum; u++)
* I* c+ o$ j" y    {
' \% e0 K. @# K$ E3 {' b        p = copy.vexTable.firstarc;
3 b# w! R) l8 m" ]- x        while (p != NULL)
# K' w% M0 ]3 K) W; n        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
* z7 ?) R' @' c" p) {, v6 z            p=NextArc(u,p);
        }
    }
    return *this;
* a% W9 I! U4 [2 m) [}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
        return p->nextarc1;
    else
        return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
, d9 J, j! u% |0 VMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
, o3 L# E; {' D, W1 ^{
6 g" ^9 l# b) ^2 }    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
4 B* h$ l5 o6 E" ^1 M  P/ L% l( T    while(q)
    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
        q=NextArc(v1,q);
    }
    return q;
( q  [- G: S/ z! ~: f# [* U}
template<class ElemType, class WeightType>
+ {1 o& d! ~" I, F. gvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
8 c: _) P' J8 B- I! `" Y% H0 ?{
( e/ u/ w- ~2 P; W- `: n; g! A    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
; E: v5 G: H1 l' X! P    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
- r8 s0 r, t! z+ P/ g2 m    tag[vexNum] = 0;
    vexNum++;
}
4 x4 _4 M$ }: Z$ Y+ Ftemplate<class ElemType, class WeightType>
% o0 E8 j( h; g1 b, T/ c" }void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
& s% l( z3 c! ?) [) s) f. w    MultiAdjListNetworkArc<WeightType>* p,*q;
5 ?( f# l: U- H7 f3 N; e    if (v1 < 0 || v1 >= vexNum)
7 q: c4 |$ a7 z: w3 o9 N- O! R        throw Error("v1不合法！");
' H, Q7 A2 a. K9 P: R3 K! B! ~' a( L    if (v2 < 0 || v2 >= vexNum)
2 N$ O6 S5 |' p0 M        throw Error("v2不合法！");
% y' g# d4 R. W# F! |, X7 C" O    if (v1 == v2)
8 m5 }/ b; L. N        throw Error("v1不能等于v2！");
0 ?  Q  p4 W( P' h( _2 z) U! o    if (w == infinity)
        throw Error("w不能为无穷大！");


    p = vexTable[v1].firstarc;
, m" ~: J' x& I' n    while(p)
    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
: A# k* c  b. a* G3 t            if(p->weight!=w)
! ?3 i, ?, ~5 U# I                p->weight=w;
( D" O1 u7 u( x; B" b* x/ p4 s6 R            return;
- r/ v' q5 z" A7 S# c3 V/ b7 y# L+ z        }
8 X, w# Z/ G0 O- T1 \
$ h, ^  f' j7 X6 q/ }+ s        p=NextArc(v1,p);
    }
2 L0 S8 N  G( a/ b+ b2 k. }1 [    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
% O/ a5 a- A# ?* m1 H/ N3 s    vexTable[v2].firstarc =vexTable[v1].firstarc;
    arcNum++;
! z2 y. y5 i+ U. {8 L$ x}
+ ]) h* O! ~0 D* t& d7 U
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
& t6 n0 s0 ]. k" m% _; U1 V{
0 M7 }/ {5 z+ ^
2 a: C4 j% S' K( p& P: k- f    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
, \; L: H4 e6 Z    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
* P, M2 l. A7 R    if (v1 == v2)
* Z* Y! ^. r# @+ C4 P8 g" l        throw Error("v1不能等于v2！");

    p = vexTable[v1].firstarc;
9 m2 [2 V1 o3 J" O+ m    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
/ S* O2 b% _: D$ s( ]! v    {
, v+ X4 g/ e5 @- \        q = p;
        p = NextArc(v1,p);
4 C% r0 g# y* [2 g$ Y( k* ?4 I( ?    }//找到要删除的边结点p及其前一结点q

    if (p != NULL)//找到v1-v2的边
$ w6 V$ w  ~- F3 z8 P) B    {
0 R5 P. k" p- N! T0 }, C, R        r=LastArc(v2,p);
7 o3 e9 L  c/ s( q        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
( l  d6 Z9 F$ X% Y# o% u. e, i            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
        {
# F' b' m5 m8 p  N5 {1 R9 ]            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
  t( Y' s) w+ T5 p            else
3 `3 _" Q; \! n                q->nextarc2=NextArc(v1,p);
% o  d2 w+ C5 X% j
        }
9 \1 M) S! a) Y4 F/ }. q        if(r==NULL)
4 f( y) _: I- h            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
1 _0 \' O3 q- S3 E8 U        else
        {
5 V6 Q( O$ l' V8 ?! `" Z3 V            if(r->adjVex2==v2)
5 B& m! K$ a8 w: ]2 \                r->nextarc2 = NextArc(v2,p);
            else
: d! E7 |1 y: ]2 @* f! u                r->nextarc1=NextArc(v2,p);
8 _+ n) w* Z  n" _        }
        delete p;
        arcNum--;
. ]' `5 t- I! E3 Q9 W    }

! Z  Y5 q! r9 o" L) t}
template<class ElemType, class WeightType> void
, B  C2 I9 S1 O3 UMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
3 _8 D" E  N; k& e( |{
( \. l: Q1 @, R/ W, I4 R* s: j% }* h& c1 q    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");

    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
% ]; V* f8 x; ]6 N) i, |8 l        {
, ~* [5 W, x$ x/ B6 }            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;
. w5 l. k! d" j8 B9 a7 R& t
    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
* b- h' {8 x8 e/ v    vexTable[v].data = vexTable[vexNum].data;
8 B, [* \3 V5 u1 i$ z' l    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
' r8 o0 m- x! v& b- l, e2 n- `1 F    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
3 e, [) X4 X: m- e        {
            p = vexTable.firstarc;
            while (p)
; L9 ~% v5 R& o            {
2 e: D* {7 W1 |( P' _8 K                if (p->adjVex1==vexNum)
+ q( O' [0 ?6 L/ p                    p->adjVex1= v;
% C7 G3 s! F$ P/ e                else if(p->adjVex2==vexNum)
) |* X3 d$ V& ~/ }7 v: u                    p->adjVex2=v;
9 N+ N. _9 n" [. _                p = NextArc(u,p);
$ o6 J* ~. B. P& w. X% [' C            }
        }
    }
* d3 G) `7 c# ~4 T}
9 Z& l/ C! }0 O4 c! z" @///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
5 M' K  e# h* u4 M: t# z) Q6 i{
  `* Q7 t- |  y* G! p, u    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
7 i7 j) V0 S2 j$ ?; ?9 n    while(p)
0 y* r: `; M# M/ u. @    {
! ?$ r6 M6 d6 c! |6 R: `. d4 Q8 }% E        if(tag[p->adjVex1]==0)
% r, t3 b: ~$ d/ J: |4 B            DFS1(p->adjVex1);
* g  J$ M& n  B& J: Z& w% x- Q" O& a        else if(tag[p->adjVex2]==0)
3 D# H4 C9 Q9 F            DFS1(p->adjVex2);
. L# q& _4 g; V6 i        p=NextArc(v,p);
' m" \. s0 ~& G3 M# e    }
}
. I  @+ |, T. _; r1 Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
/ G& k# S0 S; v, H3 |7 p0 W, N{
    for(int i=0; i<vexNum; i++)
8 D2 g% W8 [: q9 C3 Z" e        tag=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
: v5 k" }8 V, Q* [" T            DFS1(v);
    }
}
2 p- Q+ p3 M) q9 ~2 R& F/ [template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
/ W1 g7 m" s' K8 |    stack<int> s;
    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
+ Y0 B  t" u* |    for(int i=0; i<vexNum; i++)
- ?, u' C# ~: }        tag=0;
" x/ i: D7 d* d) O$ N8 t    for(int i=0; i<vexNum; i++)
$ ]4 S6 Y- [5 _3 h/ [1 u    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
" P/ C; Q) O# p2 Q3 _        {
* l, _" j* p( c            p=vexTable[tmp].firstarc;
* C7 Q& T+ R, m' V            while(tag[tmp]==0)
4 s  h% }( A1 B  Q; Z. n            {
                s.push(tmp);
7 v) G# N+ C; u% G) @/ G- B                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
1 C* l6 Y. T' B" A% K! ^. x$ n                //cout<<" 1st     tmp="<<tmp<<endl;
4 L$ P' W$ p1 ]$ ~# m            }
            if(!s.empty())
            {
                tmp=s.top();
7 q. U+ v; O* f' t: z                s.pop();
$ b$ B1 E( p# J4 {/ S. P                q=vexTable[tmp].firstarc;
* V* h$ O. ^3 |9 }/ X  Z1 y4 e7 L                int t=tmp;
/ q) r, k( `" H7 t: o                while(q&&tag[tmp]!=0)
6 ]1 c2 d$ C3 Y9 ~$ l% A& W                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
# Q1 z3 d  v" I7 D% l  O& v                }
4 u9 r3 l4 j/ U1 Y3 W                if(tag[tmp]==0)
                    s.push(t);
+ {" r- @3 I1 K' X; w                ///1、对应上面连通分支只有1个点的情况
1 L* G" E% p% Z& D                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
7 _* g5 Z. i% W% V    }
. p9 r: [, M; n5 y  K, ~+ A}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
* ?+ e9 t5 B8 j8 Y2 v( [1 c    if(head==pre)
0 w3 M% y3 C8 o        return -1;

    MultiAdjListNetworkArc<WeightType> *p;
  k$ x$ x( u8 ]! X$ G0 l7 w6 R    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
1 m( v# I! {3 T) F5 x( q' R5 l3 `        return p->adjVex1==head?p->adjVex2:p->adjVex1;
% C  y+ \1 @" m6 `  s    //pre!=-1&&p!=NULL
    while(p!=NULL)
    {
* f4 k5 N/ B2 j        if(p->adjVex1==head && p->adjVex2!=pre)
' k1 b  n6 d3 a( n6 m            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
! i, [: A- k2 u+ N        {
            p=p->nextarc1;
            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
        {
            p=p->nextarc2;
            break;
- p6 l' Q( Z) x1 n        }
9 ~! H) d, @" }1 j& o$ {' J    }
& L9 }" K2 g, z6 _+ ~" D    if(p!=NULL)
8 g+ f5 s8 k# J- u! s2 r7 l* w' F    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
8 Z6 q5 _$ {) n/ W. R+ O% V' Q; t: k    }
! {" u' z( V, |+ ~* }) f    else
        return -1;
}

1 X4 p% c( z/ D+ \
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
# r  }. y/ c- M8 h{
' `! c. ]& I( e/ J+ |% C: H4 Z    stack<int> s;
    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化

+ @# Q3 _1 Y* S    for(int i=0; i<vexNum; i++)
    {
; ]$ D/ d  Y& W, I1 _9 T* L- x: i        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
# E) F8 |( D! R4 ^; o) j. G            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
* V% A4 p9 h! m7 b                tag[cur]=1;
               //初次访问，标记入栈
, A$ S: S9 v! H; u
* `8 T7 ]7 c' Z               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
8 g' d- x4 B: W. j3 X9 \5 v. m                   pre=cur;s.pop();
                   break;
2 E, E- I* ~$ V  }4 P               }
               else
( k! ?4 D  j# ?6 u' f% W, a               {
                   pre=cur;
4 t1 I9 j$ Y# W/ v/ K                   cur=p;
5 o' K+ R* T7 `+ M0 ?: ~* Y               }

. B+ h& v) X3 q4 t' `( x            }
: m8 X* t! [0 ^2 q0 w! K            while(!s.empty())
7 V" Q: B, n- E8 u            {
                cur=s.top();
9 V# ~& k* ^' P3 s9 ^                p=GetAdjVex(cur,pre);
- n% [$ u! w" ]! r                if(tag[p]==0)
                {
" D6 Z6 z( C; |$ ~' M9 t) p                    pre=cur;
                    cur=p;
7 a( N" H2 F4 f) A                    break;
                }
" U6 n+ `) j$ a                else
                {
( u* g1 N# w  l8 \6 I                    pre=s.top();
- }. x3 Z$ ?( U                    s.pop();
3 u* X% t1 X! p                }

% s' ^' C( F  ?            }
, w2 B: [2 k5 e$ b. u! l
, e) ^" H/ q! E# j9 q0 N0 w        }
    }
}
& L2 m8 j# Y+ m! ~0 ~; O4 otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
8 r8 Z) g) p6 R4 v; m, d{
, N( L8 d, L% v: k    for(int i=0; i<vexNum; i++)
4 `8 ^1 \& J3 h5 S; n( G: A        tag=0;
    queue<int> q;
    int tmp,t;
: n. E) |! B5 L4 F- ]# o    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
7 A, p+ P1 x9 W' D- z% u9 `# C8 }    {
6 f) J0 T; t$ ~; k        if(tag==0)
        {
5 h4 \( I" L! ?: e* @+ ~% x            tag=1;
            q.push(i);
            cout<<setw(3)<<vexTable.data;
        }
        while(!q.empty())
1 G  b% X* ^0 j; b/ J  |3 R0 P        {
( e9 W% ~! n; J7 P# x7 A7 f            tmp=q.front();
* r  q4 a8 s9 Q1 `) ?# f            q.pop();
9 A" e5 m0 }* H6 X% |  r            p=vexTable[tmp].firstarc;
            while(p!=NULL)
5 T1 r' Z: c1 Z  p5 M8 D7 H            {
, O+ u9 O* z0 V2 O                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ C3 Y! j8 }8 k( j3 w                if(tag[t]==0)
                {
. S* z8 Y7 @  t  h9 t                    cout<<setw(3)<<vexTable[t].data;
# S9 D0 h0 ^( g4 O4 d) L                    tag[t]=1;
( R6 m+ X  X- c, q& Q8 E' V                    q.push(t);
. K( s, F, C  n2 {/ {, l                }
7 |+ A7 @& [2 P/ J  W' }                p=NextArc(tmp,p);
            }
        }
4 ^! H% _* x; T    }
}
$ h+ Y* m# ~6 N  Y  Q2 gtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
* X6 h2 t2 [* A- P{
    MultiAdjListNetworkArc<WeightType> *p;
7 L8 Z) ^* A# B/ P6 p& ?" t+ K/ }  t    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
6 F- w' R" J. I5 X& @3 e    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
    {
5 N7 M" x* |) S, B' Q        cout<<"和" << vexTable.data << "有关的边:";
' a2 J) B( L  ?/ B- t4 Q1 s        p = vexTable.firstarc;
        while (p != NULL)
        {
$ R% b7 v& O0 p3 N            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
" g5 Y( f' @  D% P5 C* e        }
        cout << endl;
    }
}

1 |2 m7 g- }: w! d
邻接多重表与邻接表的对比
! A$ e* Q* f0 U$ c: D$ |7 @
邻接表链接
2 C$ d$ M& I0 }; t0 r在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
8 u6 o& G1 a; c4 d2 }7 H0 e) c在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
& K8 J* ?) y. i/ C# s7 a为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' ~6 {6 G3 v0 b  X7 W) b$ F# Y原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
& ?" Y( @/ ^7 k) G! ~  z. P8 C
& [- j' F' W0 W, c. P' K


- d' f: k7 P. \( y, v+ {————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958