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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：" [3 V( H& {3 U4 k1 N
data域存储有关顶点的信息；: W1 n( ~( j( o; {+ ]2 f; S
firstarc域是链接指针，指向第一条依附于该顶点的边。
9 ]: \0 q1 Y9 x. S所有的顶点结点组成一个顺序表。

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;2 r) b* i/ ]: m% B2 A$ v
for(int v=0; v<vexNum; v++)5 I5 j7 W% ~( |6 X  m" \* R; N
{
* X( O/ L: `  V8 H- L0 O. \8 T* z       if(tag[v]==0)1 B, V" K' M5 D: B
         DFS1(v);
) T8 }* X' j( z }/ |6 w: x4 [' r+ l3 F
}
- j! d1 O. D( W1 Xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
  C! V; \8 k1 A5 t* i8 [{4 n- A% H* I7 Z
stack<int> s;
9 X& ?- a+ M2 D: Q% j6 M9 `. l0 n int tmp;
$ C  V% S( ^: `7 B6 S  T: h MultiAdjListNetworkArc<WeightType> *p,*q;* E( P( h4 z( O) c
for(int i=0; i<vexNum; i++)
1 b, D" m' C* p; i       tag=0;
$ r. y$ o* x1 r2 x: L0 s for(int i=0; i<vexNum; i++)2 L5 r$ i( G; v
{
4 o% m3 i5 l# i2 ^       tmp=i;
: q) J1 U; J+ m& D6 B- y: @       while(tag[tmp]==0||!s.empty())
7 h) K/ u8 D4 c) Q+ D& L+ K# v       {
1 B2 \# Y$ c) x) g* s% q0 a* C          p=vexTable[tmp].firstarc;3 `) k% T- k; O2 \
         while(tag[tmp]==0), B6 A0 G6 m: K5 c
         {% g# Z) O. D3 `# u$ T
            s.push(tmp);
7 m1 g& ]' E2 A& E2 D/ L             cout<<setw(3)<<vexTable[tmp].data;  Z1 o; ]% E- I" d
            tag[tmp]=1;
. j# ^: L$ M( t$ h( H             p=vexTable[tmp].firstarc;
! D0 N* A& c$ A/ A& t             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for# }1 O( r' j9 }( a
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
- P( m( Y* Z; d. y, i             //cout<<" 1st    tmp="<<tmp<<endl;
9 T/ d1 }* I& n, P* I3 L. V  {7 Y; N          }
: C3 M+ T1 o% Q* \3 W          if(!s.empty())
  e: B6 c& j& s6 f" R2 m' G6 D          {
, I: @- G+ `" [. z# v             tmp=s.top();
8 I) _( E; Y1 q! r& f# P: T             s.pop();
# s1 }! f. r2 c( t# z             q=vexTable[tmp].firstarc;
' I/ `4 q+ p* f             int t=tmp;0 @( D. i* Z7 Y# y- g4 O7 k
            while(q&&tag[tmp]!=0)
9 _% ?: n# z& b: y. A9 ]' Y1 i             {* e4 z( C, r& b% Q3 w
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);/ {5 r/ P6 U* n% ~. S. O" ?
                  //cout<<" 2nd    tmp="<<tmp<<endl;
) a7 [$ @% p* w$ z3 _+ a3 J                   q=NextArc(t,q);
9 S& L$ G9 Y8 `. O1 D- M; I5 W             }
" W1 e& f" {. ?             if(tag[tmp]==0)
" H# Y/ y8 E3 O/ z; f4 }2 ?5 m                   s.push(t);* f, V7 C* S5 y1 I. a8 w7 d. u  R
            ///1、对应上面连通分支只有1个点的情况0 v$ V" S, ~9 K% P
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈% W3 g5 Z: ^# c- B7 u  a( H9 _
            ///tmp要么等于找到的第一个未访问节点，
& f# w, k, q4 `# p) l1 F4 y- U             ///要么等于与t相连最后一个点（已被访问过）$ f/ P' h0 o4 C9 k2 N
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点* I" ?" }4 u- K4 x& g0 ]' c* w
         }' U3 z$ K8 Q5 L0 m: K8 O# t
      }3 v0 b5 B& J& O" }, m, W
}
4 s2 \* {0 N' f' f& A  S}  p, o% l4 K) q
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
5 i# N$ R! H; Wtemplate<class ElemType, class WeightType> int, c+ j6 \9 m) @) Q7 ]' o: f
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
% e/ y  n' ^- V* S{  g0 Y" \2 v/ `
if(head==pre)' u# y7 m! O. |3 S$ n8 b: `! }
      return -1;4 }% ~2 P7 k  m" j" E
$ v* A+ U' q1 v6 n' [
MultiAdjListNetworkArc<WeightType> *p;! C( n8 h; u" G+ r; S
p=vexTable[head].firstarc;% ~& [. `  v; A: O! P: Q
if(pre==-1&&p!=NULL)/ @. q" F4 e+ y3 x$ A3 c8 c; o* o: Q8 d
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 I5 x& g, n, [( ^! V4 r  f5 G //pre!=-1&&p!=NULL
- v& O# w; A  G( f4 J while(p!=NULL)
4 w: y7 e- i4 W2 n {. f# O) ?- o1 B" g: t0 ~
      if(p->adjVex1==head && p->adjVex2!=pre). J+ Z8 o4 P$ Y4 I9 F, h! Y
         p=p->nextarc1;1 j6 a8 h; p4 N! u& E" Q& L
      else if(p->adjVex2==head && p->adjVex1!=pre)
/ C- o2 ?6 C( D          p=p->nextarc2;
! v% s! B3 E' a2 W& a; O/ Q       else if(p->adjVex1==head && p->adjVex2==pre)
5 N7 T- O& p% n* B, ~7 A       {: E7 U( y6 `4 t% M3 b3 p- }
         p=p->nextarc1;* b. |7 ?+ N% Z
         break;
# S+ b7 U% W; L4 B: G% {( _; \2 @7 X       }- P5 T( T" t- a& V
      else if(p->adjVex2==head && p->adjVex1==pre)
1 @/ i1 d# W. j1 h& K; r4 {       {' E" x2 R3 S6 Q* A3 b$ b+ r
         p=p->nextarc2;
- u# G5 E# k/ q/ s          break;" D+ e5 T7 u! r
      }
3 }2 O2 b* m1 v& x+ k* e }
& t: ]6 U3 M, d+ d$ l6 r# u if(p!=NULL)
7 D; u3 N- P1 g' s0 `' d {
( s& }2 J  Z4 O7 ~- q1 ?       return p->adjVex1==head?p->adjVex2:p->adjVex1;
% |* x# v3 K( h( o% B1 p }1 b% n5 }4 j- \. y3 d6 l% Q
else
  U2 J3 V: U  |) t! j" n+ D3 c$ y       return -1;
) ]& P! r% {, p}3 N4 r  E" Y* c5 S9 p' t9 B, z
  ]; V" f, f6 y- v+ d' y

; K% h$ Q$ s% M9 |. k, `template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()( M, l; L6 C8 s4 X! ]; y: ^' I
{
" [* w0 }/ p& ?  }4 E stack<int> s;
8 }" E* U+ z) u; x6 G" h6 D int p,cur,pre;2 h# R) ^" R/ T5 z
//MultiAdjListNetworkArc<WeightType> *p,*q;* \( h- h0 s' r; R! e& ~+ H4 R
for(int i=0; i<vexNum; i++) tag=0;//初始化. {4 [1 `8 B9 Z; j$ p% Q

7 x! x1 U& k: {0 O& B4 A for(int i=0; i<vexNum; i++)0 O3 z2 X9 Y3 H' X8 y
{
" Y1 }, K5 B- j$ O) q: c       cur=i;pre=-1;$ j( y3 q& i4 U+ r# c
      while(tag[cur]==0||!s.empty())* g$ x6 O0 ~" o& t
      {0 W. A8 N+ a+ V- y  x7 D7 ~4 `
         while(tag[cur]==0)
$ x! g$ u4 ?9 u+ i          {  a3 S9 B9 ?# z) U1 o. Z5 m/ j
            cout<<vexTable[cur].data<<"  ";
  o; f. K+ a8 Q' P6 {7 ~             s.push(cur);3 H. S# Q, R& J# R8 d+ w: t1 A
            tag[cur]=1;4 X- n% S, m4 }% ~
            //初次访问，标记入栈- w7 K7 B1 ?! N8 Y7 V$ c
: W2 b3 y" ^: Q
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
+ y/ ]+ s" f* I/ p$ X: O             if(p==-1): e  Q+ t4 m; T$ Q
            {
5 R% ~, p5 O2 ?- _0 o9 ^* R                pre=cur;s.pop();( L8 k9 y4 [7 [3 i& H$ m9 \& v
               break;
- e8 r4 }8 c; `! P             }; Z- X: a( E3 A; x/ v* o! W
            else
6 D3 y( c, v& Q& `, A             {) _1 M8 A/ t9 F" g+ a! G  ^7 h
               pre=cur;
$ g$ h5 I5 z, S% l9 b8 Q/ {                cur=p;7 Z" e2 y) Z" u  X5 ~( N
            }
7 \  Z* f: F" v) N
& A9 {6 U% t6 t1 y# S          }
1 @* o: x; b/ k- I8 j          while(!s.empty())$ f( j8 B% @5 ^+ b; O* U
         {
1 w2 n8 q( M* @2 i- M' ~* o, L             cur=s.top();
& X3 R- p% K: G; ~             p=GetAdjVex(cur,pre);
" O3 w6 M; v, r/ P! L) b( b             if(tag[p]==0)
9 t8 W7 G+ W% o! }             {* q6 F1 O# \) G0 I  y. P
                  pre=cur;
. |- w- }1 a5 n8 O+ X                   cur=p;7 W1 z( v$ O4 `+ w
                  break;, P  l( k* }" g5 B8 t! w0 [- l
            }
3 @7 H. I% r! v) E             else
3 t, X4 r9 w! c7 X' u2 S             {
' ~  A  J8 L' g                   pre=s.top();
* x/ G1 T$ o6 a4 V* _                   s.pop();5 w; f0 u- {* c# K7 o; D$ G7 G
            }2 F6 n9 s! n; m  E) i7 c5 F

+ ~+ N8 ~/ \& I) q6 I          }# O9 r2 _9 @: D2 c9 @

& ]6 ~3 n" z) V9 f+ e       }3 n8 B, q1 D3 k' M8 ?& X
}
( S# \9 _' I6 p# q6 V}
" P5 i2 O' K( D) ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()! ?* y: ?$ I' p* n1 F
{0 z% {, C7 M3 i
for(int i=0; i<vexNum; i++)5 p6 a) N, R( C# D+ A
      tag=0;
, @; q9 h6 C  @$ x' R( | queue<int> q;2 D8 B9 l: {& C# P
int tmp,t;' d4 ^5 [: i- T, J3 g- H1 _4 F8 I
MultiAdjListNetworkArc<WeightType> *p;
8 |, Q! J* u% @# M& c; E- l2 \ for(int i=0; i<vexNum; i++)
% s* J0 {- s( I9 E* q! q {
4 n8 ?" V. U( k9 S* _' x- t! L' T, D       if(tag==0). @3 O. t  w+ `% ^
      {' K7 [6 d" s8 G  e+ h# k# J( b
         tag=1;
/ L6 E% J, D' N" u+ I1 I          q.push(i);
0 l7 E9 M  D: L! ]7 x          cout<<setw(3)<<vexTable.data;2 x3 C. ]; s2 S
      }: G6 _* Q4 B1 ~
      while(!q.empty())
9 L8 ~2 i! G9 X9 |- W( y1 W5 ?+ |       {6 N7 c) d9 Z. x9 \) [3 V
         tmp=q.front();
  I- F. j. p' H8 ?& }( U) h% p" o          q.pop();
6 ]  k0 R/ n8 |9 Z, U2 ~( C+ p# b          p=vexTable[tmp].firstarc;
! ]3 b; F5 A% C) K8 o" f* {( J* ?1 y# S          while(p!=NULL), o- u% R$ N" O& u7 g6 A
         {
. _, w8 I6 h6 d4 [/ v0 u             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);2 H0 v0 S2 B) k% P
            if(tag[t]==0)
- {$ P9 t8 f3 l' w# \. ~             {
6 |3 H/ J* g" u6 B) Z                   cout<<setw(3)<<vexTable[t].data;
) i$ [# u  Y. m  {) `4 P' o                   tag[t]=1;
# k) q+ Y, I- c9 t; c                   q.push(t);  l& W- j2 R1 o
            }$ W- L6 F/ ^( A
            p=NextArc(tmp,p);+ P7 e4 j/ j* v# ~; j
         }' n& k0 z% |# s1 i
      }
" q' Y) i4 b0 m* L# m6 i }, x9 C. ~8 Q3 k' Q
}
# A, u; {6 t0 H9 L8 ?" g( utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
) Q  t6 @: b8 h2 r{
' E) c, u+ H" n) x MultiAdjListNetworkArc<WeightType> *p;
9 K9 Z: i, G( f" e% T! @ cout << "无向图有" << vexNum << "个点，分别为:";
+ f9 C9 F, L8 @  H8 s! E, E for (int i = 0; i < vexNum; i++)
! j/ E: ?" F/ q: G% a* r       cout << vexTable.data << " ";
$ m4 j1 l8 q- n# `4 q! f: W cout << endl;
& P& `: Z+ K$ [# a0 P cout << "无向图有" << arcNum << "条边"<<endl;
+ a" r! x$ D: `* U for (int i = 0; i < vexNum; i++)
, P* q4 a5 D4 J" \ {* |. x* |  c$ B1 r/ E
      cout<<"和" << vexTable.data << "有关的边:";6 }2 ?* V+ T, n( G% K
      p = vexTable.firstarc;( R: X' u" z- D" p8 u" E2 X
      while (p != NULL)5 u) [9 a$ `6 u2 w- ~
      {2 ~, h) t( _; m5 ~0 Q
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
1 [: |$ z5 L' x, T; A7 h          p=NextArc(i,p);
8 i4 H: Z# ?2 K1 U2 h2 f+ y4 h$ {# h       }; B7 D# J5 Z/ L- v+ m
      cout << endl;
5 M! w/ j) v7 P" S/ B1 v- K }
; Z4 ]. g- w5 _7 G! R' K6 ?}* z/ ]8 x  C2 R- C  Z2 e$ ^
$ _4 P% \0 x7 p8 A# U" X+ J( i

, Y; Z+ E% I2 k2 E6 c( x1 M9 B邻接多重表与邻接表的对比
- A2 _0 \: y/ K1 T, I3 o# m) i0 `+ u
邻接表链接
! q: M$ ^8 H1 i: }( c5 ^在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。2 g8 p4 Y/ A. ]! m; X" s% P% G
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
( j2 D0 v2 E2 m9 `$ X为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。/ J9 x% L# [2 E# K) ^; y
————————————————
6 i0 f* N% I( K. ~版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 \' q) D4 g8 Y5 l8 O; r& W/ Q原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669580 O7 {- S; U4 K( v2 j1 T

( v+ w& s8 E; v3 N+ X7 ^+ y) w
! q8 p. V" x1 l. A& w* u3 c
; f! ^! }( I" L1 f- _# _) c- G0 P9 f0 m" n; r$ G/ O3 @6 A
————————————————2 h, q9 r' o. x" d3 Y; U- `+ Z, X2 }
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ {, l. U3 I* g1 O原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
6 s. g' Z. C3 O( V2 b+ ~
; r1 V& B" N- o: j' Q& U, `. }
# _8 `6 c. L+ i+ j, A0 g