数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：, H( R, N$ Z9 M- V8 I3 Y7 d2 L# V
data域存储有关顶点的信息；
: j- H p# \/ b6 i7 `; Y' hfirstarc域是链接指针，指向第一条依附于该顶点的边。
; c( h1 c/ t' W/ z; y2 {5 O所有的顶点结点组成一个顺序表。

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;
3 `8 W5 ]+ C9 y# e( U  z for(int v=0; v<vexNum; v++)3 E; \& ?! L. k+ [+ I) F
{
5 h& W/ F& c# e$ O* V       if(tag[v]==0)) i, z7 i4 n9 z  M
         DFS1(v);
8 x; x5 _4 U+ C% F6 O# F% _% j }
: M# E1 R! b! A, d% p  C- T}  `% r6 g3 m/ d. Z5 L
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
9 h8 w  @  _. C: E( \9 |& F{
, D& c) V& p; c! l% i* M" b3 I stack<int> s;$ e9 v* x+ ]. _$ b6 ~* _# A2 ~1 E
int tmp;
7 d0 e' X# N+ j0 L6 Z MultiAdjListNetworkArc<WeightType> *p,*q;/ m9 b0 T1 u6 B: r/ ^
for(int i=0; i<vexNum; i++)
$ ]. }& ^. t& }, O) z       tag=0;1 L+ o2 v  R  b5 z6 f, B  Y
for(int i=0; i<vexNum; i++)
  @1 ~( q& s% x) s) R  C {
8 o( W( h) A. F# J3 L+ K( T       tmp=i;* F& |6 X+ }# I+ y4 [/ q8 I
      while(tag[tmp]==0||!s.empty())4 [. x4 L4 Y% b' A/ a& {: G
      {0 I  i' S: j4 t- [9 U- g
         p=vexTable[tmp].firstarc;
/ h5 Y% c3 f% e          while(tag[tmp]==0)4 Z8 X  q' I* o1 ?& j6 C5 N
         {
' Z, F) R( A8 k: e8 c             s.push(tmp);
6 h1 Q  W; H2 M) e  q6 J             cout<<setw(3)<<vexTable[tmp].data;
0 s% @  u( B, E             tag[tmp]=1;
% p2 K* |" h; Y: d             p=vexTable[tmp].firstarc;: n5 k4 `$ \2 i
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
# X, A" G+ N( k9 _6 F) V             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; T5 o- w# u+ c: s7 {# \! v" U             //cout<<" 1st    tmp="<<tmp<<endl;8 Z7 @; c3 |9 G+ j
         }. Y: p/ J0 j8 P% X4 Y
         if(!s.empty())
" p" A3 ^* `3 W4 z          {
8 Z/ u/ A6 T9 q3 D3 y             tmp=s.top();
$ z9 v6 w$ i( {8 U, X             s.pop();9 c0 `. y9 V7 p" Y/ O
            q=vexTable[tmp].firstarc;
! A& V/ B6 T" ~             int t=tmp;
+ O, H1 `' z! G' F  t             while(q&&tag[tmp]!=0)
6 j! s1 l0 O+ M             {
& i! a& @5 h8 i, R  s5 B                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
* g: l. [1 x5 r3 ^6 K8 m                   //cout<<" 2nd    tmp="<<tmp<<endl;
- a6 ~1 r9 G1 `8 s  J' B                   q=NextArc(t,q);& ]+ r0 j0 v$ a" x+ E
            }! c, p3 r, _* W# X6 m* _$ d- y- n0 N
            if(tag[tmp]==0)* L& E( H8 b+ L/ `5 r: Z
                  s.push(t);
* _) |# a6 y/ g7 o# |4 _- R             ///1、对应上面连通分支只有1个点的情况
; u; d' h. g( w. X             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
/ F3 d0 o' B9 N$ A: J             ///tmp要么等于找到的第一个未访问节点，% u+ V" D8 E$ s! l% m; M& Q
            ///要么等于与t相连最后一个点（已被访问过）+ y* L1 S+ Z) E
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点) f8 \( M. p8 v) t
         }
, x4 W: K3 ?& V! j& R( v4 h) u       }4 S& X% X# H1 @1 ~" @
}& g, p9 W0 T2 X, R
}
; _: x6 r# K7 H3 ]//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
9 D* ^" O, i0 }* G- F2 I2 Ntemplate<class ElemType, class WeightType> int0 |, f1 g" n7 V: j
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)0 \/ ~: ~7 p3 S4 J( e
{( S0 l5 |* W- ]* B1 f
if(head==pre)
' l5 }% s( i0 |' R: O- x       return -1;) u; D1 n# I8 O# W* X/ u
* f. z  b) M' d: J5 t% a" u4 X  ?
MultiAdjListNetworkArc<WeightType> *p;- R7 ]  N- x0 W9 U. f7 z7 g8 M
p=vexTable[head].firstarc;
. f: Z* D* P+ a0 K0 [ if(pre==-1&&p!=NULL), B6 e: y% c. }6 d1 K
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
9 w9 e3 [8 g1 `" X% E) I  ^ //pre!=-1&&p!=NULL
6 ~2 n% |% u4 c4 A2 B while(p!=NULL)' a( v" B4 E7 B' K
{
2 `) Y, V7 E5 R2 n# T/ \       if(p->adjVex1==head && p->adjVex2!=pre). J- a  E3 C! p3 E  B; `
         p=p->nextarc1;; y( c* O. L  d4 R
      else if(p->adjVex2==head && p->adjVex1!=pre)+ w2 ^9 x4 d. s, G' h) L5 _/ I) x
         p=p->nextarc2;
7 r9 p7 u- f2 W& |! }       else if(p->adjVex1==head && p->adjVex2==pre)
& S0 j9 W! U$ w, d% G. p$ a+ j7 n       {
( J- g; J' C# H$ }& J' L5 R- q          p=p->nextarc1;6 b, R% r# u$ R' Q# l5 q5 j- a/ N
         break;
6 F4 C6 F: e! h2 f" R9 y       }! S6 j2 D0 T0 A+ R
      else if(p->adjVex2==head && p->adjVex1==pre), X) B8 ^/ a/ V' X0 n/ [3 J
      {
9 Z3 \) H/ H7 O- s6 b          p=p->nextarc2;/ S# _8 v3 w: p; H, l$ n
         break;& W& p+ e  o2 Z8 a
      }" M9 {- G* h7 q  I9 w' h" x, L" ^  o% O
}
, y  A# H! e  ~( T7 L if(p!=NULL)
, n* l3 ?& D0 I! E/ K- e {
2 e8 s  `$ u! P. D& H, E       return p->adjVex1==head?p->adjVex2:p->adjVex1;
. y& N3 o  e% A# b, ^( b/ b }
" Z7 @" S7 Z+ o else
8 W& c4 K! [$ _) d+ }       return -1;: P+ }; e9 j$ M8 O  j* N# ]
}; m3 l3 u3 Y3 Z2 E; m
. S9 M# W" z. Y+ [
  S# ?$ l/ X0 X
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
# F! F+ x$ k  \/ [{  g7 h2 u6 ^9 x3 S8 p) m
stack<int> s;: X- _0 h% I  u" S4 z
int p,cur,pre;
% J% g  R0 ]7 I+ d //MultiAdjListNetworkArc<WeightType> *p,*q;
9 r( O7 k% x5 l9 U1 T. v( h  Q/ ]4 M for(int i=0; i<vexNum; i++) tag=0;//初始化
" V7 H; e) n( ~/ e+ z5 ?& f2 ~3 _+ j( ^* y( P' \6 C
for(int i=0; i<vexNum; i++)( F5 n! z2 C! i( o, X
{
3 c  z- J3 C: a( _8 X, P       cur=i;pre=-1;
2 G5 N( J/ |0 k: H1 y6 x; b0 Q) I       while(tag[cur]==0||!s.empty())
- R2 b/ ?6 A2 O       {
! @! c7 K1 d1 N          while(tag[cur]==0)
: k; V9 v  \3 G5 j; Y3 i% N8 M          {
( z& i9 S) I/ w! X$ F             cout<<vexTable[cur].data<<"  ";, t9 Z' q0 X3 u, c
            s.push(cur);
" ~3 ?: i+ `+ d/ b             tag[cur]=1;
3 U  ~, e4 R% i: Y: Z% u& z) Q( N             //初次访问，标记入栈: w6 R  A$ p9 o+ W- ?5 A+ X

, d. h; n5 P6 r0 e- O             p=GetAdjVex(cur,pre);//p是cur的连通顶点
8 [) ]' ]" h5 I$ f$ i/ L0 G0 n             if(p==-1)
. R! A2 z! Y' E) R' n, h             {
2 P, R$ ]6 t9 X                pre=cur;s.pop();8 y1 u* T! @. z
               break;" _+ i; R5 W9 B6 V, w9 R+ T
            }8 V6 I- i8 R7 E- O! |
            else
1 P& G$ A1 U" P( R; P6 M3 V             {
3 S& f; v, H$ w9 \; F                pre=cur;
! l' c, g( z5 t* e                cur=p;9 h; O. y4 v8 M
            }7 ]) j9 r8 a/ Y/ z2 @

& ?4 i9 F: m( O) l3 G; v          }
' b8 B7 a3 W3 i* G' p2 P, D# s+ H3 Z          while(!s.empty())
( }* Z" X0 X7 E, w2 |4 o          {
9 K0 c, j) j4 P3 P% s: W# f9 D             cur=s.top();+ K7 y' V7 x: D
            p=GetAdjVex(cur,pre);
' z: M# D* g! [6 w- H             if(tag[p]==0), ~* [6 ?" b) j0 h
            {) Q% I3 Q0 U2 \
                  pre=cur;6 l: @8 j* F% O2 t
                  cur=p;' p7 Q, a- w" v& g) D2 U
                  break;
, }& n8 K8 J5 J: h             }. |# X: ]( x1 S: |7 T8 k2 [5 X
            else
7 a4 c2 Z7 t! F; D* a9 x             {; t6 t; M8 [6 g. E; g$ K
                  pre=s.top();
+ n! R7 \/ r) z* ~7 j                   s.pop();
: m% R6 _9 H' P0 v9 h3 e0 l$ ^             }
8 u0 L* @" R# v: _! m* I: o, I( ?& K- v7 f
         }0 d9 ?' y* U- F2 P0 _. \: T

9 l# x) Q0 b! Q7 A2 y- M0 r       }% p0 T6 e7 t4 ]' m( t" k  C
}: r5 O0 ~; q) A& a- j
}1 j1 I2 W9 w) {+ q
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
" H1 C9 `5 o& k: {8 @5 a% ?{0 }1 ]6 }0 B' l
for(int i=0; i<vexNum; i++)" w) {$ f  U; q4 }% a
      tag=0;2 ]8 _( }' \9 r
queue<int> q;
3 o/ W  E; {" o$ s int tmp,t;, z7 Z& a' f6 \* Q- j6 r, Q1 w+ F
MultiAdjListNetworkArc<WeightType> *p;
& K/ o# u+ ?; I( x for(int i=0; i<vexNum; i++)
. Y# D8 L* [& O$ j  F! n% { {
( p1 x/ Y2 l  U7 N" C+ @  l  k- M       if(tag==0)
; O3 |4 w8 G/ E- g4 N/ e       {
; k& Y- W8 B  ?# x          tag=1;
& B, p- E2 p1 B0 i0 H          q.push(i);" R, J9 w( u- P/ V/ G; [3 f
         cout<<setw(3)<<vexTable.data;
3 i" m1 a4 |' F' A$ ~2 u# V       }
7 G* y2 x, g, F' Q6 E9 g; u       while(!q.empty())
+ A2 D$ z5 l; h" A: G6 W       {0 [  Y7 Z  I8 \6 ^0 M3 }" @
         tmp=q.front();. }' W' T* _! t& t' ?
         q.pop();: R5 X2 ^+ r& K2 ?/ W
         p=vexTable[tmp].firstarc;
; {+ \) G! N6 R9 M          while(p!=NULL)  h0 r* Q( ]3 B4 R  O- s. B0 L
         {
1 G2 L$ z' O& D$ B% o             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
+ S+ ?+ s1 Z, T$ r6 n7 \             if(tag[t]==0)6 U6 q$ q( A% u# H+ s
            {
' Y% Q" E& ?) C/ x/ b5 z                   cout<<setw(3)<<vexTable[t].data;- ^2 H9 }0 d' ~- e& v( p+ F
                  tag[t]=1;
% o! x# F" b& b2 g' x  F5 r                   q.push(t);
  Y" z' O, [) k0 K) _' M             }2 i" N& J% _; U1 ?$ I7 X/ r7 i
            p=NextArc(tmp,p);+ ?4 I; w! c& l! Z9 @# ]
         }
$ S! K5 X/ {; a" v1 K       }
( u* c0 f' ]4 ]/ w6 }' |0 [ }& }9 T, o6 {9 y2 f$ X8 w2 {
}
. }/ S' K) k0 [. ^2 Y/ utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()! H, X* A6 l" O& d
{
/ m; X2 Z2 \& f% j" {" Q; F MultiAdjListNetworkArc<WeightType> *p;) k6 l* t- p  j
cout << "无向图有" << vexNum << "个点，分别为:";
8 D1 f( I3 s4 m5 ?- c8 v4 y for (int i = 0; i < vexNum; i++)
. E- r$ j( {. {( A5 n+ m       cout << vexTable.data << " ";
9 a% y/ O5 u+ W# E: ~ cout << endl;
, [& n3 n# y" h  X2 K- J, O) O% X cout << "无向图有" << arcNum << "条边"<<endl;9 g, F2 y* c0 B* E5 t9 q
for (int i = 0; i < vexNum; i++)7 c: q0 ?1 N# z
{
# f( n, E& L& C       cout<<"和" << vexTable.data << "有关的边:";
7 x  m- @. f- r/ |       p = vexTable.firstarc;
& J& K1 @6 L/ u       while (p != NULL)
" Q: @5 A% f3 r. {0 p% J3 ~7 P; M3 c       {1 O' M* a  g2 i( C. N, K& K' T
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
: Z# s4 W, |/ `- B          p=NextArc(i,p);
9 f, `  Z# M1 X/ W+ Q2 _  s/ W7 j       }
+ Q& u/ Z# l0 x) N2 D       cout << endl;
5 c1 q; c* r5 b$ B6 ?: V }0 R" W5 r! G* J
}
/ y3 i9 u/ l7 f( _
% b, r& x6 I# [1 \- S4 o( A. N
5 H' _7 f3 u" Z+ D9 ^' M邻接多重表与邻接表的对比  }5 U' S& J7 J0 V6 T

, F7 m3 u8 U+ {4 U, W邻接表链接
; f- Z" `: d+ u在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
$ x6 a3 {+ C8 ?: N# }. B: C在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
  y" t6 c5 [$ f6 }1 m' o3 c4 P为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。, X) b6 o3 A1 Y$ W
————————————————+ s4 R) q5 w' B' |2 o: E
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' W8 }  D; x) L6 o/ c- d8 L原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
1 K9 S4 Q8 {/ G, P; U8 I
# O( ]" A0 x4 K+ Q) x  K8 |
# H: u( s7 S3 [1 ]7 T3 y% d& _2 d, }( `: D

; q- B' z+ {+ K% l" L————————————————4 S, \& g$ Z# u5 h+ N+ n' E2 L$ p
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 \  B8 z: M, [( P原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958/ f! R) J  @0 X
. m* e$ |+ y- p6 |1 |+ F* w4 e& o

- ]: G, {& \/ y' D3 V+ o& ~$ d

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