数学建模社区-数学中国

标题: 图的存储结构——邻接多重表（多重邻接表）的实现 [打印本页]

作者: 杨利霞 时间: 2020-4-26 15:26
标题: 图的存储结构——邻接多重表（多重邻接表）的实现

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

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
6 F; v, b5 y% |/ K7 C( ydata域存储有关顶点的信息；
" g% k, U7 @# u8 A# d+ Ifirstarc域是链接指针，指向第一条依附于该顶点的边。9 x( ^( p; p. H3 \ c
所有的顶点结点组成一个顺序表。

template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
{
public:
ElemType data;
MultiAdjListNetworkArc<WeightType> *firstarc;

MultiAdjListNetworkVex()
{
firstarc = NULL;
}
MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
{
data = val;
firstarc = adj;
}
};

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

在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。

template <class WeightType>
class MultiAdjListNetworkArc
{
public:
int mark;                                     //标记该边是否被搜索或处理过
WeightType weight;                            //边的权重
int adjVex1;                                  //边的一个顶点
MultiAdjListNetworkArc<WeightType>* nextarc1; //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
int adjVex2;
MultiAdjListNetworkArc<WeightType>* nextarc2;

MultiAdjListNetworkArc()
{
adjVex1= -1;
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表示被搜索过
}

邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
protected:
int vexNum, vexMaxNum, arcNum;
MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
int* tag;
WeightType infinity;

public:
MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

void Clear();
bool IsEmpty()
{
      return vexNum == 0;
}
int GetArcNum()const
{
      return arcNum;
}
int GetvexNum()const
{
      return vexNum;
}

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);
void InsertArc(int v1, int v2, WeightType w);

void DeleteVex(const ElemType& d);
void DeleteArc(int v1, int v2);

MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

///深度优先遍历
void DFS1(const int v);
void DFS1Traverse();
void DFS2();

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

void BFS();
void Show();
};

2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

#include <stack>
#include <queue>

template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
if(vertexMaxNum < 0)
      throw Error("允许的顶点最大数目不能为负！");
if (vertexMaxNum < vertexNum)
      throw Error("顶点数目不能大于允许的顶点最大数目！");
vexNum = vertexNum;
vexMaxNum = vertexMaxNum;
arcNum = 0;
infinity = infinit;
tag = new int[vexMaxNum];
vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
for (int v = 0; v < vexNum; v++)
{
      tag[v] = 0;
      vexTable[v].data = es[v];
      vexTable[v].firstarc = NULL;
}
}
template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
if (vertexMaxNum < 0)
      throw Error("允许的顶点最大数目不能为负！");
vexNum = 0;
vexMaxNum = vertexMaxNum;
arcNum = 0;
infinity = infinit;
tag = new int[vexMaxNum];
vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
if (v < 0 || v >= vexNum)
      throw Error("v不合法！");
if (vexTable[v].firstarc == NULL)
      return -1;
else
      return vexTable[v].firstarc->adjVex1;
}

template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
MultiAdjListNetworkArc<WeightType>* p;
if (v1 < 0 || v1 >= vexNum)
      throw Error("v1不合法！");
if (v2 < 0 || v2 >= vexNum)
      throw Error("v2不合法！");
if (v1 == v2)
      throw Error("v1不能等于v2！");
p = vexTable[v1].firstarc;
while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
      p = p->nextarc;
if (p == NULL || p->nextarc == NULL)
      return -1;  //不存在下一个邻接点
else if(p->adjVex1==v2)
      return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
else
      return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
if (IsEmpty()) return;
int n = vexNum;
for (int u = 0; u < n ; u++)
      DeleteVex(vexTable[0].data);
return;
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
Clear();
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
vexMaxNum = copy.vexMaxNum;
vexNum = copy.vexNum;
vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
arcNum = 0;
infinity = copy.infinity;
tag = new int[vexMaxNum];

for (int v = 0; v < vexNum; v++)
{
      tag[v] = 0;
      vexTable[v].data = copy.vexTable[v].data;
      vexTable[v].firstarc = NULL;
}
MultiAdjListNetworkArc<WeightType>* p;

for (int u = 0; u < vexNum; u++)
{
      p = copy.vexTable.firstarc;
      while (p != NULL)
      {
         InsertArc(p->adjVex1, p->adjVex2, p->weight);
         p=NextArc(u,p);
      }
}
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:

perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
if (this == &copy) return *this;
Clear();
vexMaxNum = copy.vexMaxNum;
vexNum = copy.vexNum;
vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
arcNum = 0;
infinity = copy.infinity;
tag = new int[vexMaxNum];

for (int v = 0; v < vexNum; v++)
{
      tag[v] = 0;
      vexTable[v].data = copy.vexTable[v].data;
      vexTable[v].firstarc = NULL;
}
MultiAdjListNetworkArc<WeightType>* p;

for (int u = 0; u < vexNum; u++)
{
      p = copy.vexTable.firstarc;
      while (p != NULL)
      {
         InsertArc(p->adjVex1, p->adjVex2, p->weight);
         p=NextArc(u,p);
      }
}
return *this;
}
template<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;
else
      return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:

astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
if(p==NULL)return NULL;
MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
if(q==p)
      return NULL;
while(q)
{
      if(q->nextarc1==p ||q->nextarc2==p)
         break;
      q=NextArc(v1,q);
}
return q;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
if (vexNum == vexMaxNum)
      throw Error("图的顶点数不能超过允许的最大数！");
vexTable[vexNum].data = d;
vexTable[vexNum].firstarc = NULL;
tag[vexNum] = 0;
vexNum++;
}
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不合法！");
if (v1 == v2)
      throw Error("v1不能等于v2！");
if (w == infinity)
      throw Error("w不能为无穷大！");

p = vexTable[v1].firstarc;
while(p)
{
      if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
      {
         if(p->weight!=w)
            p->weight=w;
         return;
      }

      p=NextArc(v1,p);
}
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;
arcNum++;
}

template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:

eleteArc(int v1, int v2)
{

MultiAdjListNetworkArc<WeightType>* p, * q,*r;
if (v1 < 0 || v1 >= vexNum)
      throw Error("v1不合法！");
if (v2 < 0 || v2 >= vexNum)
      throw Error("v2不合法！");
if (v1 == v2)
      throw Error("v1不能等于v2！");

p = vexTable[v1].firstarc;
while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
{
      q = p;
      p = NextArc(v1,p);
}//找到要删除的边结点p及其前一结点q

if (p != NULL)//找到v1-v2的边
{
      r=LastArc(v2,p);
      if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
         if(p->adjVex2==v2)
            vexTable[v1].firstarc = p->nextarc1;
         else vexTable[v1].firstarc=p->nextarc2;
      else//不是第一条边
      {
         if(q->adjVex1==v1)
            q->nextarc1 = NextArc(v1,p);
         else
            q->nextarc2=NextArc(v1,p);

      }
      if(r==NULL)
         if(p->adjVex2==v2)
            vexTable[v2].firstarc = p->nextarc2;
         else vexTable[v2].firstarc=p->nextarc1;
      else
      {
         if(r->adjVex2==v2)
            r->nextarc2 = NextArc(v2,p);
         else
            r->nextarc1=NextArc(v2,p);
      }
      delete p;
      arcNum--;
}

}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:

eleteVex(const ElemType& d)
{
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相连的边
      if (u != v)
      {
         DeleteArc(u, v);
      }
vexTable[v].firstarc=NULL;

vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
vexTable[v].data = vexTable[vexNum].data;
vexTable[v].firstarc = vexTable[vexNum].firstarc;
vexTable[vexNum].firstarc = NULL;
tag[v] = tag[vexNum];
//原来与最后一个顶点相连的边改为与v相连
for (int u = 0; u < vexNum; u++)
{
      if (u != v)
      {
         p = vexTable.firstarc;
         while (p)
         {
            if (p->adjVex1==vexNum)
                  p->adjVex1= v;
            else if(p->adjVex2==vexNum)
                  p->adjVex2=v;
            p = NextArc(u,p);
         }
      }
}
}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:

FS1(const int v)
{
tag[v]=1;
cout<<setw(3)<<vexTable[v].data;
MultiAdjListNetworkArc<WeightType> *p;
p=vexTable[v].firstarc;
while(p)
{
      if(tag[p->adjVex1]==0)
         DFS1(p->adjVex1);
      else if(tag[p->adjVex2]==0)
         DFS1(p->adjVex2);
      p=NextArc(v,p);
}
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:

FS1Traverse()
{
for(int i=0; i<vexNum; i++)
      tag=0;5 O, j( P- S' x" f. d  W* w. d- }
for(int v=0; v<vexNum; v++)
7 Y* f. F. ?3 R {
; X: L) p* C4 g1 E, _       if(tag[v]==0); g9 S$ c( ]. u* R6 K6 ~
         DFS1(v);6 z& G) c- k! l; N
}
2 b5 z/ q7 s4 @5 H6 `$ t" G}
* v, X4 G" }2 i+ v2 N3 Q  K' vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
; K( F% \5 ^# }. ~5 H- n2 R- a{
9 ~$ }7 M( i! x' |: E# Z stack<int> s;7 o+ O4 M- E5 G
int tmp;6 P; }: R7 M- ~+ w
MultiAdjListNetworkArc<WeightType> *p,*q;  B( L. t$ I+ U' j  l
for(int i=0; i<vexNum; i++)
! a5 W# p3 n) h# u; U       tag=0;9 \0 q+ @$ ?. P2 b( K
for(int i=0; i<vexNum; i++)
: X3 \2 N& N1 k {
3 @1 w% E3 o2 _" T2 s$ c       tmp=i;
* A8 {* h/ w, }! m8 I% j3 ]$ p       while(tag[tmp]==0||!s.empty())1 U5 b7 I) t" D8 f: R
      {
% `+ X6 n0 s+ r% K          p=vexTable[tmp].firstarc;
4 J* Y) Q- K) c3 K          while(tag[tmp]==0)
3 E- _) A9 y- z- _6 I          {3 y/ r$ R6 q! Y1 u  S; v
            s.push(tmp);
0 d8 q$ e: k" A2 E8 N2 l             cout<<setw(3)<<vexTable[tmp].data;1 Y5 I( _6 v2 r1 y8 `6 e" Y
            tag[tmp]=1;/ X9 p1 B5 }  t+ U9 P8 x
            p=vexTable[tmp].firstarc;
# r" g4 t5 }! w5 g% L4 m             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
, L& w' g5 k! g             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);1 d0 `' i; J' b  T
            //cout<<" 1st    tmp="<<tmp<<endl;
+ Q. r# Y; A  Y# Z          }! L! }: m& U& x1 H2 h
         if(!s.empty()), F7 ^* g8 A: T! |6 O1 h3 ]
         {0 K0 C) K8 D% N2 \; c  w0 ], N
            tmp=s.top();1 ~# M" q2 h" b. c' V
            s.pop();
7 W. |3 V+ o8 G9 o             q=vexTable[tmp].firstarc;$ |: g' N* i: \" S' g
            int t=tmp;
3 a# u2 o7 O7 ~7 ~- X/ F) T             while(q&&tag[tmp]!=0)! @/ T$ C: |4 i
            {7 f- X; G/ \7 M$ N* x) a
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);# ]$ k- \6 I, a7 V
                  //cout<<" 2nd    tmp="<<tmp<<endl;# W2 [  U" w, i! \/ b  t% x
                  q=NextArc(t,q);1 l2 U0 l* a8 ?# G/ r
            }
" A2 @' J/ ]- ~8 T: d- N3 v7 |             if(tag[tmp]==0)
2 P8 _7 G. t6 M1 s# H                   s.push(t);6 ?( b  V7 q+ d1 h* U" K6 S
            ///1、对应上面连通分支只有1个点的情况
. w  Y9 T+ k! O8 q7 Q9 H' L3 I             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
3 {4 f$ r$ s2 _. Y             ///tmp要么等于找到的第一个未访问节点，
9 G5 T" c1 l; K$ r/ Z1 [$ W             ///要么等于与t相连最后一个点（已被访问过）. d+ d) t; B( v+ D
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点# r" K( B4 x) O' I* u/ G4 {' V
         }2 a, c! v+ v1 a, t3 \  t! e7 a
      }
; i3 o' C, G4 F: T }3 h! D1 O8 |: L- m
}
" {/ W( D' j4 {+ V//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
9 ]- V+ _/ }) U& A7 X/ xtemplate<class ElemType, class WeightType> int" s( K7 D! R  J, X# O3 [9 [3 Q, M
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
3 R% P1 y* M# L! P1 v6 j{- D4 P! P) T$ l: X
if(head==pre)
5 q2 _4 |) f% [4 g$ c       return -1;* Q# I5 s; H/ O( Q
/ V# e7 q% H( Q  \' }
MultiAdjListNetworkArc<WeightType> *p;
1 x7 J6 i% h2 R- U& U p=vexTable[head].firstarc;
+ T( s6 {8 A1 b9 k/ p if(pre==-1&&p!=NULL)' j! U- w! i0 x7 i' S6 m
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
( n$ l  m" K' s- H" c- m- {6 V //pre!=-1&&p!=NULL
# S$ g( G& N' s$ ^/ E7 p while(p!=NULL)& Q0 R/ d* U' ]$ U
{7 j, T* j$ t$ r+ b; a' ?5 a
      if(p->adjVex1==head && p->adjVex2!=pre)
  `* _* @' u  S: O& s# l3 q          p=p->nextarc1;! n* [, j' ~: I. e
      else if(p->adjVex2==head && p->adjVex1!=pre)
# p) p1 p8 m3 @' x, ~          p=p->nextarc2;
' I4 m  S" }; i, G       else if(p->adjVex1==head && p->adjVex2==pre)+ M2 f0 D# ~0 N7 ?( g9 @
      {8 P+ O8 q8 `  L
         p=p->nextarc1;
! y  H" a; Z+ H$ G3 x          break;
6 s! I/ V; H. K  o. z# r5 I       }0 M  b: U. b0 H' r3 D8 E
      else if(p->adjVex2==head && p->adjVex1==pre)
3 Y) J+ d1 f! v+ `4 t& s6 ]       {
/ L4 `! r5 J0 n. ^0 A& a6 ^2 Y( i          p=p->nextarc2;1 v1 ?) r$ X7 w& Y, p- e% N
         break;+ \9 j; F& G/ I, }
      }
2 x* X" `) F0 h& F2 \ }
% ~! J; I( k6 ]( c$ Z, r if(p!=NULL)
. C) K7 ?9 `; Z- Q8 T0 b& e& r+ k {7 Z; Z" v9 `, X% C
      return p->adjVex1==head?p->adjVex2:p->adjVex1;& m! C$ x4 O- D& N$ m! B
}; H0 v+ W) M3 O7 ~0 y
else
3 ^# f( a& y% e( ^2 W       return -1;
. Q! W# e, b; k0 |# Q: a9 j}
# n1 }: K( I% w8 }3 z
( Z  y1 Z0 J. ?4 Y4 C0 Q5 Y( M1 j  }6 Q
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
  x, N9 ]9 ?1 x" H{* h- c8 U) O; m. S3 ^
stack<int> s;
' U- b0 N" x1 Z: x/ \% {/ i! z int p,cur,pre;
4 P, k. Q; m8 G' u8 Z) W+ V& _0 T2 o //MultiAdjListNetworkArc<WeightType> *p,*q;, P! \  h% R  m; B! F; p
for(int i=0; i<vexNum; i++) tag=0;//初始化' S3 _9 `4 K! H7 f' C. c

: P& @& V  o1 f5 q% o' w8 R; Q for(int i=0; i<vexNum; i++)
+ R8 h7 ?1 ?( I  v {$ U% s9 N0 Y$ j5 m5 T8 {; Y
      cur=i;pre=-1;
" s# d! C6 e# N+ y) `       while(tag[cur]==0||!s.empty())
$ D; }+ g. S" k6 `1 ^- L       {
- g5 Y- g, a" a8 h+ I- ^# i! @. W          while(tag[cur]==0)
6 [. |  q/ `7 Q, q          {  ^4 O. C; N) Q* Y
            cout<<vexTable[cur].data<<"  ";3 u6 U6 K# m/ S* r0 c6 i/ U
            s.push(cur);
( a- ^& I  I. O! _' [  y7 _  G             tag[cur]=1;- ]2 v2 k5 V" ^( j/ S
            //初次访问，标记入栈
- j& T% g" j: q# m
! y0 E! q% e3 Y; u5 C             p=GetAdjVex(cur,pre);//p是cur的连通顶点7 J, f; |. h, g5 r6 W, L
            if(p==-1)) [, o# d/ [# h) J/ J
            {
! N; C8 _% Y5 O: ~                pre=cur;s.pop();' w0 v) G- a7 p5 _5 T
               break;
; w8 J! ?, i0 E, H) u0 w             }
; b7 D2 ?% l% K" |/ v+ W             else5 J: r4 W0 `4 f" e$ l. u7 [) `" V: @
            {
; E7 m: [$ b# ?+ T! g9 L) ^                pre=cur;
0 z. x) m: M7 w6 \# K# s5 D" i                cur=p;
7 C: G1 w' I! b$ k. L- Z) {4 `  m             }5 x3 q) w. J# F4 ~& z7 [9 n7 q. e

6 y% J2 b( y/ V$ Q8 {! ?6 |+ T          }* ?% o/ v5 U# M+ I
         while(!s.empty())
( S6 P( O$ N; j1 o& h          {
, n9 h( J" ^5 q, U9 M             cur=s.top();
$ o1 i* q( S. ?             p=GetAdjVex(cur,pre);9 B) Q% Y% f# ^3 U5 T
            if(tag[p]==0)
$ c4 J  N- N  o4 l+ O             {1 t1 S/ e3 V, L! ]
                  pre=cur;
' \! L3 q$ E8 [                   cur=p;) ^5 u6 k3 _2 z& y0 f+ U
                  break;6 T/ I. L& b0 ?; _' e
            }
& U& |' c+ f- w# f) V( j/ a- n             else
2 {$ N  |, N8 J- G             {5 X" ]5 ^- Q0 b8 b$ Y5 \
                  pre=s.top();# N- U7 {3 [  M8 g7 E& Z5 |: ]
                  s.pop();
% T% L- W0 m$ ~$ [6 \* ?: v& L             }
* [( {4 ]! y9 `5 K' y8 t  |) N# _  i' G, p- C1 |
         }6 Q# {+ R: O+ a& A( W

8 i5 r2 ?5 t% p8 D) H; ]! `% N; p       }
3 b3 {$ ~" ?! R }- E  ?+ A' e! A4 }
}! g+ E7 a# e2 H
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
0 C- O) K( g; U; ]) n3 H{& B( e% c. q* v  d7 q. R. q
for(int i=0; i<vexNum; i++)+ F, @! Z: f4 C$ _. R: N# Y
      tag=0;
. A1 U- Y5 {& ~9 { queue<int> q;
  i$ [# N* f* P: I3 k+ @  k  R int tmp,t;
+ ^5 K& \/ n' R" R" X8 i3 u MultiAdjListNetworkArc<WeightType> *p;3 w& o8 B1 B3 |- D7 }; f; {
for(int i=0; i<vexNum; i++), e1 }* Y, H& R7 v$ s, h0 _* |
{
3 {; ^; Q: d/ q; d5 |3 e5 u4 z       if(tag==0)$ s+ ~3 e! K' W% E
      {( n6 X' X3 }: Q* {9 |
         tag=1;
# O% r% e2 j1 l/ z+ u- Q          q.push(i);  z: c3 z/ E4 a4 O: M: f8 r9 U& \" \
         cout<<setw(3)<<vexTable.data;
1 i# ]8 Q4 F) l( s$ V       }0 w4 V. Z$ X+ r  m: x/ H. b8 D2 M
      while(!q.empty())
" o: w# z1 u% S& z       {! Y" I  j6 }9 h0 e/ U
         tmp=q.front();
" k8 d6 C, e! E9 w/ ~- `9 {          q.pop();9 R# O# U, o4 s$ A
         p=vexTable[tmp].firstarc;
7 |5 P. m2 [  e" V          while(p!=NULL)4 `: n8 i' o8 o, S/ E0 d
         {
/ I' p1 }* S0 ~             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
1 |+ P" n2 h/ k  L: i             if(tag[t]==0)$ e# K$ k% a. W8 j0 C- f# L
            {. n. a' p; R1 x( [7 T
                  cout<<setw(3)<<vexTable[t].data;8 e1 _8 a+ N" o" v
                  tag[t]=1;9 G1 [1 Y8 G4 z$ r! F1 c0 ^: _
                  q.push(t);# l0 u1 y9 R, ]: @+ q
            }
, U0 s& i3 V+ U0 |# R# G             p=NextArc(tmp,p);+ `, I+ s5 X; ^) G) X7 m9 I: I
         }
! G. w# m( F4 S5 a8 t' h" t) v7 O5 x1 B       }
9 h3 y2 z& o2 B  @ }9 P/ f8 V, E2 o- E! u5 b" J
}
# y0 K" ^; O+ v6 ?+ p) x+ ^template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
' J# {7 i, P( c9 \8 ?$ S. p  g- I{
3 X& ~$ D. v3 q) h% x MultiAdjListNetworkArc<WeightType> *p;
5 k8 _% x; O0 ~, v9 h cout << "无向图有" << vexNum << "个点，分别为:";
+ w  `6 @7 K" r) g+ M! \! f) \ for (int i = 0; i < vexNum; i++)
7 k/ M, H, Z3 J' k- D! B" C       cout << vexTable.data << " ";1 V$ N- |2 g+ l3 m
cout << endl;, q: U0 l5 p: Z
cout << "无向图有" << arcNum << "条边"<<endl;
2 n: J$ z+ _7 o; | for (int i = 0; i < vexNum; i++)
$ ?  [+ ?% A; A1 n' C& n/ n6 t0 L {+ L: U0 A* \, B% a- H
      cout<<"和" << vexTable.data << "有关的边:";+ K# K7 T) k- J0 l
      p = vexTable.firstarc;
2 Z# S8 |4 y. M7 ?+ C6 F1 g       while (p != NULL); V7 I) f  {2 _# s. J+ M
      {
3 l( |+ x: V/ A5 \; x          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
& k6 C+ c- ?6 l& b" K          p=NextArc(i,p);- `$ H# ^$ c, x% h0 u( [
      }; H, _  ~! r' k8 Z$ ]; W
      cout << endl;
; C. T  H/ A, P3 h  S }3 [1 V! G2 `# d. w- C3 H9 i
}1 M- Z  K- L# V8 b2 o/ R
& b7 m- M' }; {+ m! q, j
8 e1 t/ S0 J6 r# O
邻接多重表与邻接表的对比
' W0 {1 ^# [0 Q) G0 p  [6 F# z" K) M3 a* L3 @5 U
邻接表链接% C/ K  [* l# A* B, p- u
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
# x  [+ o5 l1 y3 M- J& ?+ I在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。8 [6 o3 D! G( `0 j  q
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。( {0 J& J( x3 o( C; T5 I' H
————————————————( ]4 R3 w4 Z$ d6 ?$ @5 N* q7 z2 k, _
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。: Y: U  l; n! P- C
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
5 f% s2 B6 R( G) C
2 y# k5 B5 o* C& E3 D" r
7 M- U# j! Q$ i5 K4 T& S, J$ y3 g2 x& `9 l

+ w6 I) e& ]- E5 ]* t————————————————) b6 x- t9 n) M5 F
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 c3 J% j. E9 B" p0 U; f- A原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* C/ w+ L) x8 k4 N9 r! q
# L5 Z- {% P3 B0 Y
8 q7 K. f0 J3 }# c( h. n

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5