Physics 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Physics
标  题: 图的搜索算法
发信站: 哈工大紫丁香 (Thu Jul 10 21:56:23 2003)

图的搜索算法主要包括深度搜索和广度搜索
深度搜索：
int dfsSweep ( IntList[] adjVertices, int n )
{
   int ans;
   Allocate color array and initialize to white.
   For earch vertex v of G, in some order:
     if(color[v]==white)//white代表还没有访问过
       int vAns=dfs(adjVertices, color, v)
       //process vAns
   return ans;
}
int dfs(IntList[] adjVertices, int[] color, int v)
{
  int w;
  IntList remAdj;
  int ans;

  color[v]=gray;//gray代表预访问
  preorder processing of vertex v

   remAdj=adjVertices[v]//获取v的邻接点的集合
   while(remAdj != NULL)
   {
     w= first(remAdj);//取出第一邻接点。
     if(color[w]==white)
        Exploratory processing for tree edge vw
        int wAns = dfs(adjVertices,color, w)
        Backtrack processing for tree edge vw, using wAns
     else
        checking for nontree edge vw
     remAdj = rest(remAdj)//相当于删除已经访问过的节点。
   }

  Postorder processing of vertex v, including final computation of ans

  color[v] = black;
  return ans;
}
广度搜索
void breadthFirstSerach(IntList[] adjVertices, int n, int s, int[] parent)
{
  int[] color = new int[n+1];
  Queue pending = creating(n);
  Initialize color[1],……,color[n] to white.
  parent[s] = -1;
  color[s] = gray;
  enqueue(pending, s);
  while(pending is nonempty)
  {
    v = front(pending);//取出队列的第一元素；
    dequeue(pending);

    For each vertex w in the list adjVertices[v];
       if ( color[w] == white)
            color[w] = gray;
       enqueue(pending, w);
       parent[w] = v; //process tree edge vw;
      //process vertex v

    color[v] = black;
  return;
  }
}
利用深度优先可以解决如：有向图的强联通分支，拓扑排序，二分图等问题。

--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.86]