图

表示多对多关系,包含顶点集合V和边集合E,不考虑重边和自回路

网络

有向图或无向图+边的权重

表示

邻接矩阵

  • 方便直观,方便检查2个顶点是否存在边,检查所有邻接点,方便计算出度入度(边数)
  • 稀疏图浪费空间,稀疏图统计总边数浪费时间
  • 无向图,只需要一半空间存储即可

邻接表

  • 用链表存储
  • 每条链表就是邻接矩阵的一行,每个节点是邻接矩阵中

深度优先搜索

  • 用邻接表存储,复杂度O(N+E)
  • 用邻接矩阵存储,复杂度O(N^2)

广度优先搜索(借助队列)

  • 用邻接表存储,复杂度O(N+E)
  • 用邻接矩阵存储,复杂度O(N^2)

连通问题

  • 连通: 如果V到W有一条路径.则称v和w连通
  • 连通图: 图中任意两天均连通

最小路径问题(递增,非递减)

  • 无权图:BFS
  • 有权图的单源最短路算法:Dijkstra算法(最短路径算法)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// $dist被初始化为正无穷 
// 有权图的单源最短路算法
function dijkstra($s)
{
    while (1) {
        $v = '未收录顶点中dist最小者';
        if (empty($v)) {
            break;
        }
        $collect[$v] = true;
        foreach ($v的邻接点集合 as $w) {
            if ($collect[$w] != true) {
                if ($dist[$v] + $v到w权重 < $dist[$w]) {
                    $dist[$w] = $dist[$v] + $v到w权重;
                    $path[$w] = $v;
                }
            }
        }
    }
}

最小生成树

  1. 是一颗树,无回路,v个顶点有v-1边
  2. 是生成树,v-1条边都在图里
  3. 边的权重和最小
  • Prim算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function prim(){
	$mst = [$s];
	while (1) {
        $v = '未收录顶点中dist最小者';
            if (empty($v)) {
            break;
        }

        // 将v收进$mst: $dist[$v] = 0
        foreach ($v的邻接点集合 as $w) {
        	if($dist[$w]!=0){
        		if($E($v到$w) < $dist[$w]){
        			$dist[$w] = $E($v到$w);
        			$parent[$w] = $v;
        		}
        	}
        }
	}
	if($mst收的点不到v个){
		echo '不存在生成树';
	}
}