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

杨利霞

图的存储结构——邻接多重表（多重邻接表）的实现
( P1 h8 d; o- C7.2 图的存储结构

- e2 [9 r- E- p7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
' |- ^$ ~) A. Z4 t1 X邻接多重表的类定义
. q" D. S. F, y3 J; n4 K邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
% g% a7 n$ m/ M) O  ]邻接多重表的类模板
邻接多重表与邻接表的对比
) A- C. F# `5 v  D" h: K7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

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

- m5 g" m# |) l" H/ k" ~3 Z邻接多重表的类定义
" S' q  e" x' ]* C$ z: P
) `3 j$ z' b3 M$ [8 W# h' u6 w邻接多重表的顶点结点类模板

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

- X' w/ n, z7 p, I/ c' c
template <class ElemType ,class WeightType>
6 R7 i: z5 u+ rclass MultiAdjListNetworkVex
{
public:
* S. V1 ~' w' N1 l        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;
! G( V/ i( d! q$ z+ x. U3 T
        MultiAdjListNetworkVex()
        {
                firstarc = NULL;
        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
4 K% B$ P- U: G) {% }( `        {
                data = val;
' F; |/ L! Q: E* ^5 D  a                firstarc = adj;
7 ~2 U3 |& w7 E0 ~+ C7 K4 k        }
};
, f9 x3 t! O, d. |; y7 Y( X
邻接多重表的边结点类模板
4 ]3 G" ?) M2 Y0 K+ i) B  i3 D
: ^# U& n" I& ?在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
3 I! r' J% ?: g( D+ x' |) ~
+ z' P; [7 X- \- ]3 K: `# f; a
template <class WeightType>
# j8 Y; C: l& Y2 X9 r1 [. _class MultiAdjListNetworkArc
{
public:
    int mark;                                       //标记该边是否被搜索或处理过
' @6 k, q/ T: S  r        WeightType weight;                              //边的权重
6 n5 e6 e; M8 o9 {        int adjVex1;                                    //边的一个顶点
& X/ s% d' J" S* C* m% Z        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
) V3 b8 |- }6 u4 C' R, b- l        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;

        MultiAdjListNetworkArc()
        {
+ C1 d' b% R) n. k) c' H0 b; O; P                adjVex1= -1;
                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
                adjVex1 = v1;       adjVex2 = v2;
+ Y4 ^; S# z$ G( b0 h                weight = w;
+ n1 J4 B' W4 Y3 k% o/ D                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
        }

1 N+ t7 d; n% T7 W邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
: B5 y0 R8 B4 i9 x! ?# X4 `protected:
    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
* z4 e! b  a& ^  \: ]    int* tag;
    WeightType infinity;
7 R3 L) l6 R' W3 g' [& K
5 ]8 O) R3 L: h9 B: N2 U* H) Ypublic:
( I  Q5 s7 U2 Y    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
: N2 z0 }( G# V9 f) |
4 r% h6 _1 i( U$ F5 H4 e, o3 X    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    void Clear();
; \3 i, N6 ?! Y& M    bool IsEmpty()
/ w9 y1 ^6 _* G7 J% l: f    {
        return vexNum == 0;
    }
    int GetArcNum()const
    {
        return arcNum;
    }
    int GetvexNum()const
    {
2 ?) c- t7 P- x. U9 w        return vexNum;
    }

* M4 u1 K9 E5 o1 Z) J& T
$ M* \( `- Y; ?, l$ i5 `4 k5 \    int FirstAdjVex(int v)const;
8 X4 d+ r$ m' b" m0 A( R, N    int NextAdjVex(int v1, int v2)const;
    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

    void InsertVex(const ElemType& d);
    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
1 h0 Z& M) ?2 e  P    void DeleteArc(int v1, int v2);
7 ]" Y1 ]# [1 r. m
. U3 j) f0 j* j" x9 G    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
+ g. n" y" B; ^5 H    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

    ///深度优先遍历
8 l5 a  t+ `1 U/ ^    void DFS1(const int v);
    void DFS1Traverse();
% ~) h; t7 J& D" k$ i8 X    void DFS2();
! f9 ~6 F" I8 r
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();

    void BFS();
  d" n: ^' [, X0 v% Q$ O# r    void Show();
. m! j& U. X* |% _5 d1 ~: h1 E, A};
6 k0 [" F- h1 \- _: F
5 k  l) h, v) ^6 W+ ]3 c5 _4 M2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

#include <stack>
#include <queue>
6 [  \; M5 _: v) ~# R4 t
' }. h; _1 s& u7 ^/ qtemplate <class ElemType,class WeightType>
' F. Q4 m) ~' J# BMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
  h2 a* f) n5 g7 |9 U% ?0 j( d{
    if(vertexMaxNum < 0)
: J  }: x% ?* L* o7 _/ |) o        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
  R' E1 R4 V3 k* `8 M. O9 M; G1 V        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
% J6 d) t9 {  G    vexMaxNum = vertexMaxNum;
    arcNum = 0;
& B9 Y: K% y8 V, b7 f    infinity = infinit;
/ A+ S( r( p1 m    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    for (int v = 0; v < vexNum; v++)
    {
" y: H9 V, w$ p0 Z        tag[v] = 0;
' [1 H! e* q! C        vexTable[v].data = es[v];
" Y2 k! p8 x, \( A- `        vexTable[v].firstarc = NULL;
    }
- ?5 v4 h' X5 P) |. `! @}
template <class ElemType,class WeightType>
& W$ m4 s% r& u' Y9 GMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
# h" ~8 i# S  J& t" N# S    vexNum = 0;
    vexMaxNum = vertexMaxNum;
. _& A: F& S/ K3 V7 ?0 C% q    arcNum = 0;
) Z1 n* ?6 K1 J  H& M0 N    infinity = infinit;
9 R9 k* v4 U7 |( S1 l9 y) T( C! t    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
, U4 }" T& t0 g2 `: `* C}
  Y0 K% A: c* ^7 V% jtemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
    if (v < 0 || v >= vexNum)
7 h8 i- R* O" q2 l* ?/ o& w        throw Error("v不合法！");
0 Q. d* [6 `3 N" ]1 |" @5 n. k    if (vexTable[v].firstarc == NULL)
        return -1;
    else
5 x& A: Z8 \( |6 D        return vexTable[v].firstarc->adjVex1;
# v7 ^* ^9 Z3 _- f( G}

: [6 c4 n0 x" t8 h8 L& F+ |template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
* ?5 ~% S2 m% Z1 q  y" o7 {    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
; r+ |8 y/ y  {* l: M- @) @5 s        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
4 l9 [: P! Y' C% D0 ~& g& h        throw Error("v2不合法！");
    if (v1 == v2)
  z. b% s6 d  q' L3 L. \- Q        throw Error("v1不能等于v2！");
# {* h0 K: G: }    p = vexTable[v1].firstarc;
% C5 ?; a1 |2 M) @    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
, i) N9 l4 T+ V# D6 u* m    if (p == NULL || p->nextarc == NULL)
$ P, A) O  Y, X4 I        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
- x9 Q. u: j. k+ q4 j        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
+ i* X& u  d! Y$ |# p6 [    else
. z' {+ }9 m  U! j; j8 G/ J  C        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
6 I. q9 i. ?, b/ ^8 e}
! {8 n$ e* ~0 K7 A: t# `7 Atemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
+ S7 m, i4 O2 M6 ~( l{
9 j. m0 d! T& E0 ?+ x' |& @9 V    if (IsEmpty()) return;
    int n = vexNum;
    for (int u = 0; u < n ; u++)
3 X) Z! R& G% D        DeleteVex(vexTable[0].data);
+ i* N3 z" ~6 g+ g% B7 }4 }  }4 U    return;
3 \  D# o) T% O2 f% {: z}
template<class ElemType, class WeightType>
* K* ~+ }' x# n" T" p( wMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
4 U. W& p/ h3 S. {5 a    Clear();
  m, P4 `8 Z3 P}
template<class ElemType, class WeightType>
4 {7 _$ o; z) MMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
& W5 v6 I% L- V+ Q, J9 c    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
4 v% w8 l+ U# U    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
0 J* w8 n, A+ Q; d    arcNum = 0;
    infinity = copy.infinity;
6 D3 t( |4 c2 x4 d  S6 E6 x    tag = new int[vexMaxNum];
) R1 |. p- T$ m. x- B% {" L+ g
" E0 [2 @. g; ]8 z0 I    for (int v = 0; v < vexNum; v++)
" g- s+ K7 ]; O' A; ]. J    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
; j8 N% w! O: W1 S, _        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

8 k- s& m7 F7 C4 U8 t. x* [$ }    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
- o3 x, {- K% a2 W7 L        }
" T5 G$ z# T- J, P    }
2 b" ^5 ^) v9 j}
/ t5 g: {0 n+ F, ~7 itemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
# \1 v& \  g/ f* |2 V2 h) [MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
$ o. S) a6 G( P{
    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
* \6 u; Y' U& v8 ^    vexNum = copy.vexNum;
& c$ p5 ?, @5 C5 B    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
6 t" @! o! w1 m8 M    infinity = copy.infinity;
    tag = new int[vexMaxNum];
! a1 I6 r5 o2 E3 x. {  Z
    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
+ o7 f2 n) b! Y3 R        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
3 ~' e5 C5 }) K7 P* Q# }    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
. I. e  p- h5 ?) _0 I        while (p != NULL)
        {
* L# R- W1 n/ \8 J1 X! z            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
( x& F. M6 F( d3 S8 T& P( D        }
    }
# Q# G  ?9 A6 D    return *this;
}
! `. g0 E. T+ u  p. ^  I4 Ptemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
3 Y& k) X' P" u7 |2 i+ Z0 ~    if(p->adjVex1==v1)
        return p->nextarc1;
    else
        return p->nextarc2;
1 P6 \0 t2 q5 q}
- P( L9 [+ r3 C4 q+ k. Xtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
. B& a7 F0 o1 \MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
6 [; I! o( w' {6 q2 y{
: {/ d0 n0 |. o$ k    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
# y5 ^- D7 j  }; [3 r  [# r    if(q==p)
        return NULL;
5 z) y! s" ^! N- J& f2 a0 d, s    while(q)
; @. x. s7 |8 _2 @    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
$ q. [. i& d) i) x1 N/ k7 c        q=NextArc(v1,q);
    }
    return q;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
% X! M% e0 j  [1 [/ m{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
/ d  J7 b7 c4 B" w1 t    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
    vexNum++;
}
) S3 w3 E7 g' E% b( ntemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
+ o3 j6 Z# a! @+ ?        throw Error("v2不合法！");
" n# X' c) R; u5 }- Y* f1 A; g    if (v1 == v2)
        throw Error("v1不能等于v2！");
1 T- X$ N+ v7 B    if (w == infinity)
9 b6 A. G+ v8 k& o# Y" C        throw Error("w不能为无穷大！");


6 Q9 V8 n$ n" W  G& a  q2 o! B" M* w    p = vexTable[v1].firstarc;
- R+ w$ G3 S: A$ T( M    while(p)
    {
/ ~2 j1 d: T1 q/ m5 q  ^6 Y" P- Y  n        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
& F& x2 j# f# \) q0 V; w9 m        {
1 F; p" @% }( |3 G, W            if(p->weight!=w)
  o, N* J+ y7 q: J7 f5 Z                p->weight=w;
            return;
4 i6 H" P' n* Q1 I+ H, G# N        }

' B$ w2 O. ?( G6 u, r( \7 g. |        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
0 }" C! N: _. m. _5 S/ {* o    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    vexTable[v2].firstarc =vexTable[v1].firstarc;
! c+ i. l" ^# C& @0 @) s    arcNum++;
7 q5 ~1 k' ?2 R' y4 Y! s+ {. x3 ~}

template<class ElemType, class WeightType>
7 a1 [% Z# T2 H9 b5 L' bvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
1 L4 P8 o* C, s. _, T7 Z{

) J& c8 S" @, \, m1 J    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
" l. K1 _1 V9 U    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
4 m$ X* r: G) R    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
- L6 |: m9 E) c' `" B        throw Error("v1不能等于v2！");
" C0 Y0 C$ Y9 ?! R7 L
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
3 K$ G5 k; Z1 S5 g% E2 r0 ~* O, J    {
' P0 G' b1 [" n7 @; c        q = p;
        p = NextArc(v1,p);
    }//找到要删除的边结点p及其前一结点q

    if (p != NULL)//找到v1-v2的边
    {
) i& h& R' ^+ T& J! ?2 G        r=LastArc(v2,p);
        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
4 T# j2 W; P7 x: v            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
; j3 \, ^' {1 ^* a% u* T) ?  }        else//不是第一条边
' P# [9 J+ e: K2 B7 W# P        {
  P+ S9 Z. _3 s1 @            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
            else
  M! g) X+ \6 h7 o$ t7 {) b                q->nextarc2=NextArc(v1,p);

        }
        if(r==NULL)
# u; Z" A7 H( r7 h4 ?            if(p->adjVex2==v2)
. F' D7 f* @( x! r% B: \2 u                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
        else
" k6 c+ k) m* B8 _        {
! r  P. V% V! s            if(r->adjVex2==v2)
7 l, b& d+ G: z                r->nextarc2 = NextArc(v2,p);
5 g% s, @, X# P2 K            else
4 Y% m% c; Z9 m4 G* n9 f                r->nextarc1=NextArc(v2,p);
        }
        delete p;
        arcNum--;
# }; S3 E9 j$ M) s    }

}
template<class ElemType, class WeightType> void
- `6 @, l( M" j" R( {/ J# }+ QMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
; _- u3 P2 f" Y; b{
% w1 }0 h* q% G3 w9 V( ?    int v;
* o( x6 J, e2 f) m) r    MultiAdjListNetworkArc<WeightType>* p;
- c8 j- j+ f8 {! i3 g    for (v = 0; v < vexNum; v++)//找到d对应顶点
8 `9 I/ }5 u" x1 ^) w7 D6 d        if (vexTable[v].data == d)
! f! P9 e  ]& u" I% z8 w, ?            break;
    if(v==vexNum)
0 X+ ]( j+ e/ \$ S" r        throw Error("图中不存在要删除的顶点！");
5 A: U7 a. Z$ H1 U, R
; l) J% H& G6 n; T8 w$ ?% W    for (int u = 0; u < vexNum; u++)//删除与d相连的边
3 U$ Y0 k  I% [9 f8 \3 J        if (u != v)
, d4 Y9 ]; M# s$ ]        {
7 i, k  n0 }2 [9 s% a            DeleteArc(u, v);
% u' I6 P9 k( a* P        }
! V% z1 s* |3 f$ y, n: P0 ?+ Z    vexTable[v].firstarc=NULL;
8 b' D. N8 @6 s: K, Q' P  R  `
    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
* J. C/ Q8 W2 I; u, O    vexTable[v].data = vexTable[vexNum].data;
( M& x3 R# o  F+ O  [. Q    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
" \1 D) |2 a$ }( W    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
    {
5 N( F0 V, @/ F" A! R2 |. z        if (u != v)
7 X8 _1 N' g  d        {
            p = vexTable.firstarc;
. A( R+ z$ @$ v. i, [4 B( }8 w            while (p)
            {
                if (p->adjVex1==vexNum)
$ B6 J2 N, F9 ]                    p->adjVex1= v;
& L6 q  ~: F; w) M0 h( D                else if(p->adjVex2==vexNum)
) q3 d7 W) _6 A( @5 r                    p->adjVex2=v;
                p = NextArc(u,p);
            }
        }
    }
! w  L( C; d) A1 T1 i}
5 o/ ^4 }% Q1 x///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
/ p; Z' }% L+ k& @{
3 Z: N. h: @" Z6 @( |9 V1 g    tag[v]=1;
8 i, M# D6 `1 S+ W/ }+ v    cout<<setw(3)<<vexTable[v].data;
0 Y" ]: V' ^% U! r% i! h    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
    while(p)
    {
# z; i) p3 Z3 b  e8 b        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
) i9 a0 E: y* Q- _4 z! @            DFS1(p->adjVex2);
, ]* U& q) x5 P- f1 x* Y  J        p=NextArc(v,p);
3 L5 I0 D# E* w7 ~$ ]( ?    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
{
    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int v=0; v<vexNum; v++)
    {
: W$ N! z% |& t) j! x, k. c9 ]9 b! t        if(tag[v]==0)
5 C; b! P" h# U0 }+ p! D: I7 }            DFS1(v);
& N8 }1 q8 u# i( [: v6 }4 `+ R    }
- V) S5 K" i, L* `! K) {}
- }" G2 ?+ M2 [3 Q: }+ e4 L- Ftemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
* L; N* R* @; O1 n{
/ r2 g* j5 a' D  T    stack<int> s;
    int tmp;
# n, i- c/ h+ ~* {! K    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
0 i6 r  `! n: i4 D& d) X        tag=0;
    for(int i=0; i<vexNum; i++)
    {
$ Y2 X4 k% S7 _( G- X4 r5 w$ f        tmp=i;
' `& c. Y1 V' R1 D        while(tag[tmp]==0||!s.empty())
( e! K: y% e% X5 c3 W1 b  k4 |        {
            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
+ V5 R% |1 F& k2 b, H1 E                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
' [  X9 O. ^; }: n% v5 ^& ?6 z1 U                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
+ t  G: C4 F- n9 u6 J, |6 t+ D1 _3 O                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
  i% o2 A6 [( x3 ]; G: e  P                //cout<<" 1st     tmp="<<tmp<<endl;
* k8 k5 V% Q: \1 ~% N            }
1 H/ X2 W6 D+ A            if(!s.empty())
3 I" n3 l3 [! K- K  @            {
9 P1 b  U: s4 M, ~  ?                tmp=s.top();
5 ]' M# _( b5 h. j) t' \% u+ F( Q5 W                s.pop();
                q=vexTable[tmp].firstarc;
/ V7 v! e# I5 p6 r' H9 n                int t=tmp;
                while(q&&tag[tmp]!=0)
  s0 J/ L5 ]: b8 X  s                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
; j5 B9 v% v9 k                    q=NextArc(t,q);
& g. P! r9 p& p                }
! [5 ]6 R+ h/ s8 T. q                if(tag[tmp]==0)
3 @4 _; T5 e+ A+ ]: t9 W                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
+ _4 Q  H5 a' ~' {, _6 `& l. `' r+ j# H                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
- u( ]6 I1 }6 n; t7 z1 H: F: w3 R                ///tmp要么等于找到的第一个未访问节点，
$ b' [8 N6 W9 p8 z                ///要么等于与t相连最后一个点（已被访问过）
' q7 b; f+ z; _# B+ u                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
8 M/ g4 K# d& G- }) h8 A            }
4 e( \3 H# i' F* Z, i        }
    }
0 X5 \/ n3 g1 R2 Y* R& h}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
% G0 V* Y9 A2 Q7 l' J# g8 qMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
0 A5 b8 B3 H2 Q. B{
4 z+ O! l- ~3 Y7 H3 O/ ^    if(head==pre)
$ Z0 s! I1 P* m4 s2 U3 w! k        return -1;
+ p& a6 u7 B" U0 R' [6 g
    MultiAdjListNetworkArc<WeightType> *p;
  B& h7 D  E  o9 N! K/ k    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
, s' f" F- Q  x        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
8 K/ i1 D9 k% T3 y% W    while(p!=NULL)
    {
        if(p->adjVex1==head && p->adjVex2!=pre)
$ z3 B0 Y+ Z) k" a            p=p->nextarc1;
. j* a- a* `! i9 e  P9 U& m9 P        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
5 Y. v+ c* S7 i8 D' \7 w1 e        {
3 T9 T& u' A, l) E5 v5 ^# ~2 B# i$ R8 K            p=p->nextarc1;
3 d3 K( v4 I  C+ A8 m            break;
        }
3 a5 {- ~" U. T/ s        else if(p->adjVex2==head && p->adjVex1==pre)
        {
            p=p->nextarc2;
            break;
( |2 K: {5 w' o4 @, e        }
% k7 h6 H# A  k3 z2 q    }
; l+ d' z9 o+ W' d* Y    if(p!=NULL)
    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
8 H4 B6 j. b$ y3 q# |+ y2 E' b  S    }
    else
        return -1;
}
2 j+ X! }& V& _$ g' B3 ]8 K

0 D- X! L% ]& X! j% X* dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
( G6 q. P/ T# h7 r( I{
9 T5 u, M8 j, y8 E0 Y    stack<int> s;
9 b9 j  ^- @+ U    int p,cur,pre;
, X3 B/ ?3 E8 A    //MultiAdjListNetworkArc<WeightType> *p,*q;
2 x- f4 ~( [1 @  g) ~% f: \    for(int i=0; i<vexNum; i++) tag=0;//初始化

    for(int i=0; i<vexNum; i++)
$ R" B- c5 u- F$ g    {
        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
# u# w) S1 G- I* u( r2 N: B        {
* a3 |5 Z$ w$ P. v* ~; U. N& y            while(tag[cur]==0)
/ u) @. A; G; B1 U            {
) Y( {" {# Q4 P2 d2 J                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
5 Q, u% U. P  n- ^7 `/ I! }; d               if(p==-1)
               {
                   pre=cur;s.pop();
                   break;
               }
               else
               {
                   pre=cur;
6 k. O. ]5 f# s8 a* l                   cur=p;
2 T  k7 L  k% _6 w               }
1 z8 `; o# F! e+ K0 S
            }
            while(!s.empty())
( B+ C- L$ }% Q  J+ k            {
1 Z* y. s3 t0 m) f- ?                cur=s.top();
% `6 Q% o0 M+ d4 X; A                p=GetAdjVex(cur,pre);
3 l- v" ^  d# A' g2 t                if(tag[p]==0)
                {
                    pre=cur;
                    cur=p;
7 p3 J+ v3 h* T( w. E; T$ l! P                    break;
+ j0 ]% n0 `# r5 J" N# C8 P                }
1 Z$ k) g; [+ a& h. g                else
/ ^9 ?# `( P5 z6 ]$ T$ f- R6 u  {8 m                {
0 h" ?1 B5 i' l8 K6 w% S                    pre=s.top();
: ?# \) X, S, _                    s.pop();
                }
- u: S! X2 K' d  r7 F7 c
            }
4 e# z' ^' a. s4 c: V4 b
        }
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
! d7 o% X1 ~, L2 _6 @{
    for(int i=0; i<vexNum; i++)
        tag=0;
    queue<int> q;
    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
: v0 r! M1 r9 ?  \% z9 n3 O, X    for(int i=0; i<vexNum; i++)
# o8 i% o# i4 }9 k5 Z8 ^    {
        if(tag==0)
        {
, @$ }+ x2 R8 j$ a% e            tag=1;
- G2 O+ y, K: b0 K6 i8 P+ g            q.push(i);
/ W" N& o- {9 W: }4 T* K1 [6 o            cout<<setw(3)<<vexTable.data;
3 Y6 }2 v! \; |( I2 G1 p        }
$ o$ G, h- B/ G8 U* v        while(!q.empty())
        {
            tmp=q.front();
* f3 J, r# K$ q            q.pop();
            p=vexTable[tmp].firstarc;
; o0 n6 M1 z( F: T            while(p!=NULL)
  g1 F* ^: q' t) G  y1 I" D. m6 H7 }* p            {
4 M  L' k% _3 r! o6 S                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
                {
                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
8 [: x+ }" U4 ]0 j6 x: j                }
                p=NextArc(tmp,p);
            }
/ d5 B* ^% l+ B% e. N$ }        }
# X4 B6 r  H$ R' j6 Z, Q4 N$ s    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
8 J  Z0 }9 w( m{
    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
" E" S" K4 l& w, @6 S    for (int i = 0; i < vexNum; i++)
) h( S) f/ |! @  }7 j1 h        cout << vexTable.data << " ";
    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
! E7 T. l" R. R* |3 d  t8 e) L9 k    for (int i = 0; i < vexNum; i++)
! B7 Y8 [, @' _7 E    {
; e% n. a1 W7 l8 p2 }8 K        cout<<"和" << vexTable.data << "有关的边:";
# ~: X/ C' g, T9 I% N        p = vexTable.firstarc;
2 s: b' L: [" F. _; u# H        while (p != NULL)
  T. B/ Z6 |/ S/ L; J% h# [9 f        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
        }
' t! e5 j! k: o5 Z9 M        cout << endl;
    }
}

/ d+ v, t3 E" k) y" c: H. V: I9 T
- E5 w6 g& \2 M邻接多重表与邻接表的对比

+ o) Y5 k1 o5 A( ?- t  x0 c- q1 l8 ^邻接表链接
4 j3 k$ }0 ^8 |2 n& J1 _在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
8 S6 X& J" |$ O' z9 A' h7 A0 I, ]在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
# B) r, h, j6 K为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
; F& V; z8 z5 Q7 |: T————————————————
% w) o! H& v+ D" p8 X% |版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 b# U/ k6 a- j$ e. b原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
/ k* b" C) C2 x2 V

( U( q0 u- v* G
" ^% @, E9 u3 l+ N; B* x
1 q; n: E7 r2 Q  u2 P————————————————
! F+ S2 p' i* ^( Y( s& E, A版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958


! G: h& K) {4 R( q/ L