Java赋值使用Dijkstra的搜索方法，广度优先和深度优先-6ren

Java赋值使用Dijkstra的搜索方法，广度优先和深度优先

转载作者：行者123 更新时间：2023-12-02 09:13:30

StackOverflow 社区您好，需要您的帮助。我的 java 类(class)有期末考试，其要求是:生成一个包含 100,000 个节点的图，其中每个节点随机与其他节点有 1 到 5 个连接。每个节点应包含 1 到 300,000 之间的随机值。 (因此通常大约三分之一的搜索会产生查询匹配)。允许用户输入要搜索的数字，并实现以下三种类型的搜索算法中的每一种。广度优先。 (30 分) 深度优先。 (30 分) Dijkstra 算法。 (40分)

不允许在搜索中进行回溯。 (将您已搜索的节点标记为完整，并且不要在同一搜索中重新访问它们)。每次搜索都应返回以下内容: 搜索的成功/失败。到找到的节点的最短路径的长度。搜索期间检查的节点总数。您也可以选择返回最短路径的详尽显示，以进行测试和验证。

出于某种原因，我的 IDE 显示 BFS 和 Dijkstras 有“重复的代码片段 17 行长”有人可以看看告诉我如何修复它或者可能有更好的方法来实现它吗？另外，如果我尝试在“驱动程序类”中执行nodesNum > 30k，则会出现内存泄漏。

代码如下:

类图:

import java.util.*;
import javax.swing.JOptionPane;

class Graph
{
    private Listing[] vertex;
    private int[][] edge;
    private int max;
    private int numberOfVertices;
    private int nodeCheck = 0;
    private int selectNum = 0;

    Graph(int g)
    {
        vertex = new Listing[g];
        edge = new int[g][g];
        max = g;
        numberOfVertices = 0;
    }
    private void depthFirstSearch(int firstVertex)
    {
        int v;
        Stack<Integer> nodeStack = new Stack<>();

        for(int i = 0; i<numberOfVertices; i++)
        {
            if (vertex[i] != null) {
                vertex[i].setPushed(false);
            }
        }
        nodeStack.push(firstVertex);
        vertex[firstVertex].setPushed(true);

        while (!nodeStack.empty())
        {
            v = nodeStack.pop();
            vertex[v].visit();
            nodeCheck++;
            for (int column = 0; column < numberOfVertices; column++)
            {

                if(edge[v][column] == 1 && vertex[column].getPushed())
                {
                    nodeStack.push(column);
                    vertex[column].setPushed(true);
                }
            }
        }
    }
    private void breathFirstSearch(int firstVertex)
    {
        int V;
        Queue<Integer> nodeQueue = new LinkedList<>();

        for(int i = 0; i < numberOfVertices; i++)
        {
            if(vertex[i] != null)
                vertex[i].setPushed(false);
        }
        nodeQueue.add(firstVertex);
        vertex[firstVertex].setPushed(true);

        while(!nodeQueue.isEmpty())
        {
            V = nodeQueue.remove();
            vertex[V].visit();
            nodeCheck++;
            for(int column = 0; column < numberOfVertices; column++)
            {
                if(edge[V][column] == 1 && vertex[column].getPushed())
                {
                    nodeQueue.add(column);
                    vertex[column].setPushed(true);
                }
            }
        }
    }

    private void Dijkstra(int firstVertex)
    {
        int v;
        LinkedList<Integer> nodeQueue = new LinkedList<>();

        int i = 0;
        while (i < numberOfVertices)
        {
            if(vertex[i] != null)
                vertex[i].setPushed(false);
            i++;
        }
        nodeQueue.add(firstVertex);
        vertex[firstVertex].setPushed(true);

        while(!nodeQueue.isEmpty())
        {
            v = nodeQueue.remove();
            vertex[v].visit();
            nodeCheck++;
            for(int column = 0; column < numberOfVertices; column++)
            {
                if(edge[v][column] == 1 && vertex[column].getPushed())
                {
                    nodeQueue.add(column);
                    vertex[column].setPushed(true);
                }
            }
        }
    }

    private void insertVertex(int vertexNumber, Listing newListing)
    {
        if(vertexNumber >= max)
        {
            return;
        }
        vertex[vertexNumber] = newListing.deepCopy();
        numberOfVertices++;
    }

    private void insertEdge(int fromVertex, int toVertex)
    {
        if(vertex[fromVertex] == null || vertex[toVertex] == null)
            return;
        edge[fromVertex][toVertex] = 1;
    }

    void showVertex(int vertexNumber)
    {
        System.out.print(vertex[vertexNumber]);
    }

    void showEdges(int vertexNumber)
    {
        for(int column = 0; column < numberOfVertices; column++)
        {
            if(edge[vertexNumber][column] == 1)
            {
                System.out.println(vertexNumber + "," + column);
            }
        }
        System.out.println();
    }

    void InitializeNodes(Graph G, int nodesNum)
    {
        Random random = new Random();
        for (int i = 0; i < nodesNum; i++ )
        {
            Listing v = new Listing(random.nextInt(300000) + 1);
            G.insertVertex(i, v);
        }

        int vertexListNumber = G.vertex.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nodesNum; i++ )
        {
            list.add(i);
        }
        Collections.shuffle(list);
        for (int i = 0; i < vertexListNumber; i++ )
        {
            int randnum = random.nextInt(5);
            for (int j = 0; j < randnum; j++ )
            {
                int rand = random.nextInt(5);
                G.insertEdge(i, list.get(rand));
            }
        }

    }

    int Search()
    {
        String search = JOptionPane.showInputDialog("Enter Node to search:");
        try
        {
            if(search != null)
            {
                selectNum = Integer.parseInt(search);
            }
        }
        catch (NumberFormatException e)
        {
            selectNum = 0;
        }
        return selectNum;
    }

    private int SelectPane()
    {
        String paneSelect = JOptionPane.showInputDialog("Choose a search method:" +
                "\n\t1: Use Depth-First Search" +
                "\n\t2: Use Breadth-First Search" +
                "\n\t3: Use Dijkstra's Search" +
                "\n\t4: Close  Program");
        int selectNum = 0;

        try{
            if(paneSelect != null)
            {
                selectNum = Integer.parseInt(paneSelect);
            }
        }
        catch (NumberFormatException ignored)
        {
        }
        return selectNum;
    }

    void algorithmChoice(Graph graph, int vertexStart)
    {
        int paneNum = 0;
        while (paneNum != 4)
        {
            paneNum = SelectPane();
            switch (paneNum)
            {
                case 1:
                    graph.depthFirstSearch(vertexStart);
                    System.out.println("Nodes counted were: " + nodeCheck);
                    System.out.println("------------------------------------");
                    break;
                case 2:
                    graph.breathFirstSearch(vertexStart);
                    System.out.println("Nodes counted were: " + nodeCheck);
                    System.out.println("------------------------------------");
                    break;
                case 3:
                    graph.Dijkstra(vertexStart);
                    System.out.println("Nodes counted were: " + nodeCheck);
                    System.out.println("------------------------------------");
                    break;
                case 4:
                    break;
                default:
                    JOptionPane.showMessageDialog(null, "Enter 4 to quit.");
                    break;
            }
        }
    }


}

类(class)列表:

public class Listing
{
    private int value;
    private boolean pushed;

    Listing(int v)
    {
        value = v;
    }
    public String toString()
    {
        return ("Vertex: " + value + "\n" );
    }

    Listing deepCopy()
    {
        return new Listing(value);
    }
    boolean getPushed()
    {
        return !pushed;
    }
    void setPushed(boolean value)
    {
        pushed = value;
    }
    void visit()
    {
        System.out.println(this);
    }
}

类驱动程序:

public class Driver
{
    public static void main(String[] args)
    {
        int nodesNum = 30000; //Can go up to 30k nodes, otherwise causes memory leak.
        Graph graph = new Graph(nodesNum);
        graph.InitializeNodes(graph, nodesNum);

        for(int i = 0; i<5; i++)
        {
            System.out.print("Node " + i + "\'s ");
            graph.showVertex(i);
            System.out.print("Its routes are:\n");
            graph.showEdges(i);
        }

        int select = graph.Search();
        graph.algorithmChoice(graph, select);
    }
}

非常感谢您的帮助!

最佳答案

您收到的错误是由于 exceeding max heap size创建edge = new int[g][g];时在您的情况下，g 可以高达 100,000。
我建议避免使用如此巨大的矩阵。
相反，引入一个 Edge对象:

class Edge{

    private final int fromVertex, toVertex;

    Edge(int fromVertex, int toVertex){
        this.fromVertex = fromVertex;
        this.toVertex = toVertex;
    }

    @Override
    public boolean equals(Object obj) {
        if( ! (obj instanceof Edge)) return false;
        Edge other = (Edge)obj;
        return connects(other.fromVertex, other.toVertex);
    }

    boolean connects(int fromVertex, int toVertex){
        return fromVertex == this.fromVertex && toVertex == this.toVertex ||
                    fromVertex == this.toVertex && toVertex == this.fromVertex;
    }
 }

并在 Graph 中使用它.
而不是private int[][] edge;使用 Edge 的集合s:
private final Set<Edge> edges = new HashSet<>();更改insertEdge至:

private void insertEdge(int fromVertex, int toVertex)
{
    if(vertex[fromVertex] == null || vertex[toVertex] == null)
        return;
    edges.add(new Edge(fromVertex, toVertex));
}

并添加一个方法来检查两个顶点之间是否有边:

private boolean isEdgeBetween(int fromVertex, int toVertex)
{
    for(Edge edge : edges){
        if(edge.connects(fromVertex, toVertex)) return true;
    }

    return false;
}

用途:if( isEdgeBetween(v,column) && vertex[column].getPushed())
而不是:if(edge[v][column] == 1 && vertex[column].getPushed())

关于Java赋值使用Dijkstra的搜索方法，广度优先和深度优先，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59204882/

文章推荐： java - 将字母数字字符串转换为 double

Ruby 方法() 方法
我想了解 Ruby 方法 methods() 是如何工作的。我尝试使用“ruby 方法”在 Google 上搜索，但这不是我需要的。我也看过 ruby-doc.org，但我没有找到这种方法。
VBS教程：方法-Test 方法
Test 方法对指定的字符串执行一个正则表达式搜索，并返回一个 Boolean 值指示是否找到匹配的模式。 object.Test(string) 参数 object 必选项。总是一个
VBS教程：方法-Replace 方法
Replace 方法替换在正则表达式查找中找到的文本。 object.Replace(string1, string2) 参数 object 必选项。总是一个 RegExp 对象的名称。
VBS教程：方法-Raise 方法
Raise 方法生成运行时错误 object.Raise(number, source, description, helpfile, helpcontext) 参数 object 应为
VBS教程：方法-Execute 方法
Execute 方法对指定的字符串执行正则表达式搜索。 object.Execute(string) 参数 object 必选项。总是一个 RegExp 对象的名称。 string
VBS教程：方法-Clear 方法
Clear 方法清除 Err 对象的所有属性设置。 object.Clear object 应为 Err 对象的名称。说明在错误处理后，使用 Clear 显式地清除 Err 对象。此
VBS教程：方法-CopyFile 方法
CopyFile 方法将一个或多个文件从某位置复制到另一位置。 object.CopyFile source, destination[, overwrite] 参数 object 必选
VBS教程：方法-Copy 方法
Copy 方法将指定的文件或文件夹从某位置复制到另一位置。 object.Copy destination[, overwrite] 参数 object 必选项。应为 File 或 F
VBS教程：方法-Close 方法
Close 方法关闭打开的 TextStream 文件。 object.Close object 应为 TextStream 对象的名称。说明下面例子举例说明如何使用 Close 方
VBS教程：方法-BuildPath 方法
BuildPath 方法向现有路径后添加名称。 object.BuildPath(path, name) 参数 object 必选项。应为 FileSystemObject 对象的名称
VBS教程：方法-GetFolder 方法
GetFolder 方法返回与指定的路径中某文件夹相应的 Folder 对象。 object.GetFolder(folderspec) 参数 object 必选项。应为 FileSy
VBS教程：方法-GetFileName 方法
GetFileName 方法返回指定路径（不是指定驱动器路径部分）的最后一个文件或文件夹。 object.GetFileName(pathspec) 参数 object 必选项。应为
VBS教程：方法-GetFile 方法
GetFile 方法返回与指定路径中某文件相应的 File 对象。 object.GetFile(filespec) 参数 object 必选项。应为 FileSystemObject
VBS教程：方法-GetExtensionName 方法
GetExtensionName 方法返回字符串，该字符串包含路径最后一个组成部分的扩展名。 object.GetExtensionName(path) 参数 object 必选项。应
VBS教程：方法-GetDriveName 方法
GetDriveName 方法返回包含指定路径中驱动器名的字符串。 object.GetDriveName(path) 参数 object 必选项。应为 FileSystemObjec
VBS教程：方法-GetDrive 方法
GetDrive 方法返回与指定的路径中驱动器相对应的 Drive 对象。 object.GetDrive drivespec 参数 object 必选项。应为 FileSystemO
VBS教程：方法-GetBaseName 方法
GetBaseName 方法返回字符串，其中包含文件的基本名 (不带扩展名), 或者提供的路径说明中的文件夹。 object.GetBaseName(path) 参数 object 必
VBS教程：方法-GetAbsolutePathName 方法
GetAbsolutePathName 方法从提供的指定路径中返回完整且含义明确的路径。 object.GetAbsolutePathName(pathspec) 参数 object
VBS教程：方法-FolderExists 方法
FolderExists 方法如果指定的文件夹存在，则返回 True；否则返回 False。 object.FolderExists(folderspec) 参数 object 必选项
VBS教程：方法-FileExists 方法
FileExists 方法如果指定的文件存在返回 True；否则返回 False。 object.FileExists(filespec) 参数 object 必选项。应为 FileS

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

Java赋值使用Dijkstra的搜索方法，广度优先和深度优先