发表用户:James.Liu
收集整理:James.Liu
相关讨论:http://www.mygis.com.cn/forum/dispbbs.asp?boardID=24&ID=917
信息原始来源:不祥

文章标题:应用深度优先和广度优先做最短路径分析


    深度优先:

procedure Search(dp: integer; curnode);
begin
  if dp>当前最优解 then
    exit;

  if 当前结点是目标结点 then begin
    记录当前路经和长度;
    exit
  end;

  for i:=1 to 和当前结点相连的字结点的个数 do
    if 当前结点没搜索过 then begin
      标记当前结点;
      记录路径;
      Search(dp);
      取消标记
    end
end;

调用 Search(1, 起始结点)

    广度优先:
begin
  head:=0; tail:=0;
  q[0]:=起始结点信息;
  while head<=tail  do begin
    node:=q[head]; 

    if node是目标结点 then begin
      输出结果(用递归);
      break
    end;

    for i:=1 to 和当前结点相连的字结点的个数 do
      if 当前结点没搜索过 then begin
        标记当前结点;
        newnode.parent:=node;
        记录newnode其他信息;
        inc(tail); q[tail]:=newnode
      end;
    inc(head)
  end
end;