會員之間的打印關係

Question

我有一個大學項目，我必須逐級打印不同班級學生之間的關係。這個想法是，如果我們有約翰和克里斯在同一班上學習，他們是第一級的朋友，如果克里斯在同一班上學習數學，那麼約翰和數學是第二級的朋友。我研究這個問題，我發現算法，如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

我拿出那個函數（不知道這是最好的解決方案，但它與類對象的工作）

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，標記爲「訪問」。

然後，在進入第二個之前，您爲第一個學生處理A + 1級。在他的「連鎖店」某處，你可能會發現第二名正在等待A級處理的學生。然而，他現在被分配了更高一級的A + n，然後被標記爲已訪問。

接下來，當student1的遞歸完成時，您繼續第二個。然而，他已經「訪問」...

（順便說一句，我不太明白（但我的PHP是弱...）爲什麼你第一次調用GetRelations指定水平= 2。）

無論如何，爲了讓你的邏輯正確無需遞歸。

爲每個學生添加一個屬性「級別」。把所有的學生也放在一個整體收集「人口」。

然後，對於選擇的「startStudent」，給自己的水平= 0，所有其他學生的水平= -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; 
    } 

希望這可以幫助你。當然，你仍然需要填寫樹/印刷材料;我的貢獻只涉及正確分配級別的邏輯。