打印成员之间的关系

Question

我有一个大学项目，其中我必须逐级打印不同 classes 学生之间的关系。这个想法是，如果我们让 John 和 Kris 在同一个 class 学习，他们是第一级的朋友，如果 Kris 在同一个 class 学习数学，那么 John 和 Math 是第二级的朋友。我研究了这个问题，发现了像 this 这样的算法，但我的主要问题是我使用对象作为输入数据：

<?php
class Student {

 private $id = null;
 private $classes = [];

 public function __construct($id) {
   $this->id = $id;
 }

 public function getId() {
   return $this->id;
 }

 public function getClasses() {
   return $this->classes;
 }

 public function addClass(UClass $class) {
   array_push($this->classes, $class);
 }

}

class UClass {

 private $id = null;
 private $students= [];

 public function __construct($id) {
   $this->id = $id;
 }

 public function getId() {
   return $this->id;
 }

 public function getStudents() {
   return $this->students;
 }

 public function addStudent(Student $student) {
   array_push($this->students, $student);
   $student->addClass($this);
 }

}

function getRelations(Student $start_student, &$tree = array(), $level = 2, &$visited) {
 foreach ($start_student>Classes() as $class) {    
   foreach ($class->Students() as $student) {
     if($start_student->getId() != $student->getId() && !is_int(array_search($student->getId(), $visited))) {
         $tree[$level][] = $student->getId();
         array_push($visited, $student->getId());
         getRelations($student, $tree, $level+1, $visited); 
     }
   }
 }
}

$class = new UClass(1);
$class2 = new UClass(2);
$class3 = new UClass(3);

$student = new Student(1);
$student2 = new Student(2);
$student3 = new Student(3);
$student4 = new Student(4);
$student5 = new Student(5);
$student6 = new Student(6);

$class->addStudent($student);
$class->addStudent($student2);
$class->addStudent($student4);

$class2->addStudentr($student2);
$class2->addStudent($student4);
$class2->addStudent($student5);

$class3->addStudent($student4);
$class3->addStudent($student5);
$class3->addStudent($student6);

$tree[1][] = $student->getId();
$visited = array($student->getId());
getRelations($student, $tree, 2, $visited);
print_r($tree);

我一直在编写 getRelations() 函数，它应该创建一个类似于

的数组

Array ( [1] => Array ( [0] => 1 ) [2] => Array ( [0] => 2 [1] => 4 ) [3] => Array ( [0] => 5 [1] => 6 ) )

但我无法正确递归（或者可能是整个算法）。任何帮助将不胜感激。

Answer 1

我想到了那个函数（不确定它是否是最佳解决方案，但它适用于 class 对象）

function print_students(Student $start_student, &$tree = array(), $lvl = 1) {
  if (!$start_student) {
    return;
  }
  $tree[$lvl][] = $start_student->getId();
  $q = array();
  array_push($q, $start_student);
  $visited = array($start_student->getId());

  while (count($q)) {
    $lvl++;
    $lvl_students = array();
    foreach ($q as $current_student) {
      foreach ($current_student->getClasses() as $class) {
        foreach ($class->getStudents() as $student) {
          if (!is_int(array_search($student->getId(), $visited))) {
            array_push($lvl_students, $student);
            array_push($visited, $student->getId());
            $tree[$lvl][] = $student->getId();
          }
        }
      }
    }
    $q = $lvl_students;
  }
}

Answer 2

你的递归过程中的逻辑不正确。示例：

假设您输入某个级别 A 的程序，实际上有 2 个学生可以找到该级别的连接。

你处理第一个，分配正确的A级，标记为"visited"。

然后，在进入第二个之前，您为第一个学生处理 A+1 级。在他 "chain" 的某个地方，您可能还会发现第二个等待在 A 级处理的学生。但是，他现在被分配到更高级别的 A+n，然后被标记为已访问。

接下来，当 student1 的递归完成后，您继续第二个。然而，他已经"visited"...

（顺便说一句，我不太明白（但我的php很弱......）为什么你第一次调用GetRelations时指定level=2。）

无论如何，为了让你的逻辑正确，不需要递归。

给每个学生加一个属性 "level"。将所有学生也放在一个整体集合中 "population".

然后，选择一个"startStudent"，给自己level=0，所有其他同学level=-1。

迭代关卡并尝试填充友谊关卡，直到无事可做。我的 php 几乎不存在，所以我尝试了一些伪代码。

  for(int level=0; ; level++) // no terminating condition here
   {
      int countHandled = 0;
      for each (student in population.students)
      {
        if (student.level==level)
        {
          for each (class in student.classes)
          {
            for each (student in class.students)
            {
              if(student.level==-1)
              {
                student.level = level+1;
                countHandled++;
              }
            }
          }
        }
      }
      if(countHandled==0)
        break;
    }

希望这对您有所帮助。当然，tree/print这些东西还是要填的；我的贡献仅涉及正确分配级别的逻辑。

打印成员之间的关系

Printing relations between members

php

oop

algorithm

binary-tree