数据结构图的运算（深度优先）_数据结构图的深度是多少-CSDN博客

本文链接：https://blog.csdn.net/dwLoveJava/article/details/51144936

本文介绍了图的有向与无向概念、邻接、路径和连通图等基本概念，并详细阐述了深度优先搜索（DFS）的算法过程，通过创建Graph类和Vertex类实现图的表示及最小生成树的构建。最后通过实例展示了如何添加顶点、边以及进行DFS操作。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

//图：
//     有向图：指某个顶点完成任务依赖于另一个顶点的任务是否完成；
//     无向图：可以从任意的顶点到另外的顶点，也就是各个顶点没有依赖性；
//     邻接：如果两个顶点被一条直线连接，那么这连个顶点是临近的；
//     路径：路径是边的序列，例如：A->E 中间存在B、C、D，所以ABCDE为路径序列
//     连通图：如果至少有一个路径可以链接“所有顶点”，那么就可以称为连通图
//     搜索：
//         深度优先：
//             1，从指定的顶点（起始顶点）开始查找，先将起始顶点放入栈中，查看与下一个顶点是否为邻接，如果是将下一个顶点也放入栈中，同时标记为已访问；
//             2，取栈顶的顶点继续与下一个顶点重复1中的工作；
//             3，当栈顶的顶点与下一个不为邻接时，依次退栈，然后取栈顶顶点继续比较；
//             4，当栈中的元素为空时，并且所有顶点均已访问，则查询完成；
//         广度优先：
//             1，从指定的顶点（起始顶点）开始查找，先将其实顶点放入队列，然后出队，依次查询与出队值相邻接顶点，然后邻接顶点放入队列；
//             2，如果发现下一个顶点与出队的顶点不邻接，则出队，然后运行第一步；
//             3，当队列为空，同时所有顶点均已访问，则完成查询；

class Graph{

    private $stack = array();

    private $vertexs = array();

    private $vertexSize = 0;

    private $edgeMatrix = array(); //存储边的矩阵

    public function __construct($maxNum=20){
        //初始化矩阵数组
        for($i=0; $i<$maxNum; $i++){
            for($j=0; $j<$maxNum; $j++){
                $this->edgeMatrix[$i][$j] = 0;
            }
        }
    }

    //添加顶点
    public function addVertex(Vertex $vertex){
        $this->vertexs[$this->vertexSize++] = $vertex;
    }

    //添加边
    public function addEdge($start, $end){
        $this->edgeMatrix[$start][$end] = 1;
        $this->edgeMatrix[$end][$start] = 1;
    }
    //最小生成树
    public function mst(){
        if(count($this->vertexs) === 0){
            exit('list is empty!');
        }
        $this->vertexs[0]->wasVisited = true; //访问第一个Vertex，将其标为已访问
        array_unshift($this->stack, 0); //放入栈中
        while(count($this->stack) > 0){
            $i = array_shift($this->stack);
            if(($next = $this->getAdjUnvisitedVertex($i)) == -1){
                array_shift($this->satck);
            }else{
                $this->vertexs[$next]->wasVisited = true;
                array_unshift($this->stack, $next);
                echo "{$this->vertexs[$i]->char}-{$this->vertexs[$next]->char}<br>";
            }
        }
    }
    //查找邻接未访问的顶点
    public function getAdjUnvisitedVertex($row){
        for($i=0; $i<$this->vertexSize; $i++){
            if(1 == $this->edgeMatrix[$row][$i] && !$this->vertexs[$i]->wasVisited){
                return $i;
            }
        }
        return -1;
    }
}

class Vertex{
    public $wasVisited;
    public $char;

    public function __construct($char){
        $this->char = $char;
        $this->wasVisited = false;
    }
}


$graph = new Graph();
$graph->addVertex(new Vertex('a'));
$graph->addVertex(new Vertex('b'));
$graph->addVertex(new Vertex('c'));
$graph->addVertex(new Vertex('d'));
$graph->addVertex(new Vertex('e'));
$graph->addEdge(0, 1);
$graph->addEdge(0, 2);
$graph->addEdge(0, 3);
$graph->addEdge(0, 4);
$graph->addEdge(1, 2);
$graph->addEdge(1, 3);
$graph->addEdge(1, 4);
$graph->addEdge(2, 3);
$graph->addEdge(2, 4);
$graph->addEdge(3, 4);
$graph->mst();