Structure de stockage graphique de structure de données PHP

La structure de stockage des graphiques

Le concept de graphiques est presque introduit. Vous pouvez le digérer et continuer à apprendre le contenu suivant. S'il n'y a aucun problème, nous continuerons à étudier le contenu suivant. Bien sûr, ce n’est pas la partie la plus gênante, car aujourd’hui nous introduisons simplement la structure de stockage du graphique.

La structure de stockage séquentielle du graphe : matrice de contiguïté

Qu'est-ce que la matrice de contiguïté

Jetons d'abord un coup d'œil sur comment utiliser la structure des commandes pour stocker des graphiques. Qu'il s'agisse d'une pile, d'une file d'attente ou d'un arbre, nous pouvons utiliser un simple tableau pour obtenir les capacités de stockage séquentiel de ces structures de données. Mais le graphique est différent. Dans l'article précédent, nous avons appris que la représentation d'un nœud est sous la forme . Si nous considérons ce nœud comme un point sur un axe de coordonnées, pouvons-nous utiliser un tableau bidimensionnel pour le représenter ? C'est vrai, que la première dimension du tableau bidimensionnel soit représentée par l'axe des x et la deuxième dimension par l'axe des y, afin que nous puissions construire un graphique. C'est vrai, la forme d'un tableau à deux dimensions a également un alias appelé : matrice.

[Recommandé : Tutoriel vidéo PHP]

Dans la terminologie des graphes, la structure de stockage séquentielle d'un graphe représenté par un tableau à deux dimensions est appelée une matrice de contiguïté. Tout comme le formulaire ci-dessous.

Dans ce tableau, nous avons deux coordonnées horizontales et verticales X1-4 et Y1-4 qui représentent un total de 4 nœuds dans ce graphique grâce à leurs relations correspondantes. être considéré comme s'il existe une arête entre un nœud et un autre nœud. Par exemple, la paire de coordonnées X1 et Y2 a la valeur 1, ce qui signifie qu'il y a une arête entre le nœud 1 et le nœud 2. Ici, nous utilisons un graphique non pondéré, c'est-à-dire que 0 ne représente aucune arête et 1 représente une arête entre deux nœuds. En même temps, il s'agit toujours d'un graphe non orienté, donc la valeur de est également 1, et son intention est qu'il y ait également une arête du nœud 2 au nœud 1. S'il s'agit d'un graphique orienté, vous devez alors déterminer si cette arête est définie sur 1 en fonction de la direction de la flèche orientée.

À quoi ressemble le graphique correspondant à la matrice de contiguïté ci-dessus ? Vous pouvez essayer de le dessiner vous-même. Ce n’est pas grave si vous ne savez pas le dessiner, car nous venons tout juste de commencer à apprendre. En fait, il s’agit de la matrice d’adjacence du graphique que nous avons montré en premier.

L'image de gauche correspond à la matrice de contiguïté du tableau ci-dessus. Alors, à quoi ressemble la matrice de contiguïté du graphe orienté de droite ? Essayons aussi d’écrire.

Est-ce intéressant ? Et s’il s’agissait d’une intrigue puissante ? En fait, c'est très simple. On peut remplacer directement le 1 dans le graphe par le poids de l'arête correspondante. Cependant, il est possible que le poids de certaines arêtes soit 0, donc dans un graphe pondéré, on peut définir un très. grand nombre, Ou définir un très petit nombre négatif comme un nombre infini pour indiquer que ces deux nœuds n'ont pas d'arêtes.

Construction de la matrice de contiguïté

Ensuite, nous construirons la structure de stockage d'une telle matrice de contiguïté via du code. Nous utilisons toujours l'exemple du graphe non orienté pour implémenter. Étant donné qu'un graphe non orienté nécessite qu'une valeur soit attribuée au nœud inverse, il comporte une étape de plus qu'un graphe orienté, et les autres sont fondamentalement similaires.

// 邻接矩阵
$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;
            }
        }
    }
}

Dans ce code, nous initialisons d'abord une matrice bidimensionnelle via la méthode CreateGraph(). Autrement dit, en fonction du nombre de nœuds que nous saisissons, une structure de tableau bidimensionnel de X * Y est implémentée et toutes ses valeurs sont définies comme étant 0. En d'autres termes, ce graphique n'a actuellement aucune arête.

Ensuite, après que la méthode BuildGraph() ait appelé CreateGraph(), nous continuons à saisir les informations de bord. Entrez d'abord le nombre d'arêtes. Nous avons plusieurs arêtes. Si le nombre d'arêtes est inférieur ou égal à 0, ne continuez pas à les créer. En fait, nous pouvons être plus rigoureux et nous assurer que les arêtes ne peuvent pas dépasser la limite maximale en fonction des définitions des graphes complets non orientés et des graphes complets orientés.

Ensuite, nous continuerons à saisir les informations sur le bord dans une boucle. Le format d'entrée dont j'ai besoin ici est le nœud sortant, le nœud entrant et le poids du bord. Puisque notre exemple est un graphe non orienté, en plus de créer des arêtes pour , nous devons également créer des arêtes pour . Ceci est expliqué dans les commentaires du code.

L'explication du code peut encore être relativement abstraite. Exécutez-le et essayez-le.

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

Appelez notre fichier PHP dans l'environnement de ligne de commande, puis entrez les informations pertinentes dans l'ordre selon les invites. Le contenu du tableau finalement imprimé est-il exactement le même que celui de notre tableau ci-dessus ? Avec un simple bout de code, on réalise le stockage séquentiel de graphiques.

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

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

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

从 结点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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!