图

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

网络

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

表示

邻接矩阵

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

邻接表

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

深度优先搜索

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

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

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

连通问题

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

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

• 无权图:BFS

• 有权图的单源最短路算法:Dijkstra算法(最短路径算法)

  // $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;
                }
            }
        }
    }
  }

  最小生成树

• 是一颗树,无回路,v个顶点有v-1边
• 是生成树,v-1条边都在图里
• 边的权重和最小

• Prim算法

  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 '不存在生成树';
    }
  }

最后更新于 2021-09-14 14:15:01 并被添加「」标签，已有 566 位童鞋阅读过。