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

杨利霞

图的存储结构——邻接多重表（多重邻接表）的实现
/ }' N: _( R6 p& ^& o' v7.2 图的存储结构
3 N5 W0 ^7 \( A0 [: ?
/ w; n" I) r( U- [% F3 f  T7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
# H: n1 j3 \6 a5 z, c邻接多重表的边结点类模板
邻接多重表的类模板
' A* B1 X5 M$ x" K邻接多重表与邻接表的对比
& U4 z! |- v; w4 W' |" P8 t7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

0 k2 U6 t5 ^4 f; m/ s在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
' b2 U+ p% l' Q' S! o在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义
( W% k, F8 x7 t0 {* R
  j. F. Y  U% u: O* Z邻接多重表的顶点结点类模板

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

template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
+ Y' s% w; K2 ?  W/ P. V{
public:
        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;
6 T6 g$ Z0 y8 W
7 D0 A% o* r7 `& H$ o" s7 I        MultiAdjListNetworkVex()
6 w0 d/ n5 T6 u0 u( a        {
: T7 h3 [! J& K2 w4 f" u                firstarc = NULL;
: A* J$ P/ @9 d' |% Z. w        }
9 R# ~" z, {- j# z8 H' K        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
; n. W9 d$ \4 D, p4 l, V        {
                data = val;
                firstarc = adj;
        }
};
. Z; L1 F, p7 z1 E4 v; \* H% N
邻接多重表的边结点类模板

: Y5 F7 W" x7 ]. |# S+ O! h在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
0 j9 S+ K- l1 Z9 ?; b" V; y, Fweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
# f( H7 l' M) O& ]2 x( inextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。

3 q& Z' r. i& e3 G* U
7 i1 h- Q- O. }+ A8 c' `1 wtemplate <class WeightType>
# C0 X% @/ `. @6 v' N" a( i( rclass MultiAdjListNetworkArc
{
public:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
7 Q0 `/ m3 N+ ^5 _- S        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
5 z0 X8 k  O7 j$ }        int adjVex2;
! B9 w+ J5 F$ d, o  d        MultiAdjListNetworkArc<WeightType>* nextarc2;

$ T7 e& z' k" ?. a        MultiAdjListNetworkArc()
7 \- d8 s) l9 H- f        {
- C, m+ M) K% `. j/ U( p                adjVex1= -1;
+ R+ j6 |* R" Y; g                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
                adjVex1 = v1;       adjVex2 = v2;
+ e. G7 z, J+ B; e& m                weight = w;
                nextarc1 = next1;   nextarc2=next2;
9 B8 n$ H+ u) l+ f& z% o. v: B                mark = 0;           //0表示未被搜索，1表示被搜索过
: N8 b' W! w3 h9 ]* k+ L! w" h        }

邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
; I5 G( }7 x" {: |class MultiAdjListNetwork
4 h" j- |5 {) P( Q{
protected:
8 R, a& z0 [$ Y5 c9 M. B8 U    int vexNum, vexMaxNum, arcNum;
5 K' S$ w3 p$ f# ]: W/ W    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
% Z- B. [& A. F5 O/ W% z    WeightType infinity;
. r) d# w0 f. F! Z$ m
) _0 ^2 S0 \# ?8 T( O- epublic:
" e; W5 B0 t$ ^$ S    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
4 a& ?; s" d4 P2 j2 O
& g/ x  Y5 l2 s4 H4 j    void Clear();
  u% g4 r0 j: v+ T    bool IsEmpty()
' F2 @4 N6 k% {  |; W+ M8 ?/ J& a# p    {
/ g+ v$ U# O2 p5 |: d        return vexNum == 0;
# [; N6 ?9 X  u9 d1 q    }
    int GetArcNum()const
    {
, S6 k& s' Y4 }$ c        return arcNum;
    }
    int GetvexNum()const
; s( O  ?! H8 \6 f    {
  C* r/ G2 [9 X        return vexNum;
" K# |) E! y$ e4 J% W    }
' o1 j7 [3 G; d  \" Z+ R4 {

    int FirstAdjVex(int v)const;
) @/ C4 _0 y0 e# R    int NextAdjVex(int v1, int v2)const;
+ d; H+ n! I3 W' n+ U    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

3 B7 `8 w3 [2 z2 \$ V+ |5 K) T    void InsertVex(const ElemType& d);
) f. I1 d( b9 a# K; ?# T    void InsertArc(int v1, int v2, WeightType w);

( P; d3 f! p* \, \  F    void DeleteVex(const ElemType& d);
3 f' U* |" D6 n+ j4 o9 S    void DeleteArc(int v1, int v2);
& Y; v% _& E8 z9 a1 p
3 w' C( {4 \1 Q$ s" E    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
. }) h+ ]; z5 Z' H
    ///深度优先遍历
    void DFS1(const int v);
- q! F5 k2 @% P. t6 q( t: Q. g3 q) i    void DFS1Traverse();
- H: z, S3 Q6 C    void DFS2();

    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
2 `0 [- _. h9 @, b' r+ Z- \1 P$ G    void DFS3();

    void BFS();
    void Show();
};

2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

; b+ X& J7 ?) i: Z7 s#include <stack>
#include <queue>

template <class ElemType,class WeightType>
' `4 u" n) V$ `5 R3 _: j; FMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
; j# ~$ b& H' x" }{
    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
& F: B* r4 J+ W; F        throw Error("顶点数目不能大于允许的顶点最大数目！");
# G$ q& R# B$ l, a) {) y  A: M    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
8 _# b' s6 m9 z& E- E, p: g    infinity = infinit;
% ?* _: U, F3 h9 ^    tag = new int[vexMaxNum];
8 U# M) I& R- b9 _8 X$ F    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    for (int v = 0; v < vexNum; v++)
& S3 R! e9 }) a5 j    {
7 r. C5 u& a3 f5 |( W' N1 \0 f        tag[v] = 0;
        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
" A: a4 [- ]- {: e# N( X9 E$ N    }
}
" y0 ^% M+ O- j0 O. k4 ]template <class ElemType,class WeightType>
" h/ O6 m9 b# WMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
% I4 b# W3 e  G    if (vertexMaxNum < 0)
" ^- N. h( D& {# d! |8 W! V; U% O( I4 Z        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
, r8 S( w: F- Z  Y    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
0 i3 ]7 E, H: o0 r0 m    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
& \  I6 ^/ N2 r( I4 ^; O}
! N$ W/ W3 m) s' K6 }8 e4 ttemplate<class ElemType, class WeightType>
* G7 g9 B- L% G7 Y. K4 G- {int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
    if (v < 0 || v >= vexNum)
/ e5 p( o) [* E        throw Error("v不合法！");
2 {' ]: T5 |1 N6 K5 n, u. V; b    if (vexTable[v].firstarc == NULL)
8 o2 x  I" u- A6 z5 X        return -1;
    else
7 y. Y6 N) e# n  a% a& `. l7 u        return vexTable[v].firstarc->adjVex1;
( G6 _, E+ g" K! W}

7 e" L% J2 x8 ttemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
: F0 G/ s6 J1 S' m{
    MultiAdjListNetworkArc<WeightType>* p;
! v5 L5 Y0 G/ ]8 r* Q) b; p    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
' Q7 @* R. c# w+ {    if (v1 == v2)
        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
% C; b) y& O  k7 P* N    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
; Y+ b/ a8 O& y% Y: F        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
/ [5 q. q- R" C, y  N9 I) g$ V        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
: T2 X+ B$ k# |, q9 s3 j  S3 \}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
3 ^; e, k- |2 t7 y{
    if (IsEmpty()) return;
    int n = vexNum;
    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
1 n, c2 f8 }* A; W, j( S' C    return;
}
1 T4 v( O1 k8 J$ \0 ~* f7 ^# ctemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
9 y4 o0 S& f: A0 \' a& ?    Clear();
: e8 q1 b8 Q% c6 M5 d}
template<class ElemType, class WeightType>
( _4 b! R8 |( u3 c* }( Z* TMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
4 r2 i- v; l8 r0 R5 F- J* a{
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
* e! e9 w( d2 K: t& Y+ I    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];

' D. ]7 k* F5 G' l  ^    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
4 y( r& [, ~1 R        vexTable[v].data = copy.vexTable[v].data;
, O: v8 C4 G, [. U. ]& A$ c        vexTable[v].firstarc = NULL;
    }
0 _  `+ l. z, a    MultiAdjListNetworkArc<WeightType>* p;
7 o- D3 w9 p0 q
0 |1 t& D+ s1 q( x1 f    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
. Z: P) {% I, O        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
5 N* P; o9 [3 e. W1 w+ d; s- ?            p=NextArc(u,p);
        }
    }
8 s' X  m9 }0 H- V) t}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
- P/ G- F2 P; A5 c& s' n0 R3 \MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
- \' A) \9 E8 E4 x{
    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
# x+ ]* y; h% l$ k& s( j$ L& D    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
    infinity = copy.infinity;
6 E/ C. h0 r8 ~" a    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
( V6 \" x  |/ L% ~- h3 {# K8 v    {
8 Y. G3 w  z! X' P. ~2 c: ^        tag[v] = 0;
3 g3 l: W3 [; T: o% T  p        vexTable[v].data = copy.vexTable[v].data;
  @' v5 N9 z. H! s! \) Z4 M        vexTable[v].firstarc = NULL;
  {' _) h, a3 U3 c1 Y1 x    }
    MultiAdjListNetworkArc<WeightType>* p;
1 C9 [4 s, L# z8 _( A
- ?% |& e$ v0 Z/ ~    for (int u = 0; u < vexNum; u++)
  E5 f( M3 X, C  B' c! }1 G& `    {
  v) h: Y& f2 A% _9 O        p = copy.vexTable.firstarc;
5 s; x7 P5 M3 b" v        while (p != NULL)
0 H- O9 d% j3 N        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
1 g3 Z, @, ~% R4 ~$ [4 [% d        }
    }
    return *this;
}
- n' C3 i4 C0 [. Stemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
: s. F! Q& Y3 ^) m+ e: cMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
        return p->nextarc1;
    else
9 E. |7 s2 g5 E9 j, b6 \        return p->nextarc2;
}
2 L$ d) T. _9 X) }$ w2 Ytemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
8 s+ N: u7 S* T7 o9 M) Q. }0 V9 ?MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
8 X0 x) g6 P. @7 q    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
3 I' Y7 Q% S! z$ [. V    while(q)
    {
5 K) Y; P8 ?0 z, p0 C6 n0 c( Q        if(q->nextarc1==p ||q->nextarc2==p)
            break;
        q=NextArc(v1,q);
* j7 |- r' Y5 y; U    }
    return q;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
2 E2 h* ^# X. P. J# \{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
6 e+ _; @5 i* v  J% {! f    vexTable[vexNum].firstarc = NULL;
2 e% [; M4 ?* h$ T0 g    tag[vexNum] = 0;
& ?2 z2 W9 G/ _    vexNum++;
' `  `+ f0 b7 ?, ~( r& R: ^$ y. _}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
7 I7 G# o" \, v1 Y+ Z* w  N7 s{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
1 y" V3 t6 m- p& p1 Q' P        throw Error("v2不合法！");
) C1 n3 T; J5 p& ?% X$ g    if (v1 == v2)
$ x$ }. a1 L/ V& P        throw Error("v1不能等于v2！");
    if (w == infinity)
& ^0 [4 u& [& u2 O        throw Error("w不能为无穷大！");
7 k  }5 s3 J7 e1 }7 k

+ c, F2 n2 V' X) B) N1 v/ {    p = vexTable[v1].firstarc;
    while(p)
    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
" S/ q, D3 `$ H        {
            if(p->weight!=w)
; N* D$ }" l6 u( j; c8 @                p->weight=w;
            return;
) ^# S" B0 \/ h        }

9 u- L0 V' e5 o& Y# ~2 P1 V        p=NextArc(v1,p);
+ B  y! M, `8 H4 N: c0 F    }
/ N% q8 N. n' |. r  s    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
, i4 K" ^' i5 O5 B2 w! ^- L    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
  X- ^) b% w" E2 E; Y7 {    vexTable[v2].firstarc =vexTable[v1].firstarc;
% K2 i  p3 z* q" O5 ~    arcNum++;
}
' K/ @1 x$ F8 ~5 V
% G, \( V( W* u+ _4 W! k+ {; jtemplate<class ElemType, class WeightType>
/ T! K  d9 y! f) a& T1 N, f. Evoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
) O4 X4 s2 d5 C8 F" o
# `( ?$ d: d  `' O! W/ J% _8 k    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
& n% Z! M4 w5 B" k    if (v1 < 0 || v1 >= vexNum)
" p+ U# t0 j% `  l        throw Error("v1不合法！");
/ y% A; D2 t9 F: S9 U$ ?    if (v2 < 0 || v2 >= vexNum)
& S( l; `  C* `        throw Error("v2不合法！");
3 Q% }4 p! x& w) c. Z4 _    if (v1 == v2)
3 y: O7 ~; X5 E2 O0 ?5 P) y        throw Error("v1不能等于v2！");

. Q. [7 V  J. k4 O8 j    p = vexTable[v1].firstarc;
0 E' |: ?7 Z, x. j% Z    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
( L+ M  D7 U2 _* x: V    {
        q = p;
        p = NextArc(v1,p);
    }//找到要删除的边结点p及其前一结点q
$ S& |- U# _0 L: S
    if (p != NULL)//找到v1-v2的边
6 \  [8 y4 k% _; Y2 t5 k" L4 n& G2 W3 p    {
0 h  Y0 s2 j$ b% Z0 k        r=LastArc(v2,p);
; C5 }1 J  w( O) S        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
  @" |5 E/ |6 L! _                vexTable[v1].firstarc = p->nextarc1;
3 N) O. ^: v9 B1 H3 r9 a% f! P! L            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
        {
            if(q->adjVex1==v1)
- y4 A- @  Z) v; U! q( A* K                q->nextarc1 = NextArc(v1,p);
  n5 c& A5 [  b+ F* N            else
4 |2 U) b: k+ O3 `) `0 l                q->nextarc2=NextArc(v1,p);

; _! c6 s6 q$ v; @& c" @! k( }- W        }
2 F+ Q# b1 O- R        if(r==NULL)
            if(p->adjVex2==v2)
2 [0 w: g$ h! j) x# T% N; ?                vexTable[v2].firstarc = p->nextarc2;
& E9 g( K) _7 D% a            else vexTable[v2].firstarc=p->nextarc1;
        else
7 [, Z: n: O' ^4 n        {
! d8 i' _0 `# K- B- M            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
            else
2 H* g* a7 e- V2 e( W, y                r->nextarc1=NextArc(v2,p);
        }
* U8 |; u: h3 z; ^. C8 x        delete p;
        arcNum--;
1 I+ H: G$ Q. R6 |, X, C& f    }

}
' W8 f# P( y" Q! y, W! E: stemplate<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
* Y* I: k8 k8 E0 V{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
/ I1 j$ ]4 e0 E3 H. V    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
; q) ~, N# h/ K! i3 q4 v) i5 Z    if(v==vexNum)
" A6 q& a( C; w9 J+ H; j" v        throw Error("图中不存在要删除的顶点！");

( z( g; X6 |8 @- q# V    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
" N8 O9 t  Q. a0 m& @+ q4 B5 t        {
- _$ _1 q, |; b5 Z8 |; N! `            DeleteArc(u, v);
) g5 f0 O1 r( W1 z% s5 z        }
    vexTable[v].firstarc=NULL;
7 l+ Z7 x4 r1 ?# x6 n# L0 [
2 v4 N& n  R+ M) k7 L    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
! V) L7 I4 s/ K# |    vexTable[v].data = vexTable[vexNum].data;
6 b  M0 h+ V; w. N    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
$ [( g; M5 k' J9 j. N  Q  u3 k1 O    tag[v] = tag[vexNum];
    //原来与最后一个顶点相连的边改为与v相连
1 `$ ~) `. h0 ^- \1 g) I, ^+ Q: g    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
        {
            p = vexTable.firstarc;
            while (p)
            {
  H; y8 l+ |; y$ H) G7 [                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
6 B; [+ G- j* s* A$ H                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
                p = NextArc(u,p);
            }
. L, A+ u- Y, }$ J7 D' C! g        }
    }
}
5 R" l- i, u. l///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
    tag[v]=1;
* d# F% }! i$ S2 o$ r; r    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
; |; q1 H5 E- c    p=vexTable[v].firstarc;
    while(p)
5 n  B6 `6 o7 A% O/ o    {
        if(tag[p->adjVex1]==0)
. H" ^7 }9 j1 [7 `& v9 G            DFS1(p->adjVex1);
/ Y/ i0 d$ u1 }! F  }9 A        else if(tag[p->adjVex2]==0)
7 D$ |8 r# O# ]+ z! X0 Q2 H            DFS1(p->adjVex2);
        p=NextArc(v,p);
    }
}
. w2 ]% v) o' a  A- ~' z' T: utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
7 \2 S" b- h+ V{
/ r6 z; ~% m3 @1 F' p3 b    for(int i=0; i<vexNum; i++)
2 \; X4 b' [& O; C) R( |        tag=0;
- V9 n3 }: q( @6 w- J1 ~) T    for(int v=0; v<vexNum; v++)
/ U! Q% j3 q2 w    {
        if(tag[v]==0)
9 G* q1 i* k. J; _+ R            DFS1(v);
# z0 E7 C8 B% |5 O    }
; C6 N4 O2 G2 G# m. n}
' ~; }1 `9 W' I' o$ Ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
3 w) Q1 r5 r' r! v! ~{
: ^$ ]* _. z6 h& ?- r    stack<int> s;
' V6 r+ V) X+ ~5 A    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
        tag=0;
. n& p8 X2 J$ m3 T5 a; B    for(int i=0; i<vexNum; i++)
    {
$ S9 a# f( v7 T: J3 y        tmp=i;
        while(tag[tmp]==0||!s.empty())
        {
7 D2 }: Y7 M9 i! ?, [: h3 p' p            p=vexTable[tmp].firstarc;
# x: D% H" Z9 D1 O5 K8 ^            while(tag[tmp]==0)
1 v$ o: J* f) h            {
                s.push(tmp);
" x5 c9 F' d) ?6 A& ~' f. A                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
& |! ]% _' {& V            if(!s.empty())
            {
                tmp=s.top();
+ P  g! N5 g6 `3 ^) V' Q                s.pop();
" H6 {/ {' b/ J6 C+ ~' {                q=vexTable[tmp].firstarc;
8 Y3 G! f- S5 T4 ?# f  O! J$ \                int t=tmp;
/ f( b4 T; D5 J& k7 W                while(q&&tag[tmp]!=0)
$ z% x  G' Q% G- Y3 ~/ z# h                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
6 A, m8 S+ Q+ z; Y. v2 Z, o1 ~: n# M                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
! J' o( {. n% \                if(tag[tmp]==0)
& W- ~# G0 e0 ?0 J3 N6 t7 q# Z                    s.push(t);
' l& l8 e6 z, G2 ?3 B                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
8 g' r6 {1 T* X9 v* c: Q2 Z0 h                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
4 a6 K; Q3 m/ Z+ R$ a& E            }
        }
    }
}
1 H/ R( q7 m/ d0 r4 \9 t( X//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
8 B3 R. X; ~8 a1 n) l5 wtemplate<class ElemType, class WeightType> int
3 w9 g- s3 `' u- p6 N7 m% qMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
    if(head==pre)
        return -1;
3 |& w% ?. c& W9 n$ B: S
3 d% q7 d+ y2 v& j& V, q: Z    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
. o6 ^) D1 ?. h4 S        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
    while(p!=NULL)
    {
        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
% R4 u/ }. I' O' }1 B        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
- u$ b3 z- [  A7 e! e, k        else if(p->adjVex1==head && p->adjVex2==pre)
% z4 \/ z9 I; M$ x: o1 u" c        {
' d, w8 ^  a" Z$ g' J8 B9 U: W            p=p->nextarc1;
7 o/ q& @# }! {" e* M9 e* R, s            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
+ Z6 N1 N3 F* ]- _' J        {
5 M+ }- b  g+ W" k            p=p->nextarc2;
' M7 b4 h& g4 @0 R$ w            break;
        }
8 G/ H+ U  y" j7 F$ G# M    }
    if(p!=NULL)
    {
' ]4 a1 M+ j+ T% r2 U( ?        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
9 `7 ^/ k( ^: r6 I5 s5 b' E    else
. \# ]" B1 q! f, q, }8 k        return -1;
% h+ G* |3 a6 k' ~( j: [8 a2 \}


* [8 B) j+ T4 m  h; e3 U! Wtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
; b8 f" |, y1 B5 F    stack<int> s;
    int p,cur,pre;
1 P0 _7 k4 R0 s. p    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化

" H; W9 b" w" r) r3 Q    for(int i=0; i<vexNum; i++)
" U* q3 f# o( K: v2 F9 l7 {    {
        cur=i;pre=-1;
( w6 Z* o3 J5 k% n8 R4 a9 y        while(tag[cur]==0||!s.empty())
- a2 L9 q% w! x- }3 I2 l  w        {
            while(tag[cur]==0)
# p% ?: z$ ]( U) U8 G( d            {
                cout<<vexTable[cur].data<<"  ";
7 _9 ?0 }7 }+ R9 ]                s.push(cur);
                tag[cur]=1;
8 r; t. ?3 D6 r# \) U- L$ E6 ~; x               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
* u9 ^0 u! x& E- h! z/ P6 S( T                   pre=cur;s.pop();
                   break;
! p; [' `1 `- y* U( ^1 O               }
               else
4 r- F" z6 f( ^( ?               {
/ U, ^5 o' z* X# A                   pre=cur;
                   cur=p;
  `" V5 v. g# Y1 C, f" a: C               }

4 Q3 h$ Z2 l* s            }
7 V% A3 z9 }9 u6 z& t3 F% b, e5 t% O" w            while(!s.empty())
" i/ N1 q2 ~2 }( j$ _1 o            {
                cur=s.top();
* s" l: c0 E; v/ g                p=GetAdjVex(cur,pre);
, ~. N0 p1 |2 S- C. J                if(tag[p]==0)
, a" @( S, Q1 G3 u& Q" M, v0 S                {
                    pre=cur;
% e2 d- r+ W( n3 Z                    cur=p;
                    break;
                }
- c* ^( Q* m) s; S- V$ _& Q! P                else
                {
3 r6 P9 M4 m7 }" `* ~, E# x: ~: ~5 m% |                    pre=s.top();
                    s.pop();
                }
9 Q  ?5 y' i: [/ s* k( b" l
6 q  X8 X& R* I' R            }

        }
    }
0 W" u$ \: M1 J}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
6 N3 {8 m6 Y& K8 Q" @{
    for(int i=0; i<vexNum; i++)
        tag=0;
    queue<int> q;
( i# x0 j' i6 ?" v    int tmp,t;
1 N  x- g2 x9 g/ s' D    MultiAdjListNetworkArc<WeightType> *p;
6 a0 S; ~3 S; E9 O    for(int i=0; i<vexNum; i++)
3 f; [  I+ {7 v$ b    {
        if(tag==0)
! E! c9 m2 c! }# k+ }1 K        {
            tag=1;
8 U" p7 D5 `+ b* U            q.push(i);
            cout<<setw(3)<<vexTable.data;
        }
        while(!q.empty())
3 _/ L1 J& T0 q- m: }        {
            tmp=q.front();
- q+ c' G) U7 F; c            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
7 B# d' A0 R8 t3 v" B- S                {
4 w& m& ^  Z/ E                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
7 p  t2 U8 h+ B0 _9 R* P( R! m; l                }
                p=NextArc(tmp,p);
3 M1 o' n5 C/ ?! s& Q- O            }
0 h- W$ e( v9 w        }
    }
- _( U/ F( _, N/ n$ P}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
: I& h! F" c# O, v( ~. h    MultiAdjListNetworkArc<WeightType> *p;
6 ?' U( r" a7 T5 R4 K    cout << "无向图有" << vexNum << "个点，分别为:";
3 R6 D( _, D% a; W5 W, _    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
1 U. W8 j- E/ E8 z+ \+ `/ b1 y    cout << endl;
! ?3 T8 ~9 @, H" k3 n    cout << "无向图有" << arcNum << "条边"<<endl;
2 g$ X4 \+ O% l( {% B    for (int i = 0; i < vexNum; i++)
& b; e2 }4 o* N' j( B8 }    {
, ]  G1 J8 A% U5 V# R        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
0 x. U" L' y4 r        while (p != NULL)
        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
, N: N, n, g2 B1 E8 d            p=NextArc(i,p);
) s0 H# R- X/ _* K. d" _        }
* T" \. m0 q8 V0 h5 Y4 X3 _# G2 M        cout << endl;
( y9 E2 W4 Q1 P  v0 D% ^    }
}

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


# Z2 F9 b, J6 N; |! M7 s1 q) f
: _3 _4 K: `) ^
————————————————
& H* I7 z7 R$ T0 B版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
$ `6 e  s: Q, H4 ~: _4 c: P6 u
% B1 t8 Z! O! b) f
% u8 c+ s# k6 e1 q