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

杨利霞

0 o  K$ X% P- H4 }$ ?! S图的存储结构——邻接多重表（多重邻接表）的实现
/ `0 e7 S2 O6 V4 I; |8 B7.2 图的存储结构
2 \! d( Z/ ]& d: N4 d
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
- {6 \6 \* y7 e% U. p. V邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
* ]; T4 k" C5 N7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
; m! w/ Z/ N% p* Z$ z, V& |
在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

- c' w8 a3 J& G% k; |8 j邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
  k( ~0 S) z1 }+ ~2 k3 U0 X所有的顶点结点组成一个顺序表。

( H! Q! I& m  utemplate <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
" u6 f- m' ?. U5 H1 h{
0 b& C- V9 }# j4 Ypublic:
  V( W7 z2 r$ u0 R        ElemType data;
3 t1 \% o2 r" b- Z        MultiAdjListNetworkArc<WeightType> *firstarc;

8 a# W* s4 A- c        MultiAdjListNetworkVex()
8 _; o+ E! ?1 U. n        {
                firstarc = NULL;
3 n, P6 d+ a- ~# O- f        }
+ d& ?5 R: f. c; ]8 J        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
$ T9 m% H: A9 b4 k- u        {
& V$ F+ S4 u! H1 X1 |. Q# c  S, R                data = val;
                firstarc = adj;
5 q3 [8 C5 ^  g  F        }
};
. \: O9 s" S6 `4 y0 Q6 `9 r
邻接多重表的边结点类模板

: [# H$ ~6 F2 j在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
/ s. }' ^. Q4 o4 R- @7 T+ n8 itag是标记域，标记该边是否被处理或被搜索过；
  a3 I5 ^: C) i5 _2 _# Dweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
, g! _6 l! s5 ]9 J: d' R6 [

template <class WeightType>
class MultiAdjListNetworkArc
{
public:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
6 _( Z8 ~6 S: a; m$ w        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
. O# e* ^  e) z4 c. m        MultiAdjListNetworkArc<WeightType>* nextarc2;
6 o; q, ]$ l, e& g
- l& m4 h! u% n# o4 c% m        MultiAdjListNetworkArc()
6 R( x' y1 o6 [5 H4 m) ^        {
                adjVex1= -1;
                adjVex2= -1;
3 F( E  w  w$ H% {6 V5 B: C& `        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
+ k+ E% E8 e7 \* k        {
: O7 w5 F& W) U5 Q                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
        }
: t! k# ^, m$ C5 m& ?* J% J: c3 K
8 R# j" Q7 k; r: L- Y$ J邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
3 g7 U: l' f& ?3 x{
5 v# F/ m# Z8 }9 \/ Zprotected:
    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
    WeightType infinity;

public:
1 a# c5 r" ~# h  x% \, n# ~) e0 t! X    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

- N3 c4 s+ i% W3 A& i5 K    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

* }& n$ _% b7 g; e' W    void Clear();
9 d) M3 j, L) a" N2 t* r) w! V    bool IsEmpty()
    {
* g8 M4 K+ `; a/ \( n        return vexNum == 0;
! A$ ?0 c4 H, q0 N0 F' n0 c1 F    }
) Y( z  }2 A& @( }6 H    int GetArcNum()const
    {
        return arcNum;
    }
    int GetvexNum()const
    {
; g3 K& Q+ a7 W  a* b9 ^8 e        return vexNum;
    }

& X% H2 Y! ?8 p" j" u& X# A$ {$ d
+ q. w1 k2 s+ ?    int FirstAdjVex(int v)const;
; o5 X/ F4 I, V' |& Z    int NextAdjVex(int v1, int v2)const;
/ O6 K7 A* V3 t! E! A9 ?    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

    void InsertVex(const ElemType& d);
) u0 s9 N/ \! O* _" J% r$ B    void InsertArc(int v1, int v2, WeightType w);
  x! j. n" ?0 @+ x# D
    void DeleteVex(const ElemType& d);
& i1 [! N2 \: d! p0 \* V    void DeleteArc(int v1, int v2);

    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
6 R# H. V1 X/ h. D, g    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

6 @* W  p6 D2 Z* Y9 K/ I    ///深度优先遍历
    void DFS1(const int v);
9 j# r% i. z. Q" ]8 x3 j; x    void DFS1Traverse();
    void DFS2();

+ ?3 [! i7 e) H, {' C$ X    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
& z: ?0 R* l8 @& g1 F9 H    void DFS3();

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

$ H* k' p% p( \2 _2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。
( Q2 Z5 N" l' n" M0 z6 v  k4 i; P7 @
+ N$ {& l: S2 m3 a; d! j#include <stack>
#include <queue>
0 u0 A. m" z2 e' [
template <class ElemType,class WeightType>
. f- B2 g4 e9 [/ }/ N* A* LMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
    if(vertexMaxNum < 0)
1 g4 |6 |  y; |1 `9 L        throw Error("允许的顶点最大数目不能为负！");
% r6 R) h: p# E% j    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
, l% O, m4 g$ E! K" v4 q0 P4 x    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
) N$ K! W1 l' ~" Z$ k# C& N4 \    arcNum = 0;
    infinity = infinit;
9 h6 [( z2 {7 B3 r2 P6 D9 v5 a    tag = new int[vexMaxNum];
9 W. x& w0 f" ?- Q: }6 P; e  n7 |* r    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    for (int v = 0; v < vexNum; v++)
& z1 ]2 \! k9 Y) Z4 j9 j: B    {
        tag[v] = 0;
        vexTable[v].data = es[v];
2 {" X9 I$ Z& f% [- N        vexTable[v].firstarc = NULL;
    }
" \- f& ^; e; Z6 T}
template <class ElemType,class WeightType>
' u5 N( a" Y- a0 c  m9 A- uMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
2 I  M! k3 c- K& V" m6 k    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
8 u: l- Q+ e/ G& X}
template<class ElemType, class WeightType>
  n9 f1 z: @+ v: x/ _0 F" ]int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
; k- j' c( ^+ u/ P) S{
    if (v < 0 || v >= vexNum)
" ?8 n/ P8 t8 L- E        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
    else
        return vexTable[v].firstarc->adjVex1;
: R3 M5 K/ U  \' B* U, \}

- Z+ W4 Y! t; r" Ftemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
4 G5 _$ |% s- B3 O{
    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
9 ?* i( U& I% i# u  O/ E8 m% L    if (v1 == v2)
        throw Error("v1不能等于v2！");
& q" j  L: \" Y# M* ~    p = vexTable[v1].firstarc;
; I1 ?3 \) U1 D; O    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
+ i% b6 v6 U2 `( x9 D. p        p = p->nextarc;
. R0 g6 |+ P$ N/ j; ~    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
/ d2 C3 D, B1 _: C4 m# D    else if(p->adjVex1==v2)
) n! P: g4 ~' W        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
$ a" [3 Z  j4 i, R}
template<class ElemType, class WeightType>
1 [/ e7 x. o8 x3 N3 Q2 tvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
  }2 K3 X6 q) C* `( v6 j{
    if (IsEmpty()) return;
' K; w  E" P7 i7 r. y    int n = vexNum;
    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
    return;
6 }/ J/ h/ K8 G3 S% [* \* X4 U8 J}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
5 Y+ D2 a: e  H5 N! `    Clear();
}
: e1 E. Z2 L; V; M9 o! h: ^template<class ElemType, class WeightType>
/ m3 x1 v% S1 @) [! B( v. z0 iMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
2 S4 q/ F& L, F( d7 `0 Q    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
6 y, }$ j9 J4 L& b, G+ j, o* S    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
/ }) Q9 R  ~& I3 V5 K+ _    infinity = copy.infinity;
6 s1 K0 J4 Y/ b* \" m& [1 Z    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
4 i/ G" l( w( N7 O) e4 ~    {
        tag[v] = 0;
6 P# M, M4 k# W. p' }        vexTable[v].data = copy.vexTable[v].data;
0 U1 u- g' Q, ]6 ~        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
( ^6 E3 L! F1 Y- ^) m& R    {
        p = copy.vexTable.firstarc;
% P& C. F1 c: k. D        while (p != NULL)
. }% z# a6 \5 ]" y+ R: x! C/ y        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
/ Q6 ^& v) e9 S2 S7 D4 B$ B+ \0 k            p=NextArc(u,p);
9 {% |3 p3 M; E* h  j3 @        }
    }
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
" V% g* K7 h0 Z, \7 s{
    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
8 k* ~  D; \& ~+ w+ |! ^    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
  S* \) f+ A$ t* s( B    arcNum = 0;
' ~5 v# S- h! n% u  v9 U! d    infinity = copy.infinity;
    tag = new int[vexMaxNum];

# p- H' l" e- U' D8 e& j! t' p    for (int v = 0; v < vexNum; v++)
7 T' q9 ^6 d, D2 i& X* N4 Z; u    {
# M7 ]9 q- d! `        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
8 ^( g. @! \: d: Y        vexTable[v].firstarc = NULL;
0 C8 i$ A: n. B6 I& N* r$ j% C7 Q' z    }
6 ^% v! j: z7 t7 O. E9 L- e    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
3 ~  k/ R4 _9 N6 O    {
; r: ?7 g" z4 |$ c        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
( i& N3 _! k& o- P' |0 ?9 p" Y    }
    return *this;
}
$ b# d: f( O8 F( [: H  q8 Utemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
% T! e+ v0 ~: t, RMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
3 s# B/ B1 W$ E, b9 o2 u6 N" \{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
& m9 E& m* q' b0 N+ _1 I7 A" I        return p->nextarc1;
    else
- x$ {* m& P1 c6 I        return p->nextarc2;
1 z+ S0 _" ?" g* O# S+ g}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
* y' S( t! T1 c, t{
    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
; n( j" E' A/ M9 V; b        return NULL;
    while(q)
    {
        if(q->nextarc1==p ||q->nextarc2==p)
) G( D4 s* X& D- p. S6 v4 o, z" w0 H            break;
  `9 x( Y" T5 v: s( s5 ~  C( l        q=NextArc(v1,q);
0 M6 J$ D4 m) Y- R/ S. e    }
9 N' O0 R# p, k7 |+ R6 C    return q;
& L; R; i0 {" w0 C}
template<class ElemType, class WeightType>
# \& |! I! U* O& lvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
8 L' O' M$ |+ f    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
6 l0 u0 r) k8 W3 w    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
- M4 H; x6 _1 P3 a    tag[vexNum] = 0;
    vexNum++;
- q, e. ?6 N8 o' @; f}
template<class ElemType, class WeightType>
9 J. {5 \, Q+ }6 N$ m# rvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
9 R6 s; {  s( ]: i' H# `    MultiAdjListNetworkArc<WeightType>* p,*q;
7 @( n1 E$ F3 ^) P/ D    if (v1 < 0 || v1 >= vexNum)
3 {$ \4 y$ R2 v7 N# m( K, n        throw Error("v1不合法！");
9 {& D1 {% J6 T! F" t- W$ d    if (v2 < 0 || v2 >= vexNum)
6 x: D3 u6 Z' h9 z        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    if (w == infinity)
' V7 S" y- O! C% D6 `( K9 N        throw Error("w不能为无穷大！");
4 j8 A6 E% Y# u  @9 u) m

9 ?$ u7 M' x& ]" P2 `    p = vexTable[v1].firstarc;
    while(p)
4 A9 u6 c' l& q    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
" `& @* y4 E0 K( B8 z            if(p->weight!=w)
5 D8 q. ?& U, T. k. B, o  w                p->weight=w;
7 W$ \8 B1 F1 O" |            return;
        }
( Z* Q0 c) x& m) q
& q5 ^* G3 C% a) p3 ~        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
* q! H( y6 g- m" x/ S    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
9 q' Y6 r" L2 Z8 h7 p+ {! t    vexTable[v2].firstarc =vexTable[v1].firstarc;
( t7 o1 ?0 u: s9 y" H1 Y3 L    arcNum++;
}

3 |3 U6 X6 b1 Wtemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
- e8 M1 k/ }) W4 _: w{
" y' m3 P8 F8 o
. M9 h6 j$ u: ?8 \! ~    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
, q' ?4 z# T; |! ]        throw Error("v1不合法！");
, K1 _9 }5 J) Q0 M, z; \) \    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
* Q5 F0 W# d4 L        throw Error("v1不能等于v2！");
7 w: g8 D* n8 X& q2 ~
    p = vexTable[v1].firstarc;
0 o2 V* `2 G% {  X8 K: O+ ?    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
        q = p;
        p = NextArc(v1,p);
5 \* t! @; @2 s" S8 N, N$ b    }//找到要删除的边结点p及其前一结点q
- k8 Y" w6 D& o. r
    if (p != NULL)//找到v1-v2的边
    {
        r=LastArc(v2,p);
! q" h  @4 t) Z5 I; k+ v        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
! S% w9 m' ]" H            else vexTable[v1].firstarc=p->nextarc2;
% W5 ?' ]0 j5 a0 Y. i1 K* e! _        else//不是第一条边
        {
7 Y# d$ a- j- F" t2 j0 }/ s            if(q->adjVex1==v1)
1 B4 X# i) s' s* h% @8 k                q->nextarc1 = NextArc(v1,p);
& ~& {  H: }. m' B( g4 S2 n            else
                q->nextarc2=NextArc(v1,p);
- A% ?5 H% H+ H) Q9 k# r( M* S
  {' T1 O6 b+ W* o2 i5 e3 v        }
        if(r==NULL)
9 x1 x' y( @- d0 F% M! S: p# H) H) u            if(p->adjVex2==v2)
. X2 o8 d+ Y" M  b9 \# x                vexTable[v2].firstarc = p->nextarc2;
# q# y5 X. j( a. p$ k7 v            else vexTable[v2].firstarc=p->nextarc1;
7 t6 h5 h8 J3 o4 A! g. U        else
        {
. r! v2 }0 v% W9 n$ j! ^% s3 X            if(r->adjVex2==v2)
3 K$ S. H. G* }                r->nextarc2 = NextArc(v2,p);
            else
                r->nextarc1=NextArc(v2,p);
" J4 h: g0 h% x) M( E8 }5 m4 |        }
        delete p;
        arcNum--;
    }

" v& L& \: y9 B5 G2 k}
2 v; I7 @9 C& P' E* P, rtemplate<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
6 ^( ~0 T# `& g: b& m# ^( U0 _{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
. N9 q& Z1 ^$ Y+ C. ^        if (vexTable[v].data == d)
! k5 \) L9 K! b1 ?            break;
    if(v==vexNum)
, ~% e: ^: x/ Y5 \4 p' A        throw Error("图中不存在要删除的顶点！");
$ X" E9 T, l6 R& P5 r. R
    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
        {
            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;

5 J: W2 S( f. R' ~/ `% V    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
1 U, g5 O0 k, b, W; t  z    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
* }' z* D8 U- I9 d7 l    tag[v] = tag[vexNum];
$ P9 l) \" L3 D    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
, X! j3 m" T8 T' L        {
            p = vexTable.firstarc;
- J. a- ?- i3 X. L# V1 E# k            while (p)
& l; k" {  Z7 W' e( S0 a            {
                if (p->adjVex1==vexNum)
1 A! e3 n2 s3 h# ?2 e& ?/ W                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
1 X0 D, R2 r+ F! X; H, ?# g1 V: C                    p->adjVex2=v;
+ s) T; K( a% r) K+ o                p = NextArc(u,p);
            }
- o% [3 L) Y9 f  i5 {. n. K        }
    }
}
  ]7 O6 `" U- n) B, f9 l* ^///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
! B) b! J4 A" c( E    tag[v]=1;
) F9 |8 ]; V. n    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
& Y# x1 ~9 ]# m( S, g  ~5 U    while(p)
    {
" }  [( s; g" z: e1 g' t        if(tag[p->adjVex1]==0)
) g. |% E7 z1 h3 i0 t& T            DFS1(p->adjVex1);
' D: p* H1 g) f3 i' b: |        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
/ h" x1 [! n: v6 }" J        p=NextArc(v,p);
    }
. Q9 q5 p1 j1 j+ K+ M4 A. ]+ Z}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
; j; S9 z. t  b+ a  m% j{
  Q, k6 O- n( P9 ]! o    for(int i=0; i<vexNum; i++)
% v; a, O& K4 T$ n/ d. l8 W; d        tag=0;
    for(int v=0; v<vexNum; v++)
, Y. D  H1 J- z: |    {
        if(tag[v]==0)
            DFS1(v);
    }
" d8 G2 P0 o$ S  N}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
/ t2 y/ j2 i+ Z, Y( c- n2 X    int tmp;
0 C8 T! N  d) I6 f1 D# I    MultiAdjListNetworkArc<WeightType> *p,*q;
9 W1 h0 \6 x, P$ k  ?1 m6 R    for(int i=0; i<vexNum; i++)
        tag=0;
  B% E' s2 g/ ]0 B. k    for(int i=0; i<vexNum; i++)
2 Y1 G+ c, V9 |+ r4 `    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
        {
: d  z4 [2 [/ Z0 W            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
  y& g9 G2 n( \7 @" a' B5 @- }/ I' e4 y            {
# s0 |' ]% K9 |  Q                s.push(tmp);
9 p- Q. f9 v* ^                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
  s, w) y, Y7 u/ _) A4 ]                p=vexTable[tmp].firstarc;
3 B( @: d" Q5 d' \! p+ [3 [                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
. @6 |3 [  E9 U7 m- Z$ P' |                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
$ p" X. s3 U7 j9 i" b+ m            }
            if(!s.empty())
            {
- g2 U. _1 k" {3 [                tmp=s.top();
& E( v  q9 A1 t/ I                s.pop();
1 x3 b1 k6 r+ x                q=vexTable[tmp].firstarc;
3 Y$ \8 t3 F7 i6 j                int t=tmp;
                while(q&&tag[tmp]!=0)
' q; C9 p6 Y4 p+ }0 `                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
! ^4 ]1 F: o- A) L; `; ?                    q=NextArc(t,q);
                }
8 D5 v+ p/ `# q$ X) n                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
( z2 t2 K$ {4 Z                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
2 |4 M% d& r+ A# ~* O  h: L/ G- S! `                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
( [! h" O2 h; g* U- @/ m    }
}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
* ]4 v1 l8 s1 jMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
" e9 Z! o. T/ e{
! O3 x+ e0 n0 Q    if(head==pre)
        return -1;
1 E6 `5 R# M. h7 i
    MultiAdjListNetworkArc<WeightType> *p;
/ g. Q" J! N, I8 E    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
. ]1 n4 L. V  Y3 W        return p->adjVex1==head?p->adjVex2:p->adjVex1;
6 h; J) }( F, |) `) g2 U! U3 e$ L    //pre!=-1&&p!=NULL
9 g- o+ u& U1 q- u4 y; A: X9 M    while(p!=NULL)
. l% s. w3 {# A0 i3 f' \    {
5 D; k: f0 ~' E1 k, z# m* s        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
; h! h3 S2 [; g3 Y; l# y8 R, N) {            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
        {
3 _& {+ J) b5 y/ g1 _! H            p=p->nextarc1;
            break;
* p! B* X  j6 v7 f( h! D1 x        }
        else if(p->adjVex2==head && p->adjVex1==pre)
        {
9 {) f  ?2 n( I3 x0 H4 W( P            p=p->nextarc2;
# O+ |# U3 k! m3 R            break;
& K. K$ O" P8 r. K2 A- A. T$ m        }
    }
    if(p!=NULL)
8 p4 [, U6 B1 W1 _- L    {
; T) g$ h1 _( ]" g3 p4 M        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
( B) P, w; m" V; d# `    else
        return -1;
: O2 L! N4 S  |. A  a; Z}
3 S3 ~- p! e$ v, O- j5 S) m' F

template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
+ i7 F+ j+ y# T( i" ]8 I) Y! f{
1 t5 E! R; J, n4 ~4 E& T) ?7 F" w    stack<int> s;
    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化

    for(int i=0; i<vexNum; i++)
    {
- B" a6 S. p# \7 m        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
            while(tag[cur]==0)
; G' {* l6 I% B& `5 s            {
( y3 d8 M) u$ D                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
; t3 F: P6 {' Z" x7 Z3 J9 \* M! P                tag[cur]=1;
' S3 P1 N% [$ g! ~  }               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
3 B; ]* C. g5 n, l2 r4 D               if(p==-1)
               {
                   pre=cur;s.pop();
) o0 j+ I' x  e                   break;
! `7 G$ u4 A9 \. S               }
               else
               {
% b# T" A5 L# r. Y3 Y0 w                   pre=cur;
) o5 I% c( k) |& N                   cur=p;
               }
! N+ F: D  b5 c2 m' t
1 F5 ]" Q5 ?2 U5 l0 P4 E            }
7 Z) r0 ~% M9 G0 J) I5 X            while(!s.empty())
            {
' h* F3 ~* @4 l# {  u                cur=s.top();
                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
9 t5 X+ e# [9 A  J                {
$ k! ~+ W5 `, Y8 b                    pre=cur;
1 b; |' {) r% Y& W# f) ~; g' Z1 ]                    cur=p;
                    break;
                }
  V% j2 `1 ^0 R4 d                else
( p, g% e$ p0 S" I& ]                {
                    pre=s.top();
0 x( |! m& L$ q                    s.pop();
' g/ R- G+ f/ f$ n( N4 N                }

            }

  t8 f- s0 e4 f" ?2 I) @        }
    }
7 o3 W% |4 c" {! r5 P) X4 X) Z}
! o1 N$ }0 b5 x3 h2 ^) Jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
    for(int i=0; i<vexNum; i++)
        tag=0;
$ e% r" I( H4 D0 L( i    queue<int> q;
    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
# X+ [2 A) b: B0 {    for(int i=0; i<vexNum; i++)
, }1 l# e& f2 @6 `- |    {
        if(tag==0)
        {
( P, n' o' v" P            tag=1;
            q.push(i);
# r7 L% O' L; @' `9 L4 e0 M5 B            cout<<setw(3)<<vexTable.data;
        }
+ }  d2 O' p" ~+ C6 V        while(!q.empty())
! X$ `4 ]) `' n/ e& U9 y        {
            tmp=q.front();
0 t- j* d2 G7 L3 h' f            q.pop();
" c. o1 C& J4 f- f7 m            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
3 w2 P- `3 x: d, I. l- @! j8 ~                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
6 ?8 }8 K* f- E$ L5 A3 }9 V                if(tag[t]==0)
                {
2 Y) N5 ~# P$ A3 p5 H+ b3 D9 Y                    cout<<setw(3)<<vexTable[t].data;
  E: v0 s  `3 c; l                    tag[t]=1;
* V+ i- T: ^3 S6 B                    q.push(t);
                }
                p=NextArc(tmp,p);
. I) w* u( {0 D; x/ k6 _6 r            }
        }
    }
" @) X' l: R4 P, \2 X+ G}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
    MultiAdjListNetworkArc<WeightType> *p;
* k' p/ E) O1 Y2 i# B    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
# q4 O( e) w; I9 s! ~' }- h        cout << vexTable.data << " ";
    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
2 V1 P% h3 _' k3 ^( W    for (int i = 0; i < vexNum; i++)
    {
8 @! j. m3 Z; g6 t        cout<<"和" << vexTable.data << "有关的边:";
& v8 n- G; v; ?& i        p = vexTable.firstarc;
/ C- ?; B7 Z- ~        while (p != NULL)
/ R! F7 {& p' Q& l. u* B; `        {
7 M" \3 w1 u) X- X. [* W            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
        }
        cout << endl;
5 ?- _0 ?. }# y/ i) j, @5 i    }
! g* X* N( Y) g) v9 g}
% |- u, c" ^* Z9 e; }2 U; v

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

; U) l% K9 v: ~' L' C: I: e: s9 d邻接表链接
+ `* O# @' ?0 Z$ _5 l, G在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
; U/ z, }5 t5 {————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
  ]4 ?5 f9 y1 m1 _& D

- j" p6 m, A/ M1 F" ~

) u$ G& Q+ g/ N! c1 C2 W+ R————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 a3 P7 T% Z) F1 @: V$ w原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
) |6 I( }) G; q7 Q$ ~3 y