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

杨利霞

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

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
8 L1 r. I) H' r7 N邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
( {% t+ I$ }$ k& e( o1 y$ V邻接多重表的类模板
/ o, q: r5 O- @/ h) Q( I/ ]5 w邻接多重表与邻接表的对比
% A# |& V/ H/ P3 k; S7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

+ V) ^& _; @. w& J* V% a$ A在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

8 O" r, I1 o/ W6 p邻接多重表的类定义
$ d: E- f( `4 c4 I1 h( d) y* {8 |% y
7 G0 R' [4 r+ _0 N* z邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
9 v. ]' ^1 E  e' J' Odata域存储有关顶点的信息；
2 R( J5 h  \% @; @8 K% W8 Ofirstarc域是链接指针，指向第一条依附于该顶点的边。
所有的顶点结点组成一个顺序表。

template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
1 r6 S& U3 w( R{
public:
        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;

. Q* y- _, g. Y0 p5 O' U        MultiAdjListNetworkVex()
8 |$ z8 w: g% e# H* W: |; O( \/ q1 h        {
                firstarc = NULL;
        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
. X( [+ o1 e) ~9 n9 @0 {2 R* ]8 o        {
                data = val;
5 _$ T' X1 N5 B9 a/ i9 d+ h! b                firstarc = adj;
        }
};

6 ~- O( c. S: u! r# ]邻接多重表的边结点类模板
% f9 K/ t4 N/ Z: q5 a/ g* g% N
8 F4 f' [0 y, @0 @# S' L在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
0 Q( k6 ~6 p9 g4 m9 v' t' Atag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
& V# E. ~* e: J$ x& ]nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
  v: R# G$ O& z. Z& |9 ^6 G! nnextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
3 P1 A( m/ [# r" e) {
* D6 `) d% y0 U" M, K- |
$ F  S2 Q( [% a% t! \; g7 Jtemplate <class WeightType>
: U# f  a$ C4 X- X/ {; ?7 A: e7 ~class MultiAdjListNetworkArc
& p1 a6 m+ T) r+ H8 _* a+ x( \0 m5 Q, b/ l{
4 @9 Q# Q, d; s/ v5 u* n5 ?1 lpublic:
+ b5 E/ |- L! `. k( G" [* W! w" m    int mark;                                       //标记该边是否被搜索或处理过
) c1 X! U- i% m8 w7 m        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;

        MultiAdjListNetworkArc()
, d; I+ L+ k; D6 ]) a8 ]        {
                adjVex1= -1;
                adjVex2= -1;
. [! a5 [7 x5 b. q, h" X" c        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
8 [" a$ m" f' u& _                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
* r9 N, n( T9 v        }

邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
protected:
  H- f# e% M  y    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
6 G* z/ l+ Z7 a! f1 B* C    int* tag;
5 x# X  X- z" ]5 E" N    WeightType infinity;
% @# K! `* v2 T- X+ i
: Z3 H% t' F" d% z: z5 Jpublic:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
6 H7 w( o* D/ G% {- V$ D
    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
. H2 i$ x' ~. B2 C- a
    void Clear();
    bool IsEmpty()
    {
  W% D& p* r! _1 D" Y- s        return vexNum == 0;
( e6 _, D/ v5 S3 r. A6 n    }
: x( V9 R2 E9 \  M$ U) g) s    int GetArcNum()const
    {
! p- @! _. n1 [, J2 d3 o9 I        return arcNum;
& c- I9 G' ~7 d    }
    int GetvexNum()const
* c  u% l9 l4 E, O3 ]    {
. ?4 c# @& f5 j. M+ O" P        return vexNum;
    }


) L5 @0 ~* c( h5 F: o+ v    int FirstAdjVex(int v)const;
; n( }- H9 v; S( L! g    int NextAdjVex(int v1, int v2)const;
6 G7 c) S7 N$ y$ q$ `' l    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
% p: P" E0 `* k
    void InsertVex(const ElemType& d);
    void InsertArc(int v1, int v2, WeightType w);
3 [+ m: H8 g, B* x
    void DeleteVex(const ElemType& d);
: H* X4 ?: S3 X! a    void DeleteArc(int v1, int v2);
0 e: J- p5 }% \
4 }+ {+ D- ^/ f5 F. n9 G    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

    ///深度优先遍历
* v  p& a- g4 X" O, \    void DFS1(const int v);
    void DFS1Traverse();
    void DFS2();
' [- p4 E8 d( K: v
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();

    void BFS();
/ O3 C- h6 f/ g    void Show();
, P3 }' U, r! m; U- t$ w};
, g  ^, V  C" l  U& }
7 o; G/ B8 E) n! e" q2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。
7 J1 e2 J, |* Q7 B4 q( p! W
#include <stack>
#include <queue>
0 X2 l6 b6 M* M2 ?
* \* Y+ e% a2 [; N2 v3 ntemplate <class ElemType,class WeightType>
8 ~0 L/ s. x3 i4 bMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
1 _* R: P4 |: D    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
( w$ ]* l9 M& T- m        throw Error("顶点数目不能大于允许的顶点最大数目！");
% B* `7 K, e4 k" o& C/ _7 D% a    vexNum = vertexNum;
! Z( o/ S; w3 r    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
: W  e" j7 J0 O) U3 k' Y' Y    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
7 {4 a* A& N- Y! |2 i0 ~5 t7 K    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
    }
3 m7 v7 F4 [) k/ V8 J4 Q  J0 ?}
* E# l) W" z0 ?' S# A* Dtemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
& J) w4 y3 e0 U7 u! U. \/ D{
9 D9 k/ k6 D: c    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
/ l" c; L4 h& ]  [7 O2 r7 x    arcNum = 0;
7 n% j6 B4 P4 h% T    infinity = infinit;
    tag = new int[vexMaxNum];
& C# Q/ W* y1 r  Y6 a2 X    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
$ R) j0 ]$ `! [  K}
4 o# D& n$ Z. R: Utemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
4 t* ^: I5 @* Y$ V3 D4 I# V% _. H{
* t! d4 I$ t# e2 @/ B+ h    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
$ T# ~$ l; h& P8 R    if (vexTable[v].firstarc == NULL)
        return -1;
! p  R0 S( X6 O9 E# ], x! A    else
  X4 f  F1 i3 ]( z. b3 C! }: @5 r5 x        return vexTable[v].firstarc->adjVex1;
}
8 Z% d' ^5 {7 h: v
template<class ElemType, class WeightType>
, v' m6 x/ u- K$ y3 B& G* d3 p7 _! q3 Rint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
5 ]- t3 c. [4 w) [3 ?{
    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
- U: V& k& Q5 r        throw Error("v2不合法！");
+ S6 l0 J4 f# I( s, C* s! \    if (v1 == v2)
        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
7 g% w3 Q$ ~# `" R# ~* a/ a    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
- p% ?) v% z& ?+ l2 \/ B7 T2 V0 R        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
$ f8 @' W, F( y4 a. a        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
6 |. j7 Q1 ^1 Y1 U    if (IsEmpty()) return;
9 }. O- ^0 e9 b9 b( d/ x# ?    int n = vexNum;
    for (int u = 0; u < n ; u++)
0 u3 ^# J) U; v+ x        DeleteVex(vexTable[0].data);
* a' I9 s% X- V( L    return;
( U. H- Y2 M1 N, M6 {5 z}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
}
template<class ElemType, class WeightType>
" U& S! R2 B- m! U8 V4 z% HMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
- I. b  ?  i; ]  ~# s{
1 o- v* b& [+ y9 P% x    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
% m+ e6 ~" r8 U6 b, s    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
; v; j7 L- V! ]5 U6 a    arcNum = 0;
! S+ D  a5 g! _  P1 L. t; @' ?$ _    infinity = copy.infinity;
    tag = new int[vexMaxNum];
8 X7 n, i8 ^- w/ @$ h5 b
6 q+ j. A: k  g; @+ ~    for (int v = 0; v < vexNum; v++)
6 n0 X0 z9 Z, z2 `  {2 |% Q' u  P    {
, N. A6 X7 u% ]9 O- k; t        tag[v] = 0;
* n: W1 p' |% a        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
+ p3 L7 Y9 [% h3 d" y: Y3 ?5 V    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
) K1 C. R( [, l8 N  m; h    {
        p = copy.vexTable.firstarc;
- Q. b8 z3 G5 p        while (p != NULL)
6 v7 D5 g+ z" K# G1 {0 S, e        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
    }
' ~! Y7 B' g3 e4 F6 o: p& M}
9 G! {- L5 d8 _5 G* `: ]- M3 z7 qtemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
7 j/ q. z; [% h  D$ [# e: ]% ^4 tMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
& A5 R! v: [3 G: F$ T0 l9 ~    if (this == &copy) return *this;
  u! g' J, Q" P/ B8 k    Clear();
" q9 l* m6 m, ~" q2 v3 [    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
/ s' Q2 K  T) g+ L, A( r    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
; {3 t, y* S$ c3 _' o7 C    infinity = copy.infinity;
; j# h+ \* ?; ]. ~6 A5 _* B6 g    tag = new int[vexMaxNum];

4 G. _5 |: v6 C3 @+ U; m    for (int v = 0; v < vexNum; v++)
6 S6 s" T' X  V& _* A/ D2 O    {
        tag[v] = 0;
9 z0 R6 B7 V/ c5 N) Y1 Y% [( l  a' F        vexTable[v].data = copy.vexTable[v].data;
" h. z/ {. @+ s9 a1 F" f# _$ N* E        vexTable[v].firstarc = NULL;
    }
4 p& f9 U" y2 n, ?" ^4 `' B    MultiAdjListNetworkArc<WeightType>* p;
. j" s9 p6 _8 q2 {, E" l8 J; W% q
    for (int u = 0; u < vexNum; u++)
8 M$ h& n  r) `) l$ X  E1 q    {
        p = copy.vexTable.firstarc;
        while (p != NULL)
/ n/ I9 c$ \$ O: ~9 F        {
/ X/ S' Y6 K' T' Z! J, h            InsertArc(p->adjVex1, p->adjVex2, p->weight);
0 Q, O. v1 Y3 R8 @2 q            p=NextArc(u,p);
        }
    }
    return *this;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
% \* l+ {' i+ E5 M{
9 ~& {8 O; ~* F: [+ G- J2 m    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
/ k6 @2 ^' C3 G+ z# U4 f& J- G+ d/ z# w        return p->nextarc1;
1 V3 M$ @; C/ S    else
5 x; p5 D2 r1 E. _9 O' F        return p->nextarc2;
. f' C: {7 Y3 K6 b}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
5 w8 o! `4 }% M. e) A5 R5 zMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL)return NULL;
  \; H4 _! M3 _, |( U  \    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
# b: q" w: E: V) ~0 ~! I5 `        return NULL;
    while(q)
3 T" m6 o; ^* P9 i- X    {
        if(q->nextarc1==p ||q->nextarc2==p)
6 Z! e/ ]0 Z$ B, |8 _3 Q            break;
        q=NextArc(v1,q);
% H' _2 J+ K  C$ c    }
& j8 n2 D! I& D) U7 Y) p7 ]4 e7 o    return q;
. K2 E  w, w$ l, p+ o3 i}
0 \  z& w2 @- f5 r5 Gtemplate<class ElemType, class WeightType>
9 H/ K  b# J+ O! @void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
. e" C! T% ]+ w" M+ Q% l/ r# q; h* R9 Q{
. m5 D; }# j9 A) w) m& w5 i6 b    if (vexNum == vexMaxNum)
: w7 |) Y7 q( P) x/ }        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
0 {# Z0 P* o8 @0 q    vexTable[vexNum].firstarc = NULL;
/ d3 P) Y9 z* a8 K1 |    tag[vexNum] = 0;
! j* K; ~$ ?4 X    vexNum++;
" y4 U# s( f3 I4 l}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
0 m! y1 `$ z  L/ o( |: G' u{
    MultiAdjListNetworkArc<WeightType>* p,*q;
! N( `6 g# k1 H+ E2 S, a    if (v1 < 0 || v1 >= vexNum)
& ]  J) v( r$ S' d: y        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
) D' c$ Q4 |, s) F' Q6 f2 g" h4 C        throw Error("v2不合法！");
    if (v1 == v2)
" T# B. H% G2 n" X! ]8 n5 K( c* N        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");
# N6 L# R% m2 ^* l9 f# G& O
- N7 z9 _8 j( m/ ~  n+ e( |
    p = vexTable[v1].firstarc;
4 B' B1 m# m! Z4 O. i    while(p)
1 V- ]2 n# c; c3 _' d" X    {
6 V4 h4 Z$ _7 i# ~        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
: d3 b" e2 z1 I            if(p->weight!=w)
+ S  a; l, l9 t$ d! V- s2 ^. z                p->weight=w;
            return;
        }
) @7 {5 g! E0 {7 N# f; j
        p=NextArc(v1,p);
5 _- ]7 E6 \, x    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
6 w. R; @9 q( B( `    vexTable[v2].firstarc =vexTable[v1].firstarc;
# X2 o# A" l$ m  j& D  M    arcNum++;
$ s+ O9 J6 m& k}

6 B" a1 P; H* d4 |5 s/ |template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
' [% u8 x- V0 r$ Z  u0 E{

. W+ z5 x1 l% b* n# U, M4 o    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
# o' U1 u$ R' m  p, T        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
5 }# z% N% U7 J: U* S9 n
: ?. {1 M5 u$ k/ z- p    p = vexTable[v1].firstarc;
; \; {# d+ H* }( _* V    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
        q = p;
        p = NextArc(v1,p);
0 ^) N. H0 A0 {- T; S. Z' f    }//找到要删除的边结点p及其前一结点q

6 v2 c/ Z. [( d9 o6 X    if (p != NULL)//找到v1-v2的边
! f3 D7 c% L, f) z* Q8 b" G: a    {
2 F- s. i+ I# o8 e. h        r=LastArc(v2,p);
0 H3 ~  E$ \8 h- N* ?        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
0 m* C1 e# j5 a+ Z+ h9 R4 N                vexTable[v1].firstarc = p->nextarc1;
& X1 M' g" J! I2 S            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
8 a  ~7 M+ V; H0 X; |        {
1 G  `. Y& J2 y8 U' i) m            if(q->adjVex1==v1)
, {1 x1 I0 l7 }/ f                q->nextarc1 = NextArc(v1,p);
            else
' k. @3 d( L2 L* ~$ n! B9 o                q->nextarc2=NextArc(v1,p);

) }+ N/ E/ `+ @! \        }
, P% ^9 b1 M: H- ]8 Z7 O        if(r==NULL)
& \/ K4 z+ S' ^7 |% L            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
        else
        {
            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
% ?- ^" @. r" v% b/ d            else
6 u; W( k  A; I) |4 N9 h, n                r->nextarc1=NextArc(v2,p);
        }
4 U8 J: c* h0 T% A        delete p;
        arcNum--;
    }

}
4 \1 I' A, s% `$ f' @+ l5 M) _template<class ElemType, class WeightType> void
5 L9 D. i0 L, Q% X& BMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
5 A& q7 L; j" e. I$ m: P* e{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
0 J8 u: v( N' ~) m" K! m$ m) q    for (v = 0; v < vexNum; v++)//找到d对应顶点
, s) h1 K1 K. i- o: y        if (vexTable[v].data == d)
* i2 T7 n8 B- V3 D" a8 f2 j            break;
* L; ]" D4 P$ s' O    if(v==vexNum)
& m9 g0 C% |8 u+ m        throw Error("图中不存在要删除的顶点！");
1 R0 `7 ]6 P# d1 p5 I! V! s
+ r0 D3 {: h6 l/ X7 s( f/ N! Z& x    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
        {
            DeleteArc(u, v);
" s/ Q- n, t7 ^% j3 h( l        }
    vexTable[v].firstarc=NULL;

- @% V' W# j4 A% }    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
3 L) K  c% A2 J3 ]% u* J    //原来与最后一个顶点相连的边改为与v相连
! V8 o# K7 T; [3 z; y! m    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
$ S" L, L- ~; o) T3 `/ n        {
3 s" ^$ X+ w) c& ~1 }            p = vexTable.firstarc;
3 W# V1 N" L& u+ T7 D. P            while (p)
            {
                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
5 B, n/ A( @4 V8 j& K                p = NextArc(u,p);
! N6 C0 r4 R: c# f6 K) t+ v            }
4 `$ K  p( V0 q$ k5 K  ]* l/ w) Z5 Y$ N        }
# x* m* k! S* _" m2 |( i- n    }
2 Q) y) I# h* F6 O}
8 T7 |  V' Q7 b9 _; j///深度优先遍历
* L( r) \6 U* a& ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
    tag[v]=1;
" a: b2 [' N& P3 @- s9 `% I    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
% |4 r8 c6 }# S0 Q1 K    while(p)
    {
        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
' e% g4 f6 L  z2 ]        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
! s) \9 e, V. m2 r' I        p=NextArc(v,p);
    }
6 V' i, s/ E  N3 R/ S}
9 e, y3 q' V  m& U; Z' Z' P# J+ H% ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
0 c" E# E$ N# `$ ?/ b+ t{
+ }! j; p, D: S1 M% h6 Z    for(int i=0; i<vexNum; i++)
- s- i$ D8 e% m7 y        tag=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
            DFS1(v);
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
% d+ C6 f6 U: V& M$ q    int tmp;
/ ]' A! i. o) m' s    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int i=0; i<vexNum; i++)
    {
- N# }; t0 [3 a' H; G        tmp=i;
  v9 O$ B$ w/ k' g! V5 C. }2 E  `6 z        while(tag[tmp]==0||!s.empty())
        {
1 ~% ~8 ^0 M! W$ c  }) y1 b            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
# X4 s6 F: e# K3 S  A* v- x1 Y                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
            if(!s.empty())
            {
                tmp=s.top();
                s.pop();
$ k* M3 H8 ~, ]' g2 U                q=vexTable[tmp].firstarc;
                int t=tmp;
                while(q&&tag[tmp]!=0)
                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
                if(tag[tmp]==0)
4 X' d9 c2 D! S( I                    s.push(t);
4 X9 ^* g2 {- K0 A( L; r+ o( Q& W8 q                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
$ ]+ P7 q! M$ g7 n( C                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
# W8 E7 ^9 l& ?7 g/ A0 g2 s    }
) D9 I- {$ `6 Q+ B% s* V}
" W( U8 h: g% x  f6 Q" N//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
1 h# g4 \: K3 I5 Ptemplate<class ElemType, class WeightType> int
( V8 Q9 a1 a* X3 H8 s: ~# ~! ^MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
1 E8 F1 d( Z/ K, C' E2 h" Y  h3 \    if(head==pre)
8 t- s$ M) E$ i( J, \        return -1;
0 \, q8 w9 f! H! p
; N% N: b( g- t" W' A# ^    MultiAdjListNetworkArc<WeightType> *p;
+ P/ o1 ]; h) {& i/ k9 ^4 _    p=vexTable[head].firstarc;
2 j: P: }* B, J& C( q! A6 E    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
    while(p!=NULL)
    {
8 c* H+ r) g2 R' E: g        if(p->adjVex1==head && p->adjVex2!=pre)
2 s( r6 X3 q$ Y- Q0 V) C8 M            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
0 w2 Z) \4 Z5 p, i1 w7 B) K            p=p->nextarc2;
0 @8 g- Y) {+ V; p% C        else if(p->adjVex1==head && p->adjVex2==pre)
2 z* y8 x8 Y4 _6 E        {
            p=p->nextarc1;
4 i! O* G: F4 D            break;
        }
. D0 w* I: m* s! r        else if(p->adjVex2==head && p->adjVex1==pre)
6 h. X$ s2 `0 R4 ?        {
            p=p->nextarc2;
            break;
        }
    }
( x% s7 H) I; W4 f# h    if(p!=NULL)
7 y  s9 j1 i' ^; ]5 B' y3 y    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
0 t& N1 m; H% J/ R( E    }
    else
( @' ?1 c: G# c* X; u+ `: U; i$ u        return -1;
}
, Q; a; i# O2 V& z' {0 X- H9 m

& f/ R0 \: l7 o/ x, ~; d1 w' I' Ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
    stack<int> s;
7 R3 m: A8 l4 K3 ?6 O' ?' m) U0 p    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
+ Q) T5 r$ Q! C' v    for(int i=0; i<vexNum; i++) tag=0;//初始化
6 `2 g; I5 ^' x' X
% l, r: `* E# L! k5 v. x. r    for(int i=0; i<vexNum; i++)
) U4 x1 P2 D' h1 m8 \    {
        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
" h. ]/ o- m& Z6 U        {
            while(tag[cur]==0)
) f; d) b! R# A  K            {
8 M" g% K. {. T                cout<<vexTable[cur].data<<"  ";
3 r- W" B' u6 W                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
5 B' z+ O, s. ]2 U! t               if(p==-1)
               {
                   pre=cur;s.pop();
                   break;
               }
               else
& F# h4 m7 N+ g. B8 r; [               {
                   pre=cur;
                   cur=p;
               }
! I; Q7 ]% @, R3 e% Q
            }
            while(!s.empty())
9 ]7 W0 u- k$ c4 ~/ j5 x0 _            {
5 W: }7 [  q8 S2 T2 ~- v                cur=s.top();
' d% w- {5 @! V. d( d! O4 \                p=GetAdjVex(cur,pre);
4 J1 z- M" E) A2 K- y+ o0 s: N                if(tag[p]==0)
* D+ e0 I+ q) S3 L2 I- @                {
                    pre=cur;
                    cur=p;
2 r& d) s/ A- |  ]                    break;
7 v' G* A5 C7 u                }
' T) T/ @$ G9 o$ g' t* i                else
                {
8 q" B3 x. R5 W% L                    pre=s.top();
, ~3 \0 S3 G2 X/ ^( D6 p% R4 g" d" k                    s.pop();
                }
' `+ x* U- Q9 ?) w
            }
2 I8 K% C/ L, g# Q
        }
    }
8 c) S$ f- N4 v0 \4 \}
+ ?0 N7 a/ D! p1 ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
2 w3 Y7 |4 I! t5 e" G5 z, x{
+ a! S+ x1 i" q: ^" ^$ c/ _: k0 v    for(int i=0; i<vexNum; i++)
        tag=0;
0 T! z! O5 {! a0 U" ?& r    queue<int> q;
    int tmp,t;
4 ]: q  Q9 w3 a- f    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
    {
5 n6 P4 n. q8 N2 B        if(tag==0)
        {
: }) t7 H/ q4 \8 r            tag=1;
            q.push(i);
6 S. {: {( r- c) z/ h            cout<<setw(3)<<vexTable.data;
        }
, J3 ~4 W. z: J( I        while(!q.empty())
        {
            tmp=q.front();
, m6 Z% F# N. Z# c) v            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
+ j3 i/ q- b. W- D, K1 D            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
, c" ~, @% m' c8 ^/ o8 l                {
                    cout<<setw(3)<<vexTable[t].data;
( k4 D" P. c: T4 |" t8 d                    tag[t]=1;
                    q.push(t);
                }
                p=NextArc(tmp,p);
5 y7 j) A5 _( ]# J' c) o            }
        }
: Q. ]7 w2 c1 Y8 `7 B; c- K! n# g    }
: A8 l6 o% T% m# Z1 I" f}
; W! a5 F: B0 c. E1 U4 Y" }* @template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
2 r  R& [2 e9 I{
    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
9 E! r3 l- N7 }8 Q, x5 d/ J* X    for (int i = 0; i < vexNum; i++)
- l  Z$ @9 \8 |2 }& n2 _9 Y' ]        cout << vexTable.data << " ";
    cout << endl;
/ u& R- S/ W8 R, J) z    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
2 J: b$ B# n( i: E    {
9 R' g# T( J- A        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
5 g/ r5 d7 Y5 M5 L# R& ^3 }2 R        while (p != NULL)
        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
' Z; I) I0 L! q' M            p=NextArc(i,p);
+ z* ?% y' U8 [4 K3 v        }
0 U4 Z: G. d3 P- a) h& C' L        cout << endl;
    }
; t, d( `) r& L1 v# b- M6 f}
: q0 ^9 [" x0 N  m: s
6 @$ r% J( S* y' L
邻接多重表与邻接表的对比
8 H; b$ L$ K& O$ y% b
0 F  [7 N! Q" B' U. G9 i" B邻接表链接
6 u3 b2 V5 A6 l$ W( G8 y, k在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
" O4 M5 s' e3 k版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( C6 M+ G. P5 `! C9 [- S原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
0 k" N6 [; C* E$ M. J
1 ?2 u0 R" m$ z1 s" x9 z3 i
) T% n; M. z! B/ j

————————————————
' b5 e7 U/ H+ L版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 @! r. X- L* n7 w% B  P原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958

4 q) g6 \. m2 ~! G