大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 数据结构——图深度优先遍历的递归实现

数据结构——图深度优先遍历的递归实现


[摘要]本文主要是对数据结构——图深度优先遍历的递归实现的讲解,希望对大家学习数据结构——图深度优先遍历的递归实现有所帮助。

  一、深度优先遍历 深度优先遍历遍历类似于树的先根遍历,是书的先根遍历的推广。

  1.初始状态所有顶点都未被访问,从图中某个顶点v出发,访问此顶点

  2.依次从v的未被访问的邻接点出发深度优先遍历图,直到图中所有与v有想通路径的顶点都被访问到

  3.若图中尚有顶点未被访问,则从此顶点出发,重复1,2.直到所有结点都被访问为止。

  int FirstAdjVex(ALGraph G,VertexType v)

  { // 初始条件: 图G存在,v是G中某个顶点

  // 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1

  ArcNode *p;

  int v1;

  v1=LocateVex(G,v); // v1为顶点v在图G中的序号

  p=G.vertices[v1].firstarc;

  if(p)

  return p->adjvex;

  else

  return -1;

  }

  int NextAdjVex(ALGraph G,VertexType v,VertexType w)

  { // 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点

  // 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。

  //           若w是v的最后一个邻接点,则返回-1

  ArcNode *p;

  int v1,w1;

  v1=LocateVex(G,v); // v1为顶点v在图G中的序号

  w1=LocateVex(G,w); // w1为顶点w在图G中的序号

  p=G.vertices[v1].firstarc;

  while(p&&p->adjvex!=w1)      // 指针p不空且所指表结点不是w

  p=p->nextarc;

  if(!p||!p->nextarc)          // 没找到w或w是最后一个邻接点

  return -1;

  else // p->adjvex==w

  return p->nextarc->adjvex;        // 返回v的(相对于w的)下一个邻接顶点的序号

  }

  Boolean visited[MAX_VERTEX_NUM];      // 访问标志数组(全局量)

  void(*VisitFunc)(char* v);           // 函数变量(全局量)

  // 从第v个顶点出发递归地深度优先遍历图G.

  void DFS(ALGraph G,int v)

  {

  int w;

  VertexType v1,w1;

  strcpy(v1,GetVex(G,v));

  visited[v]=TRUE;                 // 设置访问标志为TRUE(已访问)

  VisitFunc(G.vertices[v].data);         // 访问第v个顶点

  for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))

  if(!visited[w])

  DFS(G,w);            // 对v的尚未访问的邻接点w递归调用DFS

  }

  // 对图G作深度优先遍历。

  void DFSTraverse(ALGraph G,void(*Visit)(char*))

  {

  int v;

  VisitFunc=Visit;             // 使用全局变量VisitFunc,使DFS不必设函数指针参数

  for(v=0;v<G.VEXNUM;V++) pre }< printf(?\n?); 对尚未访问的顶点调用DFS DFS(G,v); if(!visited[v]) for(v="0;v<G.vexnum;v++)" 访问标志数组初始化 visited[v]="FALSE;"><BR>

  <BR>



相关评论