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

杨利霞

图的存储结构——邻接多重表（多重邻接表）的实现
# `& g- ^  b8 q, X) c0 m, t7.2 图的存储结构
/ ^5 u+ N) T) I- P
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
7 |1 _( M# v" g2 Y, v) K( T8 ?: Z邻接多重表的类定义
邻接多重表的顶点结点类模板
' h) E0 x! {, U4 Z$ }邻接多重表的边结点类模板
% |. Q4 }- L/ U邻接多重表的类模板
3 I; l# P7 F7 t. Y邻接多重表与邻接表的对比
8 B+ A8 m; b0 v/ U  a7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
; y4 `6 f0 O9 l5 ]
4 x" a, x0 {4 t5 c. m% y在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义
  ?) P( G4 ]# x" _! I9 K, W
: h! m7 G5 O6 O+ u: p7 l邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
/ S6 K+ B. J) I/ Pfirstarc域是链接指针，指向第一条依附于该顶点的边。
( s* V' d! d" A  ?: B所有的顶点结点组成一个顺序表。

+ t1 @$ R4 n) n" s$ v* L
template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
2 r5 C. a0 ?7 c4 f  l6 T{
3 D9 R/ R9 Y) J7 S7 l2 ]; d2 G; [/ rpublic:
        ElemType data;
$ r( ~, F9 F4 d6 x4 v  i& m% y0 ]        MultiAdjListNetworkArc<WeightType> *firstarc;

        MultiAdjListNetworkVex()
8 J3 g. z6 Z: ]  q, x2 Y% c        {
                firstarc = NULL;
        }
; x. \' M$ N+ g" X  y  w! x        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
1 Z8 h) x# b4 O. a1 l        {
                data = val;
3 B! m0 [4 q( n/ D; K                firstarc = adj;
9 A2 [. _2 Z2 n( I& a* g$ `        }
! d. W0 B4 R% n! E# Z" ?- Z1 U};
. m( w+ V; E" R, o6 z
邻接多重表的边结点类模板

( z8 I, J4 S6 z. X, \$ j- U在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
& G8 s* F0 `* X' u7 V4 n3 B/ \$ M8 Ctag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
& F8 J- h6 I$ t6 ]: Znextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
; s1 ]1 k, B6 P7 [  h5 v0 j& |nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。

8 O) P% _3 i& X/ q5 r0 B# j
template <class WeightType>
8 j. u0 L! b# T7 l- Rclass MultiAdjListNetworkArc
{
& T$ ~& t8 d! p2 ]public:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
6 @' D2 R+ i% M, w0 L  y7 \7 ]        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
) M$ U. ?- N! @4 ?: C        MultiAdjListNetworkArc<WeightType>* nextarc2;

        MultiAdjListNetworkArc()
        {
2 I$ R1 \' Z! z* u) g3 f                adjVex1= -1;
                adjVex2= -1;
) w/ i6 ~8 W' [, D" \+ F        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
, `5 x& L* ~. \# P7 e. o7 W                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
- V& p% b5 ]. s                nextarc1 = next1;   nextarc2=next2;
3 _: C/ v: {; s" Y7 v. a) Q  n                mark = 0;           //0表示未被搜索，1表示被搜索过
$ C# [, {2 `2 }        }

邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
$ B! b, m" T/ F$ _+ w. X% o{
protected:
* k7 V6 `. l! A0 D* I    int vexNum, vexMaxNum, arcNum;
3 R% b* i, |8 ^    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
    WeightType infinity;
; O$ O( \: r8 B, `
public:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
3 c( m% ?* _+ d3 ~, p4 o
* o7 }5 _$ S& Y    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    void Clear();
, l4 j' Z; ?; f5 \, z    bool IsEmpty()
    {
1 f9 X5 H: X( F4 U        return vexNum == 0;
8 f0 O9 ^- H/ J/ ?, k# t* \    }
' b" T2 ]  B" o1 T$ l    int GetArcNum()const
    {
" \$ a& `# Y' t$ P0 a" L- a- g        return arcNum;
/ L$ c! E1 [0 m( u+ H    }
! @& g: u/ r4 c5 a4 ~2 Z    int GetvexNum()const
    {
( p: l4 I$ b9 T& ]( u8 }- M        return vexNum;
    }


    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
- o5 R( `, @" |) F    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
  f3 l3 s( V& a9 B    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

    void InsertVex(const ElemType& d);
5 M5 L8 ^% a3 Q* ?; _8 [$ {! [! s    void InsertArc(int v1, int v2, WeightType w);
; O5 {& S+ O( U" V1 m8 S9 s3 v
    void DeleteVex(const ElemType& d);
/ N5 Q5 f# W. f) `5 ^6 G    void DeleteArc(int v1, int v2);
# Q7 Q$ G  C9 N( p, {1 Y
& ~- s  E3 M! v$ F7 n4 [$ f% {# B    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
* @2 H& ~8 V7 m9 V1 J- e  N% H    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
; C8 Q7 \8 d5 {3 Q, r
0 F9 p2 G* b! t; D1 N    ///深度优先遍历
    void DFS1(const int v);
4 o3 D9 G6 ]7 g7 {- }# R    void DFS1Traverse();
4 p& m/ |# Q( q    void DFS2();
5 T+ J/ w  L5 N% G* g* f, Q
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
& `  c* \0 n5 \0 O; u' F* ]* {1 S    void DFS3();
: _  }9 ?9 n& Q% \  c
    void BFS();
5 W- {4 g  S) H    void Show();
};

" b9 r- C- r' U. j2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。
; q1 ]7 J( H! C" I$ M, x% R3 A8 z, A
#include <stack>
#include <queue>
7 D* q. P% U8 y8 d5 l
template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
1 B- m$ N* Q" k* J! q9 r' O4 Q    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
' {+ _- o6 Z) H! @& F6 m- T    for (int v = 0; v < vexNum; v++)
8 U+ F8 T) N2 l5 P( S" a: d    {
        tag[v] = 0;
        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
    }
6 k9 b, _' @! o* y6 m6 u}
& _9 r, _# X8 U# ~% s+ S8 L$ r& B& Ltemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
" H+ s( F% ]" ]! y  n    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
3 P. S- _  Y( [9 e* F- K1 p    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
. k& x& j4 y8 Y+ _7 k{
9 e1 h' `. ^; D( g8 c8 u1 {    if (v < 0 || v >= vexNum)
, w) b* p. }- w/ D0 B% C( x: T1 d        throw Error("v不合法！");
: A  P+ {" y$ P    if (vexTable[v].firstarc == NULL)
9 \. |' ?( ?) Q/ u7 o7 ]        return -1;
5 u! K% ?7 s: T' _    else
        return vexTable[v].firstarc->adjVex1;
}

template<class ElemType, class WeightType>
$ i) i; n# J& a( O, {7 P; rint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
* ]/ D0 t- `$ a9 c3 {' l{
' W: o- r: j7 F& d2 ^3 x  A6 J    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
5 [5 `# q2 X7 j' w) j$ T3 R        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
$ {$ X) A( y2 ^' x' b# _  K        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
! @0 S$ C9 w+ B1 p2 f    if (p == NULL || p->nextarc == NULL)
" i' [! e  u. V/ p6 V        return -1;  //不存在下一个邻接点
! M/ I2 ]3 t! t  j& @/ n  V    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
' ~1 J' ~3 \. q% L% P1 v; L4 v    else
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
9 q  i  P. p1 e8 K8 ]}
/ L' w' U  r6 ]* A" ytemplate<class ElemType, class WeightType>
2 k# X) f# B, c/ J' X1 _7 }$ Hvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
    if (IsEmpty()) return;
    int n = vexNum;
+ |7 x0 X# }3 B    for (int u = 0; u < n ; u++)
7 H% h% g) [  E) m4 W6 u        DeleteVex(vexTable[0].data);
    return;
. G9 |( |) L( n: G: }& d}
) C1 [/ T! V8 D2 n# V+ c+ F% p5 ztemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
" Q# [( @0 N; Q' _" F8 b3 T  t& M    Clear();
}
template<class ElemType, class WeightType>
! s6 b" v8 a3 u/ S5 \$ O9 C8 b" YMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
3 j2 L/ z' W( C2 x3 D  I{
    vexMaxNum = copy.vexMaxNum;
7 f( L2 k4 t3 i6 H9 K. l2 k! p: A0 s    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
# ?# f3 D/ P" o" k2 v    arcNum = 0;
    infinity = copy.infinity;
/ P' \: V- d6 R5 P/ R( E8 ~    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
0 h! P+ o. T8 m    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
: v/ ]' Z; E. }, f, t: |; e+ `" Z* L    MultiAdjListNetworkArc<WeightType>* p;
! g* G# d8 Y7 G& l
    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
  ?7 k# d, l/ y0 f" |$ K) R        while (p != NULL)
2 a8 R# \; E, q! _) Y/ z        {
  o2 U% g1 H. L# N# \            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
9 v& n5 e3 t3 ]" T  N' G        }
. `+ J  v+ u- G    }
7 J! u, X8 x% d}
, U4 q7 d7 R. N/ d2 Ptemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
    if (this == &copy) return *this;
    Clear();
- p. I6 Q7 A" @2 l# x( b( I6 P    vexMaxNum = copy.vexMaxNum;
% a8 Q7 U' P2 p/ f    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
: n! ]) d4 h) |* j4 w    infinity = copy.infinity;
    tag = new int[vexMaxNum];
" ~5 Q0 W: l6 B: J( S! e+ A
5 M% i) n& H2 c( Z    for (int v = 0; v < vexNum; v++)
    {
% z$ ]$ G2 G* `) W% J7 N+ U        tag[v] = 0;
$ e4 \* e& A3 w1 b+ Z- k( D3 W6 G        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
# {' ?) n. t5 w' p    }
# n: X  E; e, }  W! H+ Z/ W    MultiAdjListNetworkArc<WeightType>* p;
1 a) L/ E  Y  `/ N) @! ^
( S6 |, m2 F  s    for (int u = 0; u < vexNum; u++)
% q( J1 O- ^( v% |" e    {
6 j+ p( C7 T  f* t/ T% c        p = copy.vexTable.firstarc;
3 U, c% K7 u& }$ o& ~( V        while (p != NULL)
        {
3 }3 e4 c: F! [            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
    }
    return *this;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
5 {0 O/ G  a9 V, S  W{
' n' ^1 q6 E: q  q    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
! p  n- j; W% t0 u        return p->nextarc1;
4 w. d* N8 p$ R2 a    else
8 n+ j7 F4 p9 S+ o( d- s8 f        return p->nextarc2;
}
9 v+ N* ^% ^6 x: Mtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
! B/ m$ m0 F: c8 Q% e1 e- I8 t5 VMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
. I0 Y$ I7 p3 F3 E, n{
    if(p==NULL)return NULL;
2 L3 Z4 p; U, E( g# o    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
4 o' t# R3 U5 s2 O# l* u) s1 w    if(q==p)
. L* s8 C% F! V) z0 e; a        return NULL;
    while(q)
- V- t7 N, I) T6 ^$ M6 E/ Q    {
. K  s" T& \; v- p4 ]8 {& D' W        if(q->nextarc1==p ||q->nextarc2==p)
            break;
" W2 o1 \: Y$ _  x- j. w        q=NextArc(v1,q);
    }
    return q;
}
template<class ElemType, class WeightType>
6 o! N! r$ h/ \8 @/ \# Hvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
+ k9 x" R  d+ W9 O& K" z    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
. q, h( _& p8 Z3 w+ R$ d    vexNum++;
}
( r, K5 P. L; z; N0 z) ]template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
! T& N4 t$ c8 b3 b% Y1 L* a3 ~& b{
" z3 u5 b7 V* Q* f2 x) R& q/ m; ^    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
0 ~) h6 D' c" ?5 Y9 ?' o        throw Error("v1不合法！");
& }, l: a  |/ l; [) D    if (v2 < 0 || v2 >= vexNum)
1 U' Q4 M) I: x  U1 S) f$ i        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");
/ R9 s2 y3 g9 e& k1 C

( @& g3 M& }+ s' I( L1 ~    p = vexTable[v1].firstarc;
    while(p)
    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
/ X! k2 F) \, @3 v% F) M! O+ u2 l4 Y        {
            if(p->weight!=w)
9 V5 t( }& A6 j& S/ G2 q                p->weight=w;
            return;
        }

        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
6 y8 z/ b7 v$ q1 ^/ u2 G    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
4 a  J6 \. j$ F. T    vexTable[v2].firstarc =vexTable[v1].firstarc;
    arcNum++;
}
6 G; L9 ~+ H/ v/ Q6 B
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
( m( ^0 m2 Y  ~" d{

    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
, b; i( ~9 O3 f6 I    if (v1 < 0 || v1 >= vexNum)
, S) v  e, C1 j* A        throw Error("v1不合法！");
9 X1 t3 E9 X) X$ u    if (v2 < 0 || v2 >= vexNum)
% R; F# S8 o5 \. |        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");

    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
        q = p;
        p = NextArc(v1,p);
& M8 Q# l1 l$ z8 x    }//找到要删除的边结点p及其前一结点q

2 v' W/ M- u! `- K    if (p != NULL)//找到v1-v2的边
    {
9 U4 W% b. D- @: O% b1 n        r=LastArc(v2,p);
        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
* |* M; Q% l- z; l% `            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
5 H; Z8 F) x2 w* @5 t2 G' c* y7 m        else//不是第一条边
) s3 \& g  @+ s. K& X- ^6 c        {
5 `8 S) R5 ~; O* w4 O- w$ Q0 k0 E            if(q->adjVex1==v1)
' Z) ~- h5 z: w) a+ `" `! l8 f                q->nextarc1 = NextArc(v1,p);
            else
! C: h& w! H; o) g* e' y                q->nextarc2=NextArc(v1,p);

        }
        if(r==NULL)
            if(p->adjVex2==v2)
3 |, d; ?" S4 l6 O0 H                vexTable[v2].firstarc = p->nextarc2;
( o% i! v, Y& u2 r# i            else vexTable[v2].firstarc=p->nextarc1;
% ~2 n  _/ @' e& J+ x        else
        {
            if(r->adjVex2==v2)
& F3 O0 e7 N  {& A! y                r->nextarc2 = NextArc(v2,p);
            else
                r->nextarc1=NextArc(v2,p);
        }
. C7 a# j2 L% j; ~6 A6 |! t        delete p;
" T7 r; c2 Y! X& K3 D. {0 Q        arcNum--;
; u* V9 E3 x9 E2 w8 Y, k" S! K    }

2 E  O. [; R0 Y}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
    if(v==vexNum)
3 v3 b. N9 {, t, f/ Q5 [7 X% t        throw Error("图中不存在要删除的顶点！");

  _! G8 |: u' r. V- q" u    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
! I* Y" F# v/ D+ X" L        {
            DeleteArc(u, v);
        }
4 N5 z+ p* s7 u: |# u1 E* `# ~    vexTable[v].firstarc=NULL;
/ \4 Q# w% d( L9 G4 Z
! _8 V4 W6 Y& V  O* ?& n% D    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
/ d, x' O2 a6 f/ f8 r. [& r    vexTable[vexNum].firstarc = NULL;
) x2 K" K' n; g' K: b$ [) _! g. }+ U    tag[v] = tag[vexNum];
, V& g- l3 {' A9 g3 M: h- V+ R    //原来与最后一个顶点相连的边改为与v相连
8 e$ t* P! r8 U" {0 [    for (int u = 0; u < vexNum; u++)
( e4 u5 L( y: \' k1 h; q3 }    {
        if (u != v)
* v$ y7 l0 H& J: C! F        {
. O% y: i$ A3 t8 q            p = vexTable.firstarc;
" K6 H+ X0 o# b: z+ V            while (p)
            {
4 |3 K. b% G' K: b                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
                p = NextArc(u,p);
            }
  G" L2 l7 j4 E        }
# ~# n* V$ G. e4 y% P    }
* E/ C) l6 _5 Q9 v6 x}
///深度优先遍历
% b' n4 z  v+ z2 H+ Q- atemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
    tag[v]=1;
3 j0 {* A' }- a6 O& U    cout<<setw(3)<<vexTable[v].data;
, y/ \) Q5 @% s7 O- g    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
    while(p)
  ^9 [9 C3 _7 e$ j/ {8 Y$ p( F$ z+ a5 D    {
        if(tag[p->adjVex1]==0)
  X+ l( A7 O6 t* ^) |& r            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
7 z$ C, b5 g+ U" \' r            DFS1(p->adjVex2);
        p=NextArc(v,p);
+ e  m7 U" Z$ }! H1 t3 g3 \- E    }
  n% o3 r9 C' f0 [}
& Y3 r( f- \" R+ }% ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
' t# m4 t# _1 t3 Q" C% E3 H1 d5 D{
    for(int i=0; i<vexNum; i++)
% d; o! ~, K; Z5 p1 f        tag=0;
    for(int v=0; v<vexNum; v++)
    {
2 ]1 N7 g6 @* ?        if(tag[v]==0)
' R7 h. e, C3 F" i1 V5 d            DFS1(v);
2 w1 a! c! c( R' a    }
1 I) z9 E/ j1 [" e! S" k5 t}
5 T6 W0 g) ~+ H* m/ wtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
8 y4 _( B8 l4 m{
# [3 [3 @; o2 o( B: e    stack<int> s;
3 k, o5 B$ W4 |& ?/ W* _+ z* ~    int tmp;
5 R! E( R  O/ e4 y4 \7 [  w, T    MultiAdjListNetworkArc<WeightType> *p,*q;
+ d0 \: R: g- b9 \* F( X6 Z7 |    for(int i=0; i<vexNum; i++)
        tag=0;
' I% a: s- F, P+ i    for(int i=0; i<vexNum; i++)
3 S" A8 a4 h" \7 }: M1 f    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
- U" y7 s, h$ P# V+ E8 f- U3 _. d        {
            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
+ t0 Y( [6 e5 ?4 r3 H% d1 e4 E# m6 F                s.push(tmp);
# i, Y6 y8 E- h1 V+ f; I                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;
' q; P0 ?2 u/ O& b) h            }
            if(!s.empty())
            {
                tmp=s.top();
                s.pop();
+ i  v$ H9 }' @4 a- [3 \                q=vexTable[tmp].firstarc;
/ O: ]# o6 q, ~; u7 Q: T3 r                int t=tmp;
                while(q&&tag[tmp]!=0)
1 B. V  A/ ]7 L# i                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
4 s' n5 J, {1 j! d                }
. \+ v3 n# i% S# l                if(tag[tmp]==0)
. ?# {+ D0 T. X, g; l, ~/ t                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
( i9 w! T: ~3 p                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
( b. A% D! j' p8 c) q5 G                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
3 O  O1 X. R/ ?        }
    }
}
# B9 y) n/ I0 G$ s6 ?! I9 t* d//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
2 b! ^" d3 P; ]$ SMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
' H0 W& o1 ]0 y; s0 @{
    if(head==pre)
* e. l. B& C, b, z        return -1;
8 G3 P) ~9 j: r4 i1 N! c) }4 D
, G$ o' p) r4 x5 I" l8 N    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
0 E' s6 V6 `0 D& L3 Q8 ~( S        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
' e  s7 Y) L" {+ t+ ]; m8 T    while(p!=NULL)
    {
1 c# \, f; `! N        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
, S! \3 t) K6 Y: `' g$ c            p=p->nextarc2;
: I3 [3 @7 h6 }! [6 k* \3 T        else if(p->adjVex1==head && p->adjVex2==pre)
        {
            p=p->nextarc1;
* p+ n+ J6 V$ a( L. Y  m            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
! _% U% ~2 }- V) d        {
            p=p->nextarc2;
            break;
        }
  q. k* I6 n7 R8 V    }
" v) [" v! m( Z& W# a9 M, h    if(p!=NULL)
    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
. J6 w/ b5 G- X! C3 V8 N    }
    else
, x; Z6 ]2 n' E7 [/ d( h, N        return -1;
}

5 ^; K  r. i; W$ F5 D
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
" I3 u6 ?9 A. W/ i# M) l6 w    stack<int> s;
    int p,cur,pre;
2 a3 _! m3 i4 l3 n    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化

    for(int i=0; i<vexNum; i++)
( m1 h7 ^, x. Y3 b1 B/ @' m5 G    {
        cur=i;pre=-1;
; Z7 p% W* }+ ]  b$ W        while(tag[cur]==0||!s.empty())
2 K9 ~; t8 R  P* Z; ~        {
; R8 K* I" W( v( f" v/ v            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
3 y) s, j2 f, e# y+ m2 \                s.push(cur);
) B- Y/ |& h; ~1 h3 M- ~                tag[cur]=1;
5 P* d* c3 P7 k& s9 s               //初次访问，标记入栈

( P. g6 M2 Y: y. l. u+ m               p=GetAdjVex(cur,pre);//p是cur的连通顶点
2 C; i! e; D. J. r4 C1 c7 N& l* z; C. H               if(p==-1)
               {
8 B) `8 n: D- ?. b. A7 s                   pre=cur;s.pop();
                   break;
               }
               else
               {
                   pre=cur;
9 ~1 y! `" N) V3 S2 x                   cur=p;
7 T+ Q& J) q# X6 N1 R               }

            }
$ p. h& T- y4 l2 c: @            while(!s.empty())
% g0 g7 F* u( y; x$ r3 K, d            {
                cur=s.top();
( G4 ^" y6 q4 O4 t+ K, Y+ d                p=GetAdjVex(cur,pre);
" j. w1 S" e; ^' ^; S6 z' Q) j                if(tag[p]==0)
# Q) |  r- R# }! W7 f- I$ g                {
                    pre=cur;
' J8 {$ i9 N: S                    cur=p;
* z* R1 W& m% r8 x) d                    break;
% E8 V+ n  h. d& T; K/ C8 ~, j                }
4 m- L, |* ~: c# a8 H4 ]                else
                {
                    pre=s.top();
4 O. z1 D. Y. z" f3 B8 [7 i% F                    s.pop();
                }

            }

7 q( s' k/ L, h7 {        }
7 d' X0 b: d" j    }
# W* c! f: y5 B: D, `5 x}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
    for(int i=0; i<vexNum; i++)
! K8 s* L' Q- I% X1 v$ H1 N        tag=0;
: T3 A; L5 L9 ~- i9 `2 H; O- E7 c- ~1 E    queue<int> q;
. G6 }( A$ k* y5 z0 q    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
    {
2 n! l  O% X* T$ B$ z% U1 A% r        if(tag==0)
3 q) U1 d* V. s4 X$ P        {
            tag=1;
            q.push(i);
( f$ S3 x0 P1 Q0 w4 k9 M            cout<<setw(3)<<vexTable.data;
        }
* ?6 G/ C' h$ f5 m" d8 V% [+ Y        while(!q.empty())
        {
            tmp=q.front();
9 q, G7 T; n0 e' L8 j            q.pop();
4 t; `  {4 R+ Q' Z& E9 q            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
4 H8 ^( c3 h% K, ?8 ^, y" \9 T                if(tag[t]==0)
$ b. W, e" T" c3 X6 [" S                {
                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
* {9 w9 }. J5 B8 O                    q.push(t);
, W2 F0 o% q3 `+ {- U                }
                p=NextArc(tmp,p);
            }
: p' W  H0 B& I! Q3 r        }
    }
5 q3 E3 d8 Q5 a: ^! h, m- F}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
8 A5 a! }$ \# ~4 s: o! _2 Q" [    MultiAdjListNetworkArc<WeightType> *p;
1 E9 y. Y9 w' Q+ U3 b8 ~/ K    cout << "无向图有" << vexNum << "个点，分别为:";
7 C! `6 w: V/ l9 X! _) A4 o    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
    {
6 y/ O8 V0 D2 G6 ~* a        cout<<"和" << vexTable.data << "有关的边:";
. D- T, n$ c3 s  w+ K        p = vexTable.firstarc;
, c2 h3 [+ H) \  u        while (p != NULL)
- m$ y) d% j, Z  q6 |4 j        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
+ M" Q7 }! W" x6 F- o7 A3 c            p=NextArc(i,p);
- Q( k0 Q9 i4 G% y        }
        cout << endl;
2 g5 j2 m# h( C& |& D2 z& I, c% \9 \$ d    }
}

, ]2 k0 |/ g. m6 M$ E6 v1 R
邻接多重表与邻接表的对比
- P3 H4 W0 }8 S0 J, O/ e  D1 j. i
邻接表链接
$ {2 Y9 ~) D- b5 F, d1 s5 [在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
( B& R4 F- @2 j( o在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
" H& T7 v7 H' |  S) P————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; h; h& ?; J4 q* @3 b" ]原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958

5 `& y' `' I- D0 }; d+ {$ b
. |8 w  j# Q' ?$ O$ |% |
, z/ H* }, @  U; u* R! B
1 q" ~4 E, M* k* A————————————————
8 @" K- W( l, F- y! t7 l版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% `4 \6 ~: x, b; i7 m+ |/ T* M原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
$ A, t! B/ s- U) [3 P# a+ S
% C* t: B* v. N0 y
& S4 s$ |9 S3 ~+ B1 X