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

杨利霞

$ @. m; ]9 k; J- ~$ [3 A* w图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
) R  z" t- M/ M; U" e# p/ |% d- \邻接多重表的类定义
邻接多重表的顶点结点类模板
6 c$ k8 [3 ?8 a5 u5 d/ y邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

/ n" W' a% y- P% w4 n1 |在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

9 u3 E% l- v, t. r) d/ C1 X& G邻接多重表的类定义

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

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

- x9 A0 e5 d2 v2 r6 {. W
template <class ElemType ,class WeightType>
2 E# ]* o5 k* o! P1 ]  Fclass MultiAdjListNetworkVex
: m* c- t. `% o+ `{
public:
  [2 t- v% V. u7 m9 V# H& ]        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;
4 u3 L* p2 Q. A  F1 y6 r
7 @$ Y7 y" ]3 ]: n        MultiAdjListNetworkVex()
        {
! i1 U7 }( l* m% w2 U2 f/ Q% p                firstarc = NULL;
1 V$ E0 Z+ }7 m) c) ]5 k        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
3 B2 a' K3 S7 t7 ?) l3 r/ `        {
7 t/ b" g4 w1 S9 c. {  A8 A                data = val;
                firstarc = adj;
        }
& U6 z# s9 R0 n# V+ t};

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

. n# [' Z; E: K在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
) b* F! q2 a! p: e' Qtag是标记域，标记该边是否被处理或被搜索过；
% U; _/ M$ k% \  P; o- [7 hweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
0 u, |* m& c. x" h$ p. T$ J- r  O) B0 }nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
: X2 h9 z: A" t' A* u. y% anextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。


' a  O# b% ?" m) A  ^template <class WeightType>
/ s+ r$ @8 Q4 Y1 W) iclass MultiAdjListNetworkArc
{
public:
3 b0 R; M# w7 T! J; ~  q4 O8 t    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
$ Q4 {# i5 t3 m$ A& o  [! u: H        int adjVex1;                                    //边的一个顶点
, ~7 \# G. n9 \        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
& b) k* |9 M0 q# g) W        int adjVex2;
: I! U1 i- k0 [7 g1 p( w4 `, J* Q        MultiAdjListNetworkArc<WeightType>* nextarc2;

        MultiAdjListNetworkArc()
        {
; ]1 c- V1 u9 ?# \8 n                adjVex1= -1;
2 j" X3 {0 |6 i2 i; i8 d                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
; h( R8 w1 \% C/ s+ l                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
. t8 t& z# \7 G: Q                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
2 i* R" V) U% L) L- ^        }
/ R( L% P  L7 ?  r  F& N
邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
* S: }/ W! e& s3 y: j7 T, w{
1 ^# l- {8 P. ~+ S$ ~0 hprotected:
    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
. M; d+ C  k: C9 [    WeightType infinity;
( J' f( w' ?1 x1 e8 F
/ n) V% A0 i7 Ipublic:
3 F% z4 j5 N8 W9 O  h    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
! T* p1 f/ N' j' [# e+ }- ~
    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
: U$ X; n, y+ `' `* S) Z9 G, @
    void Clear();
    bool IsEmpty()
    {
, T( }4 a$ P, N7 B) d. U        return vexNum == 0;
( G% c) |* P7 \# O! h# q    }
) ^- V. p7 n, [1 n    int GetArcNum()const
# h, `$ i7 y3 p- g! f' v    {
        return arcNum;
6 ~! W( ?* A" H    }
    int GetvexNum()const
    {
; E0 Z( m+ J  L2 z2 @+ ~3 _        return vexNum;
/ [9 t4 }+ f  V2 X    }
/ c5 T% R/ y6 A* U& y& d+ U3 g

. V' g, g  F1 d; d6 a# F! h2 y, F! g; Z0 x    int FirstAdjVex(int v)const;
/ i2 a) ^2 o7 F    int NextAdjVex(int v1, int v2)const;
2 n' p& ], ^* x& }# [$ f" X    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

    void InsertVex(const ElemType& d);
" A. G* L9 g$ x+ Z' ]6 u! _1 |; w0 a    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
/ T" o" x& d: e8 [    void DeleteArc(int v1, int v2);
3 a' G" {; J4 }* i2 e
  |1 \8 u5 ^& r1 A+ E4 j+ K8 O# u    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
, C1 m- }5 `4 t0 B" t
" y' }- M: V. S8 N    ///深度优先遍历
    void DFS1(const int v);
( j% ~6 ~( G5 _+ i: l    void DFS1Traverse();
    void DFS2();

    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
' I7 ]  j+ r5 F3 N* c    void DFS3();

3 M' J) s5 ]$ z4 \5 l    void BFS();
8 t+ u: C- M# n8 u4 V4 {; d    void Show();
};

2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。
1 t5 Q) l+ n/ B( \5 }1 F! Y
* f7 ^- s2 Q8 u8 W1 x; K) r, I+ ]#include <stack>
9 I2 O8 d3 i0 u9 Q# \; \3 ]4 b#include <queue>

6 ?: w3 `4 u! _5 ]template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
    if(vertexMaxNum < 0)
/ G# x* ^; `# |4 `6 x* U: v        throw Error("允许的顶点最大数目不能为负！");
& [( k: q1 w+ Z# o0 p    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
! e, x7 Q3 T0 R* j, j: G! X5 h) T    vexNum = vertexNum;
! P# v8 f9 t5 C$ X! f4 O    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
( l$ Z; E" c9 \+ s: b) G* @    for (int v = 0; v < vexNum; v++)
    {
" X8 ~. B( h, R+ K& M9 s; L        tag[v] = 0;
/ t) b/ X% u. A$ {5 c        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
: u3 ]$ A" L9 }6 D7 _9 ]' X9 h3 d    }
}
# R8 m% W& V# D0 d7 V. S# ltemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
& Y) R. K6 Q% u3 `; X2 `; b% \4 ^{
5 Q3 N5 b+ z6 V& C3 |    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
! u, u  {! q# Y$ `7 l& B& e    vexMaxNum = vertexMaxNum;
    arcNum = 0;
6 M: V3 h8 R2 {. X; o" i6 C  a    infinity = infinit;
. u5 J6 @6 }- k" E' `    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
% o0 R' C; l+ K3 G/ vtemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
1 Y, ]  p: w. p0 v1 r+ Z8 C    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
, ]) ~  T. k' F: F        return -1;
    else
( x0 i/ b3 A' f        return vexTable[v].firstarc->adjVex1;
8 I3 P  ]1 v) {) I8 j) p; |7 u. B$ T; `}

template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
$ j# g, l' T' }6 {9 h& p' v    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
4 W7 c8 v5 _6 X' R        throw Error("v2不合法！");
! x# X' {# o/ @    if (v1 == v2)
        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
# V; c. [/ a: E; ~}
template<class ElemType, class WeightType>
, Q2 z: K9 H* B, F1 Avoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
: q" p: P0 a$ {" X. {    if (IsEmpty()) return;
6 P! Q( O& \- C$ w" h0 ?& I9 e9 V    int n = vexNum;
    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
2 q; c  H- [0 Z/ Z    return;
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
$ W7 D- Y0 [9 {7 ]}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
  B' z9 N- y! H8 s9 U" _- _: d{
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
: C& v% W  m; W' i: h) ~, \, P    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
6 _5 o: }8 v0 g: e+ Y# x* p, n    arcNum = 0;
0 s. J5 }' r* }4 P0 `. w! P1 J    infinity = copy.infinity;
- m5 L& Q& j: i$ ]: i* K    tag = new int[vexMaxNum];
5 }* |4 B: q0 M7 L; m! l
    for (int v = 0; v < vexNum; v++)
" c2 T7 V3 I. B    {
        tag[v] = 0;
' s% o. S- V8 M' _2 K        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
: T/ s. D% a1 f5 h2 f' r% T3 ~    }
- `% ?0 v7 K9 U# e    MultiAdjListNetworkArc<WeightType>* p;
! s* l- v1 N+ P
' ^0 L+ m* G/ \. n) J: |    for (int u = 0; u < vexNum; u++)
0 U7 G1 V% b/ @, \2 n    {
        p = copy.vexTable.firstarc;
# j# ^" N& x! S4 x- S# x        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
5 G: F1 [. L# n/ e1 p1 I) w9 E! f            p=NextArc(u,p);
/ H5 `8 Q1 B' A* L, C& n        }
    }
  `6 w. s% L$ D3 x) ~) `9 D  N}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
/ H: S. m: a* T, _9 a, V$ z    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
8 @6 o5 Q9 l% N) ]( d, n; n    arcNum = 0;
    infinity = copy.infinity;
0 j* \9 ?* p( e, o0 i4 V; ]3 S    tag = new int[vexMaxNum];
1 z4 _/ J4 H, c2 A) i& L; P
9 @9 z( R) \4 g& J    for (int v = 0; v < vexNum; v++)
0 V/ F( C* A. p6 D  V" |    {
2 a9 C! b$ H8 x1 ]        tag[v] = 0;
6 c* F, [8 P7 m        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
0 y( [4 K( L) i) \/ T    MultiAdjListNetworkArc<WeightType>* p;
1 G1 S6 J. P9 i+ ~5 h& [, V0 V
& D2 [! Q7 B, `3 x; ~: x8 M: v    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
        while (p != NULL)
1 _1 Y3 [+ _$ N8 s5 R" ~; n        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
' Z4 |: w, P0 f# @, v            p=NextArc(u,p);
        }
# t1 A/ N3 b. z2 F3 t    }
$ a  Y8 o4 y9 o    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)
# P2 Z3 r) ]1 ^& G& j' U        return p->nextarc1;
1 L. P# [; g+ `    else
4 C) C" m) o' R7 g) ?  i        return p->nextarc2;
- Q6 n: E- H$ ^) ]: E' J/ i  l- P}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
- ~* K# z$ {( \1 l/ [5 ?    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
    while(q)
7 J1 k7 |! D. P    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
" R, u9 j' d3 O; Z8 A- A) x: ~        q=NextArc(v1,q);
( Q% d6 W/ D; R3 W* H6 K    }
/ v- [  m2 k8 U5 {' H8 O    return q;
}
template<class ElemType, class WeightType>
% i0 S2 P( D! xvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
0 c: d# I6 K' [7 V: r6 f: h    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
8 h9 K% Q4 ?- t. `6 d    vexNum++;
}
  [" {9 N* |& t2 x+ j: ]template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
1 L+ `- y$ f3 @9 c0 n{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
# ?) l9 J# i; F6 H1 P/ h6 ?        throw Error("v1不合法！");
- U/ u$ @- L7 V$ N$ k2 u8 P    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
7 ~" `% G/ B4 q    if (v1 == v2)
/ V0 O% c- o) o7 R" g        throw Error("v1不能等于v2！");
  q2 n# c+ y5 _. C4 I- Q2 H- a9 ]. b    if (w == infinity)
. M1 p+ M5 L: s; B* l3 V# [2 }4 X" i        throw Error("w不能为无穷大！");
. G5 o9 b8 [3 G5 d/ {( M+ [3 ~

    p = vexTable[v1].firstarc;
2 ?( L; ?4 t! ?, N. S    while(p)
9 i+ t' p; [1 j8 \- H    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
            if(p->weight!=w)
2 [/ w+ j# w- B+ [+ ]. I5 ^                p->weight=w;
1 v' d! Q) ~( B6 l3 o            return;
        }
/ |  M5 v" Q* i% }) x9 V
        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    vexTable[v2].firstarc =vexTable[v1].firstarc;
7 u" Q) c0 N6 x    arcNum++;
8 N* m: B4 O3 q4 w# H/ V& D}
, p" `( `) b1 A. N
template<class ElemType, class WeightType>
& ^; p# `9 B: k& R& Yvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
5 q( c$ d. ~8 J
% I/ Y* t, g, o1 B    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
8 K/ W7 r$ Q+ T. W: v. P2 A    if (v2 < 0 || v2 >= vexNum)
" g4 W" b/ @' P5 R2 b0 E& m; U1 U        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");

    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
6 x/ O9 Z: f, P! C+ @" v$ T+ D& A        q = p;
3 A8 I2 P0 {. J: E+ ?        p = NextArc(v1,p);
    }//找到要删除的边结点p及其前一结点q
3 `( Z0 s6 B! O, A6 b1 k
    if (p != NULL)//找到v1-v2的边
0 K$ v# ^* m$ o  o    {
        r=LastArc(v2,p);
. Z( F# m1 z) p0 R3 r4 H        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
! b$ X, a  H; s8 m$ U. Q. s( {: |            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
5 r' R; X2 T5 n6 h& t# Z$ {        {
& h% V4 \0 A) E  F" j  o            if(q->adjVex1==v1)
% N1 M5 t, R; G  n1 E4 `  X) }                q->nextarc1 = NextArc(v1,p);
' o7 r! w0 E6 _3 A" g/ ^3 Q, ~7 l5 c            else
                q->nextarc2=NextArc(v1,p);
1 {0 d$ d" o! }  @/ u
        }
! ~4 S0 E3 L% Y  X1 v        if(r==NULL)
            if(p->adjVex2==v2)
8 o  E6 a/ T5 `                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
        else
, m+ V/ Q4 S, M. V( A        {
            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
% f; A' S, W% {3 L            else
                r->nextarc1=NextArc(v2,p);
        }
        delete p;
6 u7 p1 k7 c$ v2 B, I6 q        arcNum--;
    }

. @  O1 i& a% c9 ~6 d}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
, _$ X  j+ y2 G9 S( l# _& b' `3 e{
' M) f" p0 b# g    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
, l  ~: t1 f4 {$ [. }0 [7 N    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");

    for (int u = 0; u < vexNum; u++)//删除与d相连的边
) ]( J8 F5 P- _* A        if (u != v)
$ ~. e( m# O8 i4 x" V  ?! h        {
# q+ l( M" l5 s% x! M9 A            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;

  |) d1 C4 A- H3 ~    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
0 Q' w+ S8 Q" M! a) R    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
. B/ [7 \) q% S$ E/ ^6 i6 \9 D% y    tag[v] = tag[vexNum];
  \) E3 W# [! ~# U; C0 l3 {9 e    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
3 d# }1 [/ O7 {& p' i    {
        if (u != v)
        {
! ]9 `% w9 J$ @3 g; E4 y& x2 Z            p = vexTable.firstarc;
5 R  U: n: e" b. @$ O            while (p)
            {
                if (p->adjVex1==vexNum)
. j0 ~( P. ?  `9 E! \8 e) j  J                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
- N$ G1 U1 l8 C7 C# `: ^                    p->adjVex2=v;
4 Z0 {' M2 X' ~3 g                p = NextArc(u,p);
            }
        }
# ?: f1 H: F' X2 b0 n# m    }
}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
7 e4 T2 y4 V0 Y{
    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
% x1 N+ H- a" k6 W3 w- A0 Q: t4 ]    MultiAdjListNetworkArc<WeightType> *p;
; M+ l1 g0 u& T    p=vexTable[v].firstarc;
7 s( G0 a1 S) N( [    while(p)
0 K. ]* d- P4 a6 C8 q: R    {
( I* M  S8 i' R- l- `+ d- {        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
$ u1 T! K- J3 C) b7 h        else if(tag[p->adjVex2]==0)
. y* g; L6 P7 W1 z- I7 v% C( x# ~' z            DFS1(p->adjVex2);
# C4 V2 ?/ l0 [4 {        p=NextArc(v,p);
3 F3 S- N# J# [( `& Y( r    }
0 P# Z* p* `, a4 w* A' E}
* F1 |& H; w* J. O' }template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
8 \6 p! z6 ?8 D' P{
    for(int i=0; i<vexNum; i++)
        tag=0;
: f6 i) p2 ^, k) e* X5 f- {1 a. u    for(int v=0; v<vexNum; v++)
2 S( F6 b8 t# F2 N- V& q. q- @# |    {
        if(tag[v]==0)
            DFS1(v);
    }
) B9 N# o) |4 |5 C7 U}
4 @( U# g% [, Q" X+ g. ]1 f; qtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
" H, C  W! F6 O$ K" t    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
' K; {8 ~( @9 h    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int i=0; i<vexNum; i++)
5 ^% H$ ?7 z: P, D% Y7 ]    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
        {
            p=vexTable[tmp].firstarc;
. s! S- f* @: _- R            while(tag[tmp]==0)
' h2 y$ d" B6 S7 _9 g! _. Y) C            {
0 i; X1 Z& B% O. k                s.push(tmp);
, H' \& a; p: H; b6 w                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;
            }
            if(!s.empty())
  P0 j4 I& e9 A4 ]            {
4 Q5 c) d  c6 W                tmp=s.top();
$ Q- l: C' |& q. }                s.pop();
2 f7 E4 S( x* r9 e) x8 U                q=vexTable[tmp].firstarc;
/ @3 h; A; o# [8 P                int t=tmp;
                while(q&&tag[tmp]!=0)
  p4 @0 _. b, J  j                {
1 z+ r4 K! W. d9 Q5 ?9 a: f                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
+ s( a& M# b3 _# o& G  A                    q=NextArc(t,q);
                }
                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
: f5 e& @+ v2 ^' e8 o                ///tmp要么等于找到的第一个未访问节点，
( ^2 E. S% |9 @7 t! b9 f  z/ [                ///要么等于与t相连最后一个点（已被访问过）
% t* p3 f3 ]$ d                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
" S% r/ J! N( w$ ?4 z; w4 @" S% {4 [    }
7 c  p% t" L6 t$ Z  @( s! \9 t}
- h- L! H, R4 j7 I: a//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
) M8 ?7 l+ o8 G& A: Atemplate<class ElemType, class WeightType> int
, Q# W3 Q; p* p2 r( g/ ~  j# b- CMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
! x2 y7 e$ \* k4 B6 y# n{
    if(head==pre)
        return -1;

    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
7 |9 K. ^! m: J* Q        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
3 L' c- v) @! B/ K( A- D    while(p!=NULL)
/ M  o9 S  x0 ?% D' Q' r$ V0 ^    {
        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
- S8 u: w9 X9 {; A. B5 D            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
        {
5 g: O8 B+ g* Q8 K! m$ b0 T            p=p->nextarc1;
            break;
        }
4 X/ C5 r7 Q8 v        else if(p->adjVex2==head && p->adjVex1==pre)
        {
: o1 C# j* j5 [- e            p=p->nextarc2;
8 f4 r1 |+ u$ R% n3 e; D% d            break;
        }
    }
) b* `3 M1 t  O; Y+ }& {% M) t  Z    if(p!=NULL)
* Q9 r2 {. d! t: p7 b" c+ O    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
, h1 C% {$ X# T) R% j! ~. U6 z    }
    else
$ l3 q4 S9 {/ P5 k        return -1;
}


* ^0 Q$ `8 s3 htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
1 Y) }$ U# U0 Q2 K& E# ^8 T7 b; m) g5 T) G    stack<int> s;
2 q" s7 g( m- @/ F8 S( h7 M' u- ^    int p,cur,pre;
& F. |8 q# C$ B5 q& c0 s2 j    //MultiAdjListNetworkArc<WeightType> *p,*q;
: L# V# f: k& q. @    for(int i=0; i<vexNum; i++) tag=0;//初始化
" L! @2 m# ?& X9 W; w) [0 {
! n8 q3 k' W) R$ P# t" K7 \    for(int i=0; i<vexNum; i++)
    {
        cur=i;pre=-1;
. i2 a* O# G  g# H1 e; e        while(tag[cur]==0||!s.empty())
        {
- l0 v" p* L! b- |: e( l            while(tag[cur]==0)
5 I* |2 A) H& M- m& M            {
                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
7 ?5 @; g; l9 ?                tag[cur]=1;
& ]; ^( M! G8 {- i               //初次访问，标记入栈
. ]) Y  c7 }/ M2 G
               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
& Z$ M- C. L1 o$ I- j: X               {
                   pre=cur;s.pop();
; j5 Y6 O: g# d, N8 G0 I5 S' |                   break;
               }
               else
4 `, E# `3 W8 L9 v8 q- a               {
                   pre=cur;
                   cur=p;
. g, ]  D9 D% w               }
; c% v4 i' ~1 o( q( F
% R5 ?) }. E$ B            }
            while(!s.empty())
3 T' B  Q# d% P2 ^, s2 e            {
% R8 [. c$ a9 H% u5 u% [                cur=s.top();
                p=GetAdjVex(cur,pre);
. v& x& Q2 ~0 Q: [                if(tag[p]==0)
                {
3 W) t% Q7 E" m$ w                    pre=cur;
                    cur=p;
                    break;
                }
                else
5 v4 O4 S+ L- J; l; k  ?                {
                    pre=s.top();
, N6 L# _& `1 F5 ~, B3 U+ B                    s.pop();
                }

1 W  I6 o9 W+ ]3 t            }

        }
    }
+ x. `& P* \: V8 W; K! q/ G! T}
8 Q7 _( ?( y" q3 Z. t1 w0 atemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
* ]0 W( T8 h8 t{
4 P$ z# ]$ Y$ \6 }( v/ Q% ^# x1 P    for(int i=0; i<vexNum; i++)
- a/ ]9 N; d' |        tag=0;
5 @& M6 ?3 b# l$ z3 {' T" `    queue<int> q;
    int tmp,t;
& k9 }" D  M/ ~/ F, H6 X1 I    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
; a4 B' Y% w) g% a' x2 O- ~* g& X    {
# n0 G" T; Z7 \7 `8 q! R' M        if(tag==0)
        {
            tag=1;
            q.push(i);
- q" s( V; h1 T8 y5 S0 {. I            cout<<setw(3)<<vexTable.data;
        }
        while(!q.empty())
+ Y, G+ x/ n# r- k" W$ ~        {
            tmp=q.front();
( w1 G" \' y% |1 L# a5 }            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
- [8 T. N5 U/ s; z; d                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
7 `3 v* i) m  J. A+ O7 w' W# a                if(tag[t]==0)
8 ^) H9 \% W' H6 Q( _% v6 q( y  H                {
& ^# Y) f) z0 U+ i5 Z3 e                    cout<<setw(3)<<vexTable[t].data;
  b: w* {3 X" k/ V0 {8 E+ h& ?! O                    tag[t]=1;
                    q.push(t);
' l, `0 n  z% E: @2 Q1 m                }
8 [  k- a) @1 r" W! f. v. C! @                p=NextArc(tmp,p);
            }
) N* ^' p7 o0 _% B, k        }
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
7 ~  S* f: m2 i# F. e  ?* b4 O{
    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
' P. ]1 T% A' C% p+ M5 P    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
    cout << endl;
: O0 f" F4 p; K# M    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
    {
# h7 ^/ B8 h* |0 U        cout<<"和" << vexTable.data << "有关的边:";
/ \% o4 D0 w* Z* K3 Y  d        p = vexTable.firstarc;
+ h9 d0 v! }5 S        while (p != NULL)
        {
4 \9 x& A2 n0 y            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
; ~; v) S5 x; R3 Q) h; @; ]            p=NextArc(i,p);
        }
: j- z- h% o# j. V) k& n  B7 i        cout << endl;
    }
}

$ Y. r5 r- p  @# B5 [
邻接多重表与邻接表的对比

/ w" M* f9 g+ v, w2 f$ k邻接表链接
/ Z2 \6 o, [* N9 O" V# I' F在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
. V: a/ @! v. K/ z2 ?7 F为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
8 A/ b& p6 w) g6 m* C$ \版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
! C" k$ n$ t! T+ X



" F( F5 [1 ^' ~1 l: W9 J————————————————
+ Q/ @1 `+ \: u# i" s6 x* a4 ^% K$ a$ \版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* o" D2 @% Y1 Q- z  x1 [7 z) a
( ?5 o5 F1 `7 }( U9 w9 e- L  J