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

杨利霞

! H% m( e# Z& m+ T3 |3 c图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构
) A' I: n2 p; [+ g7 v
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
: r2 z5 p/ \$ [* b' _  I% T邻接多重表的类定义
邻接多重表的顶点结点类模板
1 ^9 x) t- a4 q7 t, E1 L+ N% a邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
, L1 K; j/ S$ c9 m/ r# d
/ a6 P4 X( W% E& l- k: q6 y! A在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。
- D! p% X$ h: _) T
" J9 B; |6 `3 h4 o邻接多重表的类定义
/ Y+ M2 }) I: P
邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
- y: B* r7 k2 V9 J% m$ w所有的顶点结点组成一个顺序表。

template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
{
5 t) p1 o4 k. u! W) q3 lpublic:
4 E/ _' y, r% J0 L( U" x1 \& w        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;

        MultiAdjListNetworkVex()
        {
                firstarc = NULL;
7 X. S" b& h; H# J) S7 ~% |        }
  S8 \* O) R$ G$ o% P$ i5 C        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
        {
                data = val;
                firstarc = adj;
        }
. c; ^( ?9 r; s, V6 ^5 f};
4 O/ B. @& K) m8 m
邻接多重表的边结点类模板
; F6 C! I1 P! S0 K6 x
7 I% M, J/ u! x* M5 F5 _在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
! z9 K2 F! I) Vweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
$ p, a3 L6 F/ L* _* ^nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。


template <class WeightType>
class MultiAdjListNetworkArc
  [5 l4 R  v, f+ L( ]8 x{
7 f& H! p" k0 X% c8 @public:
" z" Y! E9 H% i, d5 Q" `  m    int mark;                                       //标记该边是否被搜索或处理过
4 `9 A! n9 `. r        WeightType weight;                              //边的权重
0 o+ {* O7 ~4 C+ D. ^        int adjVex1;                                    //边的一个顶点
  F0 Z8 N, w# d) o        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
$ s! H+ l0 p2 ^6 W. s. l; F3 J        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;

        MultiAdjListNetworkArc()
        {
                adjVex1= -1;
                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
6 B$ o6 \  f; p- s        {
. Z  J7 w1 M' Q, T                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
        }
  g5 {$ z4 y  x: `2 D
邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
: ~( {, k5 O; S6 o) zclass MultiAdjListNetwork
0 b' k( _/ L9 m{
protected:
    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
& X2 X/ [1 @' J    int* tag;
    WeightType infinity;
5 J# P% a. c7 J0 J, L: C8 U" {
3 a# T9 C% ?: {0 V  I! J% R% Opublic:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
# i5 }( q: I# W1 D
! I- B  y  y6 a1 |    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    void Clear();
8 X" w0 i. E1 J    bool IsEmpty()
% l7 t# F; Y4 Q$ {/ X; t" o% }    {
; C& v& G& Y$ a* M" p6 v4 Y        return vexNum == 0;
3 K+ _) X5 J( M8 Q2 {7 Q" h    }
    int GetArcNum()const
4 l) v2 g' c2 C    {
, n4 Z) _! Y0 d$ `% r        return arcNum;
8 ?6 ]4 Z6 U) K    }
6 m, y1 U3 ^* ~- y    int GetvexNum()const
+ n- l" e$ @1 D    {
        return vexNum;
    }


6 y0 ], X) ]3 q1 T9 O9 x    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
0 O' @5 x- y, ], O    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
9 w3 v+ k8 y1 h% \" C- n7 J
9 |6 v5 [3 H  L6 I$ f" ]" X    void InsertVex(const ElemType& d);
    void InsertArc(int v1, int v2, WeightType w);

9 S1 k% t1 `' K3 h5 O) h4 h    void DeleteVex(const ElemType& d);
    void DeleteArc(int v1, int v2);
7 y" H( l' M( X+ P
0 i! s% Z% g) K. O' h! p* c1 o- Z    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
, o6 k# w) N8 F* |# |    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

  m0 A' I+ C- t3 W+ N& F    ///深度优先遍历
    void DFS1(const int v);
' H. u4 G4 Q: l+ i7 S! D    void DFS1Traverse();
    void DFS2();

- B  k6 K$ F) z    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();

9 m$ I- Z) J4 G    void BFS();
    void Show();
};
4 k" Q: Z! l& X; `8 G
2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

; k0 M/ I+ a2 }, B# e0 [- \#include <stack>
#include <queue>
9 m/ n, d/ K# \
template <class ElemType,class WeightType>
9 \5 X; G1 P$ o0 H# L; L) IMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
/ x0 f0 i1 v  C- n" O{
9 y. K: h  |1 _4 H/ E# d    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
8 y1 _) h) h1 [' F& q2 \1 Y        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
5 K: R& K8 P$ j' m1 L    vexMaxNum = vertexMaxNum;
: n) B$ w0 d3 e1 d% t" C4 {3 s    arcNum = 0;
    infinity = infinit;
& _7 O, |5 [- f! o1 n* Q    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
    }
0 Q- q5 j- X$ P- p6 F0 r! E}
template <class ElemType,class WeightType>
+ o2 ]6 @9 K4 w& N/ N  M- c5 DMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
; r- O8 y( p4 N/ X{
. S& A$ k; q" S( ^) [: U    if (vertexMaxNum < 0)
8 N* f' H1 l0 o7 [        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
  Z/ ~" x- W4 [- w: Y    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
9 f7 R* F/ j9 x5 j; ^3 _; n{
    if (v < 0 || v >= vexNum)
( C) h& U* U- E& A( p        throw Error("v不合法！");
1 d- Q- _& s) x( q# b! l# J% k+ ?    if (vexTable[v].firstarc == NULL)
9 a; d" i0 P" ?" G& S        return -1;
    else
        return vexTable[v].firstarc->adjVex1;
3 A/ Z) K9 b- f/ Q7 o}

template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
    MultiAdjListNetworkArc<WeightType>* p;
& t& D) Q2 }1 s4 R% z5 t    if (v1 < 0 || v1 >= vexNum)
/ w+ w# h  O1 X, w* u2 o        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
. S4 R6 B  B1 f8 [9 h0 T    p = vexTable[v1].firstarc;
- B# W# `9 ~! I9 R* E0 `    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
5 A$ F8 q% K) H        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
% N  M0 g8 m0 M. H$ ^: |    else if(p->adjVex1==v2)
; S* R1 P: R3 \$ X7 o        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
: t( e% a# k3 o6 x& D) U+ W        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
    if (IsEmpty()) return;
9 Y6 B0 G9 U! v, L0 _% Q5 T' h; V7 p    int n = vexNum;
+ w: q& R3 r% B( ^7 R: j) V    for (int u = 0; u < n ; u++)
/ Q# g7 O, h+ T  @6 Q3 y        DeleteVex(vexTable[0].data);
    return;
}
) r: _1 ?8 Q; ]( u! r! d( jtemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
$ R, v$ h4 T, @3 ~! m{
    Clear();
}
template<class ElemType, class WeightType>
2 g$ D4 ~* ]$ i% FMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
% z1 n4 T6 ~% B- t$ f/ @/ z{
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
3 S6 u3 E0 ?4 i/ p1 ]    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
' e4 S4 B) D9 D; w, }5 [    arcNum = 0;
# C% d( s3 o5 s" N1 Y    infinity = copy.infinity;
7 T! u! M. t$ w9 Y; R    tag = new int[vexMaxNum];
* R. H" {2 Q% ~/ d9 u
    for (int v = 0; v < vexNum; v++)
/ `* h2 ^0 k9 j5 D5 D  a. H    {
        tag[v] = 0;
+ y& @# b. n9 R* B# ~9 E9 v        vexTable[v].data = copy.vexTable[v].data;
# c9 Z& `- v0 z7 K% r: T        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;
3 a& s  \7 y8 `. p) E
    for (int u = 0; u < vexNum; u++)
    {
: h6 A, [: B, r( P: E" l        p = copy.vexTable.firstarc;
$ w; Y1 u: x: r9 \        while (p != NULL)
0 i/ W; p9 I$ K7 W        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
7 R$ Q2 a* G7 E  q        }
$ o* W. {1 P2 t8 c! ^3 E    }
+ {, S5 h. B1 i* D6 Z}
$ i( q& M( [* l6 etemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
/ Y/ L4 ~, C$ Q7 U& T% G3 p& q) a/ eMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
+ y4 I  a6 W5 B, f* p6 l0 D{
    if (this == &copy) return *this;
2 h' H- }9 t. E- b/ W    Clear();
* h5 ~- p4 T. S: r" C) q# f    vexMaxNum = copy.vexMaxNum;
" @7 j% G6 _8 J( J2 `    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
. V8 m- {$ d$ Q6 c* k) P; w5 T    infinity = copy.infinity;
    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
1 w  J/ A5 N# T7 v2 a! a0 g    }
7 G4 X) C* m0 X1 p4 y    MultiAdjListNetworkArc<WeightType>* p;
) M- y9 p  L' ~% a% y+ Z
    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
! X) w& n$ b& i) V6 F2 S( |4 Z  U        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
' P2 J1 S$ M1 {$ W+ t            p=NextArc(u,p);
" ?. ]& @' R! ~) d+ a  |- T        }
6 z0 D4 `7 i, W! M/ S, _    }
    return *this;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
- E- h# r, x  i* ]/ _  a4 B; Q        return p->nextarc1;
( u2 q5 Y) a1 H8 \* \    else
1 i# `! |& U" K9 f+ p        return p->nextarc2;
7 D; z" P' @+ ?) C( T}
) w4 b- ?6 e/ T+ }# Vtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
5 @0 t, y9 H$ D" b7 c6 G" F    if(p==NULL)return NULL;
' P' @5 x! z( J9 V    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
$ ^3 n1 E5 p, x- y    if(q==p)
        return NULL;
- N& X5 {* t* ]* P# B& J& `8 {    while(q)
- e' R+ E5 ^% }' @) l    {
! z( t2 y; i0 e5 ?5 y2 m+ T0 [" g5 ]        if(q->nextarc1==p ||q->nextarc2==p)
1 d0 k; d# A( o9 \# d: \: B            break;
. Y! k9 m6 y- y# z) D( q$ `) ?" }        q=NextArc(v1,q);
    }
    return q;
+ T' Y. x5 l' v3 k$ h; `( f2 w}
6 V+ u8 _$ f9 L3 Z7 U% E! etemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
# S' B0 X- p9 B, P3 f2 O1 @, K        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
. e  {: t8 S4 \    vexTable[vexNum].firstarc = NULL;
+ Z$ r- t+ C* I3 W9 I    tag[vexNum] = 0;
+ H5 w( @6 u6 B1 K" D4 J1 J    vexNum++;
}
template<class ElemType, class WeightType>
  e$ D% o# s* d% yvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
' o/ c% H, j/ @, a9 W" d& Z; N! d    MultiAdjListNetworkArc<WeightType>* p,*q;
2 z0 }: y+ S! R; @: F0 J    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
0 r  P; D% d) a7 c) y    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
; E. w3 @7 U1 G; [- V5 q/ F    if (v1 == v2)
        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");

- ?8 \! f5 {0 z+ _5 t- [4 m  ^
3 a' s/ G( E2 c, R0 o9 S    p = vexTable[v1].firstarc;
- S5 Y8 w+ O% O- L    while(p)
" |  Z# V( ^" i4 L% x    {
0 W" R! y1 B/ S9 d9 O# @. w        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
2 s" r$ k# F, ~) h% Z        {
            if(p->weight!=w)
                p->weight=w;
" P# w7 j& @% k2 S6 Q/ q            return;
  X4 G9 N$ h# P2 U' l& @        }
- i2 j* F2 O% R4 ^3 j
8 R" i+ y! V/ @        p=NextArc(v1,p);
# s$ V9 y2 w+ E2 e6 q1 N6 H& ^& T    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
  i% Q0 W! ^: U8 S    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    vexTable[v2].firstarc =vexTable[v1].firstarc;
    arcNum++;
; Q0 Y7 G' q5 |4 K& V; O}

  N5 |! S5 @3 s/ A4 x3 ktemplate<class ElemType, class WeightType>
) J( g* Y3 N* C7 s  Yvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
" H! J. l/ U) z, }0 d
, K& \7 T2 T6 ~* k! _0 z    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
- n$ V$ m: z! u% w; ^" w& x        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
, ^3 a4 ~. z6 J' _7 q7 w8 {0 i5 h
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
        q = p;
- s( b! k* P0 h3 L! d; `; u6 w: o        p = NextArc(v1,p);
' i2 T$ u1 A$ `6 `: j" h- q    }//找到要删除的边结点p及其前一结点q

    if (p != NULL)//找到v1-v2的边
  U' k0 m. C' {    {
, A6 Y6 U7 @' l$ Q  o/ a        r=LastArc(v2,p);
4 I$ I9 G/ Y9 {% n9 i6 ~3 ^% G        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
8 v& n1 x$ h+ X- u* r            if(p->adjVex2==v2)
, |6 m. K' y& u8 ]4 ?, C                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
        {
$ [0 F2 B( X* B2 k            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
            else
                q->nextarc2=NextArc(v1,p);

        }
        if(r==NULL)
4 _3 E% l7 V* S. \4 ~            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
6 E7 X2 G* j9 ?8 r        else
1 L5 _/ T- P) i; ^3 t        {
            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
8 ~" v+ y% H3 d9 M5 }, N" |            else
8 [  {$ P& F# [: H" }" r                r->nextarc1=NextArc(v2,p);
        }
        delete p;
        arcNum--;
    }
) _% D0 v1 X/ }7 F. u1 Z: K
}
template<class ElemType, class WeightType> void
# N5 H' d6 [' J9 M3 r2 ^& {* `* \7 yMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
{
    int v;
9 X, r3 A1 @- f1 b* [1 S! [& x    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
1 s$ R  |: g, i/ Q        if (vexTable[v].data == d)
            break;
) ~! `, r1 X8 _7 z9 J) s- b; q    if(v==vexNum)
- E2 j9 G: F5 H) ?- z4 A        throw Error("图中不存在要删除的顶点！");
2 m6 B1 m. C; ^0 g2 z* q! {& R
, q) d6 a' C- ?" ^8 i2 B# u6 t    for (int u = 0; u < vexNum; u++)//删除与d相连的边
7 q9 S+ t% S6 v" j" {9 y        if (u != v)
        {
            DeleteArc(u, v);
        }
( a7 {: W, V4 X; m2 m    vexTable[v].firstarc=NULL;

    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
; F  G% X* P- h) @5 Z! ?5 l    vexTable[v].data = vexTable[vexNum].data;
8 u1 h8 D& e. [5 ]* l! z    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
# F$ k( r' s! T. p6 s    //原来与最后一个顶点相连的边改为与v相连
; R5 U  F9 S! N+ p    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
        {
            p = vexTable.firstarc;
6 U, c% F# V  f% @9 h8 ?) X" E% o- {            while (p)
6 D9 ]  q6 L4 [            {
                if (p->adjVex1==vexNum)
9 t9 \6 ]5 g" ~4 A+ P                    p->adjVex1= v;
' c6 i3 n0 W4 T4 l; u( D, G! r7 t                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
                p = NextArc(u,p);
            }
        }
    }
/ Y1 Z  Y9 d( a* t}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
. i, C- C- {2 A' c8 c" h{
    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
' v. y2 @, i% j6 Z* A+ P    while(p)
. @4 T/ a% ^. K) B    {
7 W' R# X0 a0 `3 w* ]7 z: V$ ]        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
# p  o0 Z. B* _; G- ?4 Z# S; O        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
        p=NextArc(v,p);
$ a, l: d5 E* z, j    }
) s" K7 v, R( p2 a' N}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
{
- i$ X6 r6 Z8 D0 w6 U# r    for(int i=0; i<vexNum; i++)
( r" I% i7 V" }! x) Q, F8 S        tag=0;
    for(int v=0; v<vexNum; v++)
( B8 q2 o/ C' ]- R; d% l    {
        if(tag[v]==0)
6 M4 S/ a1 V% k            DFS1(v);
    }
- }4 K# J# B5 W8 o5 l' I2 e}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
    int tmp;
, v% f5 C/ Q. [" t; Q( G0 o    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
1 O# w2 }8 e$ _5 ^7 }) o        tag=0;
    for(int i=0; i<vexNum; i++)
    {
) z2 f$ [1 ^# g' z        tmp=i;
* p$ Z% t5 Q( Q9 P6 i        while(tag[tmp]==0||!s.empty())
        {
$ X5 B* ^" q8 ^) A( P3 ^            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
$ j  K4 K/ b: s6 y3 Y& p$ ?            {
% n* b: b, i7 R5 y3 y9 T                s.push(tmp);
. F; w* k2 c8 B  M8 W                cout<<setw(3)<<vexTable[tmp].data;
% {' h  z$ ~7 T% f% F. x9 L                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
            if(!s.empty())
            {
& |+ T- C0 s. C% a/ P                tmp=s.top();
                s.pop();
1 W0 g5 w) g% ~% D: W) x                q=vexTable[tmp].firstarc;
+ _5 l4 y" a  r! Z, n2 q  z3 X) V                int t=tmp;
. @( [8 O2 P( {1 q6 }                while(q&&tag[tmp]!=0)
, i& Y* T0 x3 N+ E                {
& k# D2 N9 `3 D' L                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
! g  F4 y7 A& D1 M; u8 @) H                    //cout<<" 2nd     tmp="<<tmp<<endl;
" o+ Z- V( }' F: y+ Q$ V) ]                    q=NextArc(t,q);
                }
                if(tag[tmp]==0)
                    s.push(t);
- ?, z: o  x6 x7 P5 h$ B                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
# }4 C+ [# d4 @, j; Y# i6 }' j                ///tmp要么等于找到的第一个未访问节点，
9 y/ Y4 B0 O; c; q                ///要么等于与t相连最后一个点（已被访问过）
- M. z9 z+ }1 S! S6 v                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
) P  {- f& Y* s9 P! D: j            }
) ]' B7 u0 C0 k9 w/ N& _, C8 M% ~) D        }
( y( u6 I* J: V: G6 w2 |: T% O4 U. X    }
}
' p" o" c+ E, j//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
5 l0 K0 H+ {' x# k* x; itemplate<class ElemType, class WeightType> int
9 k6 o  r% J& a/ K! Y) EMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
2 |8 q4 ~+ h- S' {( q2 e{
) H5 l4 ]8 n6 r3 {    if(head==pre)
        return -1;
3 h# F( P" \: f$ E: f2 q, N0 l
    MultiAdjListNetworkArc<WeightType> *p;
, `9 O) q- X4 M, X. U# q    p=vexTable[head].firstarc;
' }( X3 H1 B- J* ?3 P* v" W% z6 E    if(pre==-1&&p!=NULL)
) @& \4 r; @3 ?- {( H$ H0 v        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
2 N& o; w0 A: i* J, R1 g3 \+ q    while(p!=NULL)
    {
1 f" ?- [5 }+ r1 {        if(p->adjVex1==head && p->adjVex2!=pre)
% i$ b( l# c* J8 E/ U& @: t            p=p->nextarc1;
3 h, U4 L  J: ?1 }3 z        else if(p->adjVex2==head && p->adjVex1!=pre)
0 U! ]- y3 F) ^0 A; c; E            p=p->nextarc2;
7 q/ L+ w' K- V! W        else if(p->adjVex1==head && p->adjVex2==pre)
$ {) z( q( m6 Y% }3 w        {
            p=p->nextarc1;
4 W% J9 K6 r# R- Z+ X            break;
: K% T# @! l6 H( b8 w- T1 F        }
* Z4 t8 B  q3 A+ |( p+ o        else if(p->adjVex2==head && p->adjVex1==pre)
  }  I- l7 `4 M8 T        {
& ?- G' v) J1 F) r" E# e            p=p->nextarc2;
3 R  t0 e6 G+ B$ y6 Q            break;
        }
    }
    if(p!=NULL)
    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
    else
6 `5 a  P- e! _        return -1;
}
* g9 n3 c' [! v) O8 o" K

template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
: v: x9 _4 G- _4 \5 \: U{
5 E  x, @) O4 Z; f    stack<int> s;
2 Z- S$ H6 S" b5 P    int p,cur,pre;
& m2 s: ?& [7 @" Z: t1 e% ~    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化
' B' l6 p- |: S; Y9 A
) ?' P6 r9 l* }) e    for(int i=0; i<vexNum; i++)
. @) E) v5 Q$ T2 P    {
! L3 |  ^) I7 d        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
8 \8 X3 C, A8 l( ~7 X; m% W2 ~            while(tag[cur]==0)
7 |4 e5 i; B9 e0 S% n0 Q/ o5 F1 ]            {
                cout<<vexTable[cur].data<<"  ";
9 V1 Q8 d9 X1 n, d0 z: J                s.push(cur);
                tag[cur]=1;
( \; ?  h4 a! g9 E               //初次访问，标记入栈

2 s/ s- t) T  f3 {: t& K               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
! [2 x. H* [" e9 J1 g6 ~0 d               {
  |8 r# {7 D! k1 S  j                   pre=cur;s.pop();
                   break;
               }
               else
% K4 ?( w' ]8 Q$ j( B4 d. b$ k               {
% m( y: J/ H( e                   pre=cur;
3 ^* \' h( i/ u1 c; i) d6 N' d" d1 O                   cur=p;
               }
2 K+ y- U4 O8 s7 _) G: M
0 }' M9 s: E  `+ d" a            }
9 a; u) t0 ]4 `- j5 \9 o$ M            while(!s.empty())
            {
9 d- L3 L- w( H" O8 Y0 h& }: T                cur=s.top();
( U: n8 q1 @2 J# [1 n4 k( x- J                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
                {
                    pre=cur;
' R5 l' h  G; n# |+ _                    cur=p;
3 A; q0 ?2 h* I- h+ @: n* _                    break;
* M1 C7 n6 h! g& j% k                }
                else
                {
3 }! O  v1 _6 W1 ?: U                    pre=s.top();
                    s.pop();
/ ?% K% ?3 d6 G$ ?5 n2 ^                }
8 x8 R6 @# w1 v! O( U, t9 X
            }
% C  U: c, G. o$ f  ]
        }
" }+ ~0 e4 v- m3 ?3 W0 A    }
}
  W4 L) \; }" {, C) D! @template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
    for(int i=0; i<vexNum; i++)
% n5 X8 j6 f' v. u9 g% J! Q        tag=0;
    queue<int> q;
) [* v0 @7 ?" I2 {8 O1 O    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
1 p/ Y  z8 p# }  j0 A    for(int i=0; i<vexNum; i++)
    {
        if(tag==0)
; F4 t* p. i- m% w4 H& a        {
' x+ Q2 n; S2 A0 M8 E3 g  G            tag=1;
            q.push(i);
            cout<<setw(3)<<vexTable.data;
; K' a0 k% I7 [4 j' }3 Q' m' ~5 l. c        }
        while(!q.empty())
        {
% l) P: B: w$ X            tmp=q.front();
            q.pop();
            p=vexTable[tmp].firstarc;
! n! Y7 _$ c# e9 q- s7 O# l8 u- R* N            while(p!=NULL)
4 G' S+ f9 S4 ?0 s- b            {
2 C  S; ]& i% m) z0 m$ I                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
0 I6 J, O% a" \- b& C% D7 U1 \                {
1 e* [; J: `( F                    cout<<setw(3)<<vexTable[t].data;
# X# @" N+ a4 ^5 F' g- F4 P9 J                    tag[t]=1;
                    q.push(t);
                }
. o0 n$ J7 P1 P% [                p=NextArc(tmp,p);
  Z2 C5 T5 F1 n, C. Q, i            }
& {) c) i) \. z/ s& c        }
6 ~- P$ I" T6 a. }( L& a* }    }
5 N* F& {/ i7 `+ D}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
& V$ h3 i( @* T# q" q9 q{
    MultiAdjListNetworkArc<WeightType> *p;
% t! m3 Y9 F3 \( l2 C    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
1 q" u! G5 B1 Q! @* e9 r+ Z    cout << endl;
$ I, }1 a1 |. S( O$ a: T/ x$ y$ ]- F    cout << "无向图有" << arcNum << "条边"<<endl;
5 T  a- C$ d1 t1 M    for (int i = 0; i < vexNum; i++)
    {
" y0 y& p$ O( [1 x" h# m        cout<<"和" << vexTable.data << "有关的边:";
! ?8 K9 p3 n  U; t$ |/ ~        p = vexTable.firstarc;
        while (p != NULL)
0 E* r' E9 j4 Y: p: D  J  \9 g. N        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
" d, Q6 M" n) H2 E5 T! S4 E" P8 h            p=NextArc(i,p);
; j; s* T" p; F6 _        }
( i- ?: l3 W' a' s# }2 v, v        cout << endl;
    }
}


6 z' f0 ?& G) g, e, |4 }邻接多重表与邻接表的对比
0 w* i  T' B+ @9 `
9 F7 ?4 U% j% ~$ E4 |邻接表链接
4 n1 F; {0 v! M% f$ C  z在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
& O0 ?( l' b& ]在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
! w' I2 Z  V# y  g8 h' u+ d————————————————
6 F% o. o8 t, a+ k" e4 K: B8 S版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
$ K5 K2 b4 C+ q6 k# n
: B3 t- x1 B8 m3 R( b8 q* }


————————————————
5 k) {. @( i! e9 r; c9 @! }版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
3 _3 i9 O' p# V3 P- H
7 C( U% g) _3 M