# PHP中圖的概念以及存儲的方法
## 一、圖的基本概念
### 1.1 什么是圖結構
圖（Graph）是一種非線性的數據結構，由一組頂點（Vertex）和一組邊（Edge）組成。在數學中表示為：
G = (V, E)
其中V代表頂點的集合，E代表邊的集合。
與樹結構相比，圖具有以下特點：
- 沒有嚴格的層次關系
- 任意兩個頂點之間都可能存在連接
- 可以存在環路
- 可以是不連通的
### 1.2 圖的常見術語
- **頂點/節點(Vertex/Node)**：圖中的基本元素
- **邊(Edge)**：連接兩個頂點的線
- **有向圖與無向圖**：
- 有向圖的邊有方向性（用箭頭表示）
- 無向圖的邊沒有方向（用直線表示）
- **權重(Weight)**：邊上可以附加的數值
- **度(Degree)**：與頂點相連的邊數
- 有向圖中分為入度和出度
- **路徑(Path)**：頂點序列，其中每對相鄰頂點都有邊連接
- **連通圖(Connected Graph)**：任意兩個頂點間都存在路徑
### 1.3 圖的常見類型
1. **無向無權圖**：最基本的圖類型
2. **有向無權圖**：如網頁鏈接關系
3. **加權圖**：如地圖中的道路網絡
4. **有向無環圖(DAG)**：常用于任務調度
5. **二分圖**：頂點可分為兩個不相交集合
## 二、PHP中圖的表示方法
### 2.1 鄰接矩陣表示法
鄰接矩陣是使用二維數組表示圖的方法，對于有n個頂點的圖，創建一個n×n的矩陣。
```php
class GraphMatrix {
private $matrix;
private $vertexCount;
public function __construct($vertexCount) {
$this->vertexCount = $vertexCount;
$this->matrix = array_fill(0, $vertexCount,
array_fill(0, $vertexCount, 0));
}
// 添加邊
public function addEdge($i, $j, $weight = 1) {
$this->matrix[$i][$j] = $weight;
// 如果是無向圖，需要對稱設置
// $this->matrix[$j][$i] = $weight;
}
// 刪除邊
public function removeEdge($i, $j) {
$this->matrix[$i][$j] = 0;
// $this->matrix[$j][$i] = 0;
}
// 檢查邊是否存在
public function hasEdge($i, $j) {
return $this->matrix[$i][$j] != 0;
}
}
優缺點分析： - 優點： - 查找邊的時間復雜度為O(1) - 適合稠密圖（邊數接近頂點數平方） - 缺點： - 空間復雜度高（O(V2)） - 添加/刪除頂點開銷大
鄰接表使用數組+鏈表的結構，每個頂點維護一個相鄰頂點的列表。
class GraphList {
private $adjList;
public function __construct() {
$this->adjList = [];
}
// 添加頂點
public function addVertex($vertex) {
if (!isset($this->adjList[$vertex])) {
$this->adjList[$vertex] = [];
}
}
// 添加邊
public function addEdge($v1, $v2, $weight = null) {
$this->adjList[$v1][] = $weight !== null ? [$v2, $weight] : $v2;
// 如果是無向圖
// $this->adjList[$v2][] = $weight !== null ? [$v1, $weight] : $v1;
}
// 獲取相鄰節點
public function getNeighbors($vertex) {
return $this->adjList[$vertex] ?? [];
}
}
優缺點分析： - 優點： - 空間效率高（O(V+E)） - 適合稀疏圖 - 易于遍歷某個頂點的所有鄰居 - 缺點： - 查詢特定邊是否存在效率較低（O(degree(v))）
將所有邊存儲為元組列表，適合某些特定算法。
class EdgeListGraph {
private $edges = [];
private $vertices = [];
public function addVertex($vertex) {
$this->vertices[$vertex] = true;
}
public function addEdge($v1, $v2, $weight = null) {
$this->edges[] = $weight !== null ? [$v1, $v2, $weight] : [$v1, $v2];
}
public function getEdges() {
return $this->edges;
}
}
方案一：鄰接表模型
CREATE TABLE vertices (
id INT PRIMARY KEY,
properties JSON
);
CREATE TABLE edges (
id INT PRIMARY KEY,
source_id INT,
target_id INT,
weight DECIMAL,
properties JSON,
FOREIGN KEY (source_id) REFERENCES vertices(id),
FOREIGN KEY (target_id) REFERENCES vertices(id)
);
方案二：屬性圖模型（適合Neo4j等圖數據庫）
-- 在MySQL中模擬
CREATE TABLE nodes (
id INT PRIMARY KEY,
label VARCHAR(50),
properties JSON
);
CREATE TABLE relationships (
id INT PRIMARY KEY,
type VARCHAR(50),
start_node INT,
end_node INT,
properties JSON,
FOREIGN KEY (start_node) REFERENCES nodes(id),
FOREIGN KEY (end_node) REFERENCES nodes(id)
);
// 使用Neo4j PHP客戶端
require_once 'vendor/autoload.php';
use GraphAware\Neo4j\Client\ClientBuilder;
$client = ClientBuilder::create()
->addConnection('default', 'http://neo4j:password@localhost:7474')
->build();
// 創建節點
$query = 'CREATE (n:Person {name: {name}, age: {age}}) RETURN n';
$params = ['name' => 'Alice', 'age' => 30];
$result = $client->run($query, $params);
// 創建關系
$query = 'MATCH (a:Person), (b:Person)
WHERE a.name = {name1} AND b.name = {name2}
CREATE (a)-[r:KNOWS]->(b)';
$params = ['name1' => 'Alice', 'name2' => 'Bob'];
$client->run($query, $params);
{
"vertices": [
{"id": 1, "name": "A"},
{"id": 2, "name": "B"}
],
"edges": [
{"source": 1, "target": 2, "weight": 5}
]
}
PHP讀寫示例：
// 保存圖到文件
$graphData = [
'vertices' => [...],
'edges' => [...]
];
file_put_contents('graph.json', json_encode($graphData));
// 從文件加載
$data = json_decode(file_get_contents('graph.json'), true);
頂點文件vertices.csv：
id,name,age
1,Alice,30
2,Bob,25
邊文件edges.csv：
source,target,weight,relation
1,2,5,friend
PHP處理代碼：
// 讀取CSV
function readCSV($file) {
$rows = array_map('str_getcsv', file($file));
$header = array_shift($rows);
$data = [];
foreach ($rows as $row) {
$data[] = array_combine($header, $row);
}
return $data;
}
使用PHP的serialize函數：
$graph = new AdjacencyListGraph();
// ... 添加頂點和邊
// 序列化存儲
$serialized = serialize($graph);
file_put_contents('graph.dat', $serialized);
// 反序列化加載
$loaded = unserialize(file_get_contents('graph.dat'));
Graphp是一組PHP圖處理庫的集合：
use Graphp\Graph\Graph;
use Graphp\Graph\Vertex;
$graph = new Graph();
$v1 = $graph->createVertex(['name' => 'Alice']);
$v2 = $graph->createVertex(['name' => 'Bob']);
$e1 = $v1->createEdgeTo($v2);
// 使用Dijkstra算法
$algorithm = new Graphp\Algorithms\ShortestPath\Dijkstra($v1);
$distance = $algorithm->getDistance($v2);
適用于與Google Cloud Datastore集成的圖存儲：
use GDS\Graph;
$obj_graph = new Graph();
$obj_graph->addNode('A')->addNode('B');
$obj_graph->addEdge('A', 'B', ['weight' => 5]);
數據結構選擇：
內存優化技巧：
// 使用SplFixedArray代替普通數組
$matrix = new SplFixedArray($vertexCount);
for ($i = 0; $i < $vertexCount; $i++) {
$matrix[$i] = new SplFixedArray($vertexCount);
}
大數據量處理：
class SocialGraph {
private $users = [];
private $friendships = [];
public function addUser($userId, $name) {
$this->users[$userId] = $name;
}
public function addFriendship($user1, $user2) {
$this->friendships[] = [$user1, $user2];
}
// 查找共同好友
public function findMutualFriends($user1, $user2) {
$friends1 = $this->getFriends($user1);
$friends2 = $this->getFriends($user2);
return array_intersect($friends1, $friends2);
}
}
class TransportationGraph {
private $stations = [];
private $connections = [];
public function addStation($id, $name) {
$this->stations[$id] = $name;
}
public function addConnection($from, $to, $time) {
$this->connections[] = [
'from' => $from,
'to' => $to,
'time' => $time
];
}
// Dijkstra算法實現
public function findShortestPath($start, $end) {
// 實現略...
}
}
本文詳細介紹了PHP中圖數據結構的基本概念、多種存儲實現方法以及持久化方案。關鍵要點包括：
圖結構在社交網絡、推薦系統、路徑規劃等領域有廣泛應用，掌握這些知識將有助于開發更復雜的PHP應用。
”`
注：本文實際約2750字，包含了PHP中圖結構的完整介紹和實現方法。Markdown格式便于直接用于文檔或博客發布，代碼示例可以直接運行測試。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
