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

杨利霞

5 W  m& n0 B( j* Z- A1 o% z: `图的存储结构——邻接多重表（多重邻接表）的实现
) [. q+ R* d  m  ^, u! O7.2 图的存储结构
' H4 P6 C' L, i: c( Z) T! P
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
$ {0 k% Y$ q$ ~% Z( _# h4 Z' g" |( O邻接多重表的类定义
邻接多重表的顶点结点类模板
# H1 F: d7 |2 W- n8 V6 h0 ?邻接多重表的边结点类模板
邻接多重表的类模板
2 M# \- z' _* i' v邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
: {7 g: c9 j! e# m4 M, I
在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

$ s, R6 i' x# N+ s, D邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
data域存储有关顶点的信息；
firstarc域是链接指针，指向第一条依附于该顶点的边。
; C0 n6 C1 @3 q- v; ~2 T/ X* R所有的顶点结点组成一个顺序表。

5 S" @3 V1 ~- M, c' X
+ g6 L# D3 J8 d* T0 Rtemplate <class ElemType ,class WeightType>
. U" f# ?( m- c) {) \& kclass MultiAdjListNetworkVex
{
public:
        ElemType data;
        MultiAdjListNetworkArc<WeightType> *firstarc;
( T( X3 E) H) _/ x: Q! m
& F; T& Z, y# V( f% q        MultiAdjListNetworkVex()
* I, l& a; {6 Q+ o3 h* Q# f3 Q8 f        {
                firstarc = NULL;
        }
        MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
9 J4 v0 q2 j/ L8 v0 {* k6 @        {
                data = val;
  c2 C' |  a% z) q                firstarc = adj;
+ M) P9 D$ |6 C        }
};

/ o! E: n# S# j  w. _: x1 Q4 [" U邻接多重表的边结点类模板

在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
5 w$ \7 r- @" p1 qweight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
+ n. V. [0 ?3 Xnextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
- g) r4 T0 S6 N! g
7 K/ R2 Y5 {* x, e# `! l, u3 b: r  F* A
template <class WeightType>
class MultiAdjListNetworkArc
{
4 ]' g: Z6 t4 _3 j, W' Qpublic:
6 W/ O; P) u+ X7 x' i$ P$ O. ~    int mark;                                       //标记该边是否被搜索或处理过
        WeightType weight;                              //边的权重
        int adjVex1;                                    //边的一个顶点
# ^; B) q. K7 ]        MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
        int adjVex2;
        MultiAdjListNetworkArc<WeightType>* nextarc2;

        MultiAdjListNetworkArc()
2 n8 k' b" G% C& d5 Q3 J& T        {
                adjVex1= -1;
6 _5 Z$ g2 D- w$ x                adjVex2= -1;
  c6 c8 D0 L- ]" u3 f        }
. y; i! |' s6 A/ n        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表示被搜索过
        }
, O: n1 i6 \" N* q& Y# I7 M9 g% z
0 _0 ^# P% U$ [5 M5 T$ Q邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
% P4 P: I7 ?+ N2 e" \{
protected:
( Z  n$ n, {! x% f. L% ^9 g! o3 p    int vexNum, vexMaxNum, arcNum;
2 W* H9 f/ r# K1 m' g% G; `5 N! G1 b$ |    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
* {7 v8 w3 _  _" i. i    int* tag;
    WeightType infinity;
! [" O+ x% Z% o' O/ @4 n; a% h
public:
# C. Q+ E1 V+ }6 [) E    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
* D; _5 b. b0 d
& a0 C8 z5 p/ |8 J5 Y    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);
6 B) ^0 |5 f; g- ~* h
; B; I$ z' b4 O    void Clear();
    bool IsEmpty()
    {
; N9 {' o9 m. ]4 f9 c5 a4 f        return vexNum == 0;
    }
    int GetArcNum()const
( |- S* X: F9 G7 R7 b    {
        return arcNum;
    }
( g, z# Y( G" V3 k- ?+ U. v    int GetvexNum()const
1 w" F% y+ z9 e6 R' t  U  c8 ]    {
; j1 |: S# @9 a; g5 X1 S: B0 q        return vexNum;
5 H! O3 K7 D) Z8 V; `    }

' [! x$ u/ V/ [! M" m3 r
) i( ~0 p+ g9 Q0 C2 r) x    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;

    void InsertVex(const ElemType& d);
. G5 ]" W9 ~0 }+ q" j    void InsertArc(int v1, int v2, WeightType w);

# c+ w, W0 R9 X8 U: z: E& X    void DeleteVex(const ElemType& d);
    void DeleteArc(int v1, int v2);
7 J' r0 q, d! v* I2 a* G% }, d, h
7 [# R, f4 H+ v+ C/ s1 G! W    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);
& @2 n% Z! N; `4 D0 _, W" v
    ///深度优先遍历
* R5 ^3 n/ F. u7 k( T* S' d- [/ Q    void DFS1(const int v);
9 D* E% G  S7 z+ D    void DFS1Traverse();
    void DFS2();
/ i& A6 R# ^9 |. `
    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();
4 i0 ?. A( P1 }4 I
    void BFS();
# U5 e+ x! Q& j; d1 o    void Show();
5 \; J- C& H5 m! G};

. Z# h5 Y$ w, K, L0 O4 K6 }2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

5 r, H5 N# z5 o* h# z& i$ q0 `#include <stack>
#include <queue>

template <class ElemType,class WeightType>
. ]% |, K7 o  T$ s! f' @! GMultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
) E/ G+ W' M6 n0 P" l( c+ J    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
- i. J( S1 c/ [( m% {# I4 L- X    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
5 t$ o5 x5 w" {5 M' M    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
8 {0 ?% |* ^; i# N+ W! g7 {    for (int v = 0; v < vexNum; v++)
- G) s& g4 ]( y$ |    {
% v  |  O. w! V1 j        tag[v] = 0;
# A8 n, W0 t3 }        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
% S, q  j7 p: x8 Z# U, E& k' U* Z    }
% ]3 [0 B: _4 Q9 S: D- ]  B}
template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
. T6 O4 V) K& F% [  D4 H0 {- R    if (vertexMaxNum < 0)
& i3 U& L6 d" E        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
* N$ Z0 G6 {9 K# @) j( d    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
) }  R6 B; U& p* g# Z{
. f1 K, W/ ?1 A7 P    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
( Z5 A- f2 G; }0 F6 E  ^. [  ^        return -1;
    else
        return vexTable[v].firstarc->adjVex1;
- p( N$ e1 |8 P) p* v6 p}

' F' q. e% h. U0 C1 O8 e5 F' Utemplate<class ElemType, class WeightType>
' ]0 y- ~2 w  F+ b/ c2 @1 Z9 jint MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
& n- D2 I' z' H& V- p4 _0 G        throw Error("v1不合法！");
. ]5 |  I9 l6 @, P    if (v2 < 0 || v2 >= vexNum)
6 W5 Y; S& j: \" U8 r+ Z        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
/ C$ h7 t( Y! |* `' o    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
$ J* @/ T8 B. X' Z* P+ m- `7 B        p = p->nextarc;
  g6 j' R$ H* @4 `$ V    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
$ }; H  f* b+ w" E/ D    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
! Q$ i" H0 p$ i        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
1 `/ P# \1 D- j; U# t4 itemplate<class ElemType, class WeightType>
: o  V3 ^, m5 Ivoid MultiAdjListNetwork<ElemType, WeightType>::Clear()
* J; u( `- C* a{
( y, U% l& k& X; n. f+ n    if (IsEmpty()) return;
    int n = vexNum;
9 ]; ~2 k$ X% n# _    for (int u = 0; u < n ; u++)
' ^* K5 i8 e- Q* k7 `, x        DeleteVex(vexTable[0].data);
    return;
}
% o1 z: _% F6 o5 A: J: ktemplate<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
8 f0 K4 u5 o4 U. S2 N    Clear();
}
template<class ElemType, class WeightType>
4 u# H8 d, V$ w2 f, DMultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
) Y4 E( o9 \7 x{
+ e6 q7 Q: `4 W" N" O3 F3 |) ^& r2 b9 T% Q    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
# @; r! G0 C1 T( _4 P5 P0 m    infinity = copy.infinity;
    tag = new int[vexMaxNum];
3 t' j3 H' a( W( v2 s
    for (int v = 0; v < vexNum; v++)
5 B$ [1 Y! z. }  f7 h" X1 F( J* `    {
3 }9 k: c# X6 O        tag[v] = 0;
% J" R0 t4 J  D9 e& {        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;
/ z  F! g- ?( r1 L, U& v8 Y
    for (int u = 0; u < vexNum; u++)
6 x! ^7 Z# `8 y/ g  ^    {
        p = copy.vexTable.firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
0 F$ g3 V; A+ D& j2 W6 E9 @) k            p=NextArc(u,p);
        }
    }
6 X( F1 L$ y8 S) U" B/ O}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
6 k" U1 k+ S% OMultiAdjListNetwork<ElemType, WeightType>:perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
4 S& j' X% M4 h3 X( i' V{
  X) F* {* z% n, K    if (this == &copy) return *this;
/ I, G' ?; D1 u1 t) O0 P    Clear();
. \* ~+ G7 c8 ?" g    vexMaxNum = copy.vexMaxNum;
( q; `# e: v8 D$ d% x* K    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
/ Q* \' z4 g: V    infinity = copy.infinity;
3 X3 O; l% b6 T/ s7 B; H    tag = new int[vexMaxNum];

3 l3 c' v; D3 i% @    for (int v = 0; v < vexNum; v++)
7 O7 c% T' W% z" N! p, ]* n+ Q, E5 Y    {
0 W2 `& |7 o9 @* ]& ?: r        tag[v] = 0;
" p) n9 N3 T7 z$ H- g, ?. Q) E        vexTable[v].data = copy.vexTable[v].data;
1 h* N1 @1 i6 R0 }3 M# Y        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
    {
1 r; M& a1 b; d        p = copy.vexTable.firstarc;
3 c6 q/ R* F1 Z        while (p != NULL)
/ z' `4 V5 t, M( c        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
$ S" O- n5 E  ], e. t- u        }
    }
# {8 _9 a4 Y) s+ e2 C* T    return *this;
7 t8 }' t/ b9 f) V, [}
: g5 f' }% |$ k0 ~" O: Ntemplate<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
        return p->nextarc1;
  S& v( Q  l' \: N& |& v' u+ g    else
        return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
. p) u' H/ o- P: _0 X6 OMultiAdjListNetwork<ElemType, WeightType>:astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
3 M( A6 h, ]9 `{
    if(p==NULL)return NULL;
$ ~/ x, h0 {; l) @! q- L4 J    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
, d7 L2 n5 g  o1 I- H! R    if(q==p)
- i3 s* P% P- b# ~        return NULL;
    while(q)
( y$ F! S% v  B8 S    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
- y2 G6 |( j8 r$ p: V: ^# X5 x0 Y        q=NextArc(v1,q);
    }
    return q;
}
4 t: m6 Y+ b! y1 Q9 d/ Itemplate<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
; e: O9 I& A5 H6 K& S9 N        throw Error("图的顶点数不能超过允许的最大数！");
& i" p, M$ s) ?  C, ]    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
    vexNum++;
, q& y! j! [3 F% B8 l# c}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
0 {. {! I  x$ R- @- C% @1 V    if (v1 == v2)
& R7 v* ?& _+ T' e, O/ [" K        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");
: t5 w# n5 Y/ I2 c

    p = vexTable[v1].firstarc;
    while(p)
: B$ y+ I. _* W& A: f    {
# ]# O2 j8 T, G# ?/ n. p        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
3 D" c, d2 w/ m2 x( O        {
& g/ T+ K3 r# e$ T% S# v- J8 a            if(p->weight!=w)
; r$ S4 [* m  E6 ]0 l* y                p->weight=w;
            return;
        }

        p=NextArc(v1,p);
5 U8 i& l2 o+ S. D/ y, I( `( ]    }
+ `  W  ]/ z+ C' ]6 j9 h: w1 M    p = vexTable[v1].firstarc;
: E8 T+ n- z' C: O1 M" V. n    q = vexTable[v2].firstarc;
# ^: L6 y9 x0 x% Z7 x0 V- z. `! b    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
' q9 y8 i) g2 _3 z! x0 a5 I. Y    vexTable[v2].firstarc =vexTable[v1].firstarc;
    arcNum++;
}

template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:eleteArc(int v1, int v2)
7 O, U0 O; E; r' h5 K, R# y1 ^3 Z{
0 [6 Q8 F! v( k& |/ |& V
- h" L* G) H1 L9 X, F    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
2 @6 ]: @, {& I( H& ~    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
7 a9 N. h8 B  S9 N( O- e- l    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
, d5 S$ w! a1 R1 I$ D: k        throw Error("v1不能等于v2！");

    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
! a2 A9 d/ B) t+ i, G5 g6 s" k! F    {
. I/ O3 p6 ^0 I( t3 m1 g        q = p;
        p = NextArc(v1,p);
. V) f$ J4 t2 n: y  _9 n    }//找到要删除的边结点p及其前一结点q
) m: L# \' d' K. d4 E
    if (p != NULL)//找到v1-v2的边
    {
        r=LastArc(v2,p);
        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
) U3 U% \1 I( t- Z" b8 h7 P                vexTable[v1].firstarc = p->nextarc1;
2 s  m2 M* m8 ]0 Q; `5 A# s0 {            else vexTable[v1].firstarc=p->nextarc2;
4 y$ O) i0 u) `' d3 @+ G+ V        else//不是第一条边
, Y& y7 p  X0 L3 ~) b        {
            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
            else
                q->nextarc2=NextArc(v1,p);
4 Q4 S* k- v4 M  B+ k& m; j6 p
        }
6 z- m0 \% @" }5 b% F5 N        if(r==NULL)
! y* ?/ U" y0 c) m            if(p->adjVex2==v2)
# u+ X2 z/ }& y+ Z' a  G. S                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
        else
        {
            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
0 O6 Z" E0 U' ]' @7 _            else
                r->nextarc1=NextArc(v2,p);
# t+ p* u. @( I! F9 C$ f3 U0 d) \        }
) i6 {; G& l9 b' @7 p        delete p;
1 g3 a! z! B, k3 ~! |        arcNum--;
$ e' ]; o! P  J    }
7 E6 H5 h. @" C5 C2 e+ U- ?2 ^
}
- X7 Y" v- i% Ztemplate<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:eleteVex(const ElemType& d)
9 e% W4 m  }( ]" e* K  H0 I{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");

    for (int u = 0; u < vexNum; u++)//删除与d相连的边
: V, @  @2 |. g* x        if (u != v)
$ f& i6 |  {$ }0 k9 z7 b. g        {
2 O0 P" h- g1 F) v            DeleteArc(u, v);
. S* c7 U, x3 U4 p2 \! l; e        }
% o2 l- Q+ L& |5 c+ U  t    vexTable[v].firstarc=NULL;
7 Q3 g& h& Y; b9 U) z0 i/ O
    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
' k& q; R! X: E) X2 ~    vexTable[vexNum].firstarc = NULL;
6 [. M' C$ t- [, \6 _% \    tag[v] = tag[vexNum];
    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
" f5 U) z; V% s3 Z1 h2 R6 i6 L    {
        if (u != v)
        {
            p = vexTable.firstarc;
- S& s, u0 E: R4 ~            while (p)
            {
1 V$ O# O8 a/ a8 |* o. m4 p; F                if (p->adjVex1==vexNum)
# z1 M! B$ b4 j  Z                    p->adjVex1= v;
4 s) ?, \  O# z. T) _4 M' o5 W                else if(p->adjVex2==vexNum)
0 V! _0 n! R7 k0 n6 T                    p->adjVex2=v;
                p = NextArc(u,p);
            }
  w3 w5 y: {& ?' |( V        }
& Z& c2 c) ~- c* k- W    }
}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1(const int v)
3 x; [( L( T& P) K7 |' {* I* T{
: O0 p; Z% X1 e) a, Z' y    tag[v]=1;
' Q- R( |0 a' E    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
3 Q1 Q* i3 C0 w. _8 Q    p=vexTable[v].firstarc;
    while(p)
' L! s8 z8 d; C# @    {
        if(tag[p->adjVex1]==0)
2 P$ J' J' w8 z: _3 s  E            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
# W( B# b% G$ t5 `! O4 U            DFS1(p->adjVex2);
6 F% P% r2 N& R5 q        p=NextArc(v,p);
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS1Traverse()
{
5 U5 l! T3 ~' k, ~5 Z5 V    for(int i=0; i<vexNum; i++)
        tag=0;
    for(int v=0; v<vexNum; v++)
3 |* {: x; G' Z    {
# x  G1 j, y! |8 ~/ X        if(tag[v]==0)
            DFS1(v);
    }
' n6 B& v- ^1 ]; \% {}
6 y( ^! z. f0 D" g( btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
* [; J  P  k3 h; ]& f$ K3 Y{
    stack<int> s;
. |0 Z4 s& T- ]9 x5 P    int tmp;
0 W: h3 ^$ S) K4 V8 e! f1 L    MultiAdjListNetworkArc<WeightType> *p,*q;
  u- c' R1 b* _$ @4 E) p! Z7 G    for(int i=0; i<vexNum; i++)
4 p2 y) W8 S' `5 W: ~        tag=0;
2 c& K) c. Z# f6 |, x$ c4 o& Q    for(int i=0; i<vexNum; i++)
3 Q; z+ W% C% \; _    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
        {
  b$ ?7 Z. d9 C2 A! P& i            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
* o! U$ }1 @$ b# k- G: C- V, n                tag[tmp]=1;
8 ?) n* S; B( ~, a4 ~                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
: G+ e5 Y" z) t                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
2 r3 Q( {5 ]/ k+ H0 ]+ b                //cout<<" 1st     tmp="<<tmp<<endl;
; K/ T2 G& h! u8 a4 M" b            }
" l) N4 t, d0 c2 F2 ^            if(!s.empty())
: Y& b$ V5 \2 r2 G' E8 X            {
- ^% I7 d7 n! x& A2 u7 T9 u8 x                tmp=s.top();
                s.pop();
$ Y! {# U5 l4 C9 w* B5 W, S( {                q=vexTable[tmp].firstarc;
                int t=tmp;
+ g0 E2 t# R! E% u3 X% {: O                while(q&&tag[tmp]!=0)
1 o# I& O7 ]+ U0 p3 p7 w5 v                {
( u: G* D; r7 `% b( J                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
: U" T6 ~* `- z6 ?# m                if(tag[tmp]==0)
% g/ P* }  N/ g2 m+ B, C8 J                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
+ ^& a' D4 q; ?8 F. k0 y( [                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
; e" G6 _# m6 \        }
    }
; d  V& w" l  X2 D- b}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
- h8 T" Y. b0 ?& ^* S5 q# {MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
2 E& [/ J- ^5 W0 y8 `5 ^/ n{
4 |( _, C6 ~9 ~* N    if(head==pre)
) D. F  F+ ?, q4 ^        return -1;
6 q" A1 r) D" {" M4 y
0 [3 P! i: b3 i! ]% _5 o7 M    MultiAdjListNetworkArc<WeightType> *p;
8 h/ W# o- y" l; c    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
: r3 x3 S4 @( h& l9 a    //pre!=-1&&p!=NULL
3 I; v; [/ U% Z3 w    while(p!=NULL)
    {
, l' g' K. e2 X" C& P        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
+ T+ w: l$ N( J4 k            p=p->nextarc2;
; Z; P& ?: Q, @4 M3 E7 a/ ~& c$ \) Q        else if(p->adjVex1==head && p->adjVex2==pre)
        {
            p=p->nextarc1;
            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
& Q$ s: g3 I. w8 y; M        {
            p=p->nextarc2;
            break;
        }
4 h5 k/ k5 y7 `; {  F    }
    if(p!=NULL)
    {
+ K* g( L( n2 {( |0 [1 G3 B        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
5 d" [' L7 r/ l& E( y( t- e( g. f    else
        return -1;
% K2 r* E2 f' F+ c6 {( k( x3 l8 p}
: ]( h7 Z6 l( w! `4 T4 |5 x/ z

template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
{
    stack<int> s;
# U+ x9 ^7 c' Z# d( u    int p,cur,pre;
% V9 @" c" `8 e4 r; t; t: c- }    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag=0;//初始化
+ y5 {4 G# m) \$ ]; [: _; ?
    for(int i=0; i<vexNum; i++)
& e3 H3 z% H' K    {
6 z( \* e7 X3 e        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
% P" z1 _2 h9 @  j% T            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
' V( h9 a/ ]% K% I4 {                tag[cur]=1;
               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
1 q( s# f3 B. r& Y: K               if(p==-1)
               {
  w6 S! l2 e3 N/ W                   pre=cur;s.pop();
                   break;
               }
               else
               {
                   pre=cur;
                   cur=p;
6 R1 W" Z( B+ n9 \9 u" D               }
9 x- \, @/ r( Q
            }
$ f) S% }1 _) H8 \. i+ B/ Z            while(!s.empty())
            {
                cur=s.top();
# m0 a( X  }" A6 X' a$ ~  N                p=GetAdjVex(cur,pre);
4 h& r+ p: ~( F1 x) x, u! o& w                if(tag[p]==0)
                {
                    pre=cur;
4 x7 }: a5 t9 N5 Y                    cur=p;
                    break;
- @, p5 d0 @! J4 L                }
                else
                {
; I  ~; N! j( {' u                    pre=s.top();
                    s.pop();
                }
( v5 U" A1 b* |# \3 P9 u; C+ l
6 q2 i$ }/ q8 U1 ?+ ^/ G; I            }

        }
6 [4 H3 l' k- E    }
8 D+ Q, m* i+ n( Y}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
    for(int i=0; i<vexNum; i++)
4 U/ K( p$ R6 Y5 o/ l        tag=0;
    queue<int> q;
1 E/ p' L5 x# `5 Z2 Q# F    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
    {
  G+ X  v6 k" ~) X/ D$ R        if(tag==0)
2 w9 d: O- o9 v# ]. s        {
            tag=1;
3 }% M& |7 ^3 d, r: X2 C  ~; z: G            q.push(i);
            cout<<setw(3)<<vexTable.data;
8 y# A5 L5 a. d        }
* w6 O/ I2 q1 n8 \/ }4 _  |! Q        while(!q.empty())
" F' D$ g! {% i$ R        {
3 _2 Q" Q9 a2 m( h            tmp=q.front();
( C" a8 p+ J8 I( S            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
3 }3 [4 `$ D4 j% c7 d, z                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
1 f! K8 n& g2 c( }                if(tag[t]==0)
                {
                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
0 S  R$ a/ H2 V                }
4 F# z4 ?7 _, w, A% m& M. C                p=NextArc(tmp,p);
            }
        }
8 c, X2 N$ I( l/ b" L    }
}
/ K# R6 ]" N$ L7 g1 a* L# a% R3 xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
3 ~& A: W7 P9 l0 U8 h! K/ @6 P{
    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
  W+ e. q6 C' P7 u+ V        cout << vexTable.data << " ";
    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
( ?* a2 A; w7 J! ]" B0 q    for (int i = 0; i < vexNum; i++)
    {
* ?7 X5 _' h1 K' Y2 G, P        cout<<"和" << vexTable.data << "有关的边:";
        p = vexTable.firstarc;
        while (p != NULL)
        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
# I% @& b$ K+ D/ I            p=NextArc(i,p);
        }
        cout << endl;
7 ~: l2 @4 H' H# J    }
}
' P& k* R5 d9 N" [
, i) p) G2 }3 f$ q  Y4 ~3 ~
邻接多重表与邻接表的对比
* V/ r  a# A# w2 ~9 n. m5 x. o  W- X
! q) g4 Y: {) N, s3 W邻接表链接
) Z, U8 Y" O. ~+ k: H  S在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
& D8 O; Z; }8 M. @3 J; ~在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
; B0 Z, O/ g1 u* Z为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————
/ {" G+ D8 D% c7 A6 F版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, m. l8 }$ i8 ?$ L4 P
( \- B* J: I2 h, z: H
3 u) q' k8 ~! c: E0 j
; }7 i9 s0 P3 b1 e
————————————————
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
+ S% I' Q! G1 o$ E) \