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

杨利霞

: W" @& r( o4 f图的存储结构——邻接多重表（多重邻接表）的实现
& G) b. T$ l; I7.2 图的存储结构
- r  F! Y0 C5 {6 z
+ [4 \* @$ ]/ {9 }3 U! C$ A7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
5 ^( e: G2 }$ @7 h8 W! q! X" b邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
! Z% w# b& Z$ K& p7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

$ |8 L! E. ?* Z# `4 G- w在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
* O1 o4 j8 l6 y$ \/ }) I2 v! S+ R) Z在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。
0 h  i  r3 P; j$ ~! O
% Z7 N8 S5 L! }  G1 f) b邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
% m' t6 U) `: ?- H) `+ W9 U% ffirstarc域是链接指针，指向第一条依附于该顶点的边。
8 p2 d4 c& U; N所有的顶点结点组成一个顺序表。

/ v$ p9 J+ o# H7 \/ q1 ttemplate <class ElemType ,class WeightType>
; X. |) S" n3 }' A& u  H/ [class MultiAdjListNetworkVex
{
1 U; U7 Y( ?; `3 q( X. x# j7 Ypublic:
# Z2 o9 E$ p; f        ElemType data;
3 D8 B* ], Y& a, j/ N        MultiAdjListNetworkArc<WeightType> *firstarc;
% W7 q: }7 U% [. z: U" R  I, {! {3 f
% W) e, T# W7 h; ?        MultiAdjListNetworkVex()
' Y- d3 H; l8 g0 U/ O2 H, o        {
                firstarc = NULL;
        }
: W+ Y. I% R; W        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
        {
                data = val;
                firstarc = adj;
        }
' b& F4 b" J, J& n& `7 {" y2 G};
' q# J+ Y. z# L) R
邻接多重表的边结点类模板
# a& i( D6 t. D# U# N% Q
在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
) O7 `3 W0 z* M% L/ s, t5 N# |tag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
1 ~1 V  G4 [9 l# Jnextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
  Y  A  I( T+ X* c1 S9 N( u

5 i* J1 s) u4 a, Y6 x- Vtemplate <class WeightType>
class MultiAdjListNetworkArc
{
public:
' C/ j+ B3 V& Y7 a- j- y# `    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
* r# ~. R# I1 z* E        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
+ |4 [  C' F5 H/ _' |" Q6 k! `0 U        MultiAdjListNetworkArc<WeightType>* nextarc2;
8 ?: V. m5 h5 I$ L
/ |! r9 j. r$ b$ Y        MultiAdjListNetworkArc()
        {
2 A4 l( C: d9 j$ R9 \3 {9 p                adjVex1= -1;
  ^6 u* ~  p5 A; H% a8 @                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
        {
                adjVex1 = v1;       adjVex2 = v2;
                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
        }

) D) \$ ]& y  L: ?邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
# c# E. A% e0 ~) g- I5 X% ^  eclass MultiAdjListNetwork
6 d5 Y: Z: D" H, _# h2 \1 D1 H{
protected:
8 ]  _8 j* b" r! T3 n6 F' x8 Z    int vexNum, vexMaxNum, arcNum;
# x  }0 q9 Z% |; o1 _    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
/ \" ]- f( F/ _    int* tag;
/ }1 i1 \! c* q( i6 M    WeightType infinity;
& @8 a6 I0 W, c8 G- f; m3 p1 {
public:
. z% Z' o2 Z& W% x2 y) W  ]& X    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
2 g8 A( L& u# T6 v7 z
    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
& Z( e& ]5 p9 d& |4 T; E) Z
$ }6 L6 Q3 _- W; c    void Clear();
& G) c* r1 c0 |/ `% O    bool IsEmpty()
6 I* K7 a& x. P9 o9 }7 q    {
        return vexNum == 0;
) y5 B8 K0 t9 N& P, |+ K" G    }
6 J7 z9 H( C$ v+ D  K. K    int GetArcNum()const
    {
2 _6 h/ C4 v6 |$ {8 m" U! k; b        return arcNum;
9 D$ [# ^9 j' n    }
4 [0 b3 y4 W- I; V( y: Y0 W; _    int GetvexNum()const
1 p( l! M$ B3 ?! O+ m6 k    {
. K4 ^0 p9 Y6 N7 c: H" ^3 v3 C8 K        return vexNum;
    }


5 C4 e  u; o# {. h# y* O    int FirstAdjVex(int v)const;
: @! ~9 J! v  i; S    int NextAdjVex(int v1, int v2)const;
) p/ ?( F% B+ ~    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

/ |) w1 t; l5 ?: ?* R    void InsertVex(const ElemType& d);
    void InsertArc(int v1, int v2, WeightType w);

! i7 m2 C$ ?2 Z    void DeleteVex(const ElemType& d);
    void DeleteArc(int v1, int v2);

! k6 m% w3 Z  K  e' `6 n9 r    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
) ?, R' D: g' d3 j8 ]
2 S2 @* g* F; [4 t; v' K    ///深度优先遍历
    void DFS1(const int v);
3 S% T8 K- l2 P    void DFS1Traverse();
! K; q4 S* [; c5 ]/ w    void DFS2();

" L  g% d2 J3 |, x    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
& A% r7 ^3 R" _8 X1 y3 N$ o    void DFS3();

$ K5 _) s+ c2 [% m; V6 N8 a    void BFS();
    void Show();
# @, B( [# t# n! U* f};
6 @# b" E/ k8 C8 y
/ L- o) l4 a$ l# r& k2.函数的实现
' N5 ?; G8 q: I! `) }研讨题，能够运行，但是代码不一定是最优的。
9 ^2 x% j  o1 V' Y( L
7 I2 P0 r; v" C. T" O#include <stack>
#include <queue>

template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
6 S+ z, x- ]/ {, o& B  o    if(vertexMaxNum < 0)
1 h! `( Q1 d0 v; ?+ b$ @        throw Error("允许的顶点最大数目不能为负！");
7 |% Y4 m) O) e: r( o0 _    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
4 U& B6 R) b$ F" `2 X9 ?    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
3 m3 v. [: F% p9 A" {1 O! a3 L    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
1 }5 S1 z. a' M# |9 \    for (int v = 0; v < vexNum; v++)
    {
+ `: s2 j+ }- W. Z4 z/ F/ H4 Q# N        tag[v] = 0;
+ b- q/ q8 E# M! I2 y; {        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
    }
$ K7 e8 \. t/ i# R" D}
template <class ElemType,class WeightType>
4 u1 _* b* P: C0 f3 u1 [& n* wMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
  ^% O' c6 D/ n" c# M: s{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
  s7 L9 R2 T: s4 H+ d1 L    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
+ L3 @8 C9 v* i4 _% e    infinity = infinit;
    tag = new int[vexMaxNum];
9 ]5 p1 G+ l2 m    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
* i( u% ]: {9 j& a) N( o4 ]}
, P* s5 M) ~' j' _7 m. x  l( ^) l" c9 ytemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
& n; E. M* J. _+ Y# q1 Z% v{
    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
    else
        return vexTable[v].firstarc->adjVex1;
}

( N6 n0 Z3 t* _5 }/ Btemplate<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
" b% G7 X' `6 J; _' E& M( p& `{
, o1 S" [( {3 o    MultiAdjListNetworkArc<WeightType>* p;
. Y+ W) g( M4 x' J6 `    if (v1 < 0 || v1 >= vexNum)
) ]3 \2 Z0 Q2 J        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
  t& a. P) [, p, Q    if (v1 == v2)
        throw Error("v1不能等于v2！");
! ]' I9 m5 e$ w9 l% z    p = vexTable[v1].firstarc;
/ L3 A' a9 F6 H8 a    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
, Q. ~! R% k1 W$ U3 x0 ]        p = p->nextarc;
2 f" Y/ s/ ^$ u7 I5 x2 @5 t    if (p == NULL || p->nextarc == NULL)
" N# `  V  _3 C) P+ d) f$ Z' K3 L7 ~        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
' \* I* o/ n) \, F    else
9 \/ @0 x/ x6 @! [% {        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
' p9 U8 o2 Z" [, A: Tvoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
) N3 {, @" [5 L. W2 Q    if (IsEmpty()) return;
6 L  z- k! h2 B* G  }1 c! K    int n = vexNum;
! K7 Y7 [" _7 b2 p9 L) _2 R    for (int u = 0; u < n ; u++)
* b- I! i6 ?4 `3 j: M        DeleteVex(vexTable[0].data);
* V6 p  n+ Z; ^" Z- }    return;
% g1 d* J3 r- I/ l, ?& E6 t' i}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
5 d4 S) K9 u' G' g# Y- t}
template<class ElemType, class WeightType>
# w8 [" ~1 M+ s% O* d9 ~. w5 mMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
    vexMaxNum = copy.vexMaxNum;
: t. L/ I3 n; m0 ]    vexNum = copy.vexNum;
7 @% Q$ R7 O# r+ K    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];
2 T( U8 s% E& J; C. ~( v) D
' Z' r2 o$ Y" }    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
& I$ W- E6 ?$ H% [+ ~% n, {6 P        vexTable[v].firstarc = NULL;
! X2 A0 Q+ c6 Y1 J) t/ z/ n2 z' H    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
! B8 H8 |: H* m) n3 u    {
. h3 n' E7 h. \! f  u. k# J+ d        p = copy.vexTable.firstarc;
: ^7 R! @+ a4 `: E7 {        while (p != NULL)
  e, T4 x) S3 h        {
8 F, X  u; i% P6 I. p. C5 G            InsertArc(p->adjVex1, p->adjVex2, p->weight);
. t8 g- W" X* P( b0 h; F$ Z            p=NextArc(u,p);
4 i2 H; g7 j, H5 K4 H        }
6 y, K" N9 g7 s' J8 n    }
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
% Q; a9 e; u+ E' `MultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
% b  ^1 y3 z+ }6 k    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
+ f; z! L) n# R( K% M" S$ u    vexNum = copy.vexNum;
  M7 j2 i$ t! l2 n9 K    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
+ @, b1 c1 ^) a% M    arcNum = 0;
) j3 \& K: L! Q% O: Q( {    infinity = copy.infinity;
1 r! X  t; [0 w6 b* S, v    tag = new int[vexMaxNum];
  U: I+ I3 o( _3 v0 u. U/ S7 z( }5 Y
! J$ L; g/ P2 w& B" E/ e    for (int v = 0; v < vexNum; v++)
5 d4 k/ b4 g  O    {
+ A! G* b+ \4 I& S        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
8 U- Z, D. p# Y    }
% b1 q0 Q1 S7 J- \9 H- {    MultiAdjListNetworkArc<WeightType>* p;

! g& G: S2 g: q$ M; n" r    for (int u = 0; u < vexNum; u++)
    {
, Y8 O; U4 ^1 ^        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
, Y# o, ?; L4 z" E2 s" `% P            p=NextArc(u,p);
7 W* ?* w9 e( e. k7 Y' ~8 z# d7 G        }
    }
; [' g) o( G: u* q5 a0 }    return *this;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
) ]0 I+ d. A  L! L{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
        return p->nextarc1;
    else
0 |9 d; J; K; S% w, U# U$ a        return p->nextarc2;
3 @; m3 t/ i3 ~" @4 {: S}
. t, Q- e  |# L  {! Htemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
+ Q5 X7 g: U4 n4 O* n{
    if(p==NULL)return NULL;
& I( b+ c: D- P; v" B* {. h    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
5 d2 p6 K! _0 t4 g, C    while(q)
3 L' _& b$ x6 U5 m    {
        if(q->nextarc1==p ||q->nextarc2==p)
  T9 p" U& F) `% g8 S* V            break;
$ s, o% \% V' h6 J0 S6 V        q=NextArc(v1,q);
    }
, V2 L$ q. S: c1 N5 F7 E# P& k& s) a    return q;
}
( v$ ^2 L( \5 M" ntemplate<class ElemType, class WeightType>
) ~9 \4 z9 Y! D2 n( Svoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
) w5 R1 s: ?# F) K. a, e& N    if (vexNum == vexMaxNum)
' o# J" ^9 z$ d( m. ?$ e3 _  g        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
2 E! O0 a  @: Q$ }    vexTable[vexNum].firstarc = NULL;
6 K! y% o7 S" d3 I    tag[vexNum] = 0;
& _: N- e% r4 d& @: P    vexNum++;
}
1 n3 S( C$ Y. g. X& ^" o) Ptemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
# [$ @, L+ B+ t0 ~{
* h: m) ]' T7 {7 }/ }$ L9 [% v& o    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
0 j, }+ m6 }' \  a2 @' U    if (v2 < 0 || v2 >= vexNum)
3 h. P* i2 I$ q- V" M  L8 T- ?3 ?        throw Error("v2不合法！");
    if (v1 == v2)
$ k6 P1 u5 _/ y/ q/ B        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");

3 o$ E; u5 W" D% B' v& }
    p = vexTable[v1].firstarc;
/ h9 _" p' X$ H/ D7 u7 R+ O    while(p)
    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
/ @: @: ^7 J1 Q2 S( Q            if(p->weight!=w)
$ m, b7 H5 k- {$ x, B% x7 t0 N+ Q                p->weight=w;
            return;
6 f, U+ I/ O" Z6 H3 b+ X        }

9 q3 V. c! F# y% H* E. j6 h        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
* q3 Y& C6 C! x) G; W, C# a5 L4 U    q = vexTable[v2].firstarc;
" F; Y, S" n2 [: G    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    vexTable[v2].firstarc =vexTable[v1].firstarc;
) g# q/ s9 g* a3 ]$ N" }9 t    arcNum++;
6 _2 S9 _9 n" a' U6 `}

template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
" j! Q3 G- W2 ~; t7 h{

    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
4 r6 w6 s+ m" {1 ?( e( n0 V    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
) D. W& {/ v5 i* a; \
    p = vexTable[v1].firstarc;
6 K$ m# y; y7 d/ G  V" U    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
9 x) Q* x( b" f; m0 L    {
* n% S" k! T/ F        q = p;
2 r* l/ u9 F3 `0 i        p = NextArc(v1,p);
# D2 H) N$ h4 y0 N, Y8 b' u    }//找到要删除的边结点p及其前一结点q
$ W( q! Q$ L& B6 l% J
    if (p != NULL)//找到v1-v2的边
- q5 n$ W( L8 c5 L- r& _) Y    {
        r=LastArc(v2,p);
& U# @$ ^. k) P6 g" {1 G, L$ i        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
3 f" u# Q  Y  \# c& \$ n, ?! n            else vexTable[v1].firstarc=p->nextarc2;
. r1 K: _' \' Y, l* |  {        else//不是第一条边
( H+ ]# O* F: u& i" i        {
* y0 R5 F2 o, ?            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
; U' P9 o: J+ C( @6 [  {            else
: w8 T8 U4 v! e' H3 n                q->nextarc2=NextArc(v1,p);

3 M2 L- O1 N: b        }
        if(r==NULL)
9 w8 W% z7 x$ ?- I            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
+ C+ S) K# J$ u# I' I9 K            else vexTable[v2].firstarc=p->nextarc1;
  A) O7 Y# O3 K9 c# `        else
        {
9 ~' k- Q# F2 D            if(r->adjVex2==v2)
, L  k  S& ^% r8 O                r->nextarc2 = NextArc(v2,p);
; e3 q% H6 k* t, {            else
                r->nextarc1=NextArc(v2,p);
. Z) E. L! j$ D* b% ^6 M% M5 N3 e! X        }
/ W; Y8 W6 A9 \9 H        delete p;
        arcNum--;
# j7 J( U! ^+ e8 Y# u    }

# S' D" W. P. q3 t% k}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
{
$ g& {% ^' H. k7 t    int v;
) u, {7 h1 H% F! U4 e    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
: ^$ R& F4 d0 V- s0 g% V3 R, q            break;
* T/ C$ v0 Q1 {" E8 \; ~    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");
1 c: ~0 t, A5 Q
    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
8 E+ Y: x% }) w" W        {
+ P* T$ ^5 f9 ~2 ]            DeleteArc(u, v);
' O3 H+ o! d8 @9 j/ Z- ?) a        }
    vexTable[v].firstarc=NULL;

% }8 v3 h. Y1 y9 O. E  z" D4 k    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
$ y" e, K' e& m0 s    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
! U) X+ Y- U4 ^% K- ?" J    tag[v] = tag[vexNum];
    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
    {
& a1 h8 X5 N, ^4 e& Y1 i" ^* M8 f        if (u != v)
% E/ l( a9 N) s% e7 N6 z; ^2 @        {
( R0 I& X5 T0 o! D            p = vexTable.firstarc;
            while (p)
! W2 T' M$ W0 d3 ]5 k5 w2 l* C* g            {
                if (p->adjVex1==vexNum)
: p" R0 `7 j9 J7 P% H                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
' y, q7 _6 s, O5 i                p = NextArc(u,p);
3 t7 e, f+ r( k! z$ @, a            }
" `' m7 B. P1 C$ ^8 Y* s        }
    }
8 x2 D% U) a5 R  Z}
1 c3 y. C* t, _1 O. K///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
{
    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
0 u+ P$ Y' b! H6 c# r    MultiAdjListNetworkArc<WeightType> *p;
% i0 k  T' u5 w4 M    p=vexTable[v].firstarc;
, o! ?' n. L6 T1 k* T3 s6 J+ e1 W    while(p)
    {
3 W' ]1 C2 D) F' E        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
4 M; r% X5 G6 ^        else if(tag[p->adjVex2]==0)
8 j' I2 ?( f5 F& Z0 R0 {            DFS1(p->adjVex2);
        p=NextArc(v,p);
' X9 M) o/ H9 ~$ {3 T    }
: k' G' v1 T3 l3 y( v2 |}
9 A" Y+ N( l5 ~; G& @* u+ Jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
8 \- y# D0 P* s4 R{
    for(int i=0; i<vexNum; i++)
' ]( f- d7 f+ s2 ~/ ?; v  w$ f        tag=0;
+ ^- r7 D" v- o/ F    for(int v=0; v<vexNum; v++)
3 B! ?# G9 F/ E. D0 w    {
* }6 B6 L1 ^/ c- H4 G; i! X" w5 u6 s        if(tag[v]==0)
( M! W! `2 }/ ^1 u& f            DFS1(v);
4 ^+ r9 ]0 E. E4 Y    }
}
! ~  b, `' ?. f& |. rtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
{
    stack<int> s;
4 J( K0 \5 w  O6 V8 z" N    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
9 d+ W9 v/ [% U+ t, L( J. S9 t        tag=0;
    for(int i=0; i<vexNum; i++)
+ M9 X* a+ p" E: E; w8 u  c# I    {
4 p* M" h. V. h) H9 a! m! E  S4 `        tmp=i;
        while(tag[tmp]==0||!s.empty())
5 n- {8 P( ~* {% p        {
7 V3 `/ `2 \) m; U9 [: r" I            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
  B5 n. j! I5 C$ P- X/ Q            {
                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
  [8 b# B. e1 p: f" k1 o, y                p=vexTable[tmp].firstarc;
3 {3 ]0 J, T1 Z& l                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
            if(!s.empty())
  w/ ]2 L! [' v! ?% n            {
                tmp=s.top();
7 V9 r; ?3 c/ h                s.pop();
6 x/ |1 E) [0 a8 y( a, X4 Z                q=vexTable[tmp].firstarc;
, V# `2 G( _) \; W" n# G4 M9 m                int t=tmp;
) G( |- H9 E2 h5 [                while(q&&tag[tmp]!=0)
                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
- U' b9 _8 a1 E                    q=NextArc(t,q);
                }
# ?# |2 M* E# A  M5 F                if(tag[tmp]==0)
0 @$ s' |2 [& z- u                    s.push(t);
9 k  R$ k% X5 e2 q9 {' t% j$ R# l                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
3 w5 Y% C) x  V                ///tmp要么等于找到的第一个未访问节点，
* j9 Y2 S+ ^4 u4 P8 H1 F+ w                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
( L1 i4 G5 q9 q8 K& H7 A2 |    }
! f9 b( h' a2 \# L; Q# ^* i}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
8 @5 O  i5 G+ wtemplate<class ElemType, class WeightType> int
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
* Q0 c) f  s; q) J9 I    if(head==pre)
        return -1;
. j' [5 m9 R. T9 e! M1 E, P
2 C5 d* v6 t' l$ ^3 J$ t0 v    MultiAdjListNetworkArc<WeightType> *p;
" {  L/ W  h3 J6 P* V" u0 q& ^' k    p=vexTable[head].firstarc;
% n( ]6 }4 `( X0 y    if(pre==-1&&p!=NULL)
; M2 B  O1 o" [& c. E7 F" Z/ O+ H        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
2 F3 N  w7 k: R, K$ M( D( e& \    while(p!=NULL)
    {
5 Q" `; _1 ^8 S, l        if(p->adjVex1==head && p->adjVex2!=pre)
; ]) s8 I0 A; W$ g6 N            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
! ~2 N; h0 K: @. E( x2 o. c* B        else if(p->adjVex1==head && p->adjVex2==pre)
' @) f5 W) n% u) J' R9 X+ ^6 b        {
! f7 D7 q! f2 p1 I2 X; H' G( Z            p=p->nextarc1;
            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
        {
, y3 S6 [4 W" N) V0 m5 o) R% x            p=p->nextarc2;
( Y4 d. y% J8 w" z, n6 N% I            break;
        }
$ ]% R1 l+ e' ?1 o" b  |' Z    }
    if(p!=NULL)
$ H5 S9 B, ^7 l4 o    {
, U- \: p+ T2 V8 Z        return p->adjVex1==head?p->adjVex2:p->adjVex1;
# N! {% Y& |4 m- {$ @    }
    else
1 a2 t" q3 B  t! p; r3 g5 N        return -1;
}

2 U- Z/ s& `$ ?  D0 H
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
% p. O: Q! ]  \( h; m2 U    stack<int> s;
    int p,cur,pre;
) {, C6 P/ r, [$ Q% M& H; N    //MultiAdjListNetworkArc<WeightType> *p,*q;
9 v8 a4 ^; w7 |0 i- ]& e    for(int i=0; i<vexNum; i++) tag=0;//初始化

  C9 n" j1 D4 L+ r4 |# ?7 e    for(int i=0; i<vexNum; i++)
8 Y5 X6 u! i! R& N) n    {
        cur=i;pre=-1;
2 B& x  C- w) {& [2 ^% \        while(tag[cur]==0||!s.empty())
2 c9 `! l& N4 ]5 `. ~        {
9 N* b4 N: h8 i$ c, H8 K5 X+ |            while(tag[cur]==0)
            {
' ?/ q$ v; B. Z5 d1 k) [! A$ D                cout<<vexTable[cur].data<<"  ";
" k- C8 U4 F; H9 k- ?- ~                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈
/ }9 q, J" J- C: X$ r- P% Z% q
               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
  r+ E! T# c/ p  P" [               {
4 L, y! j1 `9 k/ I. P! I                   pre=cur;s.pop();
* x7 c0 U, P& J- e                   break;
               }
               else
               {
                   pre=cur;
% B* n( E: i8 ?% q6 {9 D9 y                   cur=p;
9 m. w, Y+ t, `; ^8 ]               }
* ^* _+ G# E  s2 u! D5 e3 r
; Q; Q9 H) \& L7 U: F1 {8 C            }
9 w- w( P8 D; ]3 a            while(!s.empty())
/ g4 z: \0 F9 r' e2 `' W4 p: A" M            {
                cur=s.top();
                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
" Z7 J2 h6 p" d7 ?                {
                    pre=cur;
4 _+ Q0 c5 e2 h5 c$ i; a                    cur=p;
                    break;
+ d1 l  S/ r9 u) k! n                }
                else
                {
5 e  R1 S0 G  k  x$ u( N* t                    pre=s.top();
                    s.pop();
2 V8 k/ ?/ b' R                }

            }
% M& A, v  O9 `9 ^9 o7 s$ y
        }
( p1 K2 \' p8 U& L4 x; g  A! g    }
7 C# ~1 I- J: _}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
5 n" I# y3 C7 w: D4 Z4 s! o" ~    for(int i=0; i<vexNum; i++)
        tag=0;
6 b. ~' D  }( H; c! n    queue<int> q;
* L+ o. |  r* U& [: I    int tmp,t;
- E$ f6 A; n9 J- h! ?1 O0 p    MultiAdjListNetworkArc<WeightType> *p;
7 a* T% F& d  B* k+ l( e* Y( g2 e    for(int i=0; i<vexNum; i++)
( Q5 P, J# Q; W. Z2 @6 m    {
6 S' D0 o9 _6 ?9 T        if(tag==0)
        {
/ }4 y/ t) F0 p            tag=1;
- y6 \0 m/ X- F2 q, H% b3 j5 J            q.push(i);
  z  F- c+ s. F- h1 I9 T            cout<<setw(3)<<vexTable.data;
9 T/ w8 N; c  I4 |& Z1 s9 G        }
1 i# B- B: E0 _* C        while(!q.empty())
        {
            tmp=q.front();
            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
3 H+ L# [. P4 n5 y            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
/ W( F  P  J+ `. g' F! ?                if(tag[t]==0)
+ h; f. v- T$ q                {
                    cout<<setw(3)<<vexTable[t].data;
& q+ t6 u: k3 t2 U                    tag[t]=1;
                    q.push(t);
8 Q3 z/ S! j0 A( {- u                }
                p=NextArc(tmp,p);
            }
        }
$ W$ Y' E. Y' j    }
4 i& ]* `1 H( w}
8 K, |8 @" u! g3 |' Z$ p; f( \' ~8 Mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
% {) l7 K! f/ H2 E{
    MultiAdjListNetworkArc<WeightType> *p;
& b' {4 d5 T' s/ J" ^; N    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
5 E! g0 Y0 n1 k$ `8 ~2 ~( S2 K        cout << vexTable.data << " ";
    cout << endl;
0 O+ R- e) {; `/ g    cout << "无向图有" << arcNum << "条边"<<endl;
6 \2 X6 C- q8 U! c+ K' \" H    for (int i = 0; i < vexNum; i++)
9 W+ }/ Y1 U" ?    {
/ {0 V' g( ^2 d6 m; d9 D) X        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
        while (p != NULL)
        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
        }
+ m' y  R0 w  s1 v* G8 j, ]1 k, ?8 V7 l        cout << endl;
    }
$ H0 w% b: ?; n0 R" U8 Z}
; r% k: M7 t3 b9 a2 e. C
1 [2 y( h& G  t9 ^" B7 Z
, P8 ]+ p; l. s; y" v1 Z, L邻接多重表与邻接表的对比

6 ^$ U( t  ]' T+ Y" V邻接表链接
. i' e& a/ k' s2 H& c1 T/ I在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
9 Q: A8 q0 c" L% B  z7 K" u9 [为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
( S" N- W$ K. R, i+ y2 `$ l6 l8 O
) A) D, F5 a( S


' K) |% g; B& @( D' k8 U————————————————
7 l- N) ]' ]; d/ z' @, c版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
0 @( R9 R+ i8 R; c5 l# r, i+ _
8 g8 [& I# H. M+ z