求一算法思路，关于交友网站

A - B - F - M 最短路径算法

A - B - F - M
A要认识M，查询M的相关条件不行吗

算法最好去C或C++或数据结构与算法这几个版问~~感觉做WEB的在算法方法比较弱~~

A------B-----F-----M
AM.......AM.........MAMA.....
A
M
这样~~关系不断发展。。

怎么又来这个问题？之前有讨论过。楼主搜搜吧。那个帖子里，众多高手都有发言。
后来有个人提了个贴看了看，好像是用笛卡儿算法。msdn上的好像。另外，好像递归也是一种思路吧？

“最短路径算法”是“数据结构”中的基本算法
当然实现起来各有千秋了！参考程序
<?php
/** 节点类
* 构造函数要求传入一个数组
* 用于传递节点的信息
* 第一个元素表示节点名，其他元素表示相邻的节点名
**/
class NODE {
  var $name = ''; // 节点名
  var $data = array(); // 相邻的节点名
  function node($array) {
    $this->name = $array[0];
    array_shift($array);
    $this->data = $array;
  }
}/** 连通图类 **/
class TU {
  var $stack = array();
  var $dict = array();
  var $out = array();
  var $good;
  function TU($array) {
    foreach($array as $value)
      $this->stack[] = new NODE($value);
  }
  function init() {
    $this->dict = array();
    $this->out = array();
    $this->good = array();
  }
  /**
   * 方法 locate
   * 传入节点名，返回节点对象
   **/
  function locate($node_name) {
    foreach($this->stack as $key=>$value) {
      if($value->name == $node_name) {
        return $value;
      }
    }
    return false;
  }
  /**
   * 方法 find
   * 传入起止节点名，输出可能的路线
   **/
  function find($start, $end) {
    array_push($this->dict, $start);
    $node = $this->locate($start);
    if($node->name == $end) {
      echo join(" - ",$this->dict)."<br>";
      $this->out[] = $this->dict;
      if(empty($this->good))
        $this->good = $this->dict;
      $this->good = count($this->dict)<count($this->good) ? $this->dict : $this->good;
      array_pop($this->dict);
      return;
    }
    if(empty($node->data)) {
      echo join(" - ",$this->dict)." | stop<br>";
      array_pop($this->dict);
      return;
    }
    foreach($node->data as $v)
      if(! in_array($v, $this->dict))
        $this->find($v, $end); // 递归调用find方法
    array_pop($this->dict);
  }
}//例
$o = new TU(array(
array("A","B","C","D"),
array("B","E","F","G"),
array("E","H","I","J"),
array("F","K","L","M"))
);
$o->init();
$o->find("A","M");
?>

<?PHP
$data = array();
$data[A] = array('B', 'C', 'D');
$data[B] = array('E', 'F', 'G');
$data[E] = array('H', 'I', 'J');
$data[F] = array('K', 'L', 'M');$obj = new parse($data);
$obj->find('A', 'M');
echo $obj->getBest();class parse{    var $data = array();
    var $used = array();
    var $chain = array();    function parse($data){
        $this->data = $data;
    }
    /**
     * $start 开始节点
     * $end   结束节点
     * $chain 当前查找路线的经过节点
     */
    function find($start, $end, $chain=array()){
        //将起始节点加入当前朋友链中
        $chain[] = $start;
        //判断当前起点是否有朋友
        if(!isset($this->data[$start]))
            return;
        //判断当前的起点是否认识终点
        if(in_array($end, $this->data[$start])){
            $chain[] = $end;
            $this->chain = $chain;
            return ;
        }
        //如果当前"未完成路径" 比 "目前的最优路径" 长, 停止当前循环
        if(sizeof($chain)>=sizeof($this->chain) && sizeof($this->chain)!=0)
            return;
        //继续递归循环
        foreach($this->data[$start] as $value)
            if(!in_array($value, $chain))
                $this->find($value, $end, $chain);
    }    function getBest(){
        $str = implode('->', $this->chain);
        return $str==null? "can't relation": $str;
    }
}
?>

上面只是查找和输出最短的路径, 并且在找到最短路径的同时,停止了长度过长的递归.(推荐)
下面的更简单,显示所有的路径<?PHP
$data = array();
$data[A] = array('B', 'C', 'D');
$data[B] = array('E', 'F', 'G');
$data[E] = array('H', 'I', 'J');
$data[F] = array('K', 'L', 'M');$obj = new parse($data);
$obj->find('A', 'M');class parse{    var $data = array();    function parse($data){
        $this->data = $data;
    }
    /**
     * $start 开始节点
     * $end   结束节点
     * $chain 当前查找路线的经过节点
     */
    function find($start, $end, $chain=array()){
        //将起始节点加入当前朋友链中
        $chain[] = $start;
        //判断当前起点是否有朋友
        if(!isset($this->data[$start]))
            return;
        //判断当前的起点是否认识终点
        if(in_array($end, $this->data[$start])){
            echo implode('->', $chain)."->$end";
            return ;
        }
        //继续递归循环
        foreach($this->data[$start] as $value)
            if(!in_array($value, $chain))
                $this->find($value, $end, $chain);
    }
}
?>

调试易

求一算法思路，关于交友网站

解决方案 »