代码之家  ›  专栏  ›  技术社区  ›  Fresh

C#顶点边

  •  0
  • Fresh  · 技术社区  · 10 年前

    我在做这个任务时遇到了一个问题:如果一个n顶点图的顶点1(刺)连接到顶点2(尾巴),顶点3(身体)连接到其他顶点(脚),那么它就是蝎子。一些脚可能连接到其他脚。设计一个算法,决定给定的图形是否代表蝎子,并确定哪一行是刺、尾巴、身体和脚。 这是我要读取的数据文件: (+) is where is edge and (-) where are no edges

    我想先找到刺痛的地方,但基本上我怎么能找到尾巴和身体的联系呢? 我还必须使用递归 编辑: 好了,现在我已经发现每行有多少“+”:

    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);
                }
            }
    
        }
    
    1 回复  |  直到 10 年前
        1
  •  2
  •   Shubhashis    10 年前

    所以,我给你一个如何解决这个问题的想法。我从 this 。你应该看看那里。该网站上有一个提示。

    我的做法与他们略有不同。

    从抽象的角度来看,你需要从邻接矩阵中确定给定的点是否像这张图(又名蝎子)。(取自该场地)

    enter image description here

    现在,邻接矩阵如何转换为蝎子?让我们看看你的例子。 我用手画了邻接矩阵和图。我希望这不太难理解。

    enter image description here

    现在如何解决?这里计算每个节点的阶数。你可以从这里的邻接矩阵来计算它。(度数表示一个节点连接到的节点数,例如,对于在那里绘制的图,度数1为1,度数0为2,依此类推…)

    首先,您可以在这里找到所有节点的度数(节点表示顶点,反之亦然)。

    所以,刺痛应该是一级的。现在这个有问题了,我会再谈。但现在我们不要考虑它。

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

    与尾巴相连的节点(除了刺)是身体。

    身体会有度>=2.所以如果有一个顶点的度数如此之大,那么这肯定就是物体。与之相连的节点是脚。

    现在你可能会说,脚是2度,为什么不是尾巴?因为它们与毒刺无关。(您之前已经计算过)

    你也可以说,脚是1度,为什么不刺痛?因为它连接到具有度>2,不能(因为尾部的度数为2)

    现在这一切都很好,但考虑一个问题,如果图是这样的,

    1-0-3-4

    那么什么是刺痛,什么是脚?我的答案是两者都有。1和4都可以是腿或刺。

    我希望你明白我说的话。

    如果需要,对图像进行澄清: 你说过,有一个+就有一个边。请注意第0行的1和3上的+。因此,0连接到1和4。我就这样连接了它们。这些连接是双向的。你可以从邻接矩阵中看到这一点。