Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3293264
  • 博文数量: 406
  • 博客积分: 10227
  • 博客等级: 上将
  • 技术积分: 9807
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-17 21:48
个人简介

非淡泊无以明志,非宁静无以致远

文章存档

2020年(2)

2019年(5)

2018年(4)

2017年(3)

2016年(24)

2015年(8)

2014年(7)

2013年(3)

2012年(1)

2011年(23)

2010年(179)

2009年(147)

分类: C/C++

2010-06-01 21:16:13

  从图中某一顶点出发,按某种搜索方法访遍其余顶点,且使每一顶点仅被访问一次。这一过程称为图的遍历。

  遍历图的基本搜索方法有两种:深度优先搜索DFSDepth First Search)和广度优先搜索BFSBroad First Search)。这两种方法都适用于有向图和无向图。

图的遍历算法设计需要考虑3个问题:

  1)图的特点没有首尾之分,所以算法的参考要指定访问的第一个顶点。

  2)对图的遍历路径有可能构成一个回路,从而造成死循环,所以算法设计要考虑遍历路径可能的回路问题。

  3)一个顶点可能和若干个顶点都是想邻顶点,要使一个顶点的所有想邻顶点按照某种次序被访问。

  对于连通图,从初始顶点出发一定存在路径和图中的所有其他顶点相连,所以对于连通图从初始顶点出发一定可以遍历该图。

1.图的深度优先遍历

  图的深度优先遍历DFS算法是每次在访问完当前顶点后,首先访问当前顶点的一个未被访问过的邻接顶点,然后去访问这个邻接点的一个未被访问过的邻接点,这样的算法是一个递归算法。

1) 连通图的深度优先遍历算法思想。

1)访问初始顶点v并标记顶点v已访问。

2)查找顶点v的第一个邻接顶点w

3)若顶点v的邻接顶点w存在,则继续执行;否则回溯到v,再找v的另外一个未访问过的邻接点。

4)若顶点w尚未被访问,则访问顶点w并标记顶点w为已访问。

5)继续查找顶点w的下一个邻接顶点wi,如果v取值wi转到步骤(3)。直到连通图中所有顶点全部访问过为止。

2) 深度优先遍历算法

(1)邻接矩阵的深度优先遍历算法:

void AdjMWGraph::Depth(int v,int visited[])

 { 

cout<<""\n 顶点"<权值:"<

   visited[v]=1;

 for(int col=0;col

if(Edge[v][col]==0||Edge[v][col]==MaxWeight)

continue;

if(!visited[col])

Delpth(col,visited);

  }

}

  故用邻接矩阵表示图时,搜索一个顶点的所有邻接点需花费O(n)时间,则从n个顶点出发搜索的时间应为O(n2)DFS算法的时间复杂度是(n2)。

 

(2)邻接链表的深度优先遍历算法:

Void AdjTWGraph::DepthFirst(int v, int visited[])

 { 

int vj; 

Edge *p;

  cout<

  visited[v]=1;

  p=Vertices[v].adj;     //v的邻接边结点

  while(p!=NULL)

vj=p->dest;       //v的邻接点编号

   if(visited[vj]==0)

DepthFirst(vj, visited);

   p=p->next;       //取下一个邻接边结点

  }

 }

  使用邻接链表来表示图时, DFS 算法的时间复杂度为 O(n+e),此处 e 为无向图中边的数目或有向图中弧的数目。

2.图的广度优先遍历

  图的广度优先遍历BFS算法是一个分层搜索的过程,和树的层序遍历算法类同,它也需要一个队列以保持遍历过的顶点顺序,以便按出队的顺序再去访问这些顶点的邻接顶点。

1) 连通图的广度优先遍历算法思想。

1)顶点v入队列。

2)当队列非空时则继续执行,否则算法结束。

3)出队列取得队头顶点v;访问顶点v并标记顶点v已被访问。

4)查找顶点v的第一个邻接顶点col

5)若v的邻接顶点col未被访问过的,则col入队列。

6)继续查找顶点v的另一个新的邻接顶点col,转到步骤(5)。

2) 广度优先遍历算法

(1)邻接矩阵的广度优先遍历算法:

void AdjMWGraph::Depth(int v,int visited[])

 {  sqQueueq;        //定义队列queue

   q.EnQueue(v);        //顶点v入队列

   while(!q.IsEmpty())        //当队列非空时循环

       {  

v=q.DeQueue();        //出队列得到队头顶点u

  cout<顶点"<权值:"<访问顶点v

      visited[col]=1;//标记顶点v已访问

     for(int col=0;col

if(Edge[v][col]>0;&&Edge[v][col]

          q.EnQueue(col);

   }

   cout<

 };

  邻接矩阵表示图时,搜索一个顶点的所有邻接点需花费O(n)时间,则从n个顶点出发搜索的时间应为O(n2)BFS算法的时间复杂度是(n2)。

(2)邻接链表的深度优先遍历算法:

void AdjTWGraph::BroadFirst(int v, int visited[])

 {  

int vj;  

Edge *p;  

SqQueue Q;

Q.EnQueue(v);

    while(!Q.IsEmpty())               //队列不空,循环

      {  

v=Q.DeQueue();         //出队并且访问顶点v

     cout<

      p=Vertices[v].adj;             //v的邻接边结点

while(p!=NULL)   {

vj=p->dest;     //v的邻接点编号vj

     if(visited[vj]==0) Q.EnQueue(vj); //vj未访问,入队

       p=p->next;             //取下一个邻接边结点

    }

   }

  }

  使用邻接链表来表示图时,其 BFS 算法的时间复杂度为 O(n+e) ,此处 e 为无向图中边的数目或有向图中弧的数目。

 

阅读(2617) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~