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

杨利霞

+ R0 W, ]9 b' j: |) ?# g4 a0 }图的存储结构——邻接多重表（多重邻接表）的实现
4 r. ~4 g9 ?+ e& N5 `* V. m7.2 图的存储结构

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
& a- R* T5 l: s邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
. p! r7 ?) q" g2 I, B5 T, ~  b邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
! X) |' C# V( R, \) q
" e$ X* l; g# r. R在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
+ U- x4 z/ G" n( ~4 Y$ }在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
5 I4 P  Q% e& ddata域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
0 S% P% s0 i; t  g% ~所有的顶点结点组成一个顺序表。

template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
- t- ~# Q2 O2 ?$ r" g0 r6 f' |- \+ V{
% @# X7 y7 f% x4 A- E5 Vpublic:
        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;

5 J5 ]6 a2 L3 H        MultiAdjListNetworkVex()
3 k0 t* G6 Y) {  A& c* z0 C" u" c        {
                firstarc = NULL;
        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
1 Q1 T# `+ |, y) k9 S# q        {
4 N. G7 f8 ^5 s                data = val;
                firstarc = adj;
        }
};
7 q/ v* C. T% v2 a& P1 o7 c3 W* }
邻接多重表的边结点类模板

在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
. D2 o" |) \8 @& w. B- ^0 Qnextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
( ^  Q: R. k" e1 C
4 J8 S4 k5 a$ S2 r) M
template <class WeightType>
2 N( W; D( t, l+ t/ Cclass MultiAdjListNetworkArc
{
9 i$ a" G7 H. H$ ^. t) Kpublic:
    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;
1 j- i# H: o, s6 w9 K
        MultiAdjListNetworkArc()
        {
                adjVex1= -1;
                adjVex2= -1;
        }
        MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
- U" r, S3 {8 `( i7 G* z3 |        {
                adjVex1 = v1;       adjVex2 = v2;
( C) u+ t) `% y6 b                weight = w;
                nextarc1 = next1;   nextarc2=next2;
                mark = 0;           //0表示未被搜索，1表示被搜索过
        }
' _, Y+ A5 K5 Y: K) r; u
邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
" d/ y) }  {" W% R! w- hclass MultiAdjListNetwork
# b4 E7 M/ o+ q/ X{
% }9 @( ]: ?; k% o2 C; Wprotected:
1 i" X& P9 G" b5 V0 ^    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
4 f  T, v; ~, p8 N    WeightType infinity;
7 Y2 l* n/ B! u& {
' O2 k2 t3 V8 ~# j! Z' S8 x# @public:
2 _* T( n$ ^1 b+ b" b; X    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

/ q, e8 [9 L) r$ p    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
1 ?$ k5 y- y4 x: j; m! p$ J, r5 K
4 h, c, S. ^9 ^' t& A' N) k    void Clear();
    bool IsEmpty()
( c1 X2 \: N* Y" z5 C0 w0 M    {
        return vexNum == 0;
% W8 a/ q9 [. D& Y5 @: ]0 m: {4 K    }
    int GetArcNum()const
9 `+ Y1 z& H  R0 b2 {$ g6 Q0 y7 T    {
        return arcNum;
    }
% l( ?/ c1 \. k3 X2 |, Q( u    int GetvexNum()const
0 G0 y+ {; b1 Z# @' f' C1 [( I    {
        return vexNum;
    }

2 k, i% L; }+ G3 ~6 m+ T* R3 v  f
' `7 q; L( z0 u$ i/ E    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
" ?+ Y4 _& |0 F    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

& i9 n& ^  c) O& S, x    void InsertVex(const ElemType& d);
    void InsertArc(int v1, int v2, WeightType w);
. u' g; L' ]6 z5 n2 P' w& D
7 W4 Q. r$ E- C    void DeleteVex(const ElemType& d);
    void DeleteArc(int v1, int v2);

- {/ W+ |6 @% z4 k    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

    ///深度优先遍历
    void DFS1(const int v);
    void DFS1Traverse();
0 {, U6 |1 z. x- L! `3 O. J    void DFS2();

    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();

; s8 i( Q9 A* F    void BFS();
    void Show();
2 m5 G% ^+ x8 z6 L3 w. i};
# \4 _. Y/ W2 h$ m6 M
2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

#include <stack>
; v7 V9 H! d& L/ Z1 s#include <queue>

6 T3 F& f1 U0 k4 {6 Btemplate <class ElemType,class WeightType>
* M, O) U; G  v( K* ~. j+ G& HMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
0 y( v8 K: J7 B, x{
6 L; ~, U9 S1 ], p8 s9 V    if(vertexMaxNum < 0)
5 L, M8 S! t% W6 I; \1 \        throw Error("允许的顶点最大数目不能为负！");
& @! Q5 c) S; y% U( T    if (vertexMaxNum < vertexNum)
* N0 w6 d* h; v9 p) L" w# N        throw Error("顶点数目不能大于允许的顶点最大数目！");
9 _, o" ]  C$ y    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
% g( c# Y, ?! g' g; ~4 `1 P) `    arcNum = 0;
; C0 {7 h4 n; Q9 a/ i2 @" h    infinity = infinit;
    tag = new int[vexMaxNum];
2 X0 g1 V' l" y; p6 T1 @) W    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
5 O; `! @& a3 L/ L# L    for (int v = 0; v < vexNum; v++)
; X- O# i- R$ @    {
        tag[v] = 0;
5 s6 [, H7 G8 }& X        vexTable[v].data = es[v];
8 c. q: Z+ c" |2 `+ _1 B        vexTable[v].firstarc = NULL;
8 M+ o! i+ `* S6 |$ o    }
; P; \" J2 l6 G2 D& Q! ?0 R$ x6 O! O}
: w" T& b6 d7 s) ptemplate <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
; y' s# f% `4 M0 P  ?# y! Z{
  ?/ B1 X8 z* a$ ^# o( J5 d    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
- [7 m9 k. [0 f    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
% d& u6 P* [, w  r( x    tag = new int[vexMaxNum];
! [; D4 f8 W& X' j    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
& u. s8 N2 P4 c) a4 Q0 h}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
    if (v < 0 || v >= vexNum)
& z$ X) i$ {6 e  x, R7 E7 ~' C        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
    else
        return vexTable[v].firstarc->adjVex1;
}

template<class ElemType, class WeightType>
4 [* [+ s- q" P, _1 Hint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
' K+ A' N4 K0 \1 x    MultiAdjListNetworkArc<WeightType>* p;
! \3 j4 D3 c4 v' P    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
: Y+ V8 p7 _, t1 R: T) r        throw Error("v2不合法！");
& Y/ w) D/ H7 X) D    if (v1 == v2)
9 Q, ]# R3 P* k# i: z" p1 T        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
, T" c3 y6 {2 I+ _    if (p == NULL || p->nextarc == NULL)
. E0 {0 i* a* L6 D* [" {; A        return -1;  //不存在下一个邻接点
0 _" E; a  ]5 S9 T& L3 A    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
6 N2 o' I+ A& u$ n6 j2 O: o& Z    else
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
    if (IsEmpty()) return;
9 U0 K9 {, \2 z' Z& n2 s    int n = vexNum;
    for (int u = 0; u < n ; u++)
3 v( F: a( |# t8 t        DeleteVex(vexTable[0].data);
    return;
}
( w; X1 D: Q; G1 L  Y* H* Stemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
}
$ D% d" ~: i, @template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
0 u3 P6 y+ x$ G9 A    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
. s4 j" l# [) P# s4 }" D/ D    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];

% ^) @4 I$ ]( Q* q5 O3 O    for (int v = 0; v < vexNum; v++)
' `* u2 x' W7 }' _8 `    {
3 L" h. z! E2 N2 T        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
( N8 O2 R; x8 R+ m9 E    }
    MultiAdjListNetworkArc<WeightType>* p;
$ I7 R4 G" \9 U; u9 q
8 v* n% ~# Q7 M! L& c$ n, C6 b! k7 ^    for (int u = 0; u < vexNum; u++)
$ g( [( j! n4 n7 `+ S/ }    {
6 P# }- ~8 a& c: G, n0 V% y  S        p = copy.vexTable.firstarc;
3 y/ T# ?+ D, T1 ^. ]        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
0 C7 Z0 E; @: s+ K" i& |2 ?2 i        }
1 [( A4 j6 C7 x, N% e7 F8 K! L    }
}
8 g! \, M1 L6 G) @template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
. X& L4 Y1 ]3 l$ P  EMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
    if (this == &copy) return *this;
$ S! H1 }2 ~5 R2 R1 i$ f    Clear();
6 N, e+ T; c; l- D9 \6 Q& k; J7 C    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
5 G! X8 ?! O4 I9 @0 n# u7 G    infinity = copy.infinity;
    tag = new int[vexMaxNum];
" T7 _- G/ r" j. K3 v
    for (int v = 0; v < vexNum; v++)
0 W$ t8 k& s; J    {
8 I2 I3 c5 U. H/ A1 C( D        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
7 z( z, a  M' r3 U. r9 x        vexTable[v].firstarc = NULL;
' p4 c1 z5 U1 T$ W    }
9 {( j1 L/ a! J, S( e$ G! R    MultiAdjListNetworkArc<WeightType>* p;
4 B) I* D7 g2 Q# n2 H' u
    for (int u = 0; u < vexNum; u++)
    {
* t/ H" s$ N  `/ D        p = copy.vexTable.firstarc;
9 Q" g9 K6 s/ g3 A* A5 l' K        while (p != NULL)
4 R* {; O, n  |        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
7 U+ r3 k" J' x" R" B# p            p=NextArc(u,p);
# b3 `! h+ W4 e+ a  i        }
1 B' h  `) |/ R8 I! k5 Q- A/ ^    }
7 v9 |  ]5 T# J2 l* b. @    return *this;
}
" Z2 D$ P9 K* {( j) Ntemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
! F2 g8 l5 O  U9 f    if(p->adjVex1==v1)
6 Z0 I! C. }. b- P: A3 A5 i        return p->nextarc1;
    else
        return p->nextarc2;
}
1 ]- ?, n1 A$ S" C( r, @& Wtemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
6 g! D; K5 c$ s2 ]7 BMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
6 T) L9 t3 R2 J1 j6 o& X: Z: d    if(p==NULL)return NULL;
" L7 X$ f3 i' D    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
    while(q)
. J/ p( Q7 O7 ~, l! `  a    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
1 d" Z( n5 h/ z# u2 [' k        q=NextArc(v1,q);
    }
    return q;
}
- J& S# g: y5 `6 l8 C2 ^template<class ElemType, class WeightType>
5 Y! C; j, X3 x+ l: U; b! Fvoid MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
" I0 @7 ]- L  ^* W! Z& L{
    if (vexNum == vexMaxNum)
: ^! q, V/ L/ f- W5 w  L2 ^        throw Error("图的顶点数不能超过允许的最大数！");
/ t1 `* i" j$ @2 o2 |: q    vexTable[vexNum].data = d;
$ M+ j5 ^$ e8 o% o. f$ h4 I    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
8 ^& K% |9 u$ Y* P# U    vexNum++;
9 F. N& h5 d2 `  z, P' U}
template<class ElemType, class WeightType>
, \, y) m6 g. l. R, R4 A$ S( Bvoid MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
4 E' S% d) @, y) d( |{
: \% h- F( [' h    MultiAdjListNetworkArc<WeightType>* p,*q;
, H) Z9 Z+ Q1 A5 F8 _+ h8 L    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
& F- I% x* F% t; U/ \) W( e4 v        throw Error("v2不合法！");
    if (v1 == v2)
# g& ^) W1 r* ^) V/ p        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");
: s* S# d) o- Y# J1 K8 r3 P
/ R5 J2 ^3 w4 h2 ?! [
" @/ X( e" p3 J    p = vexTable[v1].firstarc;
* a# X% ~* F$ y: l7 l    while(p)
    {
  j2 i  n6 i- M# [# t3 @        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
4 s0 p, B# F2 j        {
6 h) w) I, i5 z) ~! R; c            if(p->weight!=w)
4 N. R! O7 m& K0 @! r* s                p->weight=w;
            return;
8 N& j7 E% u5 Y  N1 B+ B$ [: c. ^; ]        }
  @2 Z6 }  I' `: ~0 @& U
        p=NextArc(v1,p);
    }
8 v6 Q/ \, f  C6 J! S0 o3 O  ^% _2 I$ j    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;
( V$ \6 D0 M4 I& O0 j3 Q" ^    arcNum++;
3 a. [8 \: x" K1 B2 ?" L, M: T5 x8 l}

! Q3 `- l  N2 x. Wtemplate<class ElemType, class WeightType>
* l) \+ d0 P/ ^0 evoid MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
. ~8 P+ n0 g( s$ k{
. x# c( U* V7 d. r2 R* r: F7 F
    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
0 P: v* s4 F& X! \' v" _+ g5 q8 t    if (v1 < 0 || v1 >= vexNum)
% H" {4 k0 J" S% P' T! Y        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
: y1 t: N' K% K        throw Error("v1不能等于v2！");

2 R6 o) Z6 ^) v) J    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
3 v# s/ u2 A+ ]# V. ?/ h: T8 G- P        q = p;
; N. ~; Y& }0 B6 L% k( N$ h        p = NextArc(v1,p);
# X% n5 x5 e" t8 R7 V  b, W    }//找到要删除的边结点p及其前一结点q

0 r8 Y5 h- G! d* e% a    if (p != NULL)//找到v1-v2的边
    {
+ K% Z9 w  l$ s2 t! U% }1 g. x        r=LastArc(v2,p);
% v5 Z, s) R# H- v        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
" t+ v# f* H, B, z        else//不是第一条边
        {
9 F% `9 ]* ?. \" z            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
            else
                q->nextarc2=NextArc(v1,p);
5 o1 v: Y: y+ A% @1 h& S% B* O
        }
        if(r==NULL)
6 x: Q% P9 @- N& q            if(p->adjVex2==v2)
7 P: u+ B5 J- u. ~9 H: q# [                vexTable[v2].firstarc = p->nextarc2;
2 a' J& z; i# a+ z. n8 s6 J: f            else vexTable[v2].firstarc=p->nextarc1;
: O. s" L" W# J* c; u+ a        else
        {
) W- L8 V; X9 f& R, \0 y            if(r->adjVex2==v2)
5 i& e, A) c, h& x1 x3 L. ?                r->nextarc2 = NextArc(v2,p);
            else
9 N$ _- a" N  d                r->nextarc1=NextArc(v2,p);
& a# V6 N! T  g+ O7 Q1 k        }
        delete p;
        arcNum--;
    }

}
4 I$ G# Y! L" Mtemplate<class ElemType, class WeightType> void
; E; E* Z9 p4 n- c# Q6 dMultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
3 C0 k; W3 f8 n{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
, U! j! f% Z" j" U3 g        if (vexTable[v].data == d)
            break;
% ?+ A% K8 @" N. H+ U: `1 @    if(v==vexNum)
1 K. Y% h+ p, ^2 ~5 j        throw Error("图中不存在要删除的顶点！");
( w% C! U2 w  f$ R
    for (int u = 0; u < vexNum; u++)//删除与d相连的边
, E* J; B1 B4 k  R* y) |        if (u != v)
        {
# n& f) [  j/ i            DeleteArc(u, v);
        }
# w6 b  T; j' P' R: |5 ]' h( @  R    vexTable[v].firstarc=NULL;

    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
% `  W9 q" E% C9 l$ f& o    vexTable[vexNum].firstarc = NULL;
# C: b8 S+ S4 E' n4 m    tag[v] = tag[vexNum];
5 u6 w$ |( ^3 m4 a$ H    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
- h; E( {8 d5 X: E2 {8 I" i! B, Y        {
            p = vexTable.firstarc;
            while (p)
            {
                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
3 q) m7 R1 `6 w3 {. d                else if(p->adjVex2==vexNum)
: b' K' F( ~9 V1 }" O                    p->adjVex2=v;
                p = NextArc(u,p);
            }
( _- `# b, ~! u6 B6 z) m        }
    }
}
$ @: X- C! r% C5 ^2 b6 X) `///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
% w/ i7 ^, Q, y{
! U1 Z3 e4 Q7 `1 `5 _6 r/ Z    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
, R& ?" u6 p1 \1 p    while(p)
  O; L' }  f" g- r  n# S- F: j2 r    {
        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
3 z! N' B2 r8 ~2 s3 Z- R            DFS1(p->adjVex2);
        p=NextArc(v,p);
' n2 D( ?. h( t6 b6 L2 u2 L- ^4 c    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
; a8 x2 X2 r/ a) K7 w{
    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
            DFS1(v);
    }
3 i- N- t" J2 R' z' H* S}
; @5 J, c2 ^+ h% U4 n, }9 G4 q- D6 @template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
; u  ?8 u; t& V0 Y; H' V$ y{
4 {; D2 ~) B. S) i9 [    stack<int> s;
    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
, O" f5 D) b: _9 a    for(int i=0; i<vexNum; i++)
        tag=0;
$ w! o3 x  f0 f3 i6 R; s- m    for(int i=0; i<vexNum; i++)
    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
/ Y  v" m# z/ Z+ @0 f( _3 \! j        {
+ q% J7 D1 y& W+ X3 m$ p            p=vexTable[tmp].firstarc;
, q3 z3 @0 l+ ?: i5 A! Y+ ?            while(tag[tmp]==0)
2 m' Z, e3 n" ^. c            {
                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
9 G" O  ?2 D" P0 {) _% i' _                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;
4 R- Y4 v! Q% E& b            }
            if(!s.empty())
/ v& q3 K& j; a9 c# e& @+ O9 Y            {
3 T. s4 J( _$ K                tmp=s.top();
! E6 a& `3 R: g* e' K6 i, H                s.pop();
. T" ?( n+ t% S% o                q=vexTable[tmp].firstarc;
                int t=tmp;
- P; V. Y5 _8 T  c8 K  J: Z5 c                while(q&&tag[tmp]!=0)
                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ v; [7 j- o4 ?, l5 S7 E( M                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
0 [( k8 T) e4 l/ ?; c                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
2 ]; M3 J& ?3 m" T$ _% w: J6 c* `                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
1 ~! q1 \- E+ |: k                ///要么等于与t相连最后一个点（已被访问过）
/ ^; z: V1 Q" M! u9 M5 F& `) N                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
1 }' S5 ~" v3 ?4 E- t! F; @            }
        }
    }
( l' E; s/ W4 j& ?4 a- C}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
/ Z* z: ^3 V" ftemplate<class ElemType, class WeightType> int
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
& C* y! a- k! r1 }{
    if(head==pre)
0 ?, w# _0 _& b! Y4 Y: q        return -1;
; `. n( K  W2 B- C3 E1 N
    MultiAdjListNetworkArc<WeightType> *p;
9 H% G7 I$ H, c. J    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
% v: r7 d; {2 ^7 [        return p->adjVex1==head?p->adjVex2:p->adjVex1;
: t2 E, |4 Z& ~: X- d" R  }    //pre!=-1&&p!=NULL
    while(p!=NULL)
+ `' R' R$ D$ `) K: d3 X, d. B# B% q4 _    {
        if(p->adjVex1==head && p->adjVex2!=pre)
+ U. t; {: J$ P. \7 f% I8 e            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
" A* [( w, k) g0 E/ Z- I8 y3 B7 L        {
! ~) W1 G( E: Y7 @7 @3 D            p=p->nextarc1;
            break;
        }
7 f& I6 x/ X! D5 H        else if(p->adjVex2==head && p->adjVex1==pre)
$ [- p) m6 d6 y0 `6 w3 V& j* o        {
2 D3 M5 N! Z( O7 W# w  e" P            p=p->nextarc2;
            break;
; n, b% ?% |7 {  b3 ]. b2 V4 N        }
& C2 w) {3 k0 _) \' J5 |/ a6 S" ?1 H5 a    }
    if(p!=NULL)
    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
    else
" E* U5 R& t) s( _( ]        return -1;
}
- s6 n6 L- l* i) t9 P0 ^  T. b

: F5 K! P6 U% X; gtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
/ r+ \+ P, Y) X0 D- b$ D{
    stack<int> s;
4 U2 E6 d7 q( q" u; T# H" @    int p,cur,pre;
1 Y8 e* A9 v% `& b9 k0 E: P5 M5 g    //MultiAdjListNetworkArc<WeightType> *p,*q;
+ j) c8 N* v4 k1 U    for(int i=0; i<vexNum; i++) tag=0;//初始化

    for(int i=0; i<vexNum; i++)
    {
        cur=i;pre=-1;
8 f$ S8 ^# d! q' t+ C8 X        while(tag[cur]==0||!s.empty())
4 g+ J" W* c- V/ u6 V, F" i        {
            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
2 ~, I+ Q. j9 R) \# _. e                tag[cur]=1;
               //初次访问，标记入栈
3 l# Q6 v; d% ~" w& s
               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
                   pre=cur;s.pop();
1 |3 g2 j  {. F1 J2 k) f$ k! h! w) k6 T2 P                   break;
" e  [/ J/ p# _# Q0 e0 c9 X               }
& I+ G" v% y2 \+ N, e0 ?# \: i+ ]               else
               {
                   pre=cur;
7 ^; W  @' I; O$ P                   cur=p;
; Z1 Z, z% r% ?6 ?7 H2 o               }

; t! Q1 r9 A+ e3 k5 ]9 H            }
! q; t" e+ G0 L3 _            while(!s.empty())
5 V. t, l* J) S* U  c( _            {
                cur=s.top();
                p=GetAdjVex(cur,pre);
2 ~! ~. K6 R3 x8 p; k                if(tag[p]==0)
                {
: T3 V$ K  {! q, G" q, o                    pre=cur;
                    cur=p;
& Q, ~; T0 N7 M2 ?, ^; J, S% ]* |                    break;
. ~9 q( E# ?1 P7 x0 d. }/ z/ g                }
                else
                {
                    pre=s.top();
                    s.pop();
/ v6 W$ F( o% ?  ^4 `0 P- w- @                }

            }

        }
  f: \' q2 b/ T/ u: |5 f    }
% _+ X- ~) U) n: i! d/ C# M}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
3 J- T: j3 _' L9 a, X$ {1 E2 Q. _    for(int i=0; i<vexNum; i++)
        tag=0;
    queue<int> q;
( N8 a% z% F. e6 }6 F& h, X1 t    int tmp,t;
3 Q: E* C% l/ q1 v) ~* N5 x' [    MultiAdjListNetworkArc<WeightType> *p;
8 ?( e% c: c, |8 n  _0 R  k- Q    for(int i=0; i<vexNum; i++)
    {
        if(tag==0)
5 ]: l3 W* U& P/ d: B0 X        {
) t  O! Y% J7 D& A! ?7 j            tag=1;
            q.push(i);
8 v' K( h. [6 L9 r' e            cout<<setw(3)<<vexTable.data;
        }
        while(!q.empty())
        {
& P0 x+ H) E  H; n7 L2 }3 A, s  s            tmp=q.front();
            q.pop();
: L1 C+ P( J( e9 I+ ?" W$ N            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
8 k% C: |9 i  l, @0 X- u                if(tag[t]==0)
$ Q9 n9 M( l, h# t" N" `+ S                {
                    cout<<setw(3)<<vexTable[t].data;
, D5 L2 p0 q. V- L+ W8 m5 F                    tag[t]=1;
; n% ~1 m; d" a" [                    q.push(t);
                }
                p=NextArc(tmp,p);
            }
        }
1 j: L* U4 E3 \/ k3 j! ?- X( l+ g/ t    }
}
3 Z/ f% c: N$ Z& ^7 }' A* e( ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
, L' O, T# p, m{
9 D5 y# u+ T- w. _: l! J: O% {    MultiAdjListNetworkArc<WeightType> *p;
- ?: o/ V, L% s2 v( o* ~    cout << "无向图有" << vexNum << "个点，分别为:";
! X) k% q8 W$ W' s! U( E  u    for (int i = 0; i < vexNum; i++)
9 P* G% f" {- `( j  f( Q6 ~" [) ]        cout << vexTable.data << " ";
    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
1 d& M4 K9 R3 G0 ^2 o    for (int i = 0; i < vexNum; i++)
1 Q# A& u  u. o+ L) E* ?' |    {
# }. ?) O; X( _7 R/ m. U  p        cout<<"和" << vexTable.data << "有关的边:";
2 k' }' z# X/ O: K        p = vexTable.firstarc;
$ m' P  H2 Y, w% j* G. }        while (p != NULL)
8 ~8 s9 g& E) Q2 K) L- o# O# Z" [        {
4 ]6 w, v! S& U2 ?            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
& C+ u% G  a3 y( w- v            p=NextArc(i,p);
  Z% j4 Q/ d& t  o) [& h) }. P        }
        cout << endl;
    }
: [2 a- O) k- q}
( G9 X, v& r9 G& a" L9 s

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

" g& M! _$ F( ?+ l9 `3 p- _  T0 i邻接表链接
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
' p7 I4 ^( J) Z在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
9 v( A& l/ C. c' O$ d  k" J9 P为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
8 I8 h- v5 z" ]1 ~版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, Y9 L& ]/ z( \! A

8 f0 q; Q6 t7 E2 I& d7 Y  U9 Z
- v. o' L" z/ d% Q' Z8 P
————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* Z( N' ]2 o" }% n

: N0 r. d8 o+ V: Z6 C