数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：+ C0 [% D6 ]+ m& m0 f2 g% o' g
data域存储有关顶点的信息；
; n# S* _! [$ C. \firstarc域是链接指针，指向第一条依附于该顶点的边。) n. t# `0 Z6 y# Z, C5 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;* U- B; x6 ^# D
for(int v=0; v<vexNum; v++)
$ O$ I. W# h. m, Q: V {* k1 e# Q7 s* x7 b; {( s
      if(tag[v]==0)
& R. v* a! J: }" Q          DFS1(v);
; ?* D( E' f" S9 n }
8 H" O" C! u4 z* S0 |2 e}' O9 ?3 |9 w' `
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()8 b# L5 u/ \! Z/ j
{. @& W$ G. z6 v, X- F& }: l
stack<int> s;5 E+ N# F% o$ w! _
int tmp;
6 y7 R! n. o2 J/ \: r MultiAdjListNetworkArc<WeightType> *p,*q;
, g* S2 I$ h9 T- X1 V9 j6 G for(int i=0; i<vexNum; i++)
7 G- k# ?1 n: _* Q" }, z5 ]       tag=0;/ j4 l4 B& u: @, g& {3 S* }
for(int i=0; i<vexNum; i++). S# i6 f. R1 r5 I4 K# p0 ^
{
5 ^( B! I3 ^& M' H       tmp=i;1 X# [! b9 ^% j3 J. S# t1 q0 u
      while(tag[tmp]==0||!s.empty()), `7 D* b/ L1 e+ @
      {$ P$ `; }% u$ e8 f4 B  J2 J4 S
         p=vexTable[tmp].firstarc;6 ^8 e1 U: x$ ^( r! @
         while(tag[tmp]==0)# P. C8 m# u6 {/ G" F
         {
6 p* }% d( M, y  i4 j( R5 k             s.push(tmp);# n+ |: H" |5 i% O
            cout<<setw(3)<<vexTable[tmp].data;: |/ z' k# x: b/ G/ w7 w
            tag[tmp]=1;
* Q9 `! A6 F2 p             p=vexTable[tmp].firstarc;
3 t2 ]" q2 t6 B             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
3 H, {2 ?5 g4 |5 ]$ g             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ q! ?: ^* J$ C3 ?* l  c             //cout<<" 1st    tmp="<<tmp<<endl;
4 [( \6 L5 ?; j6 F9 y* j          }+ A7 k* m# o* m% c% _; q- w5 w
         if(!s.empty())- \% M0 j7 l, S7 C* {- V$ ~
         {
& J# N2 V% v0 U) O! _" z# H$ x2 k             tmp=s.top();& ^7 S  }' X* W* H7 L+ K9 i
            s.pop();4 ]+ @' F+ A* e$ L: d9 B. o
            q=vexTable[tmp].firstarc;
% Y" ~7 P. ^8 ^: s             int t=tmp;
7 ]# W6 f$ T9 b4 g4 H; n8 `( `0 L" L             while(q&&tag[tmp]!=0)
+ K% P' d& n( O) Y* j: [+ N             {8 E$ T' O2 _; \, Z9 q5 Q
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
* u" D+ w! ~+ c6 k+ T                   //cout<<" 2nd    tmp="<<tmp<<endl;3 a  i7 B4 f# O: v
                  q=NextArc(t,q);
. g8 d7 T) p- B0 T             }
" ?* X* ?7 _% w+ _0 d, D             if(tag[tmp]==0)& P0 ]2 o. R' a( t( e
                  s.push(t);
. f; Z! W9 y. ^& W) x$ o             ///1、对应上面连通分支只有1个点的情况
% L" K$ l7 y6 I* ]1 y9 L             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
! o* c4 ]- O$ ]1 v" [% Y% l             ///tmp要么等于找到的第一个未访问节点，" _. u3 y0 D- Z( o$ I
            ///要么等于与t相连最后一个点（已被访问过）: D, n1 |3 _* f1 U3 W3 P; U
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
$ Z. m" e8 W; \          }
6 f. }9 @' I+ P3 z       }
5 b4 b# z7 r7 E3 i8 U( c9 k8 q- K/ f }8 X' ^9 q: a4 V  x
}
( |$ d$ m! e7 B: `8 y//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1% [& Z  g/ D+ J! y7 n* b- _* X! N
template<class ElemType, class WeightType> int
( N- D" o/ y5 j7 r& |MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
2 X" R; g3 O; F, }{
* f6 S, [- f( ^8 {( u if(head==pre)* {7 [4 K! w" M6 x) k5 w
      return -1;1 t( \! `, [% k4 Q5 _. v
- e1 p* e% c6 ?  m9 M
MultiAdjListNetworkArc<WeightType> *p;/ a: p( t, x( \7 u5 C: m4 w  ]
p=vexTable[head].firstarc;
" F& Q% N1 o0 i' h if(pre==-1&&p!=NULL): ]( A# p! B+ f* i/ E# ~1 ~3 W
      return p->adjVex1==head?p->adjVex2:p->adjVex1;/ N+ R( Y: S0 T3 h* f
//pre!=-1&&p!=NULL
7 f/ ?; i9 {5 Q4 [* J- N# ]1 K' t while(p!=NULL)
$ E) }. n) b, x7 X+ ]# [3 S7 f {
7 c4 F) b) @1 X) c& m" n       if(p->adjVex1==head && p->adjVex2!=pre)
: T# }* I4 U) d          p=p->nextarc1;
( Y3 r6 w1 O( U2 [       else if(p->adjVex2==head && p->adjVex1!=pre)
# P7 B. A/ o" _  v          p=p->nextarc2;
7 l% o3 P- X& F# \/ j6 T8 l1 |2 f       else if(p->adjVex1==head && p->adjVex2==pre)
3 I4 Y$ g1 V! d1 U       {
7 J& Y$ A' i6 i# v- Z: L          p=p->nextarc1;: X4 r7 G8 d; F
         break;2 C1 v# x3 k6 w  X( a
      }
7 v3 Y' Y. Y+ l  _! l! R$ r       else if(p->adjVex2==head && p->adjVex1==pre)
4 s0 X# y  m0 v, [       {
8 w$ _1 p6 Z/ L* E+ o! @          p=p->nextarc2;3 @, M& Y8 Q( G; ?# h# d9 l# }# C
         break;6 l4 |6 ~# m) k; U
      }
2 ^+ s: g0 Y( k) g) v, T }
4 h' ^& P) d3 @* ~- Y; C0 \ if(p!=NULL)
  J9 E7 Q! S, A$ w {
6 `( S) L! _1 n. K* b. e) b8 m& l# X       return p->adjVex1==head?p->adjVex2:p->adjVex1;
$ ^) H. t! E* m }+ ], h2 u* \* C& t  b/ q8 k, a- S/ A; B
else
# W1 T+ r, Z% j) i* Y& J* P3 o       return -1;
' J* K- o4 S, n" n; A}- b/ [& U4 i' H( ?4 E3 P
0 O# \' i! L; |7 K
! H( i6 w! M# Z. {" W
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
+ w  P/ _6 Z# y6 ]  t  _5 I{$ s( Z! f3 r; Q0 h$ x- p8 U
stack<int> s;# a- d! j0 \+ H3 {5 b* O' C
int p,cur,pre;/ T& Z. A! g( j7 S) E. `. M
//MultiAdjListNetworkArc<WeightType> *p,*q;
3 H% p; [7 V- m* k, k; I) d" E for(int i=0; i<vexNum; i++) tag=0;//初始化
4 ]: U7 j# _5 ]5 o. D
5 d1 b5 U* N2 ~& t7 \ for(int i=0; i<vexNum; i++)# x6 h& Y' f7 C9 D$ _
{
' C( b1 [$ Z9 k! g$ C  f       cur=i;pre=-1;$ [+ Z5 ~, M6 B$ f4 i( E- ^3 i6 P
      while(tag[cur]==0||!s.empty())( h( R0 @" z8 O% f( B; E6 D' {2 Q" W
      {
, L- }, ]5 j" E          while(tag[cur]==0)
  O2 G) Y$ ~7 O2 l3 K+ J          {
' n* {) u3 s  C5 P! B0 l* L             cout<<vexTable[cur].data<<"  ";
7 O* P& f& r/ a% T2 x" W             s.push(cur);' C4 k; ^& w" X( N4 ?
            tag[cur]=1;9 O: H  W1 p% V" f" j7 Y3 f
            //初次访问，标记入栈+ k- Z8 ^& e: b5 [8 v, J: Y1 g) V

5 M5 s; z4 c6 B1 v' A& E; w2 M% A" @             p=GetAdjVex(cur,pre);//p是cur的连通顶点
( M1 i% q; ~9 b/ M' H             if(p==-1), F* g( m! O4 f3 X: m3 ^
            {
5 R9 {" I; M& q                pre=cur;s.pop();
5 D, @& j( j6 k- o                break;
$ }2 k7 ], i# w6 p" t: N5 D. D             }
" C8 R. R( x7 h7 Y7 {             else
; O! T5 a) `2 A; X0 ?. d& m             {
5 x' b$ [4 s. s9 A                pre=cur;
8 e  Y* s1 a; y$ i  z: m: b                cur=p;7 Y' B% m3 @( D$ a
            }
( |& z( Q, v# v7 T* S7 A5 @' X. U6 D$ \- e6 ^
         }
( E( P0 r) }0 ^& Y* p3 @5 [( \          while(!s.empty())1 `$ s5 |4 o9 H; B
         {. T; X1 o: t9 Y1 }
            cur=s.top();
( O! M$ h$ e& u: T             p=GetAdjVex(cur,pre);
, e2 d; [. p+ [) b- _. e             if(tag[p]==0)
" j7 M5 f+ o, @, w* n- @% ^, c             {3 X$ {2 l; o( x0 w, l
                  pre=cur;: K7 t  u* q" Z/ \
                  cur=p;
. n" |: k( V/ j, a                   break;
7 A, o& r& O+ u$ v  Q- t( e             }( Y# }. [2 {  y/ x/ Y. V; {
            else
8 r4 P& }4 j$ b3 D) V5 L2 p8 O             {
5 p  s; \2 V: \( s( G: @& i, g                   pre=s.top();- Q7 T0 a' e5 q" y' P" Q2 X9 ]- V0 V
                  s.pop();
0 f0 J5 [2 w4 Q3 d& c! ]" {             }
) _9 H& W7 A2 E- t. c: b; X& ?/ [# `8 B* G( y; w8 E& U
         }
( e+ a6 C2 o% B! w
( |7 F! W* D& i" ?: D3 |6 E0 V, t       }- r4 Q) r& V0 U( d7 e
}
2 x' d% m# R# i6 f5 s4 f0 l}+ c8 q) q4 x5 w) B1 K
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()% G. E+ L% T/ @
{* j7 X9 V  U! r. d
for(int i=0; i<vexNum; i++)
" b! L% A6 Y6 ~2 }) i       tag=0;
0 {2 U" |$ G% @9 Z queue<int> q;
4 P4 V+ j/ s; M" ~9 t int tmp,t;+ R0 q( O$ O( v; H7 [) X
MultiAdjListNetworkArc<WeightType> *p;
) E% \- a" F( Y1 K for(int i=0; i<vexNum; i++)
) c9 {1 K$ t" w8 x; l8 q8 V {
$ {- K( N" k( ?" U$ i       if(tag==0)% D# D8 w+ B: ^3 y" ^3 D
      {4 e# d. K3 R* f9 c2 Y, v9 L3 ~
         tag=1;
. b* L- ~0 r% C1 T          q.push(i);
8 Y' g" ^# F1 c' w% D          cout<<setw(3)<<vexTable.data;0 O$ H. A: E/ J0 J' p8 a# p8 g
      }# b! H+ m+ ]0 ]
      while(!q.empty())% m' A) g- M. R$ H6 v+ d& T0 W. w0 k
      {/ m3 y; o% q. X: ~% K
         tmp=q.front();) L) {* h# o* M0 H4 y: ^( r9 Y
         q.pop();
$ w2 B$ ~! m/ N. h          p=vexTable[tmp].firstarc;# X0 A, h0 q7 X" n
         while(p!=NULL)' `& E0 A3 D  m  ]5 J! ?+ J
         {
( d! X) s: i3 s. q. C4 B5 S4 y! k             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
: F: [4 f: O7 X1 }             if(tag[t]==0)8 p+ k* k+ H4 ~
            {% [# n4 T% I6 z7 K( B0 x
                  cout<<setw(3)<<vexTable[t].data;
% n* u& a# Z$ _3 {                   tag[t]=1;' N$ m! ^, O7 ~3 G/ J, R8 t! ]) _0 n
                  q.push(t);4 y$ h3 {8 D9 p1 t
            }  @+ ^) \9 U3 X
            p=NextArc(tmp,p);! h2 v2 E) p7 |& O7 D& @, |% V
         }! j% H6 a/ t( w( I) D( ~0 A& \
      }- @- G7 F; z: z3 E4 J
}% s/ ]0 e8 `% K: q
}( G, \) L2 j: [/ S/ U! z$ l1 C
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()0 H" C( P0 P& l1 `5 w4 }$ [
{
. d% ~5 d8 P+ k MultiAdjListNetworkArc<WeightType> *p;4 `  g3 f% {+ M* y3 m
cout << "无向图有" << vexNum << "个点，分别为:";  Q6 a# P% I. P; W/ x
for (int i = 0; i < vexNum; i++)$ b, I. @: X' q! Q4 ~. z) Z
      cout << vexTable.data << " ";* `- h5 [6 \$ r; Y
cout << endl;
4 l' F  d* C* k, S/ \ cout << "无向图有" << arcNum << "条边"<<endl;. s! Y% H+ H* m2 m
for (int i = 0; i < vexNum; i++)# r; L0 p6 g' m& E1 X! T# g
{# |* [- }5 k2 g" e5 Y
      cout<<"和" << vexTable.data << "有关的边:";
0 R( |7 s2 r* r) t       p = vexTable.firstarc;) d6 o: \! y# p" W4 h6 ~% A
      while (p != NULL)) M* A. p0 g1 v
      {
  t- M/ q$ @- L$ `8 \/ P! u          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
8 G7 O  s2 v5 l+ o& Y0 }          p=NextArc(i,p);
* n9 u; T5 g2 S       }
9 v; O% `6 o  D+ k" c. N' D+ z       cout << endl;" `8 o9 }+ |0 H$ x: ]
}. z) s; U3 k0 _. {
}
  F( O- d, y: R  j, w7 |, c5 g8 b: O. W) @

1 f2 y* h. ~# d1 w" w* d邻接多重表与邻接表的对比
2 Y( Q1 {& X, t
" \1 q; J* g! ^/ [邻接表链接( v2 j: x, h# b2 N" k
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
( }7 T( ]8 U0 [/ y+ k+ t/ Z2 m! `2 T在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
* [  f) f# C( y( S为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。* n$ h* E& I% t  g
————————————————
( K8 ?! B) ^( r( v% E; N7 T1 y版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. Z* X6 ]* E1 U% j原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
# e+ g% w* Q5 `+ \* S/ [8 q* [6 [' J  L6 e( \/ I

7 L4 y2 z$ V& g2 B1 q0 |) B! N6 @. B- ~! t- o8 q7 q

+ T  p( q$ ?7 _  N2 s' d! b————————————————5 h1 j) a8 d) v4 N" y
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。, R! D/ k1 Z  C. ?5 x
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669582 Y% R0 |# o- C. p' H3 w( D  P
$ O' m$ r! W, B: g4 L- o# c: D
& z5 B8 s, i% I4 }2 r. `0 Q2 v

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