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

杨利霞

图的存储结构——邻接多重表（多重邻接表）的实现
, i: J/ _, c0 q7.2 图的存储结构
9 {9 H7 z& a2 d
4 ]# a  [; F" J! d0 [7 B7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
8 x5 G9 O1 n- m邻接多重表的顶点结点类模板
# I" p2 h# |- x- h& x邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
& \4 Z: x& O: J1 ?4 p9 O* A
  Q) p- ~+ i6 j" \  |在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
1 `6 V% e- y% Y0 j& x: w! q6 e* h& c在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。
. n$ H+ A8 ]. ?: p
9 f# i& d/ h! m* z( b) }: w邻接多重表的类定义

邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
' X* Q2 P6 q) ?" Fdata域存储有关顶点的信息；
0 g* O. ^1 `+ t# Ffirstarc域是链接指针，指向第一条依附于该顶点的边。
所有的顶点结点组成一个顺序表。

; U8 ~) F/ J' q3 d* h. u/ x
template <class ElemType ,class WeightType>
* q4 A, r; p. }& s8 @class MultiAdjListNetworkVex
{
0 \9 V* V' i7 b5 Qpublic:
1 B* ?, |# Y1 ^# k3 i5 _        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;

        MultiAdjListNetworkVex()
; z2 s) H6 L9 d: I        {
                firstarc = NULL;
        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
, b! R% j4 L0 u+ }5 T        {
1 c. q1 d5 {' S+ k                data = val;
- G- K! U0 v, @$ k                firstarc = adj;
        }
};
+ J' w. A  @- K4 N+ T- v5 ]0 i6 f$ e
邻接多重表的边结点类模板
' r; w9 c2 B( {4 b5 E9 K$ O
在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
9 `6 @3 N9 I  `) L. Ltag是标记域，标记该边是否被处理或被搜索过；
( A; R" U: d/ Z; bweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
( ^: {. l( w4 [6 d3 k8 ^  gnextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
8 X) U% s6 K5 r5 S

template <class WeightType>
2 h& ]' }& ]9 Nclass MultiAdjListNetworkArc
! g1 r) C5 ^  E% z$ q+ c0 V$ C" Z{
public:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
1 z" D* ^+ W& l, |# R5 _        MultiAdjListNetworkArc<WeightType>* nextarc2;

$ Z$ O7 z: o1 S        MultiAdjListNetworkArc()
; _) v3 a1 A! O; O# a        {
                adjVex1= -1;
                adjVex2= -1;
% e' r% W; z- g0 w1 B        }
2 k5 G( u3 B# W, ?        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
& k1 I1 s7 D* b2 B* R9 _  A# o        {
                adjVex1 = v1;       adjVex2 = v2;
' R/ L/ n  s5 W  r, k$ Z7 j                weight = w;
, Q# B3 y) m0 o+ G# r                nextarc1 = next1;   nextarc2=next2;
; K- h5 r1 i% ?  Q                mark = 0;           //0表示未被搜索，1表示被搜索过
        }

6 m3 Q: }2 x5 ]3 G1 `' h5 D3 }" Q0 \9 x7 Z邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
" W" V# X2 b8 L- P{
protected:
# s* M+ ?5 t& C9 J    int vexNum, vexMaxNum, arcNum;
# Q7 ?$ W# W' l% U    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
% w+ f8 B& @! y2 O- V% @/ Q; C5 @    WeightType infinity;

public:
' k2 ^/ i/ K2 ^) J& X    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
8 A; H4 E8 K$ N; k; ?
    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    void Clear();
, G' `4 G+ J( \' x% ^    bool IsEmpty()
% r2 ]- e: ~) C# ]    {
5 b- U5 W! g0 m% c9 T9 m8 @( q7 n# C        return vexNum == 0;
: K1 t5 {- b# k+ t5 w0 L0 n8 X+ A    }
/ b, O5 t! a+ ~  \; u  ?    int GetArcNum()const
& j7 p$ F2 W9 D: t  R1 }% u% j    {
        return arcNum;
+ B9 Q  R3 [; s4 N# N8 p7 _    }
    int GetvexNum()const
    {
        return vexNum;
    }
3 v, h! B; o+ h8 u, A
0 a3 [/ G) j5 G+ C- ]7 d% f
    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
) |. B5 Z( Z7 V* a3 H0 Y8 A% O% T0 F    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
+ j7 V2 w* H' d) r+ _3 e7 m
    void InsertVex(const ElemType& d);
! }& [) r6 ^, u: N7 U    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
4 F3 Z1 H. g1 \: [# C    void DeleteArc(int v1, int v2);

    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
/ M5 ^, A+ z8 D- N7 J: F    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

    ///深度优先遍历
    void DFS1(const int v);
    void DFS1Traverse();
1 z# v! t) D* |" g. D, d  k    void DFS2();
- C, N: l$ u4 R6 S, `
. t0 C. I4 y. ]! ^' S; ]    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
2 u  Q& A% C6 s: d/ g    void DFS3();
# G; R9 d$ g  M' |# M5 ]- Y, @% }
( x2 \: K* C  m" ?! U6 w    void BFS();
6 b/ e" Z( M2 c' i    void Show();
};
6 o  V0 i0 h$ o* q* B" k! P
; w- G1 s! f1 t' k* a2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

#include <stack>
#include <queue>

template <class ElemType,class WeightType>
, R- _8 d' m: P! TMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
/ }; E( V' ~" z. a6 r1 f  s{
$ P. A/ `) z$ R    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
# `( q8 J5 W, _+ y& h$ ]    for (int v = 0; v < vexNum; v++)
    {
0 R6 l1 Y7 r6 d) {. t        tag[v] = 0;
+ S1 P# b0 _& w' o, l" @4 H0 n        vexTable[v].data = es[v];
9 [; h& Q5 c* ]0 }. |        vexTable[v].firstarc = NULL;
2 M2 l. t: ~: g  ^- R3 S$ ~4 d    }
  V+ d( ^. O" t' p}
4 b4 t. Z4 l2 T8 v& Utemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
! N+ v; P8 m7 i0 v{
7 @0 F4 B* ^1 n7 P9 A+ c$ J. K    if (vertexMaxNum < 0)
( D9 s8 D$ a* f6 C        throw Error("允许的顶点最大数目不能为负！");
9 T) o$ C: Q( O, ], t! n    vexNum = 0;
0 V5 u. `8 D1 X- j    vexMaxNum = vertexMaxNum;
( W' ?6 e- N' t# e9 ]& E" @' {    arcNum = 0;
    infinity = infinit;
4 C+ k' R4 C8 L& d, x, _0 i    tag = new int[vexMaxNum];
2 z* y/ N2 ~( ^: i) K    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
' B! @- `* {  k+ N# ]) J}
template<class ElemType, class WeightType>
# S% D" X  F5 X# C1 P! k- Lint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
. q( w$ }6 M1 ~% t: A    if (v < 0 || v >= vexNum)
  H/ s2 o- s$ @  H* ~$ W5 q( s8 v        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
% b. R) s! j  [+ s    else
        return vexTable[v].firstarc->adjVex1;
}

7 O* N4 j. r" o: m/ L8 R+ btemplate<class ElemType, class WeightType>
3 x6 U! i9 r, l/ ~3 H8 nint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
    MultiAdjListNetworkArc<WeightType>* p;
8 E( v7 x& I7 d* E& k3 C    if (v1 < 0 || v1 >= vexNum)
' a) l) h! n( \: ?5 i0 {% D# o        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
2 g, }; S7 x& p9 s2 B6 l6 j/ B        throw Error("v2不合法！");
    if (v1 == v2)
# s- D, U# t  Z4 ~        throw Error("v1不能等于v2！");
& `) |: t  O5 t$ `    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
& n, q# r9 D( K2 ~! a/ u        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
! l+ R2 X' A9 T" x! S* A+ K4 D        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
! E9 G- G/ i, f# P        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
  f6 M+ o4 `) e1 I1 l        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
3 P( O2 A, e& K9 B}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
' u5 p+ n( I) z- }{
0 o  K; J! Y% Z# L7 [    if (IsEmpty()) return;
5 {0 ]. v  P  R, i$ O- W! s    int n = vexNum;
    for (int u = 0; u < n ; u++)
! `( t& T$ M/ p5 o  n: V        DeleteVex(vexTable[0].data);
    return;
. d4 ]! ~3 V! ]/ W4 B% Z}
template<class ElemType, class WeightType>
- a- z" M  `# F. P; [2 v7 u8 XMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
! ^0 R/ a5 P8 B- i+ r{
    Clear();
}
8 D. F8 W7 ?# M+ m; F7 Ptemplate<class ElemType, class WeightType>
: d0 R5 g8 _2 ]" n, ]* FMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
- f( i0 \* x5 p1 A# X# o/ X5 |$ ^, R{
    vexMaxNum = copy.vexMaxNum;
( o# U8 ~4 X9 `    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
3 T$ v3 Q$ N1 C" x+ H5 W0 ?9 a, B    infinity = copy.infinity;
    tag = new int[vexMaxNum];
0 `: c9 [4 c9 ?( n: m4 j8 D. v
    for (int v = 0; v < vexNum; v++)
, ~% _5 p& S$ e! k    {
# o% r, j6 J: A5 o* }; A7 W        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
    {
$ ]8 i7 C5 M( V! a$ I        p = copy.vexTable.firstarc;
, d9 M4 L/ Y8 N8 |# c% b        while (p != NULL)
7 g+ M7 F8 g6 G) D: l: Q        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
5 U1 e( Y' A" F$ E        }
8 ]5 k" `6 b1 n+ I+ v7 g    }
+ |- q+ P8 b0 ]3 |' Z" W}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
) Z! b* B8 z# X% J5 |MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
+ x9 L) f# @; H" B{
( M& X$ x4 U# a1 v: r0 Z. J. t8 w9 p    if (this == &copy) return *this;
! _: w9 H) W" h; z% v& m& K/ n( z    Clear();
    vexMaxNum = copy.vexMaxNum;
/ T! _' k' A' e- n! r3 ^) X7 k, z    vexNum = copy.vexNum;
% o7 \' {; |% r& ]& [5 N    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];

& E1 U: i5 m2 [& a    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
8 {) E4 e$ B- a1 h' g        vexTable[v].firstarc = NULL;
    }
& u  Q/ }6 p8 Y4 Z5 s% Z' U    MultiAdjListNetworkArc<WeightType>* p;
# ~- }* W5 e6 Q7 c( D4 ~2 j  R
+ L2 D" y( t3 J! A3 x    for (int u = 0; u < vexNum; u++)
1 q4 s6 K" l: }$ R! K    {
        p = copy.vexTable.firstarc;
# V( z# d) a( k' z4 m% V( l# z        while (p != NULL)
! `3 h! Z* l/ {$ S  G        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
- \2 I& I" ^+ a! j2 I' K, H( K            p=NextArc(u,p);
* ~+ S7 I* l. X' {3 ]        }
    }
  E: T& D; g7 _; S+ G( n' I* ^( ]  C    return *this;
}
2 n2 n' q0 `: M4 w5 ~template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
! p9 E( {$ S; g5 n, K9 h  a{
( B5 G3 c. H0 k5 Y) p    if(p==NULL) return NULL;
0 N! e0 o9 w7 Q! o" k7 A0 o, O    if(p->adjVex1==v1)
        return p->nextarc1;
! f) |8 H2 V, F& H    else
7 W! V; @  O; I7 g2 M        return p->nextarc2;
}
/ q) F4 X7 X$ {3 M3 @template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
3 s$ ?7 h9 r& U7 R; z{
    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
    while(q)
    {
        if(q->nextarc1==p ||q->nextarc2==p)
& J$ q+ L/ {/ t# u            break;
        q=NextArc(v1,q);
    }
    return q;
( T/ F- z* d, N% |; K0 f; p}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
2 t; z& z5 d/ q( a8 }{
& u3 X  ^0 C/ ~2 W    if (vexNum == vexMaxNum)
! [9 g9 t4 v, U" X- f2 \        throw Error("图的顶点数不能超过允许的最大数！");
5 ~: W+ I& ^1 c' i! T; D' |" I    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
    vexNum++;
* E  H7 j. ~  ?6 x  |6 _" Q0 |( P}
template<class ElemType, class WeightType>
# k. g5 j. q, i+ N$ evoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
1 u7 ~2 K4 f1 p8 @; b) s# n{
    MultiAdjListNetworkArc<WeightType>* p,*q;
0 u0 j% E7 w- H$ r" q& E! m    if (v1 < 0 || v1 >= vexNum)
4 d5 U& p) A$ h7 q2 ], s  k        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
" \/ t- K9 D4 c  @2 p; A4 `    if (v1 == v2)
        throw Error("v1不能等于v2！");
% P9 ^/ t/ J* B    if (w == infinity)
  v% c) [& c! f' y* z) @2 P8 _        throw Error("w不能为无穷大！");

+ R2 m0 v5 Y7 d) j7 g& S
    p = vexTable[v1].firstarc;
    while(p)
    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
            if(p->weight!=w)
                p->weight=w;
            return;
/ z* T% ]; i. d' q        }

- l2 `4 f3 t& k8 a; w7 ?6 {' |        p=NextArc(v1,p);
7 N  {% _+ T0 T5 m    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
1 B" G" S8 i% w% T    vexTable[v2].firstarc =vexTable[v1].firstarc;
" q' }0 m- d( k+ q    arcNum++;
# a) k3 {/ ?! j- f: {}
' i! D& }# ^' b  [2 v
template<class ElemType, class WeightType>
$ Y% ?- N) W) Q3 P4 ?5 [3 |, Svoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
8 p" C; K/ G( s: O
    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
+ `9 M; f) Y' G# ]& `. @    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
; S7 D( q: }/ e- X5 w    if (v2 < 0 || v2 >= vexNum)
: b5 z; Z- Z9 L- |( N4 _% i# @! b        throw Error("v2不合法！");
    if (v1 == v2)
& I+ g2 k/ K) y# U4 [        throw Error("v1不能等于v2！");
7 h; |; m3 P  T2 k, {: Y
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
. D- R7 j0 d5 ]2 S4 K; }- k6 B        q = p;
        p = NextArc(v1,p);
+ N& `: W1 T& l' X8 c5 l    }//找到要删除的边结点p及其前一结点q
# V$ a6 J! W8 E6 C2 T' P# B
    if (p != NULL)//找到v1-v2的边
    {
# u5 D0 M. S. q6 Q9 V" _' s        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//不是第一条边
# q% J% x$ d2 Z4 o9 G% i        {
$ [; k4 f1 f7 K7 X0 L3 M0 @0 \            if(q->adjVex1==v1)
  }8 F% g8 O* ~2 u                q->nextarc1 = NextArc(v1,p);
7 h8 X# k1 a5 i" T            else
2 Q) V' ]6 D& E& z9 B6 I! R                q->nextarc2=NextArc(v1,p);

        }
" Q, [- L9 F) a. `        if(r==NULL)
            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
        else
9 c3 P- P8 s( K( @* }        {
; ]9 P8 S8 l5 h3 r            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
            else
                r->nextarc1=NextArc(v2,p);
/ t5 o, r& C% ]' Z. C        }
        delete p;
. d9 W( K- L. I1 p) A        arcNum--;
    }

: d0 ~0 @6 O" j0 Y}
  c7 i. _9 Q1 w2 u+ itemplate<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
- T/ c$ b! d8 ?2 K0 e, e{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");

& i6 s, l4 u" T' H4 c( t    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
9 b) \" l) `( o9 O6 c$ g        {
! o9 O% F; S7 b            DeleteArc(u, v);
. H; ]) R1 u( D5 A' J        }
    vexTable[v].firstarc=NULL;

    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
6 |" D+ P$ A& f0 h2 A# ~- I# B1 s9 H2 V    vexTable[vexNum].firstarc = NULL;
$ k5 W2 c, W# _  g2 _! y5 @, B+ `    tag[v] = tag[vexNum];
) @1 ]) k1 V& B7 A$ P6 t% C    //原来与最后一个顶点相连的边改为与v相连
& [& k' f/ J( C9 y2 L    for (int u = 0; u < vexNum; u++)
8 D' G$ }7 ^8 }* m8 Z    {
/ |1 k9 z5 K* N" N        if (u != v)
' X$ ?" k9 Z) S2 I$ ^( V        {
            p = vexTable.firstarc;
            while (p)
            {
                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
* Z- w0 h- n, \' M+ r  \5 i                    p->adjVex2=v;
                p = NextArc(u,p);
6 t* E. [; D0 k2 I" f            }
        }
, \. K# w" ^; z  S) T3 r5 y    }
}
///深度优先遍历
4 k; [8 r% L1 h0 ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
1 a) f) k$ Z6 @3 p' H; T3 p{
    tag[v]=1;
7 l& {1 }( q/ N/ @    cout<<setw(3)<<vexTable[v].data;
. x* I' `: G/ {; B. T    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
    while(p)
2 @8 h( m& G. Z# a5 o, |    {
' o. b4 W/ ]+ u4 Q2 K        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
! p! v# r& r# P6 Q9 E. b& i        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
        p=NextArc(v,p);
. ^  Q0 g( V. w$ j0 f9 W    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
{
4 g7 M" c' @" b5 I    for(int i=0; i<vexNum; i++)
        tag=0;
9 l0 p8 G$ _* w3 M$ e. K  @. I    for(int v=0; v<vexNum; v++)
; W8 w; y) N8 X4 v    {
! @, p2 e' D3 O$ p0 m( E/ `        if(tag[v]==0)
            DFS1(v);
+ w( l4 S( u- Z# d0 o0 g    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
4 ?7 ?1 h. J' K- q$ i- \4 c    stack<int> s;
    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
1 u5 f. S: n0 d; [% s/ [    for(int i=0; i<vexNum; i++)
% [  w+ R+ T2 S; K        tag=0;
; R, a# U. a& M5 P4 {! W    for(int i=0; i<vexNum; i++)
    {
        tmp=i;
/ E  O. l; y; U        while(tag[tmp]==0||!s.empty())
        {
  A8 E. f' b' s0 L6 J# G            p=vexTable[tmp].firstarc;
7 M# {) Z5 q$ D/ ^. V            while(tag[tmp]==0)
( S8 t1 _& J/ ^) u' e& q            {
9 i2 Y7 {' y' M& D7 c# p7 h                s.push(tmp);
" g9 R5 T! L* [3 r) s5 w                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
2 }  v3 k, H3 p9 y                p=vexTable[tmp].firstarc;
1 \4 Z  j6 V, U                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
" j# U) @0 ~! r- M                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
3 ?: \1 C3 a+ y7 d+ {% n            }
            if(!s.empty())
; w# q7 w! [) z3 f9 a            {
                tmp=s.top();
- ~& o' R7 n! ~$ H( K% E                s.pop();
                q=vexTable[tmp].firstarc;
$ f8 ]4 P# K/ s6 S                int t=tmp;
                while(q&&tag[tmp]!=0)
8 s& {+ N0 @6 [  E                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
9 X- q+ S' f$ g2 H. d5 ^                if(tag[tmp]==0)
8 S) w: m; @/ M4 n$ W                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
2 }/ k2 J  n' g% o: x. U  t                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
    }
5 x5 M, ]* K% ~1 }7 v}
/ n' y1 H  y6 _" h% `# r//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
0 _  q# d5 S( `! u+ a! k" }MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
3 B% w  j, M% V0 c. Z$ j6 d{
% Y8 O& A1 S/ q% y    if(head==pre)
        return -1;

    MultiAdjListNetworkArc<WeightType> *p;
) [- @4 _0 ]# Q3 t3 S8 [    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
    while(p!=NULL)
- R4 O$ j- ~8 }  y8 J    {
7 d2 L6 R9 U. Y) i6 @* u. @        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
6 |: Q! M# u+ ?+ L+ C            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
        {
" `9 @# z- \. y$ o5 O            p=p->nextarc1;
            break;
0 J- x0 Z8 z. y" h        }
& Q3 [1 Q# l  ^% |2 K        else if(p->adjVex2==head && p->adjVex1==pre)
        {
6 |, I4 g% b( p2 K% n! L$ A2 [3 ]; i            p=p->nextarc2;
            break;
        }
    }
1 U& x; _) u" I# v    if(p!=NULL)
    {
/ h% l+ Z" e9 {" e0 }        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
6 I- g: P2 q0 G. \2 b7 m4 F    else
        return -1;
( Y" e1 P/ h4 G% y3 L}

1 t) v7 N8 |6 O9 x* h
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
  D' I% g/ ^* A+ x6 M/ `    stack<int> s;
- _4 p+ S# V5 X; I# y4 K( I( u6 H! n' ^    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
) [+ a1 h( L, E5 P& W$ O; u    for(int i=0; i<vexNum; i++) tag=0;//初始化
7 j/ j! ]5 i& H
! {) a; ]9 f) j    for(int i=0; i<vexNum; i++)
2 z6 O* c6 y1 ]: A( a& P- q    {
        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
  q: |* O( N3 P$ I$ V3 l- A        {
2 u5 u8 a6 U# ~  Q7 e/ N7 @8 i, a6 t0 M( H            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
( z9 ~- u- P4 z9 J  J/ \" a* E; z4 N                s.push(cur);
                tag[cur]=1;
6 S% H% a' u0 c% M9 y- \( l. l               //初次访问，标记入栈
* H  S! o' F6 `* P
               p=GetAdjVex(cur,pre);//p是cur的连通顶点
2 s2 f8 r" B* [: X               if(p==-1)
, I9 s9 @' X0 h3 n               {
                   pre=cur;s.pop();
1 l; _* l6 s  h+ r1 f" L                   break;
  Q5 m! I! l3 r% n* J( Y9 b' i: e  H               }
5 j2 U3 i- x" k: U$ x! ^               else
               {
                   pre=cur;
- t" I/ V1 r# m+ H. \! t8 g. {* }                   cur=p;
               }
% h' b1 M* L" c! i- B
$ k! a8 ]3 D% s* I, z! I/ D+ \            }
            while(!s.empty())
1 ?2 Q, F1 q8 n            {
                cur=s.top();
4 P4 L% S0 i9 s! Q5 y                p=GetAdjVex(cur,pre);
  \; t9 Z8 v' E* n1 R. b  v                if(tag[p]==0)
& p- b6 g: t) w% l" U$ f. X                {
" J8 P3 b1 |' j9 c0 ~% V3 e                    pre=cur;
/ n- g+ \* _, |  V) ]; }  K                    cur=p;
/ I, |8 t# C$ K* B4 H* b: S                    break;
$ I+ V* _# ~& t. h7 b2 v                }
                else
                {
1 \6 C: J1 O) p/ H9 G                    pre=s.top();
8 a. y/ R2 s# O6 E" z+ w                    s.pop();
                }

  j+ a- u9 G" X. R- v( J- P            }
$ f& e+ s. S; o3 {
        }
    }
}
: u9 d! \- I: r9 U8 Xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
9 r: d: Y. o8 O. q$ S' Q. s    for(int i=0; i<vexNum; i++)
        tag=0;
3 \! @0 h+ r) F8 z% r+ r4 ~    queue<int> q;
    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
2 ]: e% N0 F4 v/ J9 b# u    for(int i=0; i<vexNum; i++)
1 U. k6 w1 V/ E! x# H7 P    {
$ M0 |: V5 B  P; a        if(tag==0)
        {
            tag=1;
& m, X* Y/ w* `  p2 u            q.push(i);
# k% o; G5 s$ ^" `+ ]            cout<<setw(3)<<vexTable.data;
        }
        while(!q.empty())
" \- `- O4 ~# p; I        {
            tmp=q.front();
            q.pop();
            p=vexTable[tmp].firstarc;
1 G; f2 W- H9 `* @( {            while(p!=NULL)
            {
! y2 ]( y3 ~* r* l3 J) m% K0 c                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
/ L1 k7 x( x2 _$ u                {
! j% X! J- U1 Q) {2 p, {                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
. Q" d+ `/ N% Q8 y, W                }
                p=NextArc(tmp,p);
* z; o2 ?* N1 N. l) H# j            }
) O2 K2 j+ M6 k  N& b        }
    }
5 [3 V0 v. @% x- ?: T}
+ [. R1 ^. d% W  _1 C& B* Ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
8 O& c( p7 ^7 l8 a$ \5 L. {' b    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
# g' x% s3 e' |8 _1 B    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
* i+ m0 [! ~3 ?' i8 |    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
    {
        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
        while (p != NULL)
- Q- Q; p! O5 l; n7 ]        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
- ~5 ~, P* J7 k7 B4 H# C            p=NextArc(i,p);
        }
7 T# F' j4 L. T- |& @        cout << endl;
8 ?+ l! ?4 f) m$ @8 N! z    }
}
1 L( ^7 ~3 ^5 y4 Q, m  k

+ O" S# q- W/ d0 t/ f( U- s& N邻接多重表与邻接表的对比
" y1 {1 \: k% M, |8 Z, p. ~3 P
8 O) X, Q% U% B邻接表链接
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
5 ~5 P$ e1 B/ n' R1 i, N. ?9 ]在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
. ?# ~2 [5 V4 K, Q3 a/ M/ O% L, B为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
5 w5 Q5 O% d. R. V( f5 s版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 V4 B1 t' x. G8 V/ A原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
( }' L& S2 e* [- Z! d" M
2 }% I' e% @3 H5 y0 t: w8 G
5 ]8 ^1 {! G) h: W: x7 j, o  N
# w4 y, E- h# w  R/ z8 O; l
————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% {; n1 e/ [' _$ u- M原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
5 Q$ h. b/ H9 Z; c1 ~, L
' x$ b% S0 _3 ^0 o4 v