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

杨利霞

4 Y' ?# T( G6 U. ~, x+ \' d图的存储结构——邻接多重表（多重邻接表）的实现
9 t7 g; L( |. d7 e( [7 r7.2 图的存储结构
9 p; s! e- B- P& E
$ q; ~: m# V6 R/ p% U5 E( S7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
1 K' n: d; Z1 L邻接多重表的顶点结点类模板
  O( _5 g" @' E4 j. I邻接多重表的边结点类模板
$ A& k( I2 T6 ^: d: C. O- S$ d邻接多重表的类模板
6 K; ]6 t. ^/ a; E邻接多重表与邻接表的对比
4 v3 h1 U* r, S* X7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

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

- a' H; R7 K; L- Y/ t, x邻接多重表的类定义
* k% w4 S: T0 K" m
邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
& T, }3 X: V# A! Q4 pfirstarc域是链接指针，指向第一条依附于该顶点的边。
所有的顶点结点组成一个顺序表。

- q+ [6 n5 A1 b1 A: W1 ktemplate <class ElemType ,class WeightType>
- f, M. S0 x7 ^' Aclass MultiAdjListNetworkVex
{
8 k- ^; W0 [! qpublic:
        ElemType data;
  M6 @9 e* \( L1 A6 ^# g4 X        MultiAdjListNetworkArc<WeightType> *firstarc;

  Y; a5 J  {9 y. N. Z8 u1 g: b: D        MultiAdjListNetworkVex()
% ?1 r; i6 O0 |: T9 z        {
                firstarc = NULL;
        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
        {
5 \1 t" E  w' j* [* t; Q                data = val;
                firstarc = adj;
        }
; ?8 ~* G" S( ?};

: T  n6 h# G: G; [" t  V( _邻接多重表的边结点类模板

1 x' m/ m0 _; h在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
. X7 I) s, l, q, k  s$ pnextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
' H' A! J4 v/ A* J" E4 f

& ?0 G9 C, k5 q2 O. l+ Rtemplate <class WeightType>
# f4 E1 J, t- yclass MultiAdjListNetworkArc
$ ?+ I+ F+ Z$ I! G; {{
9 S4 T" v# c, _public:
  J5 }/ _- w0 ~; {$ {    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
/ v' W0 g' Y/ d# o! a2 c% @        int adjVex1;                                    //边的一个顶点
' w7 ?' z  F- h$ l" `3 O' L        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
6 ]& s9 J4 G; l4 J- i( x        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;

, I7 |3 U6 u( z' u        MultiAdjListNetworkArc()
% |9 x* B5 [6 W" `2 Y8 a* ~        {
                adjVex1= -1;
                adjVex2= -1;
        }
) b: o( i$ ~5 P' S5 P6 ?9 f5 G2 `        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
% K# \4 R: w  z        {
$ M" A5 g& y7 B                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
: Q3 ^: a& ~3 F5 d  ~% r' z7 P        }

邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
% h9 q% T1 x4 {! |class MultiAdjListNetwork
3 c# r$ h9 B5 Q% R# @6 k' T+ Z# e{
protected:
4 k9 Q9 w1 e) G+ e- M1 S  G% q" O    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
, Y, y8 C& `6 c6 x    WeightType infinity;

$ z3 p. O% _/ N1 n' {public:
6 I! _. Q5 R) W    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

+ S: l8 M1 ]0 I) R8 M  ^1 h    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
& R% _. D+ F0 M" n3 d' L
    void Clear();
! F# \& A; c  f, f    bool IsEmpty()
* M7 @6 J9 @- K/ @    {
        return vexNum == 0;
" W+ X) i7 A. |% J& o9 ?( X- N: e    }
7 ?9 n9 G, C7 w( F1 i: W# l3 b    int GetArcNum()const
    {
        return arcNum;
    }
5 T- d" S/ k% O: w) [3 G    int GetvexNum()const
    {
6 M1 I8 ?+ {: B8 k# s/ ~        return vexNum;
# r' T& M* \0 k1 V8 b    }
, j* V" r5 y- Q( g" x
/ p' w, A" k" J& a- E
    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
5 Z* ?- s2 U8 r" o& Y    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
: _8 Y9 D7 u* M) ~) {    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

" z' O( [9 D9 ^    void InsertVex(const ElemType& d);
9 t, O0 e) W4 l$ a    void InsertArc(int v1, int v2, WeightType w);
1 q8 E* f7 C6 g' v1 u6 @
, x1 L% x8 u1 z1 o, I    void DeleteVex(const ElemType& d);
$ o  g. p7 G7 B    void DeleteArc(int v1, int v2);
6 T3 b, R; P/ w8 e
    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
: c) G% }7 L" O, R
    ///深度优先遍历
2 t8 P) U$ c4 s/ w/ C    void DFS1(const int v);
    void DFS1Traverse();
2 h0 j4 c; W$ u4 c9 ]$ L    void DFS2();

* @2 I; R* H( y/ Z$ j    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
/ U5 d5 i, G4 p4 V    void DFS3();

* \6 E9 {0 b! d3 P, @7 D    void BFS();
2 h& v# X0 k! z: C- b3 l- ?& i: N    void Show();
$ n3 z$ C; a# T. r7 i* a};
% l8 ]% H+ V1 Z4 T1 t
+ x' q4 X5 l! c+ K( p2.函数的实现
# b6 Y9 n; m7 L研讨题，能够运行，但是代码不一定是最优的。

: c4 h9 p+ [, S3 v3 z+ K#include <stack>
8 ]/ W. |, k9 _7 A( @& x0 t) v" E#include <queue>
2 F' G+ f1 h$ M- y- B
6 k+ c, _/ [, {6 v! c2 ntemplate <class ElemType,class WeightType>
3 O+ u, |. r1 C" u! GMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
    if(vertexMaxNum < 0)
" y) m8 s! i) s% \' j        throw Error("允许的顶点最大数目不能为负！");
- a) H/ n8 T! c    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
: {4 l" B$ \6 u    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
; I" ?$ I/ _% u2 l    for (int v = 0; v < vexNum; v++)
    {
* |# d. G+ M# Q- X# A$ t2 l        tag[v] = 0;
) R8 _: l; L- L& B+ J3 f        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
6 R+ X7 y7 p0 |6 n8 w; U    }
}
template <class ElemType,class WeightType>
7 n6 g: u( O0 U# Z9 W# n" rMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
3 R5 q# [3 @  s. I7 x9 M) P{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
/ W- z  X5 p" O3 E! F- N: d    vexNum = 0;
    vexMaxNum = vertexMaxNum;
! `" r. H# O. s: p" `/ s2 W$ q    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
" K% ~) ]& W( d4 B}
- F  N7 B/ h. Htemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
& J9 Y8 N2 Z0 @5 ?    if (vexTable[v].firstarc == NULL)
        return -1;
    else
' F/ d) S% T0 y        return vexTable[v].firstarc->adjVex1;
! B8 a( s9 Z) p, x0 x7 w4 ~/ P}

- `+ X. \5 y6 N0 |template<class ElemType, class WeightType>
* R, e" n* W' \. o2 Kint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
& V: s+ z0 V8 o{
9 P: h& S3 Q7 r    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
4 q1 x$ E! g- O! t5 e7 r    if (v2 < 0 || v2 >= vexNum)
0 h: }, n; c3 X        throw Error("v2不合法！");
    if (v1 == v2)
! i% X" S+ f# d        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
. h9 i' z$ M' ^    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
/ L6 Z! m( H* p        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
4 Q- ]- [6 L  ~* ?        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);
, q) a7 Q) m6 H7 t}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
    if (IsEmpty()) return;
$ J) W1 o3 W3 ^$ F1 j8 }* O    int n = vexNum;
    for (int u = 0; u < n ; u++)
, R# x+ B3 |. p. g        DeleteVex(vexTable[0].data);
$ b: M* S: ]9 W/ h$ F8 A    return;
}
template<class ElemType, class WeightType>
$ W6 y  f$ l: |$ KMultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
2 Z8 f" w. \3 z, ?, r3 s% ^    Clear();
8 j; P7 L( t& N+ H}
- ]( b1 Z( ?8 ~& m: ltemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
+ c7 y: V+ h' u7 B{
& \3 G3 ?7 T9 k0 Z    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
' d% Y& Q! p& V$ A7 T    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
8 j% v1 G4 i3 I2 B0 W: Z    arcNum = 0;
. ^/ E3 d3 ^& H3 g7 S! g& w    infinity = copy.infinity;
2 U0 B: O1 X% t9 b    tag = new int[vexMaxNum];
# C. {0 L, I3 F0 \& E
% Y* B6 }* Y4 k' O    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
1 k. M* Z' o* u% \% I9 ?        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;
2 l* P, u9 a4 n/ |
    for (int u = 0; u < vexNum; u++)
    {
1 m6 e2 l9 Y5 P        p = copy.vexTable.firstarc;
        while (p != NULL)
" v" \5 ^9 W5 _4 ?+ h3 R        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
0 [' j, C: w3 J: Y! t  _7 N4 w$ ^& \! s            p=NextArc(u,p);
$ [; R' U' ^& }, _        }
    }
5 f7 }5 g' b0 i! Z) T( x+ |; m}
6 Y6 q7 g; z, V" e. s" Ntemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
0 ~- P; k& j8 ?) v( T* @MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
+ _0 i. @0 r1 h( `8 S0 U  Y: H{
    if (this == &copy) return *this;
/ e* x& Q. i; |$ a5 S& e+ [  j    Clear();
7 d4 F* ?7 Q4 j& w/ G3 b    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
6 R. u1 B' q, S( k+ H    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
- G3 o$ k6 G; @* o8 K& v$ q$ l) G    infinity = copy.infinity;
2 A' d7 C( @$ r  T    tag = new int[vexMaxNum];
8 h; D- G! [5 G! ]/ \/ K
+ f/ n% X5 R) i    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
# M: k& d& }! G# A$ Z+ ~/ ]        vexTable[v].data = copy.vexTable[v].data;
8 v3 F2 E' g3 r- w9 M2 h+ w        vexTable[v].firstarc = NULL;
    }
# {8 i/ G7 r. I, j6 u    MultiAdjListNetworkArc<WeightType>* p;
, z6 a! w% h$ c# p; p% V& J
9 K" n, q* Y# F' d    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
0 u; P+ d2 ?; H8 k) ^            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
- U9 A4 s! f( S1 X3 r: x# k7 @    }
2 |: S; Q1 w7 N5 I    return *this;
}
! y$ b6 {9 h8 [* i- L  {template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
6 q. @' p% @2 X" f% rMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
, b' Z6 U, N, Q3 f& V    if(p==NULL) return NULL;
/ a. |5 v; f7 O7 p% `; I) H3 x, m  N    if(p->adjVex1==v1)
        return p->nextarc1;
    else
        return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
: g# m' d: T4 M2 B+ J/ K& {# @/ oMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
3 w" w- C% e$ d4 q    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
! {/ K# b3 ?3 D7 Y9 z+ W+ N    if(q==p)
        return NULL;
$ V" b& }4 ~& G7 i0 c9 f    while(q)
3 d, ]3 [# y% {2 p( S) Y9 H    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
        q=NextArc(v1,q);
    }
    return q;
: b# I; q7 N7 S' n. o}
% D' ~/ J- ?. h' @% W4 A% ttemplate<class ElemType, class WeightType>
- o$ _) ]# c" A- Fvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
1 X" s) H& h2 H# }( f7 a& @; C* D        throw Error("图的顶点数不能超过允许的最大数！");
6 D3 d0 Y# Y3 n6 t# o    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
    vexNum++;
}
template<class ElemType, class WeightType>
) J- W" D3 [  n9 N# [. o- fvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
2 ]9 F% D) }! u' {  \$ X+ l  E2 W{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
5 [, }- D) y9 N( H- b' d    if (v2 < 0 || v2 >= vexNum)
/ G$ z; J/ k% I$ ~        throw Error("v2不合法！");
9 o; ]6 M9 M. v- b% Z    if (v1 == v2)
        throw Error("v1不能等于v2！");
' n! C0 }3 b( i& f- {    if (w == infinity)
        throw Error("w不能为无穷大！");

, k! \! ^+ Z' y/ [
( e* u+ x1 j7 f3 |" E) i3 b2 m4 x    p = vexTable[v1].firstarc;
( w+ F, K( h: H5 K6 ^- H    while(p)
7 R+ F, \) A6 @$ i0 ?    {
1 j& h5 f% U; g8 z% Q        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
; K4 h: X" a  Y5 L% b  b            if(p->weight!=w)
                p->weight=w;
            return;
        }

1 h9 [3 E7 k' \5 X* x/ b+ D& |        p=NextArc(v1,p);
    }
% L1 y& [- {+ I* p8 X" `$ u    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;
8 S  H# z# p) ~    arcNum++;
3 f$ K  f  Z# n3 c: |: ~: y8 r, w}

( U6 Y0 ^3 N' f9 O0 i8 L- Utemplate<class ElemType, class WeightType>
+ a$ t( Z: M* I$ I0 ~% s6 Dvoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
{
+ C$ Y# F8 J, k1 y* D( e
/ E1 S: ^8 T$ A1 c. G% F    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
3 s5 q% {5 y3 c' q/ q    if (v1 == v2)
        throw Error("v1不能等于v2！");
6 K  x  A# M& G/ @2 O+ E5 B
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
9 S# b) f& N! ~* ]1 ^        q = p;
        p = NextArc(v1,p);
& `+ E7 w/ F3 |  }9 F    }//找到要删除的边结点p及其前一结点q
4 K4 s8 q3 k/ N' X6 }# e! K& c
    if (p != NULL)//找到v1-v2的边
    {
        r=LastArc(v2,p);
        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
% G* T! R; g4 w+ _8 J0 F! m            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
        {
            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
# q1 Z) d& f* `4 h# s3 ?5 A            else
                q->nextarc2=NextArc(v1,p);

, C4 P7 B3 p5 h. z# M        }
7 Q" B! V& z: {% l        if(r==NULL)
) o- S/ _) s4 {, a, B            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
) r- G1 W# j$ Z9 n2 Y; ]        else
2 b3 U1 F* N& i/ N        {
            if(r->adjVex2==v2)
9 {3 o( @9 y  P6 {0 }3 d/ o                r->nextarc2 = NextArc(v2,p);
5 q/ L3 c6 g. p/ p, \* {            else
" l8 ?# c# `5 I+ k                r->nextarc1=NextArc(v2,p);
; D( [& Y5 \8 ~4 H- X( U        }
        delete p;
2 N3 n' P! p& t5 O1 X        arcNum--;
5 G) m7 G: k- G! p    }

& t8 _' R& s5 I}
template<class ElemType, class WeightType> void
9 q; V& D  `/ i3 @MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
{
: x, j& _  J3 p    int v;
; t" J8 [2 g0 r2 w( P; `    MultiAdjListNetworkArc<WeightType>* p;
- V2 b2 W# d9 v5 {" g    for (v = 0; v < vexNum; v++)//找到d对应顶点
' b2 s+ j- k! U5 p5 g3 }        if (vexTable[v].data == d)
8 B6 z( I# G: u7 Y4 g            break;
    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");

6 ~( T8 x3 k& ]    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
6 b0 j* K- \5 z' D/ P+ `        {
            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;
+ a4 `- o) E* }9 B7 B
9 }5 b- r/ @+ w# f    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
! T2 P0 M: c# z: o4 N    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
; n% W1 y+ O. I# @+ X    //原来与最后一个顶点相连的边改为与v相连
  e3 q$ y7 B& }# }" z: U    for (int u = 0; u < vexNum; u++)
5 S. @" P8 M, a- `  }* ]6 |2 a    {
        if (u != v)
        {
& j1 T- Y+ @9 G5 U9 u            p = vexTable.firstarc;
' u: G  [( N9 b& A4 y% X1 K            while (p)
$ V* L% i' y5 L" s% C            {
: f' `; h) [2 f: G                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
, r7 ^) r% y3 }1 f0 @) {" W                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
                p = NextArc(u,p);
4 f( a8 o3 D/ L# D/ A. c            }
        }
    }
0 `* ]. @& [- G) f0 J}
' E2 Q+ ]$ ~' i///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
) g- O2 q# Z9 E& W# T9 m    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
9 o' ?& ?$ o/ a- l8 \$ p/ e    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
6 A& |! \6 ^: ~+ r    while(p)
    {
: U6 n+ f3 e0 g( }        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
$ J9 s0 S0 I& Y$ {' |9 E$ x0 i  g        else if(tag[p->adjVex2]==0)
. Q- ]- ?& ?" D+ T            DFS1(p->adjVex2);
        p=NextArc(v,p);
" @. _; G0 |6 }+ k    }
}
* N8 E; D' R; l; vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
{
) ]+ I' y; {3 F7 e* j- l% q    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
            DFS1(v);
% ~% w! _; G, k6 t& ^: H* T6 [    }
$ F, Y1 y( H1 |}
" i1 q( B3 q9 L! n6 g* ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
5 |" n: p8 J! \    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
6 D7 \, z5 ~1 b    for(int i=0; i<vexNum; i++)
+ e1 `( f5 s& I, I2 y+ i( k8 I        tag=0;
    for(int i=0; i<vexNum; i++)
    {
8 {% B$ Y6 d4 S8 ]8 q1 N: t* e8 `        tmp=i;
; _+ r& M, K" J$ o        while(tag[tmp]==0||!s.empty())
, {5 o; a# j* I# n        {
7 d8 x) O# O* ]            p=vexTable[tmp].firstarc;
% C' [1 R6 N" z/ f0 o: J            while(tag[tmp]==0)
            {
                s.push(tmp);
                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;
- u: \: w; ~% F+ H/ I+ Y5 N            }
            if(!s.empty())
$ Q1 ?& L8 Q" T9 d) z+ O            {
                tmp=s.top();
                s.pop();
                q=vexTable[tmp].firstarc;
5 u3 d  d; D" t                int t=tmp;
                while(q&&tag[tmp]!=0)
                {
$ [5 x, k; G' r! M( o$ g                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
8 l/ L% B  v6 w( S                    q=NextArc(t,q);
                }
4 E% |: z0 ~8 }- c                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
; K2 v7 G( s) [1 J+ {                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
+ y  z% G- J, l% {# W  ~            }
        }
    }
8 m' }& N" T2 O# I+ c}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
# w' Q$ ^/ Y# S6 JMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
- y& Y/ T' ?9 X* S! B* X9 A; J5 x    if(head==pre)
. t: {. ?5 t% H        return -1;
2 n' o' L1 ]- G1 V  b! Y+ I- D
8 B5 c6 x" j/ `* n1 s/ i    MultiAdjListNetworkArc<WeightType> *p;
; T7 M8 F* Y& Z" ?, f    p=vexTable[head].firstarc;
. s2 }" K/ p! M" x6 `( v1 o    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
8 ], j/ B' W" P% I" P% @( g* i  Y    //pre!=-1&&p!=NULL
$ l& ~; V3 w% C+ V% g    while(p!=NULL)
    {
$ k3 Z# U% B! V. D        if(p->adjVex1==head && p->adjVex2!=pre)
6 n" @6 M5 r+ U5 ~6 V* K            p=p->nextarc1;
/ Z* c0 B' g$ u- S9 d4 ]6 N        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
; j5 J8 Q; A" p! k6 ^        else if(p->adjVex1==head && p->adjVex2==pre)
        {
& z/ {3 j1 ]2 r. y            p=p->nextarc1;
+ m9 V  V# W# {$ @0 g            break;
9 g* @! |* q. Q# z- S3 y  C. A  W        }
- o- A+ m! w0 c" z2 T6 P7 W! R! O        else if(p->adjVex2==head && p->adjVex1==pre)
0 |$ E  D7 k+ y9 Y6 l( C        {
            p=p->nextarc2;
            break;
        }
    }
    if(p!=NULL)
( E4 Z& u# I1 s    {
% I" F" Z  ?7 D( A$ V        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
; V: T8 l) z  y  c    else
' _- S. n; x9 u" Z# o; D/ j        return -1;
}
4 G0 r- q: V+ S2 b. y) O, p$ Z

; |+ M1 S& [3 y7 R2 C% Ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
8 Y' ~+ T& g- u) |0 q! m{
    stack<int> s;
& I; A# R# M- A; ~( l    int p,cur,pre;
0 n* H& J* ]3 c    //MultiAdjListNetworkArc<WeightType> *p,*q;
3 u+ I+ s; P0 [    for(int i=0; i<vexNum; i++) tag=0;//初始化
* L8 u  o# i1 d# C5 H
/ u9 U" w7 }  F1 z; u. q    for(int i=0; i<vexNum; i++)
4 T' r8 N9 R6 G! H: k& f8 Q    {
) a& ?' v0 F4 Z3 }$ U& C        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
; U. L8 D6 Y; E2 L& V            while(tag[cur]==0)
            {
( v* p9 B( g% h/ e( c                cout<<vexTable[cur].data<<"  ";
6 u# w# r0 }4 J! ^4 [5 W5 Z                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈
  z8 D5 C* ?- p. }- V) F: [! I
( b( ?1 B3 \3 t' Y               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
) a: Y6 a( j# _                   pre=cur;s.pop();
. p2 y9 N/ z+ b) H                   break;
) s) c3 u% D, |8 c3 `               }
/ s0 `) ^9 S! h               else
               {
# U0 ~& U, B- c, f; I                   pre=cur;
2 e( T* ~0 E- g) M5 L8 o                   cur=p;
# a  U2 u, I4 g  h3 @0 p               }

# q: k, v% O, c& v0 t( F2 Z6 Y            }
* q% n$ Z9 q( w8 p            while(!s.empty())
& K+ p: ~5 n/ e* ^            {
9 t, K$ @2 o2 T6 R                cur=s.top();
' J8 C- t' ~& Z$ Q2 J  i                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
" F1 R! }" r% ?/ |% ^                {
* I1 G3 Q4 L1 V3 r7 c2 p                    pre=cur;
5 z) o) D# C+ B6 Z, Y                    cur=p;
2 d6 b0 L% H) B! D; b8 y                    break;
$ A8 d6 [7 n5 v. e6 o, A. i                }
                else
                {
+ L% n4 N$ O! L                    pre=s.top();
                    s.pop();
. \! L1 V! o, E* x2 Q. i                }

            }
; F$ Q; T# Z; [7 }
        }
' J$ e' @0 J' ?' b  T8 i5 ?    }
  _9 ?2 y* Y1 \( m$ E0 b7 B}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
( q8 i  L, O/ w: g- Q# X, ~: ]{
    for(int i=0; i<vexNum; i++)
$ Z$ J- \5 T/ j) v$ x        tag=0;
    queue<int> q;
6 T; j! W. t+ D% c    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
  S5 P' O1 w5 H7 c9 }: t9 @    for(int i=0; i<vexNum; i++)
    {
        if(tag==0)
        {
            tag=1;
            q.push(i);
' a8 {4 z$ P: \' E            cout<<setw(3)<<vexTable.data;
        }
        while(!q.empty())
        {
8 d) Q. e/ O# R9 w( ~            tmp=q.front();
7 r7 U9 j4 n7 F% [            q.pop();
/ G& X  H- }& g! c7 X$ F            p=vexTable[tmp].firstarc;
            while(p!=NULL)
) |6 M& Z( `2 K( L; E            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
6 [' ~, t1 D7 a' \( o, t) j/ u1 j                {
                    cout<<setw(3)<<vexTable[t].data;
+ H( B8 J  L  s9 N+ y" {                    tag[t]=1;
3 v( ^$ i7 H, k9 i; K& O- h- K                    q.push(t);
; n  \: h, |/ Y/ V* ~: x& ^, n                }
7 x1 Z0 R1 |7 Q/ A) D  P                p=NextArc(tmp,p);
& J$ t6 U: y. _0 x: L$ Y# ]            }
        }
0 C3 A5 J! z* ?$ v$ h- S    }
. o& [( b, _- Y6 _2 @5 s8 j}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
) ~/ i2 Q% R8 f  q    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
) p) ^* u6 U/ X% ?; x( Z" T3 ~    for (int i = 0; i < vexNum; i++)
    {
        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
        while (p != NULL)
        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
( j/ d" U$ y8 I' d        }
8 s8 _2 f" v' K" c- z# s( |  {        cout << endl;
    }
}
' B9 X0 ~1 K9 z& n1 Y' v& H: {

6 b3 t8 V- ?% V0 ~1 f& }1 U邻接多重表与邻接表的对比
6 o% }& k, J% D# p- e- ^8 o
% L! g- k" c: {0 A* \( h* D+ ^邻接表链接
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
9 h6 T) [9 K! X, O为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
; s4 Q, e9 F# n7 C- y版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958



8 D8 g" r: X, \+ M, l, L/ l8 v
————————————————
1 Z- @5 B: _. U版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
. z( G' _7 p0 u0 L: x
7 ~' p; X  I) \% _+ L
, n' |/ m& g. J  _# U9 x