利用栈实现DFS

悠悠 2023-07-17 15:56 15阅读 0赞

public static void DepthFirstSearch<T>(Graph<T> graph, Vertex<T> sourceVertex)
            {
                foreach(Vertex<T> vertex in graph.Vertices)    //初始化每一个结点
                { 
                    vertex.visited = false;
                    vertex.Parent = null;
                    vertex.Distance = 0;    //设置初始距离为0
                }
    
                Stack<Vertex<T>> dStact = new Stack<Vertex<T>>();
                sourceVertex.visited = true;
                dStact.Push(sourceVertex);   //栈中放入初始结点
                
                while(dStact.Count > 0)
                {
                    Vertex<T> curVertex = dStact.Pop();   //栈首出栈
    
                    foreach(Vertex<T> vertices in graph.GetAdjacentVertices(sourceVertex))   //扫描栈首结点的每一个邻接结点
                    {
                        if (!vertices.visited)
                        {
                            vertices.visited = true;
                            vertices.Distance = curVertex.Distance + graph.GetEdgeWeight(curVertex, vertices);  
                            vertices.Parent = curVertex;   //保留父结点用以打印路径
                            dStact.Push(vertices);   //入栈
                        }
                    }
                }
            }

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关利用Python实现顺序栈

1 问题在常用的数据结构中，有一批结构被称为容器——栈与队列。那该怎么利用Python学习栈这种结构的特性并用Python实现其相关操作呢？ 2 方法栈相对于是一个容

以你之姓@/ 2024年02月17日 10:35/ 0 赞/ 61 阅读

相关利用栈实现DFS

public static void DepthFirstSearch<T>(Graph<T> graph, Vertex<T> sourceVertex)

悠悠/ 2023年07月17日 15:56/ 0 赞/ 16 阅读

相关利用栈实现十六进制转换

拿到需求后自己写了一份，然后参考别人写的好的，修改之后重写了一个版本 v1 import java.util.Deque; import java.ut

快来打我*/ 2022年11月04日 11:15/ 0 赞/ 105 阅读

相关利用栈Stack实现队列(Queue)

实现说明：入队时，将元素压入s1; 出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队; 这个思路，

谁借莪１个温暖的怀抱￠/ 2022年08月02日 07:30/ 0 赞/ 250 阅读

相关利用两个队列实现一个栈

import java.util.ArrayDeque; import java.util.Scanner; / Created

末蓝、/ 2022年07月16日 03:50/ 0 赞/ 243 阅读

相关利用单链表实现栈

栈是一种仅限于在头尾操作的数据结构，和队列相反，栈的特点是“现金后出”，因此又称为LIFO。和队列一样，栈也有链表和数组两种实现方式，各自的优缺点和介绍队列时提到的基本相同

冷不防/ 2022年05月29日 06:35/ 0 赞/ 272 阅读

相关 Java-利用栈实现括号匹配

SqStack.java package test; public class SqStack{ private Object[]stac

古城微笑少年丶/ 2022年05月28日 22:43/ 0 赞/ 198 阅读

相关利用栈实现括号匹配算法！

算法：检测表达式中的字符，若是左括号就入栈，如果是右括号就出栈一个元素与其配对，配对成功则继续访问下一个字符，否则退出。出现非括号字符则跳过。 include <st

た入场券/ 2022年05月09日 08:04/ 0 赞/ 224 阅读

相关利用栈实现进制的转换！

问题:将十进制数转换为任意进制数(2,8,16...). 算法:假如N为输入的数，n为要转换为的进制，若要将十进制231转换为8进制数，过程如下; N

ゝ一世哀愁。/ 2022年05月09日 03:36/ 0 赞/ 223 阅读

相关 C++利用栈实现计算器

后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行，所以不需要算符优先级，这对我们编写计算器来说很好实现

你的名字/ 2022年04月03日 14:44/ 0 赞/ 221 阅读