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

杨利霞

$ @% _5 l( g' T4 g  R图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构
% b% a, d& B9 w7 e* q; g! u) \$ w
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
! Y  o  l7 j/ A" E6 K+ E0 F邻接多重表的边结点类模板
! u9 R! N& G; d  V$ C" W% _邻接多重表的类模板
; X4 ~& n9 z6 \邻接多重表与邻接表的对比
& g/ t, x% i# x# s+ v3 V7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

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

邻接多重表的类定义

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

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

: ^4 |% c9 n# K) w: ztemplate <class ElemType ,class WeightType>
' Z/ \0 M% _: }6 w; p6 L$ tclass MultiAdjListNetworkVex
/ p# K, H8 W" {- m{
public:
        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;

        MultiAdjListNetworkVex()
( r) s/ f+ O; A6 {' W' N        {
2 g3 i6 L3 f0 [" x, p& R3 d- d                firstarc = NULL;
6 W3 q3 J5 t9 y  s, J: V        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
) H0 Y7 Y* t& G" Q4 J9 t        {
% o. G$ i/ f- D; Z; k                data = val;
. k4 F! ^: t/ d+ z6 l                firstarc = adj;
        }
8 @' q! i0 j8 J# V% u3 [! W, |) w};

! M" X5 s- f& t3 ~" ?- I) X3 n. g邻接多重表的边结点类模板

; w& y( {! g4 K( j在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
% Z# q: z( `* I) ^0 ptag是标记域，标记该边是否被处理或被搜索过；
% U. z1 P. R) ?- k& @weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
. J$ @4 G) ^0 h( F3 bnextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
! U+ m  U! B1 ]9 J$ o

template <class WeightType>
/ H2 G# k! A% Y& q; t) @class MultiAdjListNetworkArc
{
$ F. @6 A& J9 C; g( M: W# z- ]2 C8 wpublic:
% u' c( N; o8 _: z( O, b0 E; S    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
0 B0 D% h; I6 G# n  t' X6 T$ s1 r. C        int adjVex1;                                    //边的一个顶点
        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;
2 m+ F# ^) Y. E! n% Y8 `( h
        MultiAdjListNetworkArc()
        {
                adjVex1= -1;
                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
2 A+ t) g0 J8 F% ?6 Z8 n        {
0 M' |" C/ Z% u8 G                adjVex1 = v1;       adjVex2 = v2;
! w: s, s) B5 s7 Z% w; M, g- k0 t                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
9 E! N( B5 G. T$ T% {        }

/ \+ h+ I5 D$ q3 i5 z邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
1 Z" p% A( p- Z, a' n- N' y- nprotected:
2 x5 }4 i) d; ^8 o2 p$ W$ V    int vexNum, vexMaxNum, arcNum;
! |/ A2 a, w- J5 {$ O* ~) [    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
7 T# b4 [! k8 x; i5 @' B  |2 V    WeightType infinity;

public:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
% D: p4 A; l# k
% q  n# u  R* c- Y    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

' q1 |: L* @+ u$ i- e# x9 u  V" J+ F    void Clear();
    bool IsEmpty()
* f- |6 {$ [/ d  M    {
* _7 X6 G  C) p" o" x        return vexNum == 0;
    }
    int GetArcNum()const
    {
8 U1 [  P. C9 b9 Y& e. [1 a        return arcNum;
    }
    int GetvexNum()const
( D# u+ h2 O& T, z    {
; r9 @6 g+ S  p- z        return vexNum;
3 w% r6 |8 W. R6 a% x. Q4 D    }


9 v7 b1 O0 n/ k) O% i6 @* v    int FirstAdjVex(int v)const;
    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;
& C3 I: @% B* ~+ t0 }, `+ O. S
    void InsertVex(const ElemType& d);
5 T6 w3 b' a' ?# U1 C    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
    void DeleteArc(int v1, int v2);
! d- t0 k& N; x+ m
, ]) v2 [! {, S: N    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
, D0 G  S1 b( Z: |* x9 x9 X    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
+ y! x  I3 i, [) L6 n
    ///深度优先遍历
    void DFS1(const int v);
# q, G4 n3 l3 z8 P    void DFS1Traverse();
1 Q# h5 P- j8 U6 G% i    void DFS2();
$ O' ]) d2 B9 P5 K. u: m# s8 f
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();
0 u0 Q( \! z9 |: _9 z) w1 G7 O
    void BFS();
' w& l& E2 ]0 I, m    void Show();
};
; V! t- a) w# B$ q) v2 ^
5 e! f( n5 H. Y1 M2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。
9 Z2 d$ p9 O7 ~; I2 Y( n0 s
8 G0 H: Z5 ]2 ]# H4 k+ q4 r- z#include <stack>
#include <queue>

template <class ElemType,class WeightType>
3 k9 R: A  v" ]( R. v$ L* e5 |MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
3 ]" g& x# U) t( @; ]9 U# b+ R{
    if(vertexMaxNum < 0)
8 U0 ?% C5 ]' l0 O# w  H        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
" e% @, p1 c  V, p4 i9 |& Y$ I3 d    arcNum = 0;
    infinity = infinit;
8 D5 Q1 `/ ]. ?6 K4 i0 }* R    tag = new int[vexMaxNum];
, u) X# _: j( X" u. h0 R: Z4 G4 T. b    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
$ @8 b+ p3 t: H: x! L7 k9 b    for (int v = 0; v < vexNum; v++)
" J9 J2 ~/ x; a8 R$ E' ?% ]    {
        tag[v] = 0;
        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
$ ]: B7 p3 L! b    }
}
template <class ElemType,class WeightType>
8 u% p* l, x3 R# [* H8 NMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
# Y; F: ~, q3 Z2 N& N    infinity = infinit;
- @& A# m) A3 ?8 Z+ Y    tag = new int[vexMaxNum];
$ U% t! s- H5 N/ f, b    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
/ G' G3 c" q! Nint MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
" ~' o; O$ m& X1 h; d, y3 ?& F+ w{
    if (v < 0 || v >= vexNum)
% E; M' t. v% {) R        throw Error("v不合法！");
, {0 b5 g8 J! O1 ~" S7 |% k    if (vexTable[v].firstarc == NULL)
/ M' ^2 b  V) U" W4 E& t- g' z3 r: T        return -1;
( y" g" Y% ^. K! ^    else
        return vexTable[v].firstarc->adjVex1;
/ H( p( O* m/ N9 v8 }: C}

template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
1 ]$ c0 ^, {# u" d1 n6 p    MultiAdjListNetworkArc<WeightType>* p;
, T. [- ?3 T; O: R4 \    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
# E) h" @& a& }4 R  c* V# A    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
3 _2 H8 m, q5 o* ^/ G( m    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
6 ]& g6 F" {% B# B+ C' R    else if(p->adjVex1==v2)
) o! q. e; d9 c8 x' }3 q% O        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
6 t2 J4 o6 s: R9 `* a        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
! J' G0 Q, Z# ~; j4 R; Btemplate<class ElemType, class WeightType>
2 P7 a6 T5 o5 N% {: i. f8 uvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
" J4 \* B0 [: N) b1 j* d  `) k& p{
    if (IsEmpty()) return;
    int n = vexNum;
    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
    return;
}
9 v2 C; z0 p  ^template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
) P3 z4 _/ @7 W, ^0 [% ^2 n{
    Clear();
* \6 z0 d) f' s* N}
5 A5 m8 r# v. m5 y/ jtemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
9 c' C/ t0 Q9 X: S4 Z    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
# F: _4 B- H+ _* d8 |( Z    infinity = copy.infinity;
: B$ G3 z) T8 f! m' B    tag = new int[vexMaxNum];
) y$ Q6 }1 Z" D" D
. ]8 ?, _6 L* z, x) I5 K5 H( h& P; C    for (int v = 0; v < vexNum; v++)
* }; u8 }; f, Q9 W" H    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
1 K0 k  C5 W9 D# [0 ]        vexTable[v].firstarc = NULL;
( N$ y5 b8 B) z4 ^/ H    }
6 U3 X! N. k) s' Q9 u    MultiAdjListNetworkArc<WeightType>* p;
/ G8 T" D; I3 T) c. `$ }4 }
    for (int u = 0; u < vexNum; u++)
8 \) b1 Q& t4 ]- c    {
: x6 O# Z- w6 h$ @2 s9 a        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
1 K. ^& {8 f$ P  [2 [9 u            p=NextArc(u,p);
        }
, J0 a' N6 y$ P% n# R$ X1 d" C# U: ~    }
}
5 I" q+ ^/ a: f9 _1 E# L& Qtemplate<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
/ q& e+ m, T- d$ ]) D& c7 fMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
    if (this == &copy) return *this;
    Clear();
* N$ c/ g1 ?9 }% \$ `: t    vexMaxNum = copy.vexMaxNum;
3 m# M" p2 D/ m* c    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
8 u( f' F) y4 v! p; Q" N    arcNum = 0;
    infinity = copy.infinity;
: C% e; |2 D: W" S* a    tag = new int[vexMaxNum];

. t7 `6 R8 ^" X    for (int v = 0; v < vexNum; v++)
    {
% T3 x# x# o% \" T        tag[v] = 0;
7 Q0 Q. Y2 p# f% t- P, @" O        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
0 {. F4 r& y: }  K$ d    MultiAdjListNetworkArc<WeightType>* p;
$ U, w9 i5 R6 j: S/ k
( B9 W+ G; ~5 b: {) A    for (int u = 0; u < vexNum; u++)
7 x- [) b! W4 ?! C4 j6 D    {
        p = copy.vexTable.firstarc;
        while (p != NULL)
9 _$ W' n: ~/ y( @/ F9 _        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
" F% M  q  Q1 Y7 g( n3 a    }
4 |3 Y. C. X" o    return *this;
}
" U; j6 B3 f' }7 Rtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
7 a; r( V6 f# b/ ~2 _6 K& RMultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
2 `5 B8 N- u. m{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
% g* J$ B& P9 @% c! W        return p->nextarc1;
    else
        return p->nextarc2;
}
4 d0 A. C5 s( L6 Ctemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
) P- o0 Y" K' u- kMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
2 q+ S) p0 A, t    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
# |/ ^; `/ n+ @        return NULL;
    while(q)
' u- K; F6 ^3 ~( q) A    {
  E& Z# ^) s! D  e8 |6 ?        if(q->nextarc1==p ||q->nextarc2==p)
            break;
        q=NextArc(v1,q);
! m- _3 \" |& j4 R- r    }
    return q;
}
' K9 E2 ?( H7 S* M: q6 ~( Ftemplate<class ElemType, class WeightType>
  s* @* U8 b3 A- a1 [7 Pvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
" {$ Z& Q+ i8 a1 j4 G7 e    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
+ k3 d3 _: v" ], y( [1 \0 Y) l    vexTable[vexNum].firstarc = NULL;
, s) j0 A1 f" L; u    tag[vexNum] = 0;
    vexNum++;
' J2 K' I) n+ e4 g+ H}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
0 B, y2 Z# w* N    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
0 v8 N  k* s3 J. X" s  o6 b        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
# U2 j# \! r2 v! R    if (v1 == v2)
9 L- M& v, h5 G6 {6 e        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");


% y2 G1 [) p+ U. `. `    p = vexTable[v1].firstarc;
: ]0 a7 v; w& I( R& Q+ P* O    while(p)
) h9 t- e3 ]4 C! [    {
/ u; {  p+ {: z, Z" i# e3 W! t        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
/ {; z6 S1 x: R6 [0 N4 E  `        {
8 w1 w) s8 \4 P6 t! u' \/ c, H            if(p->weight!=w)
                p->weight=w;
            return;
  O. w9 E6 X! H: z( {( O- i        }

        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
) S% \2 `5 ~: F% g" W1 Q' e    q = vexTable[v2].firstarc;
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    vexTable[v2].firstarc =vexTable[v1].firstarc;
$ O3 b/ c$ c9 A; c' H8 {    arcNum++;
- P$ D) w0 Q3 z2 E}
3 y; t6 O1 j9 w& ^% ?% x- O
& {( O% E0 C6 v3 n+ a( o, n9 btemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
7 P. L( b3 k4 F/ o{
# U% ?* l7 S1 J  M' w5 o  J
6 i% D/ F& G/ L( v    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
. l$ l1 H) L8 Q( j, A    if (v1 < 0 || v1 >= vexNum)
0 T1 F- c# ^) L( V. v        throw Error("v1不合法！");
" [' S6 g6 p2 t- B2 c    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
2 G. u* l& q* B1 ]. j        throw Error("v1不能等于v2！");

. o6 y/ K7 S, p7 X    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
0 H# k$ t0 f' s% o# k    {
# e7 c8 s8 ?* ?! q: X0 `. V        q = p;
" k/ N' a1 q$ o1 `! e        p = NextArc(v1,p);
" w7 O) g) @8 |% v: f; s    }//找到要删除的边结点p及其前一结点q
: w1 b% D4 k, U3 l5 O0 W+ ?
7 w6 J0 `& E- O! e    if (p != NULL)//找到v1-v2的边
/ d' H$ k, Y0 U5 A1 p    {
  a8 t; P! _% x* [! |5 f& C6 g' Y        r=LastArc(v2,p);
; ^8 h$ m# p. m  A/ @# o$ {, F        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
* }, R$ Q# |8 G0 @4 @0 m, g* w' k                vexTable[v1].firstarc = p->nextarc1;
& u6 V$ g6 i: B% u1 s  P            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
        {
- \# v3 w; A$ R- s! ?# R- k            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
  A! Y0 D. ?$ r            else
8 z: O; s: c6 A, c2 r9 A" X% {. Y                q->nextarc2=NextArc(v1,p);
0 Y7 V; I5 t  X9 o$ {7 h5 f
3 T+ S9 q" w6 {; J3 p        }
3 U" Z) S" ?" [        if(r==NULL)
2 j% Y: o9 s9 e            if(p->adjVex2==v2)
1 Z5 m7 n& K9 r                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
+ J/ r" I: L& z' J1 Y        else
        {
4 G1 _* `% R1 s" G! }4 ]% F* b" Z            if(r->adjVex2==v2)
3 o4 R! D, x9 v9 ~, d& d) l$ L                r->nextarc2 = NextArc(v2,p);
            else
$ d2 A& @- U' v5 x6 M- I8 S' {# j                r->nextarc1=NextArc(v2,p);
        }
1 H- [1 \/ _% N7 {- ]9 @$ c8 a        delete p;
* P/ Q( R2 T* _- g, N        arcNum--;
    }

}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
; L  M9 h: ~; p) z{
    int v;
# ?: v# k1 ~5 a; ^% M    MultiAdjListNetworkArc<WeightType>* p;
3 m% Q0 `" E3 z4 e6 m& S, [0 C    for (v = 0; v < vexNum; v++)//找到d对应顶点
9 X1 P0 w7 {( _6 n        if (vexTable[v].data == d)
5 h  a# `" `# ]' i4 g( y7 f            break;
    if(v==vexNum)
' H, U+ p/ ?) |/ K        throw Error("图中不存在要删除的顶点！");
; ]! V, J* |( b/ ]( ?( J' ~6 F
: x( x/ C) s' g: o3 z4 T- d    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
        {
            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;

$ Y- e. Z1 f2 z9 m' \; X# i    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
; j# i) Y2 P5 M) {( Y    tag[v] = tag[vexNum];
    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
% o/ U1 K5 W# i: l; w' a- A- q    {
  O* ]. e6 y' ~        if (u != v)
$ A% U! |6 m; c$ M; d6 y        {
            p = vexTable.firstarc;
2 B9 L$ U$ @/ F" _' E  j            while (p)
            {
0 ]4 G  g! p4 i' _& Y/ G                if (p->adjVex1==vexNum)
2 w' S+ D) K/ X: C  V                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
4 o5 l9 g  O) B: }8 U# |                    p->adjVex2=v;
: T" V( a' D( }2 }* u* R                p = NextArc(u,p);
# [$ n( d* }, C: A9 x0 }( _8 y2 W            }
9 m; p9 Y) |- t: \' r# e$ U; c4 a, w        }
    }
; c, p  d& D  q) Y}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
, m* J/ j. e0 c9 F    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
* b+ H; R8 t5 v  J0 e    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
6 w1 h, @2 H6 y% H2 t    while(p)
    {
        if(tag[p->adjVex1]==0)
* U/ }& K$ w5 ~1 S1 ~* s            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
        p=NextArc(v,p);
1 P# |8 J0 ^5 E$ e9 `1 |! E" l    }
* X) m. ^9 X) a+ @: u& d* ^# w* v3 H}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
{
& _  T8 ~0 C" w1 o6 q* f5 U9 B    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
            DFS1(v);
    }
$ R- m2 g( ?& f: c9 K, h' r}
% L7 X( F! x) M* R! g; [' T/ ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
8 j0 n' y  t* [2 F    int tmp;
, Q3 z6 C6 i9 c0 ~    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
        tag=0;
' @5 }/ k6 O, F% I6 f" o& F( N    for(int i=0; i<vexNum; i++)
$ U" w% z- u4 J8 U1 E  J% f2 A7 S    {
( r# M+ J8 \9 L( z- \8 g4 v# E        tmp=i;
9 `5 n' i" S' [/ o3 v8 l        while(tag[tmp]==0||!s.empty())
3 _' e7 ~; Z$ @( ~' Y" K* \        {
            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
                s.push(tmp);
4 N6 n$ d! y7 Q$ c" O                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
& e$ f$ X- v9 _" z  R                p=vexTable[tmp].firstarc;
* Z1 k1 Z8 J1 L5 J5 O                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
            if(!s.empty())
            {
0 h, C$ d% I+ e8 U9 J7 L, v: b                tmp=s.top();
# _, H! n2 b* {                s.pop();
                q=vexTable[tmp].firstarc;
                int t=tmp;
                while(q&&tag[tmp]!=0)
' L+ m, Q  z1 K" h                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
; ]4 e& b" M& o- A: k                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
6 S. Q5 [7 l3 I2 E                ///tmp要么等于找到的第一个未访问节点，
( T0 w4 p: @1 [9 }- ]2 `& e. B                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
- g2 |: ]" N' g% o/ q$ _        }
    }
}
( F7 E4 A4 l' s% K/ ]" w' |" F//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
* @: q6 y3 l! j  sMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
& y- z7 L5 `8 D# N- {9 M4 R{
    if(head==pre)
        return -1;
% ~" X0 u4 g0 x7 T
1 r0 ?- D( n3 j) y, [* _. s    MultiAdjListNetworkArc<WeightType> *p;
8 I1 Z* P1 P( X    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
; h: {4 t+ |& x% n, S. r7 {    //pre!=-1&&p!=NULL
    while(p!=NULL)
( P+ S3 P$ O6 ~    {
        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
- n/ h1 J+ `) a6 D) ?            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
8 @, e+ J6 p9 S1 o' C9 }" w        {
+ G, n# m' O, s            p=p->nextarc1;
! m3 w% p. x) A/ y! K" i* u( T            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
5 J/ e6 t# W( b( a1 [        {
            p=p->nextarc2;
            break;
( B; @6 O2 s2 @        }
    }
; a3 |! a0 Z6 c  }* ^+ \    if(p!=NULL)
7 A1 g! y/ w5 ?/ u! V    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
    else
$ \$ L( z: ]5 \0 J        return -1;
}
  h) z8 L0 U. S: n6 m
# ~2 E8 k7 J" p0 a+ X7 n
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
+ Q/ A6 C: \8 I( h1 u& P{
    stack<int> s;
    int p,cur,pre;
+ l% Q4 l. J8 Z5 X; o5 M2 }    //MultiAdjListNetworkArc<WeightType> *p,*q;
7 M$ T, N0 R- L! q) i: @9 t    for(int i=0; i<vexNum; i++) tag=0;//初始化
# f9 U5 S* w; r
5 P1 W7 x; q) g4 i    for(int i=0; i<vexNum; i++)
    {
0 X/ T) w6 ]5 R  K8 n$ n* s        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
) B6 d# t( D; o" |( g6 O) ~            while(tag[cur]==0)
            {
" P& v5 e% O) d                cout<<vexTable[cur].data<<"  ";
/ @, H* k/ B/ c) B& o, s. @" }                s.push(cur);
7 K" W6 t7 Y; l/ e9 }, l                tag[cur]=1;
; O" F% v4 M0 T1 i& A               //初次访问，标记入栈

  y/ Q& {) V" H" G6 j: E               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
/ w: T, e) l/ ]6 @                   pre=cur;s.pop();
7 {) Z, i& x6 F' j                   break;
               }
( s  p' h9 }. u' x' x               else
$ x1 f. e/ s: B" J1 m0 j               {
. i- v% C% P6 m, i  m9 m( i: S  W                   pre=cur;
, M* P( h8 n! `6 N. F; |2 l                   cur=p;
5 G! C+ Z4 j' s3 p4 X               }
4 D6 q: k9 h! @& A. L: K$ \
            }
2 z3 O5 c3 C% z6 H: L9 c6 ~            while(!s.empty())
2 D& U/ p' o* i5 I+ k            {
                cur=s.top();
! h6 w! c( _3 y# b2 R                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
                {
2 T/ a) T1 J5 G8 @5 T                    pre=cur;
( ]0 `3 [7 f$ [3 a* Q. ?( p                    cur=p;
                    break;
) Q$ ?2 H& o$ W3 @4 A                }
  A$ e. a. @* _' W) t7 z% i                else
                {
                    pre=s.top();
3 J% t( Y4 l0 m2 o+ |( a. k                    s.pop();
                }
0 E% A* B  G- M. j- Y7 F
            }

1 ]6 x( X  x. F- z' z        }
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
7 {  B3 W' C5 \( [{
    for(int i=0; i<vexNum; i++)
        tag=0;
    queue<int> q;
    int tmp,t;
2 }6 j6 {! G* G/ \    MultiAdjListNetworkArc<WeightType> *p;
" D5 N1 F/ p" ]! c6 x0 N* C, s    for(int i=0; i<vexNum; i++)
    {
        if(tag==0)
        {
            tag=1;
            q.push(i);
4 U: D9 p, n- P% ?$ C* [/ s) L            cout<<setw(3)<<vexTable.data;
        }
) I7 `$ P6 t: {& T9 b; F* B        while(!q.empty())
0 T) Y6 |4 O9 D% Y: ~! d5 |# l3 D        {
' m+ C/ J" J6 M; U9 y            tmp=q.front();
/ I4 d+ W7 f6 L            q.pop();
            p=vexTable[tmp].firstarc;
+ F0 w2 q( S: e3 ?" b, w3 u            while(p!=NULL)
8 y. C. x' z8 W/ W9 G5 n            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
" ^0 S( H5 R5 A                if(tag[t]==0)
/ H( E0 D& R% u" q$ p' b) Z                {
0 e3 r- k8 ^0 s                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
                }
                p=NextArc(tmp,p);
# B; Z# Y! O* z; n            }
        }
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
! D4 a0 z; o1 \/ O# \9 U9 j& g    MultiAdjListNetworkArc<WeightType> *p;
; d" \  }4 f( N! h1 N4 R( b5 q* W# Y    cout << "无向图有" << vexNum << "个点，分别为:";
4 I, |# v3 F8 F# O& m2 n    for (int i = 0; i < vexNum; i++)
        cout << vexTable.data << " ";
    cout << endl;
5 i- C: L; h0 U5 V    cout << "无向图有" << arcNum << "条边"<<endl;
4 W4 E% T2 q7 l8 W" @2 l    for (int i = 0; i < vexNum; i++)
/ r) @8 [8 r. z7 R9 U    {
; u# Y& _' |* q& [5 H        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
        while (p != NULL)
( d* o# h4 X5 V+ S3 r6 g1 P        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
  V" k+ u+ I7 H        }
        cout << endl;
( a' A! d4 ]- {! x    }
}


5 U2 z% V6 n5 c, r# B' G+ O; |邻接多重表与邻接表的对比
8 R" {3 s0 E/ M+ z9 s, F
邻接表链接
  S0 S8 o  ^5 E: I# Q在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
* G# X# U# q( `% \  o————————————————
- W  k# J% N  t+ z版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
. j9 j  r7 x: c8 y* A
" x7 f, q' A* i

0 R5 w7 O$ m" k7 I) ^* o
( M% L* v! e. r. D————————————————
: V, l2 m7 A2 e版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
2 M0 A' u9 M% I8 Z1 d
4 X/ Y) W4 a  b
' v9 _% r9 U6 D/ j6 ~