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

杨利霞

9 H! e  n. P( g. _图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构
& Z' j1 i: Y' v8 O% M
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
  }" ~+ P# W3 n9 n  q邻接多重表的类定义
邻接多重表的顶点结点类模板
# [1 X7 w/ O8 K) k1 x) V' @! |邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

2 K+ d% Z/ s/ |6 h. w9 f$ s在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。
% x$ X; B% e: t" A3 z6 |6 v
5 O* ?/ ?" f8 _: B3 ~邻接多重表的类定义

+ `) }% I0 S- ^4 K3 H% L邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
* H( `+ z! ^  I* }& k2 odata域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
7 p: c$ S& z+ E3 z+ `9 x所有的顶点结点组成一个顺序表。

+ v, k6 H& M3 q. c1 ]
template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
{
. p7 N1 c# s" j/ Cpublic:
        ElemType data;
. u/ _0 ^5 d1 U( q* {6 Z6 p        MultiAdjListNetworkArc<WeightType> *firstarc;

7 W- p3 v/ i& N' I        MultiAdjListNetworkVex()
        {
5 `9 o# S, V+ P4 e                firstarc = NULL;
: u6 `- K0 @4 l0 H( u& N9 {# ~9 [6 B        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
        {
                data = val;
                firstarc = adj;
, c: s6 e7 r- \  o7 F% E; |        }
};

6 M; y3 i/ H2 T邻接多重表的边结点类模板
; T1 [0 C: q: g' M; }' e
在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
( b1 h% E! O7 |4 W$ o! f/ qweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
; [- g8 y% A. {$ Q5 v7 _, Q
) b) `3 f, ?" z+ B3 Q
( z6 h8 V9 @5 R  {% }template <class WeightType>
. V" ]: O6 M( s$ I- x" ?/ Iclass MultiAdjListNetworkArc
( q- i* m" F" X3 X3 A) T( h{
public:
    int mark;                                       //标记该边是否被搜索或处理过
3 X3 ]- b/ j$ T3 X7 [1 K8 `        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
; B) M+ ?7 v1 Q        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
" h* ]8 b: Q& V" j. \        int adjVex2;
, @# Z5 ]5 B8 q; ?        MultiAdjListNetworkArc<WeightType>* nextarc2;
) ^9 S- H9 t: N  ~
        MultiAdjListNetworkArc()
6 K( G$ R; Y, R1 K! [; L( u        {
1 @3 H5 v" |3 a' i; C  w                adjVex1= -1;
( ^. k0 R6 f$ }7 H% R0 X0 a7 S0 T* k                adjVex2= -1;
2 _/ m+ O7 l! O, H  K        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
1 X* `6 @, M7 Q. u3 }8 c$ z                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
* Q& @2 o( A- E6 r: Q' A0 q                nextarc1 = next1;   nextarc2=next2;
3 J! m; D0 [* q* |/ z5 {/ H$ V                mark = 0;           //0表示未被搜索，1表示被搜索过
+ _  c( p# _- Q2 z" b        }
  J& {/ e3 O" `" m: u6 c+ {
0 K* m  v+ F1 Q: p1 A: r0 T邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
) |: R+ ?7 ^* b& W! b' h) eclass MultiAdjListNetwork
+ Z8 o$ c) d2 R# k9 V, k5 f{
protected:
6 o, h! B) S; P3 g  |8 h4 L; B    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
' |2 x' W) U" F0 A- O    WeightType infinity;
; }) o) ^) t6 c( b) M4 J
3 M) m+ C5 r) y2 U, _public:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

* J" o3 u/ _  U) s    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

6 F5 l" O8 E4 |) R    void Clear();
    bool IsEmpty()
    {
        return vexNum == 0;
    }
8 i6 n4 Y- L9 r1 A5 k& E    int GetArcNum()const
; c! t1 f' a, n7 h6 x1 h    {
        return arcNum;
7 ]' B$ J/ _) F5 I/ ?    }
    int GetvexNum()const
% \; C* Y1 I4 W' N8 }    {
        return vexNum;
    }

$ C% D( Z( M" Q7 w
% n+ K1 a5 ]! t    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
  J1 I! l: v6 W+ B$ m8 E7 w    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

    void InsertVex(const ElemType& d);
( P( Z; ^: s1 D8 U1 M: b: g* C    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
4 B" l4 Q2 v+ k    void DeleteArc(int v1, int v2);

; T- P8 ^; l$ [; ~3 ~    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

    ///深度优先遍历
9 d5 D2 E  e# n1 v/ ?& `1 K" o    void DFS1(const int v);
* \$ v4 N" j, Y, ?    void DFS1Traverse();
# K% c  D8 ~* C4 b: `) v3 U8 u    void DFS2();
4 D% G# u7 E* }2 `/ ~& q! ?
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
; a6 U  p4 S# e- \* n/ X/ g& I    void DFS3();
: s4 @9 ]1 S5 v+ q0 k. |
/ E9 X. H" r% a" I/ F    void BFS();
    void Show();
};
  P, t6 L, t2 T: n7 z/ s" G1 h# [
7 K5 M- d, a$ d. E2 p2.函数的实现
9 J) A* y8 l' c8 S研讨题，能够运行，但是代码不一定是最优的。
/ D" H( s; L/ S; ~% B- n
1 d, m6 G* J( ^* C$ z) O) g7 b#include <stack>
#include <queue>

template <class ElemType,class WeightType>
  D7 U% m6 e! Z% }2 ZMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
+ G, N/ [2 o4 T: M- L/ E. R7 U; d    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
4 k  B# q0 ]- P8 T        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
3 ~2 w7 n6 g+ ?2 X3 Q! m    vexMaxNum = vertexMaxNum;
    arcNum = 0;
* C0 }7 I: L3 p7 }    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
; r) q' ^! W5 [' j; x. s6 n* n4 s        vexTable[v].data = es[v];
  t/ K  G5 y. g7 ?- p5 F        vexTable[v].firstarc = NULL;
' k! _8 C. V4 K* J    }
}
( R& V: z- n' W4 Ltemplate <class ElemType,class WeightType>
$ Q( V2 Q4 {1 |" O! Q  H# v! kMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
( x* }; z# v& x% s    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
7 ]" A# }/ N1 o8 x: l8 }1 K3 T4 q9 k{
    if (v < 0 || v >= vexNum)
' `+ r9 C$ {; V        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
& q& ^9 F% x) _2 Q& P3 t$ V8 n; R    else
) G" @+ i, F" o9 ~* [        return vexTable[v].firstarc->adjVex1;
1 t# e/ F/ w, H/ V( N* H8 C5 O}
# ?8 g& u6 ~/ Z& D$ Z4 M
template<class ElemType, class WeightType>
6 \0 ?8 P4 E: d+ u$ o0 x! zint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
, ~: A7 l: E3 m( R8 I, m9 w6 ^    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
, I" Q. z: C- V% o' \4 |8 H* w        throw Error("v2不合法！");
    if (v1 == v2)
" Q6 v8 g! Q4 N9 i        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
; d) ^6 U# G6 P& v    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        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
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
, }: c5 E. T0 L: X0 t{
    if (IsEmpty()) return;
    int n = vexNum;
" z, p+ ^- I5 c( D3 A    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
    return;
}
template<class ElemType, class WeightType>
4 N  z; P7 Q6 d1 cMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
" v- b2 U' M$ u! p! l$ a5 p{
$ h! K( ~2 r2 g    Clear();
}
- P  {" C$ X& C3 ]( {template<class ElemType, class WeightType>
! u+ ?3 Y* k5 jMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
& F3 Y0 e/ q6 }! f! M8 H, j    arcNum = 0;
7 _$ F* t2 e# |' }- ~. x. ?    infinity = copy.infinity;
; {0 j9 \- Z5 ^    tag = new int[vexMaxNum];
% C9 w) a% V% B
    for (int v = 0; v < vexNum; v++)
$ X% y$ m  t/ M7 o9 h& X& D    {
        tag[v] = 0;
7 L- s) Y" J  U1 h1 P2 s1 q        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
% E( H' X" A. Q% @1 o; ~    }
    MultiAdjListNetworkArc<WeightType>* p;

0 R3 t7 J' o. ~  E+ ~9 A    for (int u = 0; u < vexNum; u++)
    {
5 @: a9 g$ _6 t. w8 t& @; @        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
$ c6 f+ j  S/ |            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
, a4 x$ c" O: q1 p7 q, P7 {        }
8 t6 ]: j( Y- t    }
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
2 ]- a7 v! J6 ~+ q2 iMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
4 X! K1 R+ p* @2 I( }1 O0 \5 a7 b    if (this == &copy) return *this;
+ p, o) {" B' r/ V/ z    Clear();
( B8 M7 J5 L: B. m    vexMaxNum = copy.vexMaxNum;
( l% l, S) i6 E- }: c    vexNum = copy.vexNum;
7 \+ K0 ]$ P6 f2 Y% C    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
9 S0 r) R+ L9 ?9 H! _3 P    arcNum = 0;
" k& r3 i1 s. g' g    infinity = copy.infinity;
    tag = new int[vexMaxNum];
! P8 c, @' I- R( C% N% p# a$ I
5 c9 _, c3 Y9 H2 Z+ S  K- b: \6 a    for (int v = 0; v < vexNum; v++)
    {
, V% D3 Q) g: n" ?        tag[v] = 0;
: x, p2 a+ d4 U. ~* ~        vexTable[v].data = copy.vexTable[v].data;
" q2 q; {8 `, H' b7 E        vexTable[v].firstarc = NULL;
0 m4 y) H0 s% w4 x8 b' |2 ]    }
    MultiAdjListNetworkArc<WeightType>* p;
7 x: @. V, _9 s! U4 C9 x
  Z) f) B( k: p    for (int u = 0; u < vexNum; u++)
    {
0 p3 ~: `$ s4 _! l        p = copy.vexTable.firstarc;
2 _  d4 H# L! z  z8 a$ a        while (p != NULL)
/ T9 k  C* X4 t" @$ S! ]4 ~        {
8 p3 E7 J" p7 \7 Q0 q            InsertArc(p->adjVex1, p->adjVex2, p->weight);
: K4 p+ C3 a2 [            p=NextArc(u,p);
        }
& P- V" M. ^4 }+ w  e8 F4 k7 j6 \    }
    return *this;
}
1 V' p0 G2 A% \7 g6 q( Ftemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
' L( }" D, _: D4 b8 Z- _{
* A: g9 Q+ z" O' o1 L    if(p==NULL) return NULL;
" P2 O! a" J1 X    if(p->adjVex1==v1)
0 ?2 S( ~# C4 l( y: O$ o5 W        return p->nextarc1;
    else
4 ]% B# [, k! |/ q+ z        return p->nextarc2;
3 N  t( h3 C3 G1 I}
" o# H1 u" Q6 {/ U  p& \& etemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
7 R% J+ H/ P" {* ^& B$ m- Z{
, d9 @% K) @; T% C" T9 @8 |* C    if(p==NULL)return NULL;
: a) _4 f& M# X* P    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
% h& R6 M$ I) a4 h, g) [+ d0 A        return NULL;
$ M% [$ R# q, T* R$ m5 k. k- R2 C    while(q)
    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
        q=NextArc(v1,q);
: R1 R! V1 j+ m0 r    }
    return q;
( Y# _& Z# c! O, f  A}
template<class ElemType, class WeightType>
9 O* e- u( y7 U. Y5 j2 Kvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
8 K' v5 l2 t& W+ V6 C7 V+ E1 v    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
) C% `5 w+ o1 m+ O2 X    vexNum++;
9 m% B0 k9 f/ T# u" g7 C}
template<class ElemType, class WeightType>
/ b2 f8 Z) x- C9 n8 U" Rvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
% |4 ?+ C( q) q: Y2 y{
  I' T; E9 _0 r7 C4 M    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
& `6 G; u) y4 M        throw Error("v2不合法！");
+ D1 j2 @$ Y$ ^4 f! J) ?    if (v1 == v2)
        throw Error("v1不能等于v2！");
' R5 q: @" z) U, P: D    if (w == infinity)
        throw Error("w不能为无穷大！");

* C. R6 {# u$ y
9 W1 {, k; A+ Y$ R( q    p = vexTable[v1].firstarc;
    while(p)
) a. e. e- ~5 H, C3 ]+ A9 t    {
* u1 m7 ~& K) V* ~# ]        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
! @- O( T2 Z5 w9 q" N            if(p->weight!=w)
                p->weight=w;
% E! u1 \6 J+ r            return;
        }
1 X9 ], U! q! Z$ k# D( h
        p=NextArc(v1,p);
    }
! A* a5 T$ h% p! ?1 _8 \& g    p = vexTable[v1].firstarc;
* q4 z+ o: ~7 n8 S    q = vexTable[v2].firstarc;
# y' w/ ]6 H, U. j+ B$ ?4 O% w! s  C    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
1 b2 I) ]( d  n+ Y    vexTable[v2].firstarc =vexTable[v1].firstarc;
    arcNum++;
}
. F! W3 r% d+ u4 C# T  z! D: }& l
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
* A% u# \/ k+ i8 o1 f  W
" `( Y6 F* i1 y1 r- Z    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
/ e% V: F7 S) k5 P) h5 J2 D    if (v1 < 0 || v1 >= vexNum)
2 z' Z) p2 J7 y( e7 v& M  Y        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
  A$ W; ^& p# U7 B, S    if (v1 == v2)
        throw Error("v1不能等于v2！");
8 o6 N+ P  X5 P" h, a
    p = vexTable[v1].firstarc;
5 O' j  R( G8 A    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
+ |, k- y' \8 n" v    {
, r" B( s' r; y4 x        q = p;
        p = NextArc(v1,p);
. J% ]$ ?  P9 j4 `4 K    }//找到要删除的边结点p及其前一结点q
5 k% l8 |; W6 `7 p/ p
    if (p != NULL)//找到v1-v2的边
    {
9 W, D0 R8 |! Z1 `9 R        r=LastArc(v2,p);
        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
9 z' n+ }9 ^0 O. L        {
            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
9 u9 C) |6 i5 @/ C* z            else
                q->nextarc2=NextArc(v1,p);
6 _' m/ C" ?1 x+ c- J4 g9 m' u
6 Y! {% O. o4 Z' c( A& Z        }
4 a% O+ k4 R  _" d' P        if(r==NULL)
- v. e  L/ P6 A2 O            if(p->adjVex2==v2)
) V$ z% V; U- u4 ]* h                vexTable[v2].firstarc = p->nextarc2;
8 ?! T/ @4 e1 |9 C4 K& J+ m            else vexTable[v2].firstarc=p->nextarc1;
        else
        {
            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
8 `( X# h# G& q% u            else
                r->nextarc1=NextArc(v2,p);
        }
        delete p;
* K  k# T. H4 i- {        arcNum--;
$ `: X- ^- v4 }; P9 Y' ?    }

7 ?" a  ]: _0 z6 h# Q+ C}
7 b7 |7 y. w9 \$ c0 F8 O- @, dtemplate<class ElemType, class WeightType> void
1 Y6 v; r1 @  ~; X0 ?$ @4 xMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
- z5 [: ~, x5 j            break;
- X5 h' @: a! V    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");
' [1 c# a! z9 M* m+ ~5 f
    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
        {
            DeleteArc(u, v);
        }
6 L7 v3 `6 R, P. @: _/ T    vexTable[v].firstarc=NULL;
) X' z3 J0 Y. L5 P6 e4 k$ S% T
    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
# |; c$ s/ O& `' C" F6 \% i  f    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
& g3 i! V( z/ s/ U) y7 ~. q    vexTable[vexNum].firstarc = NULL;
! k. r+ P+ U4 J4 a2 F. p8 g1 G5 ?# T0 p    tag[v] = tag[vexNum];
) I( w+ `! b- t" A9 }& E0 N    //原来与最后一个顶点相连的边改为与v相连
, E  F% R, p& o3 k* v- O2 m' x6 M    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
        {
            p = vexTable.firstarc;
! [, Y- G. Z9 M0 k0 d8 `            while (p)
            {
                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
5 R; K% A. }1 k- W" w% K. o                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
                p = NextArc(u,p);
0 e- ~0 n) K5 `            }
        }
/ S/ U8 N3 _% j5 m/ c- D  ^    }
2 t9 u* y/ J, a/ E; h}
  q1 Q1 L8 q* e4 O///深度优先遍历
; H- X9 |! o- V$ p6 W3 htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
. D7 E2 q& w3 l    tag[v]=1;
7 g' \) _% m  z5 e, U5 }" S( G    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
    while(p)
1 A' L' V: Q7 V6 @% ?* M5 O: N    {
        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
( n! I! |9 m0 L- J        p=NextArc(v,p);
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
$ v. {5 p8 r1 \0 q3 T7 w1 D{
# r% T% \) I, P+ h$ R* {    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
6 T* @5 q- H+ ]: R  W            DFS1(v);
    }
8 X! q( ]5 i- |1 `- S}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
3 h. c2 F: ?$ E" B0 s' P+ h' f    for(int i=0; i<vexNum; i++)
  |1 h: H+ h( R4 k% B        tag=0;
    for(int i=0; i<vexNum; i++)
    {
        tmp=i;
* h. x7 i( @& u$ t        while(tag[tmp]==0||!s.empty())
        {
/ X  v' @6 ~1 r            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
! w0 [8 E7 Z; z. K  W) n                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
. A, P9 x$ X5 A* Y2 {% T# ^                //cout<<" 1st     tmp="<<tmp<<endl;
            }
            if(!s.empty())
6 X; V7 M3 P+ y5 D6 j            {
                tmp=s.top();
$ z. J2 F7 P5 X5 D                s.pop();
9 l+ A" i( y& ]- v7 m8 T                q=vexTable[tmp].firstarc;
                int t=tmp;
0 J2 M; J1 h0 E8 P6 C0 h                while(q&&tag[tmp]!=0)
                {
) X+ X# u7 T9 f. a- e8 l                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
; {! l) H* q- M& H; e4 p                }
8 W9 ]3 I' I" _' K                if(tag[tmp]==0)
                    s.push(t);
0 m* E! o( r3 `/ }                ///1、对应上面连通分支只有1个点的情况
2 n$ [6 G# y* c' I                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
' @/ |. @( F/ D( F( H3 p" \0 k! h                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
4 q  V) d% r+ j            }
        }
/ d; ]$ n' ?2 Y& v' {" U" U    }
}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
' h- O9 W; @. l# v/ {+ t& ytemplate<class ElemType, class WeightType> int
6 k" K9 d7 M  q+ Z7 `/ ^9 [/ P. l8 aMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
  h2 P8 B' P$ c, \+ {{
- h7 ^( K8 ]" ~' p; y    if(head==pre)
        return -1;
8 s8 ]( ]$ }- p1 n  R
4 t9 j. D- q8 \, v( `- ?    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
+ D* J1 |9 N0 O: s3 S7 Z& X    //pre!=-1&&p!=NULL
    while(p!=NULL)
    {
        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
, P4 ^$ H- _3 B0 g0 T        {
            p=p->nextarc1;
9 B! \2 \* H5 Y3 a% \8 M            break;
% X* o; E) E7 ]0 ?1 k        }
        else if(p->adjVex2==head && p->adjVex1==pre)
  b* @  s/ z+ S: S) y* Y$ [        {
            p=p->nextarc2;
* c( p; n0 q4 f1 A# s- ]            break;
        }
    }
$ h; \3 B, c' @- g2 V3 \7 Q7 D7 Q8 g    if(p!=NULL)
    {
  e$ g1 t& e* Y4 f, c) o8 \, d        return p->adjVex1==head?p->adjVex2:p->adjVex1;
  i7 g0 C, R5 }  p    }
    else
        return -1;
}

" G+ f0 d/ c" i6 r- w; L' X5 O4 F% p
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
( f# g" }9 M3 N8 Z+ F$ E$ g{
    stack<int> s;
    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化

1 L0 i$ P; W, e; y0 M    for(int i=0; i<vexNum; i++)
$ g: ~- e4 X) H# K2 U5 x: E5 n  o1 a    {
        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
- w' }9 {( E& j; I& D' Z* }            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
  B" g; Q& r3 q6 x  D               {
3 o3 i3 g! N' A6 n/ j8 P& d: Y                   pre=cur;s.pop();
                   break;
" Y/ z' M$ x! ]! ], d               }
% Z( I- `+ }: u+ q& H9 `, A               else
) O) k- J4 u4 Q/ a! j' _               {
% f7 f- O7 Z. `2 f' q+ ^* C  h) }                   pre=cur;
% m- j3 c* \. G1 a" J                   cur=p;
2 V; W( X0 Y, O( E4 W. s               }

            }
            while(!s.empty())
- J1 ]# n  }5 T- v! v% y- a; N& E2 [4 `            {
                cur=s.top();
                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
                {
                    pre=cur;
                    cur=p;
                    break;
8 e* P; |. a5 l; ~                }
                else
                {
3 o' D$ k$ J' s" A% w  a                    pre=s.top();
  f* U! I' i, A1 T! t* J. W* k3 ?                    s.pop();
                }

! \9 d' L" g1 t* e( ]! v( V            }
0 z$ }, s; P! o% Q4 B$ u8 |/ p
' i* ]6 B9 e- R% r% E  k8 }: k        }
2 {& E  Z7 j7 `/ j- _/ y* f/ i    }
3 G: F& ~5 t$ P! B5 L- R}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
( V) J( ~5 L  I. v$ ]$ w+ J- I{
    for(int i=0; i<vexNum; i++)
6 [; o4 c5 Z) S6 X" @4 w' p8 d        tag=0;
    queue<int> q;
+ o9 e2 G( m- _* b  ^+ x    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
. N4 s: B7 R) j9 _2 F$ I# s    for(int i=0; i<vexNum; i++)
    {
! W0 D2 }! R/ W1 [/ I. g4 z# b        if(tag==0)
) V! u" f: j1 [0 e, M! b        {
( q5 U4 I: C8 @% q- I8 R. a            tag=1;
            q.push(i);
            cout<<setw(3)<<vexTable.data;
5 R1 r9 Z- U2 s        }
        while(!q.empty())
3 m$ J$ {2 z5 @& _! `        {
            tmp=q.front();
" p3 {9 u, U, p            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
0 O/ r2 U, U, f: A# n- a; L6 \                {
                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
2 o; q; r. I# J                    q.push(t);
                }
* K* r  X6 D& U8 `                p=NextArc(tmp,p);
" [4 m1 _) I7 _& G$ C7 J            }
        }
    }
( u. U3 t5 T8 \( G5 s6 `}
- L( P4 z. O. o8 s% R, E0 [2 dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
/ N9 V. t! {5 v/ i{
( [, [0 b' d1 Y6 J8 ?. T! T# r    MultiAdjListNetworkArc<WeightType> *p;
) i/ X0 Q1 v5 U5 c6 q    cout << "无向图有" << vexNum << "个点，分别为:";
7 b3 x" M/ r: E    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
    cout << endl;
$ T: j  p  u$ m6 U0 Z1 N. Z1 N    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
6 z1 y" a6 a" X& L# i& |    {
        cout<<"和" << vexTable.data << "有关的边:";
& R& w3 {# C' X$ a        p = vexTable.firstarc;
        while (p != NULL)
  m  g% {% _; h/ ~! G+ ?! @* l. \        {
& v: E( O8 U  m  J. y. B1 Q" o2 A            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
& y4 n4 n! y/ R) U+ j, L            p=NextArc(i,p);
        }
2 z" Y2 i4 b  W& @0 Z        cout << endl;
2 K" ?7 ]) y, h" B5 k' U6 F, C    }
}
+ K$ C. P2 A* e) H/ a

邻接多重表与邻接表的对比

+ r+ A: {4 v( @+ O" n# o' |3 P邻接表链接
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, S( K9 l' A  [' t原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958

  W- J' \6 m: h- d

% q% h4 X% y- z# u
————————————————
2 m' v4 Z9 y% Q$ X% O; C版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 A% O0 ~. B* n6 Y" [1 f0 Y原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958

+ L7 S. t- m5 N  [