C# 顶点边

Question

我在完成这个任务时遇到了问题：如果一个 n-vertex 图有一个顶点 1（毒刺）连接到一个顶点 2（尾巴）连接一个顶点 3（body) 连接到其他顶点（脚）。一些脚可以连接到其他脚。设计一种算法，判断给定的图画是否代表蝎子，并判断哪条线是 sting、tail、body 和 feets。这是我要读取的数据文件： (+) is where is edge and (-) where are no edges

我想先找到刺，但基本上我如何才能搜索与尾巴和 body 的联系？ 我还必须使用递归 编辑： 好的，现在我已经找到了每行中有多少个“+”：

int[] B = new int[100];
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               int HowMuch = Regex.Matches(A[i,j], @"\+").Count;
               Saving[i] += HowMuch;
           }
           if(Saving[i]>=3)
           {
               Console.WriteLine("It's a scorpion!");
               Console.WriteLine("The body is in: " + i + " part");
           }
       }

通过递归，我试图找到路径连接...我应该如何继续？

static void Find(string[,] A, int n, int j)
    {
        for (int i = 0; i < n; i++)
        {
            if(A[i,j]=="+")
            {
                j = i;
                Find(A, n, j);
            }
        }

    }

Answer 1

所以，我给你一个关于如何解决这个问题的想法。我从 this 那里得到了帮助。你应该去那里看看。该网站上有提示。

我的方法和他们的略有不同。

从抽象的角度来看，你是在问，从邻接矩阵，确定给定的点是否像这个图像（又名蝎子）。（取自该网站）

现在，如何将邻接矩阵转换为蝎子矩阵？让我们看看你的例子。我手工绘制了邻接矩阵和图形。希望不会太难理解。

现在怎么解决呢？您在这里计算每个节点的度数。您可以在此处从邻接矩阵计算它。（度是指一个节点连接的节点数，比如我画的图，1的度是1，0的度是2等等...）

首先你在这里找到所有节点的度数（节点表示顶点，反之亦然）。

所以，刺应该是一级的。现在有这个问题，我会回来的。不过暂且不考虑。

尾巴的度数为2。它与刺相连。所以，你找到一个与 sting 连接的节点，你就完成了。那就是尾巴。

与tail相连的节点（除了sting）就是body

物体的度数 >= 2。所以如果有一个顶点的度数那么大，那肯定是物体。而与之相连的节点就是脚

现在你可能会说，脚的度数是2，为什么尾巴不是？因为它们没有连接到 sting。（你之前已经计算过了）

你也可能会说，脚都是1度的，为什么不刺痛呢？因为它连接到某个度数 > 2 的节点，这不可能（因为尾部的度数为 2）

这样就好了，但是考虑一个问题，如果图形是这样的，

1-0-3-4

那么刺是什么，脚是什么？我的回答是两者兼而有之。 1 和 4 都可以是 leg 或 sting.

希望你明白我说的。

如有需要，请在图片上进行说明： 你说，有+的地方就有优势。注意第 0 行的 1 和 3 上的 +。因此，0 连接到 1 和 4。我已经像这样连接了它们。而且连接是双向的。你可以从邻接矩阵看到。

C# 顶点边

C# Vertex Edges

c#

algorithm

matrix

graph

adjacency-matrix