递归边缘搜索-Java 学习之路

我正在尝试编写一个算法，该算法将获取沿边缘访问的点列表，以及构成对象其余部分的未访问边缘列表（由点对组成）并在其中搜索其中的路径完成边缘（即连接开始到结束） . 我目前有：

public static int PolygonSearch(Point start, Point end, List<Point> visitedPoints, List<Point[]> unvisitedEdges)
{
    int count = 0;
    for (int i = unvisitedEdges.Count - 1; i > -1; i--)
    {
        Point[] line = unvisitedEdges[i];
        if (((Equal(line[0], start) && Equal(line[1], end)) 
            || (Equal(line[1], start) && Equal(line[0], end))) 
            && visitedPoints.Count > 2)
        {
            return count + 1;
        }
        else if (Equal(start, line[0]))
        {
            unvisitedEdges.RemoveAt(i);
            count += PolygonSearch(line[1], end, visitedPoints, unvisitedEdges);
        }
        else if (Equal(start, line[1]))
        {
            unvisitedEdges.RemoveAt(i);
            count += PolygonSearch(line[0], end, visitedPoints, unvisitedEdges);
        }
    }
    return count;
}

（开始和结束是该行的当前起点和终点）

这里显而易见的问题是删除，这会弄乱外部循环，但我不确定如何纠正它，我尝试每次都创建一个新列表，但这不起作用（我甚至没有实现一种方式返回路径，只计算有效的路径） .

任何帮助解决这个问题将不胜感激 .

1 回答

要避免删除对象，可以将其设置为“已删除”，如果已设置则忽略它 .

以下使用名为 Visited 的标志 . 如果是'removed'，则 Visited 设置为true .

我没有明显地测试过这个，但它应该让你大致了解该怎么做：

public struct Edge
{
    public Edge()
    {
        this.Visited = false;
    }

    public Point[] Points;
    public bool Visited;
}

public static int PolygonSearch(Point start, Point end, List<Point> visitedPoints, List<Edge> unvisitedEdges)
{
    int count = 0;
    for (int i = unvisitedEdges.Count - 1; i > -1; i--)
    {
        Edge line = unvisitedEdges[i];
        if (((Equal(line.Points[0], start) && Equal(line.Points[1], end)) 
            || (Equal(line.Points[1], start) && Equal(line.Points[0], end))) 
            && visitedPoints.Count > 2
            && line.Visited == false)
        {
            return count + 1;
        }
        else if (Equal(start, line[0]))
        {
            unvisitedEdges[i].Visited = true;
            count += PolygonSearch(line.Points[1], end, visitedPoints, unvisitedEdges);
        }
        else if (Equal(start, line[0]))
        {
            unvisitedEdges[i].Visited = true;
            count += PolygonSearch(line.Points[1], end, visitedPoints, unvisitedEdges);
        }
    }
    return count;
}

回复于 2024-04-29T20:51:51+08:00

递归边缘搜索

1 回答

相关问题