Kaedah pelaksanaan algoritma aliran maksimum dalam PHP

Kaedah pelaksanaan algoritma aliran maksimum dalam PHP

Algoritma aliran maksimum adalah salah satu masalah klasik dalam teori graf Ia digunakan untuk menyelesaikan masalah aliran maksimum dalam rangkaian. Dalam aliran rangkaian, setiap tepi mempunyai had kapasiti, dan setiap nod mempunyai aliran masuk dan keluar. Matlamat algoritma aliran maksimum adalah untuk mencari nilai maksimum aliran dalam rangkaian, iaitu nilai maksimum jumlah aliran tepi yang melalui rangkaian.

Dalam PHP, kita boleh menyelesaikan masalah aliran maksimum menggunakan kaedah yang dipanggil algoritma Ford-Fulkerson. Berikut akan memperkenalkan cara melaksanakan algoritma Ford-Fulkerson dengan PHP.

Pertama, kita perlu mentakrifkan kelas graf untuk mewakili graf dalam masalah aliran rangkaian. Setiap nod dalam graf mempunyai pengecam unik dan senarai bersebelahan. Dalam PHP, kita boleh menggunakan tatasusunan untuk mewakili senarai bersebelahan. Berikut ialah definisi kelas graf ringkas:

class Graph {
  private $graph;

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

  public function addEdge($u, $v, $w) {
    if (!isset($this->graph[$u])) {
      $this->graph[$u] = array();
    }
    $this->graph[$u][$v] = $w;
  }

  public function getAdjacencyList($u) {
    return isset($this->graph[$u]) ? $this->graph[$u] : array();
  }
}

Seterusnya, kita boleh menentukan kelas algoritma aliran maksimum untuk melaksanakan algoritma Ford-Fulkerson. Kelas ini menyimpan maklumat graf dan mengandungi kaedah untuk mengira aliran maksimum. Berikut ialah definisi kelas algoritma aliran maksimum yang mudah:

class FordFulkerson {
  private $graph;
  private $visited;
  private $source;
  private $sink;

  public function __construct(Graph $graph, $source, $sink) {
    $this->graph = $graph;
    $this->visited = array();
    $this->source = $source;
    $this->sink = $sink;
  }

  public function getMaxFlow() {
    $maxFlow = 0;

    while ($path = $this->findPath()) {
      $minCapacity = PHP_INT_MAX;

      for ($i = 1; $i < count($path); $i++) {
        $u = $path[$i - 1];
        $v = $path[$i];

        $capacity = $this->graph->getAdjacencyList($u)[$v];
        $minCapacity = min($minCapacity, $capacity);
      }

      for ($i = 1; $i < count($path); $i++) {
        $u = $path[$i - 1];
        $v = $path[$i];

        $this->graph->getAdjacencyList($u)[$v] -= $minCapacity;
        $this->graph->getAdjacencyList($v)[$u] += $minCapacity;
      }

      $maxFlow += $minCapacity;
    }

    return $maxFlow;
  }

  private function findPath($u = null) {
    if ($u === null) {
      $u = $this->source;
    }

    if ($u == $this->sink) {
      return [$this->sink];
    }

    $this->visited[$u] = true;

    foreach ($this->graph->getAdjacencyList($u) as $v => $capacity) {
      if (!$this->visited[$v] && $capacity > 0) {
        $path = $this->findPath($v);

        if ($path) {
          array_unshift($path, $u);
          return $path;
        }
      }
    }

    return null;
  }
}

Akhirnya, kita boleh menggunakan kelas graf dan kelas algoritma aliran maksimum yang ditakrifkan di atas untuk menyelesaikan masalah aliran rangkaian. Berikut ialah contoh penggunaan:

$graph = new Graph();

$graph->addEdge("s", "A", 10);
$graph->addEdge("s", "B", 5);
$graph->addEdge("A", "C", 15);
$graph->addEdge("B", "C", 10);
$graph->addEdge("B", "D", 20);
$graph->addEdge("C", "D", 5);
$graph->addEdge("C", "t", 20);
$graph->addEdge("D", "t", 10);

$fordFulkerson = new FordFulkerson($graph, "s", "t");
$maxFlow = $fordFulkerson->getMaxFlow();

echo "The maximum flow in the network is: " . $maxFlow;

Dalam contoh di atas, kami mentakrifkan graf terarah, dengan "s" mewakili nod sumber, "t" mewakili nod sink, dan nod lain diwakili oleh huruf, dan masing-masing. tepi adalah nilai kapasiti yang ditanda. Kadar aliran maksimum yang dikira menggunakan algoritma Ford-Fulkerson akan dicetak.

Melalui contoh dan kod di atas, kami boleh melaksanakan algoritma aliran maksimum dalam PHP dan menyelesaikan masalah aliran rangkaian. Algoritma ini mempunyai aplikasi yang luas dalam senario seperti pengoptimuman rangkaian dan peruntukan sumber, dan sangat membantu dalam memahami dan menyelesaikan masalah yang berkaitan.

Atas ialah kandungan terperinci Kaedah pelaksanaan algoritma aliran maksimum dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!