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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
; V* H& P6 e. n" |3 V. wdata域存储有关顶点的信息；
4 R( y; l4 h( L9 lfirstarc域是链接指针，指向第一条依附于该顶点的边。
9 y0 V6 i( n1 J; n9 ~所有的顶点结点组成一个顺序表。

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 o9 V% {8 @7 e4 f) T# ^
for(int v=0; v<vexNum; v++)5 a. L3 L; k( [! w) \( K
{( z1 G7 @5 }9 O8 ~
      if(tag[v]==0); o4 d, U7 b5 s7 ~" n: {3 L
         DFS1(v);
# \7 F5 w: t4 T3 a3 V; t }
* e( A/ E, O. m% T8 g3 Q}- J, G; H5 P0 t6 U" U
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
$ k8 v4 l: }8 X1 ?- w{
+ n9 v; B, j' u7 w0 N9 ` stack<int> s;9 E$ j- k2 {' ^, }9 D- @1 l
int tmp;
$ R7 Q! n$ I- S, L! O! R MultiAdjListNetworkArc<WeightType> *p,*q;
+ f: a/ Z1 Q' l3 a% } for(int i=0; i<vexNum; i++)
3 l/ o9 ^- `" [/ v       tag=0;, m0 q# Z# E' O' ?  x, W0 M
for(int i=0; i<vexNum; i++)
9 x6 e" I, Y" K& V% `. B& U {7 ]8 M0 O, C% z! a5 x9 X2 x
      tmp=i;
9 Z5 `2 M2 o: W5 F3 m9 U       while(tag[tmp]==0||!s.empty())
1 M2 C/ Q! j. ^" R       {: w. ^% y7 p, C  Y9 j3 D0 D  P
         p=vexTable[tmp].firstarc;
6 O; M5 q) {: j' f0 T$ C5 t) w          while(tag[tmp]==0)5 k" n) z4 ?9 G- {
         {- v; w! a. W; ?! y3 a
            s.push(tmp);
' W* y2 J6 u: p. ~4 D; p/ m0 J             cout<<setw(3)<<vexTable[tmp].data;
+ r. m8 A+ l0 v) Q) {/ [$ H             tag[tmp]=1;
1 Q7 q' M! ]+ Q% ^5 U& @             p=vexTable[tmp].firstarc;0 Z+ e0 q" Z' b" Z" h& G
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
& O  O) v  n" T3 Q# D             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% G3 Z4 O' I3 `% S# a, F* s
            //cout<<" 1st    tmp="<<tmp<<endl;
# J- T. V+ G! B          }
4 z7 D$ m0 Y- r3 c2 k6 A. w          if(!s.empty())
' S9 |' {0 o/ R3 @/ Y8 z8 l' R4 ^          {3 Y0 j- y' H9 V" P! k% o* m* Y
            tmp=s.top();
* N" j$ }3 j7 j9 b+ Y             s.pop();7 M3 Q% K  K1 Y8 H* S7 ]
            q=vexTable[tmp].firstarc;
5 U$ q2 m, Z0 H! m6 t) H             int t=tmp;
0 D1 Q) _# \2 L7 `# o# l/ ?& J             while(q&&tag[tmp]!=0)
- b! ^! b! K7 E: G0 L9 y1 U             {3 `( e5 G5 B! i' s( q: t  {! x, J
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);9 B# ?4 `3 E8 E9 {+ f; v4 L
                  //cout<<" 2nd    tmp="<<tmp<<endl;
( y$ ]( L' b$ F. d& S. h) G                   q=NextArc(t,q);" \0 E" y* n% r% `
            }
  Y6 `8 {& C/ L5 I8 n; W             if(tag[tmp]==0), F( N0 b* W% c% X6 D, O" _
                  s.push(t);
( i- p0 f' Z" M3 S             ///1、对应上面连通分支只有1个点的情况" H  |% z. V0 l- w, A5 n
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
7 p$ V/ r/ h! \: ~4 P, ^7 Z             ///tmp要么等于找到的第一个未访问节点，/ n% D: P% p! ^, w8 y' Q3 G
            ///要么等于与t相连最后一个点（已被访问过）
7 _- D& t' S: V" ]# A+ M/ d             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
) l" X% _1 b  A) B7 V( S9 s          }
8 s% G: Z: S4 [       }
3 C  {& d* K4 c5 S }+ w' O8 `1 _; r( \. o. {
}
% g1 R9 l0 H4 c# B! Z//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
- ~/ c4 d8 Z1 ]5 Jtemplate<class ElemType, class WeightType> int
5 S7 I0 o# V- s$ D6 p& |MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)1 @  z8 f# B% X8 o( X
{- X# c+ C, _* G: U$ `$ G) ?9 t0 K
if(head==pre)
& w+ _% [4 ?  r, P  b       return -1;% c& \- b2 R2 x& z

4 [$ R* |  T) ?3 s MultiAdjListNetworkArc<WeightType> *p;2 v! k$ a. S* V7 A, i1 K
p=vexTable[head].firstarc;
: ^. C0 H/ k5 F; N. l" I if(pre==-1&&p!=NULL)
2 D4 m- o4 O; P7 D& A2 M       return p->adjVex1==head?p->adjVex2:p->adjVex1;9 }* {  O: R# Y7 i9 @
//pre!=-1&&p!=NULL( c6 M" c; a8 O& [% s3 p. t: X
while(p!=NULL)
; M' K4 E: V) f) l7 k3 ~& f {
/ n1 @* A4 v* V/ {0 x       if(p->adjVex1==head && p->adjVex2!=pre). S' a, C/ r) O$ m/ M4 `
         p=p->nextarc1;" g+ ~6 e0 {7 r1 I0 S0 h! V- |! f
      else if(p->adjVex2==head && p->adjVex1!=pre)5 _5 S1 W+ V$ }1 M
         p=p->nextarc2;
3 Q# Y0 V3 T& Z" s       else if(p->adjVex1==head && p->adjVex2==pre): A$ [- U* S! B* O6 U7 ~1 E
      {
1 @3 M6 p; J( G8 c' b  a  x. Z( b          p=p->nextarc1;- q5 D3 K/ s+ q% K! E* b; c
         break;
9 m- J& ^6 ^% M. d: \$ k. [+ X       }+ F/ @. E' |1 ]( [% y* Y
      else if(p->adjVex2==head && p->adjVex1==pre)- ]5 K( v: b" I5 I9 i0 Y0 M4 b# S, S
      {
/ ?$ n' b" y. j* J          p=p->nextarc2;
  S  @+ X9 q- r! `- S/ U: i- Q          break;
8 A: o& O# r7 {- o- Q- t       }$ c* K, A8 f* s  h, D  j) k# J5 i2 G0 y4 S
}' h5 f1 H5 ?* f/ L" o
if(p!=NULL)
/ `. h5 ]/ Z# V" E {8 F* x' o9 k7 }+ m7 E; r
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
& l, [9 a$ Y5 l. v6 N( p }5 y9 t2 t4 Z# l$ F  j% U- u) S
else
  n, {2 t4 C: ]3 i, ]% S! F       return -1;! F- R' Z2 N8 `, b3 B
}' R- G2 T0 B/ g6 \# F  }7 K
. ]# s* e- Q! S5 {
- J. W. K% b: y; D- V9 ?
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
5 l9 V6 B. P5 l8 r{+ Y; {8 @3 O+ a' \' O' g9 v
stack<int> s;
. u2 j, @; x2 r& E& _+ W; K int p,cur,pre;. D( g/ u$ f5 i$ G, u- H7 E4 h1 x' O
//MultiAdjListNetworkArc<WeightType> *p,*q;7 ~5 a1 S4 e% V+ w
for(int i=0; i<vexNum; i++) tag=0;//初始化. o7 F( Q, z! X- u9 r, _; l) Y0 o( R
7 A2 e8 y5 c5 Z9 D2 {/ t
for(int i=0; i<vexNum; i++)+ e9 O! [) {) S6 f9 J3 l
{$ p' E2 i8 O. i
      cur=i;pre=-1;; O! J# n8 |+ ?" @
      while(tag[cur]==0||!s.empty())
  Y1 l; L! T* a1 D/ e2 B: j" D       {
3 D# q  f1 r" j$ o# [4 W          while(tag[cur]==0)
+ \9 h8 k* Z' U  F          {# b# S" f4 e" j) v1 M# O/ a
            cout<<vexTable[cur].data<<"  ";
8 E3 z; L5 b: Y5 N9 G" S             s.push(cur);
, C, D  H5 |2 k- o* e2 |             tag[cur]=1;
* v' }- D/ C/ q9 l; ?* ]             //初次访问，标记入栈
: ~" G* H- e- U1 ^; ]+ E4 V
. M/ ~$ ?" u) a6 @. q             p=GetAdjVex(cur,pre);//p是cur的连通顶点
- H# z; L9 l) C             if(p==-1)3 @& d- w% V2 K' |4 j
            {
/ o, X  n# p: V/ e1 z, Q  y                pre=cur;s.pop();
8 U) {" T! ^/ n# j, n% Q                break;
) l. Y6 b, Z) D& T! W# v  q' X" {             }
( y7 W& |  f' R2 _             else! ?7 s% J; c3 ^/ o; O: j' O) J
            {
4 u* _4 C) S2 |8 p. E. t                pre=cur;
$ d+ a, T' v0 c( B3 g  g$ R: ?                cur=p;
0 U% V! [4 L0 [$ Y! X- O             }  Z3 C  L9 W. y3 _6 b6 q( B& \
& t9 h& O; Y2 g+ Q9 A' e: R" N
         }, T0 W- v$ G- e
         while(!s.empty())
9 ?0 J9 T2 @9 r8 C          {
, W- o, |% B" q" c9 n             cur=s.top();/ ]! ]2 i1 A, A7 D3 M6 l
            p=GetAdjVex(cur,pre);5 M1 F$ N7 u: X' _, x# `, w$ ?; ?% R
            if(tag[p]==0)
: |, U0 Z* q+ g9 S( f- Y+ H' E7 U             {0 G8 D3 I1 a" I( L
                  pre=cur;
4 J2 l: `( B7 V, K" m: m: G                   cur=p;
6 a2 t1 a  t$ U6 r2 ^; @                   break;8 }- Q! H# r/ T: w) U0 {, R  e
            }8 W3 x! l5 r% a# d! _
            else
  ^' R) N8 S6 |) o, |7 v1 Y# u             {
+ F) v& ^3 q1 z, S: e                   pre=s.top();' A2 c4 U4 G9 F
                  s.pop();" j& J1 S- B2 W6 |& `1 Y
            }
, @5 I6 x* C3 Y) W3 d+ a5 ]6 m0 ?8 R6 }. k$ Q
         }
- `7 ~( O9 u4 `' w6 C0 y8 V  Z* y
      }
) a/ h) k( L, d# a4 T }
' A" P  C! _9 y1 b' s}; y& \7 w5 k4 S% {7 Y& f+ X, h
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
" d$ }6 a3 ?4 v$ w/ ], x{6 ?& y0 g" J' h. e- `
for(int i=0; i<vexNum; i++)
% k- j* p5 a/ G& x3 A: K& l# p       tag=0;" q4 a# ~$ v! ^
queue<int> q;
. D& z9 J$ r( Y, K2 V& ?: ?$ q int tmp,t;
- c/ s* N; @2 t* y5 m MultiAdjListNetworkArc<WeightType> *p;3 Y$ s9 X6 l6 x8 N- _2 }! |& ?8 ]
for(int i=0; i<vexNum; i++)8 x1 e- L# H; x
{
" t+ j7 _, H7 d# G3 p) X+ u       if(tag==0)
. G7 l# s- [) m7 s  p8 ^       {
8 }  r6 o8 |( @8 k4 M) n          tag=1;: H" A% J2 `0 A& e
         q.push(i);, n- w: P& A( t
         cout<<setw(3)<<vexTable.data;+ A) f+ k* B9 p6 x& C
      }
4 R, P5 s; y4 Z       while(!q.empty())
3 ~/ C4 `" G, o$ h  q% l       {2 F$ ~9 o3 n; [8 g
         tmp=q.front();
6 \! X. ]2 @2 X* _          q.pop();! ], v3 a8 S8 N3 V8 m( z& t, m
         p=vexTable[tmp].firstarc;
, g2 H( r# W. R& d          while(p!=NULL)2 N+ H2 v6 R# m0 v) N  F  I
         {
6 y1 B0 d- G. O' O3 U8 {             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
7 s0 D) V. R% }" Y; Z             if(tag[t]==0)+ r; l, r' H9 z9 Y1 J/ [  z
            {
8 u8 d7 _6 ~6 X& a9 h1 ?                   cout<<setw(3)<<vexTable[t].data;
5 y( b6 D" d! k# Q2 V                   tag[t]=1;
1 v0 H8 b% U6 }2 J* I                   q.push(t);4 i% |7 x0 A4 }0 `: D1 t6 Q
            }0 `: w4 _, D- s0 k, H5 L
            p=NextArc(tmp,p);
) }9 M* t/ Z# m: J/ @# D          }) S/ j7 s( ^! @! P% r
      }
: \- V( H6 H( Z- N }
8 V- P2 r$ N: y}" q# f! y6 u: L9 P8 D
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
' a" u& l6 X% H3 e8 V0 H{. ]: O) S, S! X: {  ^- N
MultiAdjListNetworkArc<WeightType> *p;1 h0 K0 @' N; P& E: V, q
cout << "无向图有" << vexNum << "个点，分别为:";4 A5 Y6 f0 D, x6 F; F: _
for (int i = 0; i < vexNum; i++)/ Q" H5 M7 J: g# q- H2 _8 O5 e4 e
      cout << vexTable.data << " ";
2 C0 q& p4 B; }% \ cout << endl;
6 G/ k0 Z0 d8 ^  l( G( X cout << "无向图有" << arcNum << "条边"<<endl;2 M5 g  X! U3 l0 w
for (int i = 0; i < vexNum; i++)
: C  O+ E; L" Z) U, A5 q6 D' J3 ~ {
. \- c! @3 A3 T. [/ g+ F# A       cout<<"和" << vexTable.data << "有关的边:";/ R: S" e3 ]- j! n0 f
      p = vexTable.firstarc;8 H& x4 u4 e, Z! H7 R1 p% I+ i
      while (p != NULL); |5 ^% H; ?* `+ L, u! U2 S5 L
      {
2 X- s8 E# J- q2 E# h( ?          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";! r0 q: G1 F( D$ @) i/ F+ L
         p=NextArc(i,p);4 h) [  m3 L  M3 C- |' J6 L5 P; n
      }
0 R8 w" F) Y  p  D4 ]4 n       cout << endl;
3 ]  f) O6 i7 n" `, @$ P }
4 [! `' q; |4 L8 e& @" z3 r}
8 }% U0 Q! D4 X4 P6 D/ P0 w/ O  D) E
% N6 F& l3 E7 Z: N- n! I/ `
邻接多重表与邻接表的对比& {$ a) K( @, W  H% U- Y1 {: R, m

/ o$ L: P: \- D/ \$ m9 a6 q) l邻接表链接
( d# y, e( m' c  `" g* Q# r在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。! j) V- x* C0 F$ e4 Z$ ^
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。0 J) F6 y% E3 I: @
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。; y. w1 X! {( b2 A, ]% e
————————————————
* v6 k& N: |; R4 Z版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 Y6 n* ~! g/ p' R1 A6 ]原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958: B5 h, E/ b& G* R
* j, C4 c" r1 K' Z0 S
/ ^9 S+ u. S2 ~0 K+ R
9 \/ j3 O7 @, t& R) m. B
  ~. Y; v7 @5 S, C* m/ b& y
————————————————9 j! O5 I) `8 d9 G
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& S& z0 B2 l; u( F6 y& ~原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958% E* e) u( B" d

% Z* `& g7 N/ R. M& B7 P/ J+ M/ c: @