C＃Vertex Edges

我在完成这个任务时遇到了问题：n顶点图是一个蝎子，如果它有一个顶点1（sting）连接到一个顶点2（尾部）连接一个顶点3（主体）连接到其他顶点（英尺）。 一些脚可能连接到其他脚。 设计一种算法，决定给定的图形是否代表蝎子并告诉哪条线是刺，尾，体和脚。 这是我要读取的数据文件： （+）是边缘和（ – ）哪里没有边缘

我想先找到刺痛但我基本上可以搜索尾巴和身体的连接？ 我也必须使用递归 编辑：好的，现在我发现每行有多少“+”：

int[] B = new int[100]; for (int i = 0; i < n; i++) { for (int j = 0; j =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

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

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

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

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

现在该如何解决？ 您可以在此计算每个节点的度数。 您可以在此处从邻接矩阵计算它。 （度数表示一个节点连接的节点数量，例如，对于我绘制的图形，1的度数为1，0度为2，依此类推……）

首先，您可以在此找到所有节点的度数（节点表示顶点，反之亦然）。

所以，刺痛应该是一度的。 现在有一个问题，我会回到它。 但是现在让我们不要考虑它。

尾巴将是2度。它将与刺痛相关联。 所以，你发现一个节点与sting相连，你就完成了。 那是尾巴。

与尾部连接的节点（除了刺痛）是身体。

身体的度数> = 2.所以如果有一个具有那么大程度的顶点，那么这就是身体肯定的。 与之相关的节点就是脚。

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

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

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

1-0-3-4

然后什么是刺痛和什么是脚？ 我的回答是。 1和4都可以是腿或刺。

我希望你明白我说的话。

如果需要，可以对图像进行澄清：你说，哪里有一个+有边缘。 注意第0行上的+ on 1和3.所以，0连接到1和4.我就像那样连接它们。 并且连接是双向的。 您可以从邻接矩阵中看到它。