PHPデータ構造 - グラフ格納構造

グラフの格納構造

グラフの概念はほぼ紹介されましたので、それを理解し、次の内容を学習し続けることができます。問題がなければ次の内容の検討を進めていきます。もちろん、これは最も厄介な部分ではありません。なぜなら、今日はグラフの記憶構造を紹介するだけだからです。

グラフの逐次記憶構造: 隣接行列

隣接行列とは

まず見てみましょう順序構造を使用してグラフを保存する方法を参照してください。スタック、キュー、ツリーのいずれであっても、単純な配列を使用して、これらのデータ構造の順次ストレージ機能を実現できます。しかし、グラフは異なります。前の記事から、ノードの表現は の形式であることを学びました。このノードを座標軸上の点と考えると、2 次元配列を使用して表すことができるでしょうか。そうです、2 次元配列の最初の次元を x 軸として表し、2 番目の次元を y 軸として表すと、グラフを構築できます。そうです、2 次元配列の形式には行列という別名もあります。

[推奨: PHP ビデオ チュートリアル ]

グラフ用語では、2 次元配列で表されるグラフの順次記憶構造を隣接行列と呼びます。ちょうど下のフォームのような感じです。

このテーブルには、水平方向と垂直方向の 2 つの座標があります。X1 ～ 4 と Y1 ～ 4 は、このグラフの合計 4 つのノードを表します。それらの対応関係を通じて、次のことが可能です。あるノードと別のノードの間にエッジがあるかどうかとして認識されます。たとえば、座標 X1 と Y2 のペアの値は 1 であり、ノード 1 とノード 2 の間にエッジがあることを意味します。ここでは、重み付けされていないグラフを使用しています。つまり、0 はエッジがないことを表し、1 は 2 つのノード間のエッジを表します。同時に、これはまだ無向グラフであるため、 の値も 1 であり、その意図はノード 2 からノード 1 へのエッジも存在することです。有向グラフの場合は、有向矢印の方向に基づいて、このエッジが 1 に設定されているかどうかを判断する必要があります。

上記の隣接行列に対応するグラフはどのようなものになるでしょうか?自分で描いてみることもできます。まだ学び始めたばかりなので、描けなくても大丈夫です。実際、これは最初に示したグラフの隣接行列です。

#左側の図は、上の表の隣接行列に対応します。それでは、右側の有向グラフの隣接行列はどのようなものになるでしょうか?あなたも書いてみましょう。

#興味深いですね?では、それが強力な陰謀だった場合はどうなるでしょうか?実際、これは非常に簡単です。グラフ内の 1 を、対応するエッジの重みに直接置き換えることができます。ただし、一部のエッジの重みが 0 である可能性もあるため、重み付きグラフでは、非常に単純な値を定義できます。または、非常に小さな負の数を無限数として定義して、これら 2 つのノードにエッジがないことを示します。

隣接行列の構築

次に、コードを通じてこのような隣接行列の記憶構造を構築します。実装には引き続き無向グラフの例を使用します。無向グラフでは逆ノードに値を割り当てる必要があるため、有向グラフよりも 1 つ多くのステップがあり、残りは基本的に同様です。

// 邻接矩阵
$graphArr = [];
function CreateGraph($Nv, &$graphArr)
{
    $graphArr = [];
    for ($i = 1; $i <= $Nv; $i++) {
        for ($j = 1; $j <= $Nv; $j++) {
            $graphArr[$i][$j] = 0;
        }
    }
}
// 邻接矩阵
function BuildGraph(&$graphArr)
{
    echo &#39;请输入结点数：&#39;;
    fscanf(STDIN, "%d", $Nv);
    CreateGraph($Nv, $graphArr);
    if ($graphArr) {
        echo &#39;请输入边数：&#39;;
        fscanf(STDIN, "%d", $Ne);
        if ($Ne > 0) {
            for ($i = 1; $i <= $Ne; $i++) {
                echo &#39;请输入边，格式为 出 入 权：&#39;;
                fscanf(STDIN, "%d %d %d", $v1, $v2, $weight);
                $graphArr[$v1][$v2] = $weight;
                // 如果是无向图，还需要插入逆向的边
                $graphArr[$v2][$v1] = $weight;
            }
        }
    }
}

このコードでは、まず CreateGraph() メソッドを通じて 2 次元行列を初期化します。つまり、入力したノードの数に基づいて、X * Y の 2 次元配列構造が実装され、そのすべての値が 0 になるように定義されます。つまり、このグラフには現時点ではエッジがありません。

次に、BuildGraph() メソッドが CreateGraph() を呼び出した後、エッジ情報の入力を続けます。まずエッジの数を入力します。エッジがいくつかあります。エッジの数が 0 以下の場合は、エッジの作成を続行しないでください。実際には、より厳密にして、無向完全グラフと有向完全グラフの定義に基づいて、エッジが最大制限を超えないようにすることができます。

次に、エッジ情報をループで入力していきますが、ここで必要な入力形式はエッジの出力ノード、入力ノード、重みです。この例は無向グラフであるため、 のエッジを作成することに加えて、 のエッジも作成する必要があります。これについてはコードのコメントで説明されています。

コードの説明はまだ比較的抽象的かもしれません。実行して試してみてください。

BuildGraph($graphArr);
// 请输入结点数：4
// 请输入边数：4
// 请输入边，格式为 出 入 权：1 2 1
// 请输入边，格式为 出 入 权：1 3 1
// 请输入边，格式为 出 入 权：1 4 1
// 请输入边，格式为 出 入 权：3 4 1
print_r($graphArr);
// Array
// (
//     [1] => Array
//         (
//             [1] => 0
//             [2] => 1
//             [3] => 1
//             [4] => 1
//         )
//     [2] => Array
//         (
//             [1] => 1
//             [2] => 0
//             [3] => 0
//             [4] => 0
//         )
//     [3] => Array
//         (
//             [1] => 1
//             [2] => 0
//             [3] => 0
//             [4] => 1
//         )
//     [4] => Array
//         (
//             [1] => 1
//             [2] => 0
//             [3] => 1
//             [4] => 0
//         )
// )
//  x
//y 0 1 1 1
//  1 0 0 0
//  1 0 0 1
//  1 0 1 0

コマンド ライン環境で PHP ファイルを呼び出し、プロンプトに従って関連情報を順番に入力します。最終的に出力される配列の内容は上記の表とまったく同じですか?簡単なコードでグラフの逐次保存を実現します。

可能有的同学会一时懵圈。因为我第一眼看到的时候也是完全懵了，不过仔细的对比画出来的图和上面的表格其实马上就能想明白了。这次我们真的是进入二维的世界了。是不是感觉图瞬间就把树甩到十万八千里之外了。完全二叉树的时候，我们的思想是二维的，但结构还是一维的，而到邻接矩阵的时候，不管是思想还是代码结构，全部都进化到了二维空间，高大上真不是吹的。

图的链式存储结构：邻接表

说完顺序存储结构，自然不能忽视另一种形式的存储结构，那就是图的链式存储结构。其实对于图来说，链式结构非常简单和清晰，因为我们只需要知道一个结点和那些结点有边就行了。那么我们就让这个结点形成一个单链表，一路往后链接就好了，就像下图这样。（同样以上图无向图为例）

从 结点1 开始，它指向一个后继是 结点2 ，然后继续向后链接 结点3 和 结点4 。这样，与 结点1 相关的边就都描述完成了。由于我们展示的依然是无向图的邻接表表示，所以 结点2 的链表结点指向了 结点 1 。也就是完成了 的反向指向。

对于代码实现来说，我们可以将头结点，也就是正式的 1-4 结点保存在一个顺序表中。然后让每个数组元素的值为第一个结点的内容。这样，我们就可以让链表结点只保存结点名称、权重和下一个结点对象的指向信息就可以了。

// 头结点
class AdjList
{
    public $adjList = []; // 顶点列表
    public $Nv = 0; // 结点数
    public $Ne = 0; // 边数
}
// 边结点
class ArcNode
{
    public $adjVex = 0; // 结点
    public $nextArc = null; // 链接指向
    public $weight = 0; // 权重
}

接下来，我们来看看如何使用邻接表这种结构来建立图。

function BuildLinkGraph()
{
    fscanf(STDIN, "请输入 结点数 边数：%d %d", $Nv, $Ne);
    if ($Nv > 1) {
        // 初始化头结点
        $adj = new AdjList();
        $adj->Nv = $Nv; // 保存下来方便使用
        $adj->Ne = $Ne; // 保存下来方便使用
        // 头结点列表
        for ($i = 1; $i <= $Nv; $i++) {
            $adj->adjList[$i] = null; // 全部置为 NULL ，一个无边空图
        }
        
        if ($Ne > 0) {
//
            for ($i = 1; $i <= $Ne; $i++) {
                echo &#39;请输入边，格式为 出 入 权：&#39;;
                fscanf(STDIN, "%d %d %d", $v1, $v2, $weight);
                // 建立一个结点
                $p1 = new ArcNode;
                $p1->adjVex = $v2; // 结点名称为 入结点
                $p1->nextArc = $adj->adjList[$v1]; // 下一跳指向 出结点 的头结点
                $p1->weight = $weight; // 设置权重
                $adj->adjList[$v1] = $p1; // 让头结点的值等于当前新创建的这个结点
                // 无向图需要下面的操作，也就是反向的链表也要建立
                $p2 = new ArcNode;
                // 注意下面两行与上面代码的区别
                $p2->adjVex = $v1; // 这里是入结点
                $p2->nextArc = $adj->adjList[$v2]; // 这里是出结点
                
                $p2->weight = $weight;
                $adj->adjList[$v2] = $p2;
            }
            return $adj;
        }
    }
    return null;
}

代码中的注释已经写得很清楚了。可以看出，在邻接表的操作中，无向图也是一样的比有向图多一步操作的，如果只是建立有向图的话，可以不需要 p2 结点的操作。特别需要注意的就是，在这段代码中，我们使用的是链表操作中的 头插法 。也就是最后一条数据会插入到 头结点 上，而最早的那个边会在链表的最后。大家看一下最后建立完成的数据结构的输出就明白了。

print_r(BuildLinkGraph());
// AdjList Object
// (
//     [adjList] => Array
//         (
//             [1] => ArcNode Object
//                 (
//                     [adjVex] => 4
//                     [nextArc] => ArcNode Object
//                         (
//                             [adjVex] => 3
//                             [nextArc] => ArcNode Object
//                                 (
//                                     [adjVex] => 2
//                                     [nextArc] => 
//                                     [weight] => 1
//                                 )
//                             [weight] => 1
//                         )
//                     [weight] => 1
//                 )
//             [2] => ArcNode Object
//                 (
//                     [adjVex] => 1
//                     [nextArc] => 
//                     [weight] => 1
//                 )
//             [3] => ArcNode Object
//                 (
//                     [adjVex] => 4
//                     [nextArc] => ArcNode Object
//                         (
//                             [adjVex] => 1
//                             [nextArc] => 
//                             [weight] => 1
//                         )
//                     [weight] => 1
//                 )
//             [4] => ArcNode Object
//                 (
//                     [adjVex] => 3
//                     [nextArc] => ArcNode Object
//                         (
//                             [adjVex] => 1
//                             [nextArc] => 
//                             [weight] => 1
//                         )
//                     [weight] => 1
//                 )
//         )
//     [Nv] => 4
//     [Ne] => 4
// )

使用邻接表来建立的图的链式存储结构是不是反而比邻接矩阵更加的清晰明了一些。就像树的链式和顺序结构一样，在图中它们的优缺点也是类似的。邻接矩阵占用的物理空间更多，因为它需要两层一样多元素的数组，就像上面的表格一样，需要占据 4 * 4 的物理格子。而邻接表我们可以直接数它的结点数，只需要 12 个格子就完成了。而且，更主要的是，链式的邻接表可以随时扩展边结点和边数，不需要重新地初始化，我们只需要简单地修改上面的测试代码就能够实现，而邻接矩阵如果要修改结点数的话，就得要重新初始化整个二维数组了。

总结

对于图来说，除了邻接矩阵和邻接表之外，还有其它的一些存储形式，不过都是链式的邻接表的一些优化和变形而已。大家有兴趣的可以自己去了解一下 十字链表 、邻接多重表 这两种存储结构。

好了，基础的存储结构已经铺垫完了，关于图的概念也都熟悉掌握了，接下来，我们就要准备去做最重要的操作了，那就是如何来对图进行遍历。

测试代码：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.图/source/5.2图的存储结构.php

以上がPHPデータ構造 - グラフ格納構造の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。