如何在C＃中为矩阵中的给定元素创建生成树 [英] How to make a spanning tree in C# for a given element in a matrix

问题描述

我需要从像这个数组这样的矩形数组中提取长度方面的最佳路径：

I need to extract the best path in terms of its length from a rectangular array like this array:

引用：

| 1 || 0 || 1 || 0 |

| 1 || 0 || 0 || 1 |

| 1 || 1 || 0 || 1 |

| 0 || 0 || 1 || 1 |

|1||0||1||0|
|1||0||0||1|
|1||1||0||1|
|0||0||1||1|

寻路规则：



1-从方法签名中提供的索引开始，其中rowIndex和colIndex是起始点的位置。



2-必须能够水平，垂直或对角地相互连接。



3 - 你不能移动到包含零的单元格。



4-你可以通过路径返回但不使用相同的单元格，即你可以向上移动但是没有使用相同的单元格。



5-所有提取路径（可能的解决方案）的最佳路径是相互连接的路径中最长的路径。



6- N. o如果起始单元格的值为0则出现问题。



我尝试了以下递归算法，但它对我不起作用并产生错误输出，即不如预期!!。



以下是结果：结果

The pathfinding rules:

1- Start from the indexes provided in the method signature where the rowIndex and colIndex are the positions of the starting point.

2- The ones must be able to connect with each other either horizontally, vertically, or diagonally.

3- You can not move to the cell that contains zero.

4- You can back by the path but not using the same cells i.e. you can move up the down the up but not using the same cells.

5- The best path from all the extracted paths (possible solutions) is longest one in terms of the connected ones by each other.

6- No problem if the value of the starting cell is 0.

I tried the following recursion algorithm, but it does not work for me and generate wrong output i.e. not as expected!!.

Here are the results: Results

        using System;
        using System.IO;
        using System.Text;
        using System.Drawing;
        using System.Collections;
        using System.ComponentModel;
        using System.Windows.Forms;
        using System.Data;
        using System.Threading;
        using AUV_Topology;
        using System.Collections.Generic;
        using System.Media;
        using System.Linq;

        namespace AUVtopology
        {
            public partial class Form1 : Form
            {        
              static int[,] array;
              static List<int[]> path;

// *******************************************************************************************************************************//
        //This method is used to make sure the coordinate array 
        //is contained in the list. List.contains(new int[] {val1,val2}) was not enough.
        static Boolean containsArray(List<int[]> list, int[] array)
        {
            if (array == null || array.Length == 0)
            {
                return false;
            }
            foreach (var listArray in list)
            {
                if (listArray != null && listArray.Length == array.Length)
                {
                    for (int i = 0; i < listArray.Length; i++)
                    {
                        if (i != listArray.Length - 1)
                        {
                            if (array[i] != listArray[i] && array[i + 1] != listArray[i + 1])
                            {
                                continue;
                            }


                            return true;

                        }

                    }

                }
            }
            return false;
        }    



// *******************************************************************************************************************************//

        //This is the recursive method of the algorithm. It finds the 
        //maximum path of 1 cells in a matrix of 0/1 cells
        static List<int[]> getMaxPath(int[,] array, List<int[]> maxPath, int rowIndex, int colIndex)
        {

            //Add the current cell to the path.
            maxPath.Add(new int[] { rowIndex, colIndex });

            //Get the array limits.
            int rowLength = array.GetLength(0);
            int colLength = array.GetLength(1);

            //If the path contains all the cells in the matrix, stop
            if (maxPath.Count >= rowLength * colLength)
            {
                return maxPath;
            }

            //remove one from lengths to make it the maximum index
            colLength = colLength - 1;
            rowLength = rowLength - 1;

            //We'll use this variable to see which of the 
            //potential 7 paths are the longest.
            List<int[]> futurePath;

            //Go over all 8 possible adjoining cells:
            //If we can go one down, one right, and it's a spot we 
            //have not yet visited
            if (colIndex < colLength && rowIndex < rowLength &&
                array[rowIndex + 1, colIndex + 1] == 1 &&
                !containsArray(maxPath, new int[] { rowIndex + 1, colIndex + 1 }))
            {

                //We use maxPath first, since this is the first 
                //direction and by default is the longest
                maxPath = getMaxPath(array, maxPath, rowIndex + 1, colIndex + 1);
            }

            //If we can go one down, and it's a spot we have not
            //yet visited
            if (colIndex < colLength &&
              array[rowIndex, colIndex + 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex, colIndex + 1 }))
            {

                //We use futurePath now, since this is a second
                //direction and a potential contender
                futurePath = getMaxPath(array, maxPath, rowIndex, colIndex + 1);

                //We only need the maximum path.
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //If we can go one down and one left, and it's a spot
            //we have not yet visited
            if (rowIndex > 0 && colIndex < colLength &&
               array[rowIndex - 1, colIndex + 1] == 1 &&
               !containsArray(maxPath, new int[] { rowIndex - 1, colIndex + 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex + 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //If we can go one left, and it's a spot we have not
            //yet visited
            if (rowIndex > 0 &&
               array[rowIndex - 1, colIndex] == 1 &&
               !containsArray(maxPath, new int[] { rowIndex - 1, colIndex }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one left and one up, and it's a spot we
            //have not yet visited
            if (rowIndex > 0 && colIndex > 0 &&
              array[rowIndex - 1, colIndex - 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex - 1, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one up, and it's a spot we have not yet
            //visited
            if (colIndex > 0 &&
                array[rowIndex, colIndex - 1] == 1 &&
                !containsArray(maxPath, new int[] { rowIndex, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one up and one right, and it's a spot we
            //have not yet visited
            if (colIndex > 0 && rowIndex < rowLength &&
              array[rowIndex + 1, colIndex - 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex + 1, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one right, and it's a spot we have not
            //yet visited
            if (rowIndex < rowLength &&
              array[rowIndex + 1, colIndex] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex + 1, colIndex }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //We return the max path. Note: If none of the directions around 
            //us was applicable, we simply return the path we started 
            //with our cell included.
            return maxPath;
        }

所以我以不同的方式思考!!如果我们可以为每个节点生成一个生成树，还有一件事;如果未将其列为前一个父级，则可以根据索引返回到较低的单元格。查看示例：



查看图片



圆圈内的蓝色分支表示最大路径，其值为1的单元格数。

我的问题是如何实现这一点。如何为每个分支创建一个数组，以便在长度方面对它们进行比较，以获得最长的最佳解决方案？



我是什么尝试过：



递归函数提取路径作为规则，但我没有为我工作，因为它产生错误的结果和大数组大小它使堆栈溢出!!。

So I thought in a different way!!. If we can generate a spanning tree for each node with one more thing; which is that you can back to a lower cell in terms of its indexes, if it is not listed as a previous parent. See the example:

See the image

The branch inside the circle with the blue color represents the longest path in terms of the number of cells with the value 1.
My question is how to implement this. How to create an array for each branch in order to compare them in terms of the length to obtain the longest one as the best solution ?.

What I have tried:

Recursion Function to extract the path as the rules, but I did not work for me as it made wrong results and with large array size it made a stack overflow!!.

推荐答案

using System; 
using System.Collections.Generic; 
 
namespace Prim 
{ 
    class PriorityQueue 
    { 
        int heapSize; 
        List<Node> nodeList; 
 
        public List<Node> NodeList 
        { 
            get 
            { 
                return nodeList; 
            } 
        } 
 
        public PriorityQueue(List<Node> nl) 
        { 
            heapSize = nl.Count; 
            nodeList = new List<Node>(); 
 
            for (int i = 0; i < nl.Count; i++) 
                nodeList.Add(nl[i]); 
        } 
 
        public void exchange(int i, int j) 
        { 
            Node temp = nodeList[i]; 
 
            nodeList[i] = nodeList[j]; 
            nodeList[j] = temp; 
        } 
 
        public void heapify(int i) 
        { 
            int l = 2 * i + 1; 
            int r = 2 * i + 2; 
            int largest = -1; 
             
            if (l < heapSize && nodeList[l].Key > nodeList[i].Key) 
                largest = l; 
            else 
                largest = i; 
            if (r < heapSize && nodeList[r].Key > nodeList[largest].Key) 
                largest = r; 
            if (largest != i) 
            { 
                exchange(i, largest); 
                heapify(largest); 
            } 
        } 
 
        public void buildHeap() 
        { 
            for (int i = heapSize / 2; i >= 0; i--) 
                heapify(i); 
        } 
 
        int heapSearch(Node node) 
        { 
            for (int i = 0; i < heapSize; i++) 
            { 
                Node aNode = nodeList[i]; 
 
                if (node.Id == aNode.Id) 
                    return i; 
            } 
 
            return -1; 
        } 
 
        public int size() 
        { 
            return heapSize; 
        } 
 
        public Node elementAt(int i) 
        { 
            return nodeList[i]; 
        } 
 
        public void heapSort() 
        { 
            int temp = heapSize; 
 
            buildHeap(); 
            for (int i = heapSize - 1; i >= 1; i--) 
            { 
                exchange(0, i); 
                heapSize--; 
                heapify(0); 
            } 
 
            heapSize = temp; 
        } 
 
        public Node extractMin() 
        { 
            if (heapSize < 1) 
                return null; 
 
            heapSort(); 
 
            exchange(0, heapSize - 1); 
            heapSize--; 
            return nodeList[heapSize]; 
        } 
 
        public int find(Node node) 
        { 
            return heapSearch(node); 
        } 
    } 
}

这篇关于如何在C＃中为矩阵中的给定元素创建生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！