查看: 1510|回复: 0

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

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-4-26 15:26 |只看该作者 |正序浏览

|招呼Ta 关注Ta

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

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
( \% A* ^; m3 Z& e+ U' Udata域存储有关顶点的信息；
) e" T( Z: c. {6 qfirstarc域是链接指针，指向第一条依附于该顶点的边。
: U. G+ I, N* t! G6 G! f+ E所有的顶点结点组成一个顺序表。

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;8 U7 @4 W+ I% C. }6 P8 n
for(int v=0; v<vexNum; v++)7 F* A( K! v6 y/ _1 v+ [4 b
{5 A* C% n* P( j2 Q
      if(tag[v]==0)" ]& N2 ?3 f7 b
         DFS1(v);
# Y/ `: U7 @/ ~- {( N }
3 [9 C2 y1 a/ x) ]: v# k}
0 ]" o) _# m( s' ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
/ A/ Y& T; H' D# v0 l/ S, O{( \8 [( B) K. K8 t3 t7 X% B/ S! _
stack<int> s;
- i) k' N) d; H" Z int tmp;, J+ {" A/ Y* c* @
MultiAdjListNetworkArc<WeightType> *p,*q;
2 J6 I: g! B1 y8 N% r9 `# l. e for(int i=0; i<vexNum; i++)
$ f3 c- b; l9 P1 {5 ]' l- X% R; B       tag=0;  L- ^4 G7 ?3 m. y: y, u/ z) J, {
for(int i=0; i<vexNum; i++)
{
  x& U% s2 \! l7 G; `5 p  Y2 p1 c       tmp=i;9 B: u; Z! G* d* u9 s/ v2 @3 |
      while(tag[tmp]==0||!s.empty()), s, p1 M1 R$ U+ k2 p: n3 a
      {% Y) _# _( p5 K( p4 b
         p=vexTable[tmp].firstarc;
, F* ~2 F+ N0 h+ M: @' T4 P          while(tag[tmp]==0)4 P& U7 \. \9 q" w$ {+ M1 M
         {: X& u8 f/ Z8 v' X; K/ }( |/ _
            s.push(tmp);. W( n' z  Q, L& p
            cout<<setw(3)<<vexTable[tmp].data;2 b) z' ?5 p; ]5 O7 n2 z
            tag[tmp]=1;
0 W! o0 r, K" X1 Q+ g; \/ E             p=vexTable[tmp].firstarc;
8 O& R+ f* E! I, l             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
3 K% e- ~" g  o7 R* M+ C- M* p             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);/ t* Z0 Y: y1 `4 @2 W2 c
            //cout<<" 1st    tmp="<<tmp<<endl;2 \8 `, z* }, v; [: x* z% x
         }/ U* p# \4 ~# U/ o" I
         if(!s.empty())* y6 D+ R# \: W6 I7 F' B
         {& m# j: s( {1 D& @; Z
            tmp=s.top();( Y; ?! D. K) y0 m3 p
            s.pop();) C- D9 w4 D$ P/ O: g9 b1 s( A
            q=vexTable[tmp].firstarc;
/ R9 v) z1 y9 q1 g             int t=tmp;4 s- e$ m5 k7 N  D3 [
            while(q&&tag[tmp]!=0); A" I2 x$ a. O! t/ V6 n
            {
1 o5 N+ H) \! n' K  j* ]) x                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);% v' r8 ^( A) C& w- l% X. F
                  //cout<<" 2nd    tmp="<<tmp<<endl;6 L& v1 y; R- k& y/ m' r1 `8 P; Q) c
                  q=NextArc(t,q);% l' n7 p& @: l3 H
            }
! g+ x8 K7 C8 a: Y- X             if(tag[tmp]==0)2 D  Z1 e7 c- V$ a5 s( m
                  s.push(t);
: V# e: Y0 B' \: ~1 [             ///1、对应上面连通分支只有1个点的情况5 p! n2 p  s' g& S& L; a& u
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
( C! H  Z0 p" H1 w5 m. i             ///tmp要么等于找到的第一个未访问节点，3 N3 n% m. G0 Z0 ?# K! a4 Q
            ///要么等于与t相连最后一个点（已被访问过）
1 e# p6 X  A9 k6 O6 m1 J. |' [             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
0 X! R; F2 u$ X* a2 e/ q          }4 J; K8 p& }4 _; Y7 Y
      }. X4 ^; A+ j( u1 o
}# E" U6 y) S8 s1 b" V# Z
}
( X) Z& k5 [/ E* c( |; t//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
; F# P8 |( ?1 L7 T; @& b8 o7 J2 Xtemplate<class ElemType, class WeightType> int8 q* G" c9 p7 K1 O4 ]% ~5 E
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
* i# \4 C% I/ _, }- G( k7 ]{0 o3 ?* Y2 k0 R& p* P. W2 L! s
if(head==pre)" {/ T& X. j$ c. f( a) K
      return -1;
2 y! x. g, n, l. q$ x8 N# b6 ^; B7 ]& r. B$ B" U' C
MultiAdjListNetworkArc<WeightType> *p;4 h: Q( ]5 @- h0 m
p=vexTable[head].firstarc;
, Y+ [( o# ]( s; c! Z if(pre==-1&&p!=NULL); J, i; q2 q, X* [  w- _& @
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
* y" D# I! S: s/ V //pre!=-1&&p!=NULL' d( z+ @8 V1 o: d5 i$ G# u% r
while(p!=NULL)
5 y+ B; z" q9 x3 E2 p {2 C/ F) N6 G2 _# o% f
      if(p->adjVex1==head && p->adjVex2!=pre)) m) X' Y/ z$ |# U6 S
         p=p->nextarc1;  X' h$ A, K2 p; b6 f8 G
      else if(p->adjVex2==head && p->adjVex1!=pre)
: T8 g5 M; I/ T0 V, H          p=p->nextarc2;* L$ H  q3 l) p8 w7 c# N' j9 U
      else if(p->adjVex1==head && p->adjVex2==pre); {( L2 d3 L1 J7 Y0 w
      {
0 F8 y2 s$ ~% o" f' d          p=p->nextarc1;
& j! h8 ^: g5 I" l3 ~          break;: R' z/ x- R' V9 W1 p# L* h( L
      }  Q. D) Y- ~' W
      else if(p->adjVex2==head && p->adjVex1==pre)+ k" @0 i2 t. S
      {
8 u4 n+ C7 I/ \4 H  k          p=p->nextarc2;7 d, k# p3 m, {1 q2 B; J6 r
         break;% p5 Q  v7 Q. o9 [2 N. I
      }+ p$ U5 ]3 R8 e1 [- o* s
}
  d% W$ ?, k4 K( l& y7 M if(p!=NULL)
3 P+ e; q" @& N* h) `1 W/ ]1 b {. J% X2 h/ |8 e- D/ i
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
- \+ J# p1 N! Q- @, ]0 \ }0 w9 j6 ?* y5 E+ l
else
# }2 t4 c4 B0 L0 |) r  q       return -1;
: @1 [  W! f1 r: @4 S1 K! U}. _# K0 y& |1 T' y& ?* |
6 n9 [, Y. e1 s

; q, X' I& `& D/ Rtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(), @; _4 }" q! c- @8 {- Q
{
6 q, h- a% g! o9 ^: G stack<int> s;
/ j+ o+ H1 z6 d1 h" i& \/ q int p,cur,pre;: Z8 B2 L  W6 u6 f# Q
//MultiAdjListNetworkArc<WeightType> *p,*q;
* f5 ?0 {4 m+ R for(int i=0; i<vexNum; i++) tag=0;//初始化/ T7 |4 S! E- H8 B6 H' Q/ e% U
  c  J9 a8 `* A: H! [
for(int i=0; i<vexNum; i++)/ H- l( S( `9 S% ~$ G
{
# a7 Y- I7 J/ X6 u       cur=i;pre=-1;
4 m  t, h9 m7 ]1 j       while(tag[cur]==0||!s.empty())
1 _/ F8 q( T8 u' c       {
* `' q: q1 t; p2 G% @$ d          while(tag[cur]==0)- @' g; K4 w9 m$ Z1 p' |
         {( X5 U6 W' |& b4 F( p, C1 {5 n& n: p
            cout<<vexTable[cur].data<<"  ";
; ?8 l; U- _; n. l, H             s.push(cur);& j+ M9 Q$ E: `; ?3 z# _, `
            tag[cur]=1;" ~5 D7 o& {/ @% t% w3 Z
            //初次访问，标记入栈( F$ R# ^8 T. l+ r( m3 |
, i8 u6 E" W. J' V
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
$ ~) M2 Y3 c& u  ?             if(p==-1)3 M. B* f0 B2 \1 {4 G: x2 l6 C& ^
            {
/ B* {2 w! q$ K; @, N% F8 Q                pre=cur;s.pop();5 G; ^/ b1 B+ A" y2 Y
               break;
# V/ M$ M6 p3 q2 Q! K* ^! N1 z# y             }) r3 i! v9 o) B! L3 z, n9 V% L: ]
            else' z8 O/ B. o( C1 M
            {( c) h  e# O7 y" B; U+ P8 S  h& j
               pre=cur;
. ?9 C# W' v- y( r- S                cur=p;
, T0 m+ w7 v0 {& k/ P             }
! N' Z- ^/ X. s9 D0 T- ]5 Q3 }. b- E  V6 t9 @4 E
         }
5 d, ?5 Z$ U0 j2 }% l9 D& n2 {          while(!s.empty())% _; j' P7 z5 w2 `
         {# r" Z$ d  W4 K7 r; c
            cur=s.top();2 }$ A4 ~# Y5 }3 R# N8 v4 N
            p=GetAdjVex(cur,pre);
% ~5 P6 a% X5 O7 J+ B; q# W             if(tag[p]==0)
" v6 ~9 N# N! j/ q) T: m             {
, H! b7 d& C: `/ ?                   pre=cur;
& q5 B0 ]( [9 S" D4 f3 [                   cur=p;
8 d. V# A( \/ R$ o  M: Y                   break;
+ I/ C4 P; h0 m; ~             }6 n6 a' n( f: {% [
            else: B0 ?; O* i9 ?- W# I7 o
            {
$ T8 \: A' h$ I5 N                   pre=s.top();5 f% ^! g4 w+ F1 F+ i
                  s.pop();
$ \' C% @, {( v; h2 _             }- B- ^% g# l# J) |

- _6 ]2 g6 j! `+ [          }1 r+ r! B3 e! z  `2 {
, J% f: y+ C- M# C( V
      }2 m: P" f& d% c# y$ s2 y5 l6 r
}
( l. ~4 b. Q* `. H9 @}2 x" y5 y) _- x& _9 V
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()) \' q$ b2 H# X& Q" |/ K+ x
{
+ D) F$ d1 _& X+ H5 S0 Y) ? for(int i=0; i<vexNum; i++)* ?! |/ m  h1 z
      tag=0;* r9 J( i+ a" F2 I& y( f. f
queue<int> q;6 R" O; o$ @, T
int tmp,t;
' n6 c! F2 T  v# v& e$ ` MultiAdjListNetworkArc<WeightType> *p;
7 g9 }% _4 I% q  I0 s% Z5 P for(int i=0; i<vexNum; i++)
: a; m" W4 J" [! o- p {
% C! K/ X: _; p7 c: ~4 u# G) I. _       if(tag==0)
$ V. N$ ~  I1 i" h7 f2 A- X* A+ n" w       {
- e" a) p- h3 u6 a4 O4 _          tag=1;" i; W+ L# q5 M/ R: \' A$ W
         q.push(i);
' ]/ a6 u$ U# U* J; O          cout<<setw(3)<<vexTable.data;
3 M8 z, P  z/ A* B       }
) g2 W+ m- j' e       while(!q.empty())! O, Y1 I8 ^1 r9 t" j! m" U. c
      {
. n. `  A5 h0 N4 E5 r          tmp=q.front();
# \3 N" Q7 m  }* m  j: ~7 B! D          q.pop();
3 W7 Z2 j( X' Q1 N/ i6 X          p=vexTable[tmp].firstarc;7 C/ Q+ u# h% s
         while(p!=NULL)
4 K2 B7 L7 Q  W8 z: n+ o+ {          {
5 Y# {  v; N& C1 ~             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
# m5 L  X3 j+ p( C             if(tag[t]==0). x2 n5 q  t9 Y, Y* A% h3 _
            {* ]: K% `2 c, F* Z% v' [. l5 Z
                  cout<<setw(3)<<vexTable[t].data;
; s6 o# m/ t5 Z7 Z$ a; ?9 r- `                   tag[t]=1;, Y. S5 T; d% {/ N& G
                  q.push(t);& q& q' o9 s% U) H7 a3 Y) i3 c2 t
            }; L) e( x- f8 ^. P  e
            p=NextArc(tmp,p);! u4 {, [$ q' J- k, P) y  P7 u
         }
" T! w6 Y6 `4 y: t4 u$ y+ x* z       }' e6 r8 G& A2 g* T4 ?7 \
}6 _2 T% Y" n* R& V: G) T% l
}$ t- h. w" u# `% X3 H) _
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()9 p7 E' d5 V! Q& b2 B7 ?
{2 x7 X6 \, o; j
MultiAdjListNetworkArc<WeightType> *p;" K- x- B! f( Q
cout << "无向图有" << vexNum << "个点，分别为:";2 U- ?% Q# S, d# I. I
for (int i = 0; i < vexNum; i++)/ ^  n, m5 O+ u2 [5 F- Y9 o
      cout << vexTable.data << " ";
( B3 }3 H4 I, r% { cout << endl;! H$ [. n2 L# }) ]% S, a
cout << "无向图有" << arcNum << "条边"<<endl;$ w% ^7 u: C  \6 v# ?4 H5 z
for (int i = 0; i < vexNum; i++)8 K/ X  Y% ^  y
{
% C; ~6 |& h  N+ |6 F7 S  Y9 `2 I       cout<<"和" << vexTable.data << "有关的边:";9 L' p: V- a1 V- q( k/ ?# S8 Z! d
      p = vexTable.firstarc;+ L8 ^2 a  N8 g% P  y9 I, O
      while (p != NULL)
# w; ^- A& D( B3 z* F, m3 U5 J0 a       {; E- l4 O8 p3 L$ r9 J
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
% s0 b4 e% d1 i; k. X" ^          p=NextArc(i,p);) d3 y  l- \/ o, L* N4 s/ m# G
      }# F5 ~, Y2 |( s( @  `
      cout << endl;" }7 F7 W* Z1 O+ i3 B" x" Q' a5 Z
}) T9 w7 E7 ]5 f
}
. i' _4 B( |/ X* W& U$ x: j& h% N
3 E9 N7 a; W/ x8 o' `
9 U* d) B/ y+ m9 s" {. @! e邻接多重表与邻接表的对比
4 G; r9 S" B) S4 U3 I% N1 m( B
8 G7 H! F- \" D4 ^. ^( p9 }邻接表链接" g7 f( ^0 v! }0 r9 Z
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
0 k$ _: n8 j; S  }& l在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。# l. C, W1 x6 W( c1 |6 V! I5 q5 M
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
  t8 H  C8 n% U, I% g' I1 v) G& X————————————————
5 T% n7 t7 e( g# M& S+ e7 ?& t版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 A7 W% ~* P. M3 t2 S7 p原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
: {2 U' _  b# n/ {5 ~3 ?4 m% I2 M1 X' N3 @

$ L* u0 P. N4 ^& n4 A+ Z9 A' p/ _$ M$ p* b' O

% ?+ z0 }% ^, L- ~  Q————————————————4 ^: w' v/ A" N) O
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。0 M8 u( v5 R- K- B; i$ t
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958; l0 f$ L* I  @: R- J" C& \
8 r2 `/ F. T3 o* E

# @7 T- g' z6 t8 }# T+ \+ ]