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

杨利霞

, a" c. T1 y9 y) M) n5 i图的存储结构——邻接多重表（多重邻接表）的实现
1 q- q, c$ R4 ?# J) N7.2 图的存储结构
& F( }1 t4 a. s9 J0 t4 [8 T
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
3 g# ?/ g. p8 f邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
% v, d0 P3 ~+ I' n" T: _邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

8 c( a- O" _) S+ C在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
  f0 z% Y. M& p在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。
; q7 N7 W0 {1 k  B. D7 R# J
( _+ Y( u  _* V$ [$ e) u邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
) h' S! L' D, u3 E所有的顶点结点组成一个顺序表。

2 i! A- ]7 ]; T: @/ n$ o: Htemplate <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
{
public:
        ElemType data;
& X( \% l; t* Q% P; V        MultiAdjListNetworkArc<WeightType> *firstarc;

        MultiAdjListNetworkVex()
        {
                firstarc = NULL;
# u7 `, w" h2 c$ U        }
. T/ e  }8 N" [3 p. P( |        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
, A/ Z, \$ H; Z9 f6 `* l  v; k        {
                data = val;
) `4 t% U  Z( _& ~                firstarc = adj;
        }
/ @0 _! b% e& i- K" H* ~3 D/ M};

邻接多重表的边结点类模板
! o; }0 m9 h; j- ~) u
在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
7 s: U6 N! g0 G) T: h* a: utag是标记域，标记该边是否被处理或被搜索过；
% s: h0 {/ P$ k$ bweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
  v% h8 g, Q2 O! w! O2 snextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
2 `0 Q# n% j. d4 }9 Enextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。

4 I& b2 y  m& T- D  B- \$ G' O2 u9 ?% B
template <class WeightType>
class MultiAdjListNetworkArc
{
; ]$ S8 z" ^, c$ j4 X+ |/ tpublic:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
2 P& [9 b2 }3 ?& D; F  l: F) v        int adjVex1;                                    //边的一个顶点
4 u% q5 v2 x+ r        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
2 y8 q6 E7 x( V, W* u6 n+ e        MultiAdjListNetworkArc<WeightType>* nextarc2;
) \; N4 U) U# J3 J6 W. y& n
" O) J0 ~) q5 y9 B' P        MultiAdjListNetworkArc()
( w2 f1 m5 c0 l$ P% y        {
                adjVex1= -1;
& Q/ P. S1 [, }* o' _! {                adjVex2= -1;
        }
4 m& F4 d6 Y" a4 @        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
% s2 Y) g. [4 o        {
+ Q1 i/ `% w# g5 P! F3 ~4 E- P                adjVex1 = v1;       adjVex2 = v2;
& V- U& c6 P! P, u" |. N. D, J                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
, T- a9 w. q" ?        }

5 o/ x: V- P% G. l- Z4 \& @+ p邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
. v' {  b+ Q4 I8 O; x3 B2 |* e' x7 Aclass MultiAdjListNetwork
  N$ I" }+ Y  g: r- `{
protected:
    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
& \, g4 a  e* j$ s7 a$ }) T  d    int* tag;
    WeightType infinity;

public:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

. ?' f, j) ?7 n( I; w+ c    void Clear();
    bool IsEmpty()
    {
9 j1 Z! B/ p- B& `3 `        return vexNum == 0;
, Y: V* b# R8 l* E    }
    int GetArcNum()const
& [" d$ O7 _1 R' G9 X2 b    {
) e0 S+ r7 s( p) e  X( e8 S        return arcNum;
    }
    int GetvexNum()const
    {
- q: s+ y1 B' ?3 `        return vexNum;
" I6 Z" J& d7 {    }


    int FirstAdjVex(int v)const;
$ p+ q; e( j6 m7 ?    int NextAdjVex(int v1, int v2)const;
+ @/ R$ |9 H6 g% w" J3 e    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
/ z- [; b2 Y* l5 D' b3 T* q    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
. l: @2 Q: Q) I, L. [( n6 v9 Z
7 G) m4 V: t" u6 J    void InsertVex(const ElemType& d);
) l% o% e- g1 V    void InsertArc(int v1, int v2, WeightType w);
. S! x. e5 }: j8 `9 R9 `
    void DeleteVex(const ElemType& d);
  p# S/ A+ M: d    void DeleteArc(int v1, int v2);

, t+ Y# w) n! j% I2 l4 u+ ^- E- {    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
3 t1 C; A' Q8 T, R- }    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
$ `4 z. k& B: o8 Q
  a8 a8 ?$ z# r" z" K! Z    ///深度优先遍历
7 W( r) B3 B3 F+ M    void DFS1(const int v);
' ?& s, i- x/ ?0 |5 V/ m    void DFS1Traverse();
0 z3 c& h/ P: J; Q6 l    void DFS2();
# D. x5 L$ [, T1 ~
: p' D. Y1 x# t  [) Z8 \7 S    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();
1 ]' m) y# n3 Z' u) q! z
- U1 J: z% t. d8 j& c    void BFS();
    void Show();
};
3 q; b- Z  r; B6 n1 Z+ s0 I
2.函数的实现
- {/ r2 X7 O& p8 [$ ~6 z研讨题，能够运行，但是代码不一定是最优的。

#include <stack>
0 Q  T% X  c; ~; O#include <queue>
# S. f8 x8 {1 w! R- L8 {5 P) i
template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
) c2 s  q3 }6 N, z& C{
    if(vertexMaxNum < 0)
- D) s0 O4 m3 k; E        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
. b. a( c6 D0 W$ V  d5 G* U5 ^    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
8 D- m9 E. O7 ?" T    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
$ r2 Q- }' Z& H% K7 r7 j8 E* W    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = es[v];
6 X% s6 _$ q4 ]$ m8 c        vexTable[v].firstarc = NULL;
3 [4 v5 q+ H( r% R    }
}
template <class ElemType,class WeightType>
$ R0 J1 a% P# c) P! wMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
. B. W; \, |) w3 O) Y1 s{
    if (vertexMaxNum < 0)
& m0 N) r+ L4 J% l! U7 M        throw Error("允许的顶点最大数目不能为负！");
" y4 v3 n/ e8 H7 b; l% ~9 f; z    vexNum = 0;
' k( u" b! g5 H# w    vexMaxNum = vertexMaxNum;
9 g) [. P8 L* l! u* ]    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
( L( }7 j& @& D( u{
    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
7 |( I! F# j) N0 w1 d0 Y        return -1;
    else
. P+ s# L4 b. s. ]        return vexTable[v].firstarc->adjVex1;
7 \) P% U/ a- K" I% Q}
+ _& O' }  P8 ?& h
template<class ElemType, class WeightType>
  h5 M  l  M% W: v$ Wint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
' }' ?3 S  D1 p! T        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
0 e) n( l( l7 J) A6 e    if (v1 == v2)
, a0 B' X+ ]$ ?0 e        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
( l# j7 Z) [1 z: O' }% ^9 C    if (p == NULL || p->nextarc == NULL)
8 q) ~! ~* `. ~6 {5 M        return -1;  //不存在下一个邻接点
5 f8 ~  y  u$ e) k0 t+ F    else if(p->adjVex1==v2)
9 u- m9 k- S% W' a$ g        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
9 v' O# x$ O1 L    else
  u  j: ]* h5 ?- C+ y" z) d) K        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
1 M1 k7 l( k7 t1 r8 gtemplate<class ElemType, class WeightType>
2 |/ K  Z; t' r  E! fvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
2 @2 G3 m+ R' A2 l* N8 a. l{
; N) H( F0 W; T1 z2 T! }" `4 T    if (IsEmpty()) return;
: s9 q0 w- m) ]2 O    int n = vexNum;
- B. p& ~; T- F/ B    for (int u = 0; u < n ; u++)
. q4 [( [5 y9 ?: b# V( |' Z        DeleteVex(vexTable[0].data);
1 I/ H0 ^  E5 q# s9 F    return;
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
( }0 G, O. Z- h- @{
    vexMaxNum = copy.vexMaxNum;
, [5 F* @! ^7 ?% [$ F. F  l    vexNum = copy.vexNum;
0 T6 r% o+ H5 q$ H    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
# e+ r, o1 P. \$ Q    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];
' C' Q5 Y! z7 {; u& w
/ j/ C( V" f7 t    for (int v = 0; v < vexNum; v++)
, f$ J: r' P; R4 ]    {
4 w1 N; |6 f: c. |        tag[v] = 0;
2 \0 M1 i! n6 ]( V        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
5 [4 I" J# ~3 ]; V4 V    }
# i% {1 `' {- r; X3 s) R    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
+ s0 \2 o# S5 U: E; h4 g    {
        p = copy.vexTable.firstarc;
' F' q1 f) u4 P        while (p != NULL)
        {
! F& J  R5 V; c5 O) q5 c            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
! z0 K! w7 M' D        }
    }
}
' `2 |( D: X2 y5 `& Gtemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
' K1 v6 o1 D! d, }    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
( c& o7 r# N( D$ k# d    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
) p, s; O, t+ @) ~" x    arcNum = 0;
% V$ R% H' T1 d( Z4 r    infinity = copy.infinity;
    tag = new int[vexMaxNum];
+ u1 q, r' `1 j8 c0 \
    for (int v = 0; v < vexNum; v++)
+ c: W# i" ~, _0 c( z    {
5 s1 \1 T( h: \' F4 ?  i  W        tag[v] = 0;
% z" Q2 `+ _3 W. Y        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
  n4 U9 {# Y0 `5 @* }3 B! ?    {
5 N/ h- M* @! r2 _8 e( L  c        p = copy.vexTable.firstarc;
+ o/ R& j( h8 y, r- H8 k        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
, b" p( h& K- t: G9 v! q: I        }
; I+ y" t3 n" c; u' E7 z    }
. M* m4 w" T3 P4 \* K/ [    return *this;
5 b( G4 @" W% N% Z5 o% c( F}
* U: R" @* C* y1 h* u! k# Ltemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
2 x# M. [3 [# v& k8 I9 }MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
5 h: F% \* y0 g' g" }' U* \( w& i    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
        return p->nextarc1;
- R. [% m9 ^" R8 U/ Q8 I    else
        return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
" W% V' p% P- Y. ]MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
/ W  L; M# ]4 D, N3 d/ V7 v  x, l    if(q==p)
        return NULL;
    while(q)
, M; J! c" |- k( F    {
( n4 @0 f+ x3 t; s7 F        if(q->nextarc1==p ||q->nextarc2==p)
/ s2 _( ~) Y$ q: Y$ w9 [            break;
        q=NextArc(v1,q);
    }
    return q;
; F7 L& Z5 V1 O* P" {* o}
/ d0 z" \6 n$ r3 f" }' K2 `template<class ElemType, class WeightType>
7 C3 e5 R7 ~" P7 y( Mvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
- j5 K' C, u9 f6 O, w{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
    vexNum++;
0 |; \5 U3 \1 v- P}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
9 @; T, H7 {0 |7 Y+ N; B        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
/ x9 s- v- _' @  I3 A/ i1 n  W        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");
- t  |9 I: p# j% e, v1 y

" o: w6 ^% f1 X& n5 ~    p = vexTable[v1].firstarc;
    while(p)
    {
' k: K# Z) u) v  @1 W        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
) y3 T' l, ?6 y0 D& }3 c! g$ |        {
            if(p->weight!=w)
8 D8 z$ S! v% n% E. o                p->weight=w;
9 |) D4 M: L" A4 {8 Q7 f7 ?            return;
        }

. n4 W$ z% z3 O+ ^: U7 C+ S/ o) O        p=NextArc(v1,p);
    }
( Z( [# |2 v* O# i2 C/ c    p = vexTable[v1].firstarc;
( ~) a# ^. P* o6 X/ M    q = vexTable[v2].firstarc;
8 k+ V0 T2 B6 t5 k9 v4 ^    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
& O1 z1 S. m! `) }( z6 q. M    vexTable[v2].firstarc =vexTable[v1].firstarc;
! q! C" P9 a! x; I! j3 M    arcNum++;
* n" b, w( L' @  h2 D}
2 n& ]. e2 e- B( O# }5 O7 k( e: X
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
' L+ J% |( T$ J2 K4 T, `' E) h
    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
( ~7 |8 [; P9 W! Y- g6 W) y. B6 h        throw Error("v2不合法！");
    if (v1 == v2)
# C/ p& w8 E- v8 H: {# P, ]' j        throw Error("v1不能等于v2！");

3 }. T) W# ^5 N    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
. H" [* S# z2 m3 V% b        q = p;
- G* x7 T  Y5 \8 ]9 e4 j6 C) Z7 @' S4 |        p = NextArc(v1,p);
6 y- t. l# c2 T  K    }//找到要删除的边结点p及其前一结点q

  |) p1 l: ~. c, ~& n, L    if (p != NULL)//找到v1-v2的边
6 z4 v2 h- G8 ~" ?0 F% {    {
        r=LastArc(v2,p);
' |/ m2 y' G" H        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
# u( J$ M4 t5 _7 X                vexTable[v1].firstarc = p->nextarc1;
/ h+ a5 F7 d, E  S1 f            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
5 R; h" V( D' H1 y3 u. {0 N        {
            if(q->adjVex1==v1)
, e  r# c4 @* [! m0 q( P                q->nextarc1 = NextArc(v1,p);
            else
                q->nextarc2=NextArc(v1,p);

! U" V8 k; K6 {5 F+ z; X) X        }
        if(r==NULL)
; d) b' D+ }  X5 U5 V            if(p->adjVex2==v2)
# w: ^. d. x9 K2 a2 `                vexTable[v2].firstarc = p->nextarc2;
0 F2 J) S. d1 @. H6 H7 J            else vexTable[v2].firstarc=p->nextarc1;
        else
        {
" Y0 i9 a: [7 x/ ]            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
- \% d5 J4 M4 g4 O) f            else
4 D. T& j) R5 B- P+ [0 j" Q                r->nextarc1=NextArc(v2,p);
3 V$ C& J3 Y. V2 |/ w* {        }
" ]+ h5 b- a+ m7 j* k& W        delete p;
) c$ _1 X( K6 ~/ l. S" m' i2 e        arcNum--;
    }
3 M! F$ [# R* }9 n
}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
{
5 \% g" a& H( k0 P2 Q6 O- B4 x: O2 r    int v;
    MultiAdjListNetworkArc<WeightType>* p;
7 L% H0 Z6 S& R! h! |% g1 O    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
  H9 ^, l* f+ j9 `# R            break;
    if(v==vexNum)
# y; v3 o% v) O' K  w        throw Error("图中不存在要删除的顶点！");
5 v9 ?' _' z2 s( m- ?
    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
* s  K) v  U, T6 d        {
* Q; A  j1 j3 N            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;
/ r, O% C" E8 ]; `4 b' J, k) U
    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
& G. c+ W' S& R' H, d" o    vexTable[v].firstarc = vexTable[vexNum].firstarc;
- M& r5 o/ c" T" N3 P- a- H, V    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
    //原来与最后一个顶点相连的边改为与v相连
" r% u, g1 V' s1 a: m    for (int u = 0; u < vexNum; u++)
4 ~9 z( ?: k- L+ Y! V$ G    {
        if (u != v)
        {
' ^  ~$ l# O% {7 |8 ]            p = vexTable.firstarc;
: K3 \( o. S: C0 j5 X' E, f            while (p)
" E8 E$ l# x# F8 h            {
                if (p->adjVex1==vexNum)
! H. Z+ H! s" ?3 S* b) T                    p->adjVex1= v;
% W& k! A$ x9 n# y: Z                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
' h$ D/ I0 ~: b8 p! g% a                p = NextArc(u,p);
            }
        }
    }
}
" H' }2 a  I7 J% w1 D( D///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
/ {6 n3 _+ T4 d; v& t{
    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
) Q  A1 U0 W5 ^, \    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
( T  T  ]" k  t3 c1 l" h7 I( B* Z; z    while(p)
    {
' s& H% S- {% O& s4 I; e, A5 W        if(tag[p->adjVex1]==0)
; f) y) l( ^/ T5 Y            DFS1(p->adjVex1);
8 ^  j+ B" s  W$ p, v& x        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
, \9 c, X# ~- d3 t        p=NextArc(v,p);
# R1 y( v& \: K# D$ E$ `2 t    }
}
. G5 W" ~$ d4 a/ ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
- _. |2 r( Q1 h7 m: Z" t{
& M) o7 {0 o" |" S, a    for(int i=0; i<vexNum; i++)
' r! Q2 g% {2 {. }% C        tag=0;
3 j  ]8 t$ O$ Q% F' t! D/ K3 q    for(int v=0; v<vexNum; v++)
" ?  W8 l2 k" J  _! s1 N    {
" s% c: T4 `' C5 e/ i+ f& j        if(tag[v]==0)
& ~- O7 m  R5 _            DFS1(v);
    }
7 H5 j- ~6 q( c6 w) Y4 d}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
    int tmp;
) i# X) C$ b& K% G, M5 x5 u8 v    MultiAdjListNetworkArc<WeightType> *p,*q;
" {$ Z0 O( d0 G% b6 r    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int i=0; i<vexNum; i++)
    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
        {
" t5 x/ b, Z4 [7 G5 {7 h            p=vexTable[tmp].firstarc;
3 V8 z: ^/ G+ K- k% `; \0 n2 s6 C            while(tag[tmp]==0)
            {
                s.push(tmp);
* D  X1 v" u4 |5 e0 f! q                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
; V* B" e' T0 A                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
9 z' t3 z5 R* z9 |- p                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
. t# \9 @& a9 U            if(!s.empty())
/ A$ ^- t- N5 ^! N            {
" Q3 B6 V- ~' A0 q/ \( }+ N                tmp=s.top();
+ ^' ?1 A/ I$ O  T* `9 n                s.pop();
7 ~4 |- N, H8 \7 Y; ~2 }$ [- {                q=vexTable[tmp].firstarc;
1 z" ]. E5 G' k% P8 F1 W+ W                int t=tmp;
+ H1 s5 g/ u* H. _                while(q&&tag[tmp]!=0)
                {
- I( S6 m3 s0 a' F1 T  A9 W& o7 U                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
* n9 o0 r4 u; w% w                    q=NextArc(t,q);
                }
: ^4 R/ S3 u3 ?$ v7 C0 e$ ]                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
$ j# ~$ ~3 Y/ w' J: {' @5 q                ///要么等于与t相连最后一个点（已被访问过）
8 o; k+ k! U2 _3 ?" K' D; V                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
    }
+ f1 J; R6 a+ W# f. E& g}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
    if(head==pre)
- x. x4 F1 @# c; E% i1 S        return -1;
+ {' N' g7 E+ `9 l
! d" j5 U, c; ]    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
! b, [% {# o2 {! L0 `        return p->adjVex1==head?p->adjVex2:p->adjVex1;
' J, P( u# P5 `4 L1 Z9 ~    //pre!=-1&&p!=NULL
    while(p!=NULL)
    {
8 i! o; p2 r: }: ]( z" y. ?        if(p->adjVex1==head && p->adjVex2!=pre)
: p4 V) O! J5 b# Y) r1 y+ n8 R            p=p->nextarc1;
" w/ r: x9 C1 D, n# |        else if(p->adjVex2==head && p->adjVex1!=pre)
* g0 I* p# |/ T6 b7 C            p=p->nextarc2;
) X  U, `9 |0 ^1 {1 r* z        else if(p->adjVex1==head && p->adjVex2==pre)
        {
            p=p->nextarc1;
& }0 n6 D, S9 k& H/ P            break;
) V  c8 t) M( d        }
        else if(p->adjVex2==head && p->adjVex1==pre)
        {
! p6 h$ O2 |9 `& c! c* r: t            p=p->nextarc2;
: i2 i* P3 f+ l            break;
9 s9 _* i: B9 |+ }/ n- v% F        }
' E' F) H) B5 e2 ]7 I3 @  z$ W    }
    if(p!=NULL)
    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
    else
& j% `6 ^' ~) ~7 G7 ^        return -1;
* e/ @% a9 ]; f0 q# k: E}


) T3 ^# B  i" O% o  |6 u4 Stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
& P7 O4 u& A9 c+ q% g( O    stack<int> s;
+ K7 C" l* u; W, C    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
  _% m- q4 C7 x- E    for(int i=0; i<vexNum; i++) tag=0;//初始化

& a1 A. X& P. a4 C9 |  B) q: n    for(int i=0; i<vexNum; i++)
    {
- g4 W* n1 _( o' J        cur=i;pre=-1;
9 @4 v, D! {% x6 h9 U        while(tag[cur]==0||!s.empty())
        {
' ^& C) e8 \) A            while(tag[cur]==0)
* {# j4 {. s9 E) c4 K6 Z! B" @            {
& r' E7 C' K) h6 P& g  V                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈

9 O" ?* ~' X$ |# i' Q" @               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
, o0 m& S* U  f5 H                   pre=cur;s.pop();
                   break;
' j0 ?# l3 ~5 I               }
               else
8 I- O. g( _2 t7 T: f               {
                   pre=cur;
3 d# x: f2 B( O& T" N  ~' u                   cur=p;
# t: i: L# o7 u- ?6 l               }

7 C% A9 M3 F  ~6 q8 w* }            }
( n7 @' b- S- J$ o. ^            while(!s.empty())
            {
2 [  c" L5 x6 h* k- i                cur=s.top();
0 d8 f& F: O" N. G% F2 Q! h6 k7 P                p=GetAdjVex(cur,pre);
' O% h1 q* C( I, i" E. k( U                if(tag[p]==0)
                {
2 R$ s: N2 G- C) `' H  C8 s                    pre=cur;
                    cur=p;
9 g  \# |% d6 H( e) r$ R* y                    break;
, z- G  E; ~$ O) s                }
( g2 H8 ]0 ~; E  n  ]                else
                {
                    pre=s.top();
                    s.pop();
$ b: n8 L, [9 {# D$ P- e                }
8 n5 O) D! B# j' o) U: O
            }

        }
( L( j% X* g% }/ c3 x; ^    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
    for(int i=0; i<vexNum; i++)
1 F' R/ Z  E% c        tag=0;
3 S, @+ O, z' y! c: s    queue<int> q;
; z$ _! V0 Q. [1 m2 X! u; q, ]. b! ]    int tmp,t;
, n8 E) h/ \7 \# U    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
    {
4 Z! L4 ?9 T4 G. d        if(tag==0)
        {
; r# S% G& \: X& V. v0 N            tag=1;
2 ?! _( y7 z7 [. Z0 d# Z2 f; z# _            q.push(i);
" Q: N* [, Z8 a8 K            cout<<setw(3)<<vexTable.data;
        }
" v7 T) \6 p/ ]8 A1 T/ X# h        while(!q.empty())
        {
' A: p: U* j$ z            tmp=q.front();
            q.pop();
& L  l: ^+ k9 s9 }            p=vexTable[tmp].firstarc;
9 o3 }2 w9 b3 n0 s. B. }            while(p!=NULL)
9 Y0 K5 ?- F2 l, S( g5 R# ?            {
4 |/ a  p, Y" b) l                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
                {
: B) ?1 ^/ ~1 L0 D6 ?                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
. H4 t0 J- D, R1 q0 U                }
                p=NextArc(tmp,p);
: y  x7 L( ~6 B" s( l            }
        }
, t$ S! p7 s7 _4 G8 j    }
8 J$ o, @& j9 F7 o* g}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
    MultiAdjListNetworkArc<WeightType> *p;
# K4 F( I) @# R( ~& ]" _4 V    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
; v, [7 a& P$ n& e$ |) q1 W6 U        cout << vexTable.data << " ";
( I% O6 k- f9 ?& |7 g    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
" C& C* Y; I. I/ V' o& w' T. @    {
4 G3 Q" R! L) Z( |. R$ z; O        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
$ N2 A- p% k5 N, y/ f        while (p != NULL)
" b& v2 C" N2 b- o% `        {
- l# ]# C* B+ b2 \& V            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
  X+ v7 t8 L' i3 L" X7 X: `2 k2 l            p=NextArc(i,p);
        }
        cout << endl;
    }
5 Y5 W1 ?3 s3 p0 |0 ~. {1 b+ q; V}


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

0 c. m8 n( h! A3 \' H$ u邻接表链接
; |: y9 k8 H' _3 d' N+ w; U在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
3 p; Q  c8 _7 [1 q  m在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
" P( L! ?/ o, r4 K( U$ Y" R" |" ]$ i+ N————————————————
% c/ R$ w6 O1 y/ b9 K版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 j7 F  b7 J+ y) f8 H原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, X0 t+ `8 f3 N5 T. H
  S. n  I+ H' H( c* ~/ j
+ c9 F' w# A& r$ j4 m& m
2 a1 g+ [$ K5 j
7 o8 X% i' p, }+ A+ B/ o- v: Q————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958


  n+ c3 I( Z3 H$ X& P. i