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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
; S- ?9 W: o1 c p5 e2 L% v Sdata域存储有关顶点的信息；
1 v3 P6 G1 O& [# H5 o- \firstarc域是链接指针，指向第一条依附于该顶点的边。
, W8 W$ m( B/ s7 \) W' 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;
0 G+ b* t/ R  Y( A" }& B2 K for(int v=0; v<vexNum; v++)8 M7 m/ K5 t' N$ m
{! G$ F( V) r9 n8 y
      if(tag[v]==0): z- H' ~; Z9 g: e. L6 M
         DFS1(v);
/ e3 a+ N' d; ^6 `6 j4 N }
8 x7 q; y8 e3 ^& C  O5 V9 ?}
7 i" S# t* S) c% Y8 }! Btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
; W9 V# Q1 h; _{3 H" x3 P' D' Y; i5 m2 g: w
stack<int> s;
. {/ W8 m: x/ I int tmp;
, x% E8 G* S, u9 x2 x MultiAdjListNetworkArc<WeightType> *p,*q;& X- n/ J+ D4 H; g2 i8 Q- g. C" h9 ?4 G
for(int i=0; i<vexNum; i++)
5 \0 y6 m! S4 C       tag=0;5 _# L2 `( J, }3 `9 f& w" g
for(int i=0; i<vexNum; i++)
) I: x% h" U5 q% q0 X" N2 ]# j {' A# Y/ k% K/ v
      tmp=i;
5 d6 k" A9 {& E0 n& _4 ~5 }       while(tag[tmp]==0||!s.empty())
6 g% _; h7 g9 |( N: [& m- d       {
* G* d8 M8 T7 m          p=vexTable[tmp].firstarc;; a) T9 Q0 b8 }( U9 o
         while(tag[tmp]==0)
- ?& |1 m  m8 `+ z8 S( d5 d5 y          {5 t% G* d, ]9 K0 g
            s.push(tmp);$ w, h& s) q1 ^9 O3 a
            cout<<setw(3)<<vexTable[tmp].data;
: ?; q% U3 C1 z+ `             tag[tmp]=1;& {+ C! k/ _% C, {5 L
            p=vexTable[tmp].firstarc;
) n0 w( B& J9 Q  A  R             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for8 L3 ]4 t- g- m- f5 c
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
9 G0 W* b7 V5 V( r# T7 v) v             //cout<<" 1st    tmp="<<tmp<<endl;
: S8 v' Q1 N5 y. i          }
( w  [* d2 {8 A  c          if(!s.empty())
+ T: B2 a/ }* p- o          {
, M1 A' k4 t/ F3 R! H4 v$ R             tmp=s.top();$ q  X) C4 n7 Q! p# \9 P$ T' n
            s.pop();' M! G. ]  m$ l+ G
            q=vexTable[tmp].firstarc;
, @) C0 C; y- q- R             int t=tmp;
: s  \* z+ P5 J2 j: q6 D6 `  j             while(q&&tag[tmp]!=0)
9 [' f2 A" ^9 v% b             {
3 V. Q4 O7 y: x6 D                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
4 E9 y# O1 ?) M! F. ?                   //cout<<" 2nd    tmp="<<tmp<<endl;
* `: _2 X- B9 M# i3 [                   q=NextArc(t,q);: [7 F* Q8 I, c) h5 q
            }
# q+ g* d/ ~& `# ~( y             if(tag[tmp]==0)
; s: d1 }0 L' ^; _; I: f% h  a                   s.push(t);
: W; u6 H3 i, w             ///1、对应上面连通分支只有1个点的情况
; ^5 E* H( x9 d# [& Q5 W# h# ]: j0 ?             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈1 J9 Z* H; W8 ~9 i* n" X- ^& n
            ///tmp要么等于找到的第一个未访问节点，
. S  ^( c% f0 e% H             ///要么等于与t相连最后一个点（已被访问过）
- e- j  S7 B! R, o, f, o             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点1 T$ |) G0 {6 O! k; o# ^( `
         }% {5 L/ T4 @+ R
      }
- C$ j  i! V3 i$ V, Y* c# T- @ }, K- U/ r: x1 |' Z
}
8 o. A% I# C6 {; I* t2 [. v, }, Z//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
+ k1 [9 }8 ~) m8 R( Otemplate<class ElemType, class WeightType> int+ o% A' ^" M. f% C3 l8 S
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
/ m+ u$ I/ Y- X, }{, o" X. ~* \2 o' X- ]( g5 x
if(head==pre); J2 r, Z4 l+ \# e* @
      return -1;
8 c- S5 B' J; b7 m# H9 O7 X  u& m
" [' X, [4 W7 c2 \# V- u! ? MultiAdjListNetworkArc<WeightType> *p;
# e+ N# x" j! ~" r! c$ t p=vexTable[head].firstarc;
2 a8 a1 Y4 y4 d9 o& {. L if(pre==-1&&p!=NULL)
: m; ^6 \7 _0 I: F1 I) Z       return p->adjVex1==head?p->adjVex2:p->adjVex1;  {; I8 G1 N# M4 L) p; ?1 ^' a
//pre!=-1&&p!=NULL
& ]. t) d0 t# d; D) O8 ^7 R) `. n while(p!=NULL)8 v# r, K4 s- a$ Y% f. ]% F
{
" T  ]/ J# e: d       if(p->adjVex1==head && p->adjVex2!=pre)9 i% x) n4 F+ i  x4 A
         p=p->nextarc1;
9 N  H( N% ?6 S) P. A, J3 y       else if(p->adjVex2==head && p->adjVex1!=pre)7 l8 R9 O6 [. b0 h* ]8 s4 ~. `
         p=p->nextarc2;
8 P# x8 o8 g; d; t$ \6 R       else if(p->adjVex1==head && p->adjVex2==pre)! Q% O; }3 L0 P4 F
      {
2 \1 \7 f: [  V4 Z- R          p=p->nextarc1;
3 P* D! u8 }9 b; `  M& ^          break;9 J+ Y2 B, l# t1 X# Q4 ^# g
      }
: R4 I9 r9 u! b: l5 I8 }       else if(p->adjVex2==head && p->adjVex1==pre)2 e2 w8 E* d! r6 H+ l
      {+ c# o5 Z. [/ ~
         p=p->nextarc2;4 N% I/ D% E. E' c% G! P
         break;- z6 x9 O3 B. `
      }
+ Y- ?1 k8 N) a- B4 U, _/ ] }
( o1 m. e5 j' z, d& F0 W- A if(p!=NULL)% e  ]1 [. L; L/ D- b5 l7 k
{( C+ C. y% X1 S' v7 E
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 ]2 _7 H0 U. I# I3 d. T$ C9 V+ ~6 m: @ }
8 B2 r- @. g7 W else7 c+ q9 m2 G+ C0 [; z2 O
      return -1;( w/ X1 `  }0 M& b% H
}6 l. C  A2 S/ I% n0 M/ V
" G  _" ^9 r( T* b) X9 ^7 B
9 |' a% H: L7 q5 H, b
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
+ q7 M' _  j" o: q{
) m3 s* c! ~; P  T, i stack<int> s;& t5 ?* L' G( a6 s+ b) _( y2 M- C
int p,cur,pre;
' O& e+ E$ ?' ~/ B- { //MultiAdjListNetworkArc<WeightType> *p,*q;
7 J1 _# O8 o4 V. M) [3 [8 T for(int i=0; i<vexNum; i++) tag=0;//初始化7 |' ~9 a$ k1 w0 Y" \2 t" n4 A" ^

2 ]0 A, ?! h' H" h for(int i=0; i<vexNum; i++)' B! J6 M2 O% ^# J8 O
{
1 h. l. L8 W+ M" R9 z# x: _       cur=i;pre=-1;- |9 b$ }& p0 n# b1 k% r8 c9 \8 L
      while(tag[cur]==0||!s.empty()); s& r/ b0 f, M$ @: P, r9 W- t
      {
! N4 Q8 n' g/ J; Z& f# \          while(tag[cur]==0)' ^. M# X* T% A. O
         {
- x  u. [5 Q+ C' H( I& c! W' b             cout<<vexTable[cur].data<<"  ";' h" r% i9 j/ a7 T+ i& K
            s.push(cur);
; Z' u7 K( M  \* h             tag[cur]=1;+ A" ~! k! y7 X4 c  _
            //初次访问，标记入栈
; F8 _& ^/ C5 A; ]- P8 k: U+ E0 [$ f. b( G' @
            p=GetAdjVex(cur,pre);//p是cur的连通顶点2 Z8 f! V, j5 {# ^8 d
            if(p==-1)
3 t+ d, b3 z8 h+ c0 C+ a/ p             {, g1 v; }" a* i+ ]/ k- d( A0 `0 e
               pre=cur;s.pop();
. q3 J; H( t* e1 x                break;& U% @  U: I0 p
            }
5 _4 V/ H/ f9 d7 \             else
# `& C' K: U! X& O" A* U$ L: \* E3 M             {; g6 h# w& Q3 N* B% x
               pre=cur;
5 g. ]; W& r0 c                cur=p;
/ X' [  Z+ ]$ S4 n. l& h) q3 w             }9 B" d/ u% {' A  Q& [

4 I1 X# W# x. l9 R9 |8 I          }6 G1 l( V0 T; Y$ }1 A
         while(!s.empty())
% U7 |( g: N, y( X- ~7 k; v4 B          {
- r8 K9 G3 K. f# k0 q! @             cur=s.top();: w1 Z6 Y" G' @2 ?
            p=GetAdjVex(cur,pre);/ E" G$ \3 x+ m- F* y! a
            if(tag[p]==0)
) }; R/ k2 m: {, p5 S# @5 }+ Q             {- O1 H( ~! L% O/ U
                  pre=cur;
1 A* S. L8 _: e% b1 o! G                   cur=p;
- a7 z$ Y! M6 j                   break;
, D( w+ b8 c' [0 P8 i7 l* r             }3 u; @4 v! ]3 a5 E
            else% [7 P8 `, [7 p
            {
; x2 t) ?! t2 N- G0 \2 a) m. o                   pre=s.top();
2 J0 D$ f' M7 e$ V                   s.pop();
: a0 @9 K7 V" j) |1 X, C             }
3 c# V+ X- y% @* k: f. y' S2 D( u+ H$ E
         }
7 Q+ v0 F0 E2 h1 m$ U% Q
* G. b& m/ Z! y5 J- c7 G       }
" m0 X% s! U7 _/ e7 j; m }
2 n3 }5 U2 B, P3 x4 u}; `- q. A! K$ }/ |( S
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
. E; D. H6 h. n# [% [{
) j, S- ~4 K' u# b for(int i=0; i<vexNum; i++)1 V0 i' K: E5 c7 Q
      tag=0;
1 r3 _. H! n% R queue<int> q;9 u- O0 N- v/ [; i& p( Z
int tmp,t;
- }+ x2 Q2 i$ X# Q, r MultiAdjListNetworkArc<WeightType> *p;8 V( P- `8 |0 |1 C. ~
for(int i=0; i<vexNum; i++)0 A! ?, O: M. I
{
$ L- O' G) b1 R( l1 Q& @       if(tag==0)3 ]' y/ f- `8 O. G- t
      {
         tag=1;4 F1 d0 U8 U" {" L
         q.push(i);
3 r& u3 k9 }! \          cout<<setw(3)<<vexTable.data;
' s4 $ s5 L" C% C! x" B       }/ x. L. S0 o5 L' s7 G* s0 J
      while(!q.empty())
( O$ h! z. `7 _       {
- @; n% C9 s) W5 ^$ _          tmp=q.front();
3 k0 e! R7 Z; h: M          q.pop();$ ]5 l2 h, I+ c
         p=vexTable[tmp].firstarc;
, _! V0 d2 R9 T: T! U          while(p!=NULL)
% N" o1 n" ~: M8 n$ g          {
# j7 i) b( b9 v9 f             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
! e/ N6 q% c/ Y/ F# a             if(tag[t]==0)
2 [' L0 T$ U; J8 J9 w0 ]             {
4 @1 l/ }* [$ o% H5 V- h                   cout<<setw(3)<<vexTable[t].data;
( ^- M& q  x$ z0 @; C" l$ V' a                   tag[t]=1;
, X( E" e1 p. g7 w" G" @( h                   q.push(t);1 o; W+ P2 o2 ]2 ?" U
            }3 J+ B5 n& M+ d3 G9 R6 \: z2 s) Z
            p=NextArc(tmp,p);
* l; [$ q3 M& x1 a( C1 S7 B          }% o4 p% |! U; _7 @3 B9 ]
      }6 r; }# i7 j1 c
}
5 q8 u+ p" W9 n( C/ {}, Y' Q5 e8 ^; D6 F& m: q/ x
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()0 ?8 G! _$ Q" Y
{0 $ L" |# O- h6 m- U2 R; N! y! p) ~
MultiAdjListNetworkArc<WeightType> *p;: ]$ E/ w8 Q! ]6 \
cout << "无向图有" << vexNum << "个点，分别为:";+ K+ l% C+ Y4 g- T( z  k
for (int i = 0; i < vexNum; i++)2 W( a9 p7 h; J& S
      cout << vexTable.data << " ";% |" S' q) P+ ~" v  a5 H
cout << endl;# G, h& s1 T+ y% g
cout << "无向图有" << arcNum << "条边"<<endl;
, u% ^- X/ N& ^. k for (int i = 0; i < vexNum; i++)
4 @$ {3 N# Q0 x) r5 j {/ {4 L$ b" ^+ J  p
      cout<<"和" << vexTable.data << "有关的边:";# W' z, v( p& b. f7 Z2 C; C
      p = vexTable.firstarc;
/ }, Y8 t. s9 c" u, \       while (p != NULL)) H& F: b( h; I3 U: h  L% U1 t
      {
1 _) |* V6 ?2 ^2 Y6 K! _          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
3 B. }1 j. L( ~1 g$ ?          p=NextArc(i,p);
; w2 @5 L, c5 ^% T$ S& z+ w       }- s* Z6 u! @6 J1 Z) Z
      cout << endl;0 Q  N" G1 D9 |
}
/ D3 v9 p4 ]7 K8 G: v}
: J. p: O/ l5 v7 F8 Q2 F( F
: w2 g# j7 }% M7 w' O) k( s# A3 ?6 R5 ?! a
邻接多重表与邻接表的对比5 \& T& f' J' U( P0 G4 m' q
1 `; r) p  l' @. ]8 U
邻接表链接
8 f8 d) {! _$ Z在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。' f9 u& n- `4 j% O) i
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。1 g* c9 b; z' L  A) ?& V
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。( {& w4 u/ F0 {" r
————————————————& L; U$ I- m5 @
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。* W) G! m$ c4 U. {
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* a4 n7 c8 L& Y! B  W" R
* F  ?8 {( P; W) ~2 i) G! r* @( C, {( |" |( k- d
5 K& X- R( n4 N% ?5 k) c7 C
# i! _' C0 X+ L# [3 _; j- o
————————————————
  v) ?1 i7 W# n2 ?& a" f版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  h$ h- U2 ]3 E2 v5 H2 s原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, y, J; W0 b2 |0 c& x& y+ U# o$ ~
+ H5 V" ]8 X+ p! L2 `4 M# E+ [8 o2 F/ f. Q9 @1 A4 k