Cấu trúc dữ liệu đồ thị PHP

Biểu đồ là cấu trúc dữ liệu phi tuyến tính bao gồm các đỉnh và cạnh, trong đó các đỉnh chứa thông tin hoặc dữ liệu và các cạnh hoạt động như một liên kết giữa các cặp đỉnh

Nó được sử dụng để giải các bài toán đố thực tế như tìm đường tốt nhất đến vị trí đích và đường cho mạng viễn thông và mạng xã hội. Người dùng được coi là một nút trong Biểu đồ và các dây là các cạnh kết nối người dùng

Nếu các cạnh được biểu diễn dưới dạng E và các đỉnh được biểu diễn dưới dạng V, thì đồ thị G có thể được viết dưới dạng tập hợp các đỉnh và cạnh, chẳng hạn như G (V, E)

Ví dụ

Đây là một ví dụ đơn giản về cấu trúc dữ liệu đồ thị

Đó là một đồ thị vô hướng đơn giản (một loại Đồ thị). Ở đây tập hợp các đỉnh là. {A, B, C, D, E, F}. Hai đỉnh tạo ra một cạnh. Ví dụ, A và B được liên kết với một cạnh. Tuy nhiên, A và F không được liên kết với bất kỳ cạnh nào

Thuật ngữ đồ thị trong cấu trúc dữ liệu

Sau đây là một số thuật ngữ quan trọng được sử dụng trong cấu trúc dữ liệu đồ thị

Ứng dụng cấu trúc dữ liệu đồ thị

Một biểu đồ có nhiều trường hợp sử dụng. Có rất nhiều thuật toán sử dụng Đồ thị rất nhiều. Sau đây là một số ứng dụng của Graph

Structures Graph là một gói để tạo và thao tác cấu trúc dữ liệu đồ thị. Nó cho phép xây dựng đồ thị có hướng và vô hướng, với dữ liệu và siêu dữ liệu được lưu trữ trong các nút. Thư viện cung cấp các hàm để duyệt đồ thị cũng như trích xuất đặc trưng từ cấu trúc liên kết đồ thị

Tài liệu trực tuyến đầy đủ có sẵn tại đây

SPL cung cấp một bộ cơ sở hạ tầng tiêu chuẩn. Chúng được nhóm ở đây theo cách triển khai cơ bản của chúng, thường xác định lĩnh vực ứng dụng chung của chúng

Danh sách liên kết đôi

Danh sách liên kết đôi (DLL) là danh sách các nút được liên kết theo cả hai hướng với nhau. Các hoạt động của iterator, truy cập vào cả hai đầu, thêm hoặc xóa các nút có chi phí là O(1) khi cấu trúc cơ bản là một DLL. Do đó, nó cung cấp một triển khai phù hợp cho ngăn xếp và hàng đợi

đống

Heaps là các cấu trúc dạng cây đi theo thuộc tính heap. mỗi nút lớn hơn hoặc bằng các nút con của nó, khi được so sánh bằng cách sử dụng phương thức so sánh đã triển khai là toàn cục cho heap

Mảng

Mảng là cấu trúc lưu trữ dữ liệu theo cách liên tục, có thể truy cập thông qua chỉ mục. Đừng nhầm lẫn chúng với mảng PHP. Các mảng PHP trên thực tế được triển khai dưới dạng các bảng băm có thứ tự

Bản đồ

Bản đồ là một cơ sở hạ tầng chứa các cặp khóa-giá trị. Mảng PHP có thể được xem như bản đồ từ số nguyên/chuỗi đến giá trị. SPL cung cấp bản đồ từ đối tượng đến dữ liệu. Bản đồ này cũng có thể được sử dụng như một bộ đối tượng

<?php

class Graph {

   private $adj;
   private $V;

   public function __construct($vertices) {
       $this->V = $vertices;
       $this->adj = array();
       for($i = 0; $i < $vertices; $i++) {
           array_push($this->adj, array());
       }
   }

   public function addEdge($from, $to) {
       array_push($this->adj[$from], $to);
       // If using an undirected Graph, uncomment this line:
       //array_push($this->adj[$to], $from);
   }

   public function size() {
       return $this->V;
   }

   public function getEdges($vertex) {
       if($vertex > $this->V) return null;
       return $this->adj[$vertex];
   }
}

Tìm thấy bất kỳ lỗi trong mã?

Cấu trúc dữ liệu đồ thị là một loại cấu trúc dữ liệu phi tuyến tính đặc biệt bao gồm một số đỉnh hoặc nút hữu hạn và các cạnh hoặc cung. Đồ thị có thể có hướng và vô hướng. Đồ thị có hướng chỉ rõ hướng của các cạnh, trong khi đồ thị vô hướng đề cập đến các cạnh chứ không phải hướng. Do đó, trong đồ thị vô hướng, cả hai hướng của cạnh đều được coi là một cạnh. Nói cách khác, chúng ta có thể nói một đồ thị là một cặp tập hợp (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh

V = {A, B, C, D, E, F}

E = {AB, BC, CE, ED, EF, DB}

Trong đồ thị có hướng, cạnh AB khác với cạnh BA trong khi ở đồ thị vô hướng, cả AB và BA đều giống nhau. Đồ thị rất tiện dụng để giải quyết nhiều vấn đề phức tạp

PHP có tốt cho cấu trúc dữ liệu không?

Cấu trúc dữ liệu nào là tốt nhất cho biểu đồ?

Cấu trúc dữ liệu trong PHP là gì?

Biểu đồ trong cấu trúc dữ liệu là gì?