数学建模社区-数学中国

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

作者: 杨利霞 时间: 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)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：5 o+ C$ P7 N% I! _; |. @( W& p
data域存储有关顶点的信息；
+ D+ t, @8 g# P2 P, ^4 [firstarc域是链接指针，指向第一条依附于该顶点的边。3 ^5 T9 ^6 a \$ `' _
所有的顶点结点组成一个顺序表。

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;
, y' c7 i( g! a& i$ ? for(int v=0; v<vexNum; v++)" p& d( D3 Z) t" Y' O4 j' [  T+ g
{
: ?# w6 \& ?4 j. P! s       if(tag[v]==0)
$ k# ~7 b) f4 N" t          DFS1(v);' r+ n9 Q! X6 [1 M5 U
}( _" W. A. w! C/ P/ a
}
9 \- M3 D  T) n  \: L9 {template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 ]1 `' B2 \4 f' ?  U& E3 U( y
{! Z4 [! x' j  O
stack<int> s;4 F4 o8 @% t5 b! A  P8 [
int tmp;# m6 L* V0 ]8 D! k% R
MultiAdjListNetworkArc<WeightType> *p,*q;
3 `2 _$ i+ H8 E6 x for(int i=0; i<vexNum; i++)& I4 L3 ?, C2 g8 V7 B. R
      tag=0;
8 w+ v# p5 \4 [, m* C9 e; r for(int i=0; i<vexNum; i++)
" Q+ c* Q) p" ~# ?2 d" z7 y {
7 K5 O5 H- O4 y* d/ n3 k       tmp=i;
. W- P' Y1 D3 {% l; v9 q8 u       while(tag[tmp]==0||!s.empty())
0 o7 w) \4 p, k7 Y       {
0 Q1 v3 d5 z- n/ r: y) \- a          p=vexTable[tmp].firstarc;3 h; W& A' V* @# P) M- X7 \, b
         while(tag[tmp]==0): G! \* m, ^9 w
         {. x5 F8 v: s5 {) x
            s.push(tmp);$ B& P  H! g& n7 D( r
            cout<<setw(3)<<vexTable[tmp].data;
/ x- W& C- ?& {, ~+ }0 a             tag[tmp]=1;
9 v' q' i0 x/ @             p=vexTable[tmp].firstarc;
6 P/ p% ?" N; e5 ]2 t4 k* X9 l             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
* R5 Y* @- E/ o1 `' ]# m( i7 `  N             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);/ K0 [) z# D) P+ P, \; C1 H
            //cout<<" 1st    tmp="<<tmp<<endl;
: n! d" i# j" i  E          }
8 F. w. q7 v( F! j2 e% u: x5 p          if(!s.empty())7 D- W2 d. n% s. r0 I7 A7 b& F
         {
9 j% _" f  b5 E! `% A, u             tmp=s.top();
9 X+ z0 b# y5 Q, Q             s.pop();
8 s) `1 d; }4 W6 e! D1 {             q=vexTable[tmp].firstarc;
9 {  g7 A) `- z% v  i             int t=tmp;* l: U2 U+ l, }1 u% O
            while(q&&tag[tmp]!=0)# r. G% Y! r7 g. _( a& r
            {" o; Y8 l) P. d1 l
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);" [. @7 g) u+ Z9 }
                  //cout<<" 2nd    tmp="<<tmp<<endl;% Q8 Z) q  n0 }6 M  }) A
                  q=NextArc(t,q);3 i9 e9 J, H+ O* E
            }# m& W! H7 |1 P' E; O" E
            if(tag[tmp]==0)% I& m6 d: G: W1 X. C
                  s.push(t);
. l3 j3 h1 k- p% I- t             ///1、对应上面连通分支只有1个点的情况
- }2 H: M  j2 @  H0 }             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈6 m0 }3 _# S+ \/ [
            ///tmp要么等于找到的第一个未访问节点，
6 U. K' V% L0 o7 |             ///要么等于与t相连最后一个点（已被访问过）
. F. A* g+ x3 D8 N             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点: Q, P( s% M7 K# N( @
         }. R$ Y/ W9 w( r- p, Q4 M- D8 Z2 V. t
      }
" K7 n; |1 K5 j2 e+ G }
$ Y: ~$ F( \4 C  m# w# i}9 B! v1 A* c+ j# S8 c0 X, T5 s
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1* H( Y  K: l, F8 Y
template<class ElemType, class WeightType> int' }; N" N" k* ?1 j7 y( }3 D
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
  K) `- G. ~7 T+ D0 w+ {2 }! `{
* C, O9 l" W) N: I, Y) y4 r( a/ T if(head==pre)
      return -1;
3 ^" }+ ?/ \. S0 D0 a0 [' d, @% p8 @3 h2 T9 t, w8 {6 F& K$ ~
MultiAdjListNetworkArc<WeightType> *p;
# h8 b1 v9 ~2 g/ d# m p=vexTable[head].firstarc;
5 ]: k# V& y2 F  N2 } if(pre==-1&&p!=NULL)
( G- P, g  [! a) A+ q  ?7 u' D       return p->adjVex1==head?p->adjVex2:p->adjVex1;
4 h$ ^( m- z7 s& j, X4 r& g) P //pre!=-1&&p!=NULL6 N1 G% v5 x! p1 L$ s' y* G
while(p!=NULL)
2 V: G. H% n2 f0 g# D {
1 n! w- w+ m  z# a       if(p->adjVex1==head && p->adjVex2!=pre)
- f2 F# w2 A" G          p=p->nextarc1;
- W4 @! l+ K/ I7 T6 p, H! L' T       else if(p->adjVex2==head && p->adjVex1!=pre)
" T/ z1 C1 u6 k1 `7 l          p=p->nextarc2;/ c! k' K( I( j: t2 K; o/ ]/ z
      else if(p->adjVex1==head && p->adjVex2==pre)) k8 ?" E$ f! d: p, X8 B; W# B
      {& R: N# h: O8 ^" a) _9 @
         p=p->nextarc1;
) ]. }4 U5 r2 B, F1 x" V          break;0 d7 z/ r/ b0 r- W- f& r  M
      }
. I, i! j: p. `8 y& k0 D7 y0 t       else if(p->adjVex2==head && p->adjVex1==pre)
# o! o; P1 z7 i$ z: g2 z       {
. f0 e! K- o, x2 _: F1 _          p=p->nextarc2;
$ k8 o( _: [2 {) }          break;
* ^$ Q* _" @" l; }       }2 Z# v7 ], p8 g- c/ m& ?, F  {& T" P7 i
}
% r  k8 E/ r- ~4 a  g if(p!=NULL)5 ~. T( Q; T$ \$ t4 ~
{
; Z7 I4 l0 r) g* @7 P" h       return p->adjVex1==head?p->adjVex2:p->adjVex1;0 U7 @8 N: R  F7 \6 U; w( \
}$ F8 K# F' Z' \3 f
else
/ m0 ]9 x) k7 _3 @5 ]2 O       return -1;$ B9 S, @" Q' y- _+ `( }" c
}4 O9 H# }9 s. a0 @3 z

  ^' d  `+ c: z) F9 @- y# B( n# ^- R$ ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()4 J% K  N7 }4 t4 W
{0 D' q4 h* e. A# c: _. P$ w
stack<int> s;
2 H& l0 P1 a5 C1 f, X/ @, L int p,cur,pre;
& ?1 L1 k. L9 ~ //MultiAdjListNetworkArc<WeightType> *p,*q;
6 k; e7 y  W, T7 @" m# _ for(int i=0; i<vexNum; i++) tag=0;//初始化' k$ z" x) m% D- O% Z: ~
4 A7 L: ?- x6 b$ ?: {
for(int i=0; i<vexNum; i++)0 d' F( m1 K  z5 {& _: @) w
{
6 _/ F4 d% o4 K$ n/ a       cur=i;pre=-1;
; @+ B, t) F8 ]) L       while(tag[cur]==0||!s.empty())
/ V. q4 s8 i$ g  F- K3 D8 ~( J       {/ t, V6 W' b/ [: G
         while(tag[cur]==0)
; z- D# b% L3 n, u; q          {
! r: |5 v7 Y& {' x8 G             cout<<vexTable[cur].data<<"  ";
7 i' J$ V7 e5 }! j             s.push(cur);
+ K3 c# z# i5 C# M7 V# l* H8 s             tag[cur]=1;
* \8 s) v' R5 N3 l             //初次访问，标记入栈3 x4 A6 a' Q* V& \9 p. t2 ~
4 b; W( ~5 Y! Y, E" H. G
            p=GetAdjVex(cur,pre);//p是cur的连通顶点0 x% |* c7 I1 d& g; b6 P+ t. B
            if(p==-1)/ N- t  M: h& a7 S$ r: T0 {: \0 B2 J" E8 B
            {  S# _6 D  \' G6 W1 E& r( i0 ~
               pre=cur;s.pop();
* f$ k5 E) [& V1 ^                break;
; ]5 V3 v& S1 g" |             }
8 u* P1 b, ]2 d* t% h+ S             else$ ~5 z( b5 V+ U! ?- r
            {' {  x+ k' H) G  P* l
               pre=cur;# ?  M% F) ^& E; q4 s# A
               cur=p;
2 L6 g- ^, `6 H  t0 F2 ~# u             }
7 J. \; W$ ^. ?* P) |5 O. ~
) y7 C" ?$ {, [1 ]  Q2 P2 j$ h5 u          }6 L1 h" C2 Y; O) \  E& b) i
         while(!s.empty())# P, V6 D, U& Y  d4 [
         {
# H5 Q4 g( l6 e             cur=s.top();
9 y. ~* s/ ~" V  g/ `             p=GetAdjVex(cur,pre);
1 @5 @$ _( I( T7 }' {             if(tag[p]==0)
+ q/ S9 g' X0 ^  X, H) E/ [, p             {3 b" `, T0 n4 q- b' T! g: R/ c# z
                  pre=cur;
: F1 H3 p% A4 D8 }; s- d                   cur=p;$ {" m6 j% |7 j9 U1 s
                  break;
3 [4 b9 m5 o7 P0 B8 I             }
; ?: b& e( ^2 v' X             else0 m( P0 x7 ~* f* i$ b5 [
            {
$ @- M, @$ ^3 v+ e                   pre=s.top();; y+ [+ F" f) ]( q
                  s.pop();
0 p6 G: ?# m& y6 ~6 u             }  w4 A& f, |- z6 T6 r! Z; R, W

! V4 W/ l" ]2 Q% d$ W  c& {          }6 Y- f: ]" K  H. F' X* u
. i  t, U5 e2 d7 U$ r6 `
      }
2 B# P/ {5 r9 g }
. x  L; ?4 t" w- T, k}# t$ j* O4 z/ p1 C* }9 ~% t
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()& C7 j* R' _$ c
{
2 U& `  ^, w: o3 s4 y for(int i=0; i<vexNum; i++)2 B$ y. ^  s- P
      tag=0;+ a* ^" Z) y1 Y( z. c! R
queue<int> q;
9 Q$ R; t8 I' t) C) r1 ] int tmp,t;
8 o* @' b) W, |, [6 r: \( q( x' U MultiAdjListNetworkArc<WeightType> *p;
+ v8 s- Y2 Y" p. L( w8 B8 t' D for(int i=0; i<vexNum; i++)
) J9 [$ K) z" a {* _; f6 N5 X8 T8 T) v" U
      if(tag==0)& c, d- G1 M- U% c$ M
      {
  S6 l3 P% N/ v0 P! P          tag=1;7 e1 e7 o8 }$ H
         q.push(i);
: t8 k5 R, U& i# w6 M) a          cout<<setw(3)<<vexTable.data;
, f8 L" b7 ]+ L3 h4 ]' L5 s" l       }
( d+ M. ^9 O' H, g       while(!q.empty())
+ I* t7 `( h# s       {7 @# Z) [  ~" ?1 D1 A% y( J- T) f
         tmp=q.front();
% }5 d1 w# I9 A          q.pop();
7 F* _% P/ Y  {3 o) Z. g3 N          p=vexTable[tmp].firstarc;6 i# J" w1 ~& z. V5 R" y% I1 q
         while(p!=NULL)7 G6 m. |% Z/ z! s
         {
* Y5 N& |. O0 _2 N             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
: `4 |9 L" `3 ^, a& @1 [8 q             if(tag[t]==0)
/ I# {6 a0 ?* s8 {5 e; Z             {
, z$ r. [1 J! T4 K% \                   cout<<setw(3)<<vexTable[t].data;
# r* Y1 m2 r* c( u                   tag[t]=1;
& Q: q$ l9 ?( F! k                   q.push(t);$ A) c( G1 k8 d5 L* a1 g% s' {
            }
! T% }0 r# A  b% z- a             p=NextArc(tmp,p);3 m/ M( C* e! K+ `+ A; e5 ?
         }3 t( ]. O2 r! g8 B6 ~6 x
      }
. v( }" @8 I; v6 t( Y }0 i2 B1 T& P* y0 N1 K: ?: ^3 T
}
: i& t* V0 t' X; V, K4 {0 j6 btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()) r# b9 ^) E4 D' y* _
{
4 R- P% E  f8 B# T- }# r MultiAdjListNetworkArc<WeightType> *p;/ ^; c5 {" ]- Q
cout << "无向图有" << vexNum << "个点，分别为:";
  k5 s% I. {# L; O, ^# `5 z- T for (int i = 0; i < vexNum; i++)4 e: j5 g: ?/ ?" \- f+ z
      cout << vexTable.data << " ";: ~6 x1 y# {' a1 r* K
cout << endl;' ^/ |! y2 o8 \2 Y
cout << "无向图有" << arcNum << "条边"<<endl;( c: H* \" y: f: I$ f0 c
for (int i = 0; i < vexNum; i++)5 }$ @# E7 t; e8 k  f  x* r" b: P
{; j) S7 {; B/ ^! T
      cout<<"和" << vexTable.data << "有关的边:";8 ^8 }& V' m1 I  U$ v0 T
      p = vexTable.firstarc;
/ W# t' X* x" t5 n! y4 U& t" H( S$ [) e       while (p != NULL)4 h  n& S6 O9 ?$ o
      {
; v/ Q8 k1 \: v  S" S5 h8 q          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";/ v+ S5 ]- n' Q2 z2 Z! h( s2 N
         p=NextArc(i,p);
: Y6 U( _$ X0 ^8 a8 @       }
+ ?2 H9 W& ~$ ~0 a& M4 Q       cout << endl;7 N3 r( S7 @1 {& C1 g9 ?; D
}: O8 y( D9 V7 b* y
}5 k" P+ \9 K9 y9 S7 Q

) ~( a1 d  o4 e; K7 a+ [' K% D  I+ J: b0 t! v
邻接多重表与邻接表的对比
9 G4 m. {) W; {8 B0 p$ z" a
' o& G$ V. @" z8 Q' S! Q邻接表链接8 C( k5 K9 B0 w7 ^) r
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
1 |- @, U6 o" `& ?9 X/ a在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
# K( I) S& q5 g5 H, E! q* y为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
  g: ?& ]; E5 e3 e% |& W————————————————' F0 `4 e6 r8 A" d' D) Y* a2 {
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。* d0 s) @" r9 `1 Y" e
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
% d& U! ]" I# \/ O) {, m4 p% p4 J9 d' {& W! ]
7 n+ c  Q5 U1 ~2 z2 k6 l. k

) \& s. \1 r& ^( U/ n% D; F! W
  M3 o' I, Q/ v# [9 m  ]% n————————————————5 {- P7 D# Y3 d  H6 N
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& E6 H! ?% b' g) R原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958, ~6 z; M' k7 a/ G/ g/ I; |

( K$ z( q/ m0 x
3 Q3 _$ [% z0 {3 y- _6 z8 h5 w

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