图

广度优先搜索 & 深度优先搜索

<?php

class Node
{
    public $linkNodes;
    public $value;

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

class Graph
{
    public function build(array $array)
    {
        $result = [];

        $nodes = array_keys($array);
        foreach ($nodes as $node) {
            $result[$node] = new Node($node);
        }

        foreach ($array as $node => $arr) {
            foreach ($arr as $linkNode) {
                $result[$node]->linkNodes [] = new Node($linkNode);
            }
        }

        return $result;
    }

    public function BFS($graph, $begin, $end)
    {
        $this->check($graph, $begin, $end);

        $queue = [];
        array_push($queue, $graph[$begin]);

        $isFind = [
            $begin => true
        ];

        while (!empty($queue)) {
            // 先入先出，横向搜索
            $node = array_shift($queue);

            l($node->value);

            if ($node->value == $end) {
                return true;
            }

            if (empty($node->linkNodes)) {
                continue;
            }

            // 压入候补节点
            foreach ($node->linkNodes as $linkNode) {
                if (!empty($isFind[$linkNode->value])) {
                    continue;
                }
                $isFind[$linkNode->value] = true;

                $linkNode->linkNodes = $graph[$linkNode->value]->linkNodes;

                array_push($queue, $linkNode);
            }

        }

        return true;
    }

    public function DFS($graph, $begin, $end)
    {
        $this->check($graph, $begin, $end);

        $stack = [];

        array_push($stack, $graph[$begin]);

        $isFind = [
            $begin => true
        ];

        while (!empty($stack)) {
            // 先入后出，纵向搜索
            $node = array_pop($stack);

            l($node->value);

            if ($node->value == $end) {
                return true;
            }

            if (empty($node->linkNodes)) {
                continue;
            }

            // 压入候补节点
            foreach ($node->linkNodes as $linkNode) {
                if (!empty($isFind[$linkNode->value])) {
                    continue;
                }
                $isFind[$linkNode->value] = true;

                $linkNode->linkNodes = $graph[$linkNode->value]->linkNodes;

                array_push($stack, $linkNode);

            }
        }

        return true;

    }

    protected function check($graph, $begin, $end)
    {
        if (empty($graph[$begin]) || empty($graph[$end])) {
            echo "node not exists";
            exit;
        }
    }
}

// 有向图
$array = [
    'A' => ['B', 'C', 'D'],
    'B' => ['E', 'F'],
    'C' => ['G', 'H'],
    'D' => ['I', 'J'],
    'E' => [],
    'F' => [],
    'G' => [],
    'H' => [],
    'I' => [],
    'J' => [],
];
// 广度优先搜索
$graph = new Graph();
$result = $graph->build($array);
$graph->BFS($result, 'A', 'H');
line();
// 深度优先搜索
$graph = new Graph();
$result = $graph->build($array);
$graph->DFS($result, 'A', 'H');
line();
line();

// 普通图
$array = [
    'A' => ['B', 'F'],
    'B' => ['A', 'C', 'D'],
    'C' => ['B', 'D', 'E'],
    'D' => ['B', 'C'],
    'E' => ['C'],
    'F' => ['A', 'G', 'H'],
    'G' => ['F', 'H'],
    'H' => ['F', 'G']
];
// 广度优先搜索
$graph = new Graph();
$result = $graph->build($array);
$graph->BFS($result, 'A', 'E');
line();
// 深度优先搜索
$graph = new Graph();
$result = $graph->build($array);
$graph->DFS($result, 'A', 'E');
line();
line();

// 闭环图
$array = [
    'A' => ['B', 'F'],
    'B' => ['A', 'C'],
    'C' => ['B', 'D'],
    'D' => ['C', 'E'],
    'E' => ['D', 'F'],
    'F' => ['A', 'E'],
];
// 广度优先搜索
$graph = new Graph();
$result = $graph->build($array);
$graph->BFS($result, 'A', 'D');
line();
// 深度优先搜索
$graph = new Graph();
$result = $graph->build($array);
$graph->DFS($result, 'A', 'D');

function l($string)
{
    echo $string . ' -> ';
}

function line()
{
    echo '<br>';
}

function p($data)
{
    echo '<pre>';
    print_r($data);
}

贝尔曼福特算法

# 给所有节点编号
nodes = {
    'A': 0,
    'B': 1,
    'C': 2,
    'D': 3,
    'E': 4,
    'F': 5,
    'G': 6
}

# 节点编号映射节点
nodes_flip = dict((i, v) for i, v in enumerate(nodes))

# 把图从左到右列出，如A节点到B节点权重为9，表示为：[0,1,9]
graph = [
    [0, 1, 9],
    [0, 2, 2],
    [1, 2, 6],
    [1, 3, 3],
    [1, 4, 1],
    [2, 3, 2],
    [2, 5, 9],
    [3, 4, 5],
    [3, 5, 6],
    [4, 5, 3],
    [4, 6, 7],
    [5, 6, 4],
]

INF = float('inf')

N = len(nodes)


# 初始化各点到其他点的权重，不直达用inf表示（行、列索引都表示当前节点的编号）
def init():
    w = [[INF if j != i else 0 for j in range(N)] for i in range(N)]

    for i in graph:
        w[i[0]][i[1]] = i[2]
        w[i[1]][i[0]] = i[2]
    return w


weight = init()

'''
设置起始点为0，其他点为∞
遍历所有边，边的权重+出发点的权重<到达点的权重，更新到达点（出发点和到达点是指边的两个顶点）
重复N-1轮，N为节点数量（如果中间没有更新可提前退出）
如果重复N-1轮后还能更新，说明是一个存在负权重的闭环，无最短路径
'''
def bellman_ford(src, target):
    src_index = nodes[src]
    target_index = nodes[target]

    # 距离列表（用于记录起始点到各点的距离）
    # 初始节点为0，其他为INF
    dist = [0 if i == src_index else INF for i in range(N)]

    # 更新列表（用于记录每个节点最后被哪个节点更新，用于追踪轨迹）
    last_update = [src_index if i != INF else -1 for i in dist]

    # 松弛n-1次，因为最短路径的深度最多是n-1，n为结点数目
    for i in range(N - 1):
        change = False
        # 分别遍历边的两个顶点，从而实现遍历所有边
        for j in range(N):
            for k in range(N):
                if dist[j] > dist[k] + weight[j][k]:
                    dist[j] = dist[k] + weight[j][k]
                    # 记录更新该结点的结点编号
                    last_update[j] = k
                    # 标记更改状态
                    change = True

        # 如果本轮未作出更改，说明已完成
        if not change:
            break

    # 判断负权回路
    for i in range(N):
        for j in range(N):
            if dist[j] > dist[i] + weight[j][i]:
                raise BaseException("存在负权回路")

    # 输出从起点到终点的路径结点
    tmp = target_index
    path = []
    while tmp != src_index:
        path.append(nodes_flip[tmp])
        tmp = last_update[tmp]
    path.append(src)
    print("->".join([node for node in reversed(path)]))

    return dist[target_index]


res = bellman_ford('A', 'G')
print(res)

迪杰斯特拉算法

# 给所有节点编号
nodes = {
    'A': 0,
    'B': 1,
    'C': 2,
    'D': 3,
    'E': 4,
    'F': 5,
    'G': 6
}

# 节点编号映射节点
nodes_flip = dict((i, v) for i, v in enumerate(nodes))

# 把图从左到右列出，如A节点到B节点权重为9，表示为：[0,1,9]
graph = [
    [0, 1, 9],
    [0, 2, 2],
    [1, 2, 6],
    [1, 3, 3],
    [1, 4, 1],
    [2, 3, 2],
    [2, 5, 9],
    [3, 4, 5],
    [3, 5, 6],
    [4, 5, 3],
    [4, 6, 7],
    [5, 6, 4],
]

INF = float('inf')
N = len(nodes)


# 初始化各点到其他点的权重，不直达用inf表示（行、列索引都表示当前节点的编号）
def init():
    w = [[INF if j != i else 0 for j in range(N)] for i in range(N)]

    for i in graph:
        w[i[0]][i[1]] = i[2]
        w[i[1]][i[0]] = i[2]
    return w


weight = init()

'''
设置起始点为0，其他点为∞
创建未达列表（除起点外的所有点）
从起点出发，找到能够直达且权重最小的点，更新相关距离列表
再根据被找到的点，去找它的能够直达的点，只要权重小于起点的距离列表，更新距离列表
然后记录被更新节点是被哪个节点更新的
并把当前找到的节点从未达列表中剔除
循环处理，直到未达列表被清空
'''
def dijkstra(src, target):
    src_index = nodes[src]
    target_index = nodes[target]

    # 未到的点的索引（剔除掉起始点）
    u = [i for i in range(N)]
    u.remove(src_index)

    # 距离列表（用于记录起始点到各点的距离）
    dist = weight[src_index]

    # 更新列表（用于记录每个节点最后被哪个节点更新，用于追踪轨迹）
    last_update = [src_index if i != INF else -1 for i in dist]

    # 所有点都到过后，退出循环
    while u:

        idx = 0
        min_dist = INF

        # 找距离最近的点并标记该点的索引和最近距离
        # 每次距离列表会被当次找到的点的相邻点更新（满足条件）
        # 而每次min_dist都会被重置为INF，所以每次都能找到idx
        for i in range(N):
            if i in u and dist[i] < min_dist:
                min_dist = dist[i]
                idx = i

        # 找到的点从未达列表中移除
        u.remove(idx)

        # 更新距离列表（用当次找到的点）
        for j in range(N):
            if j in u and weight[idx][j] + min_dist < dist[j]:
                dist[j] = weight[idx][j] + min_dist

                # 记录更新该结点的结点编号
                last_update[j] = idx

    # 输出从起点到终点的路径结点
    tmp = target_index
    path = []
    while tmp != src_index:
        path.append(nodes_flip[tmp])
        tmp = last_update[tmp]
    path.append(src)
    print("->".join([str(i) for i in reversed(path)]))

    return dist[target_index]


res = dijkstra('A', 'G')
print(res)