C＃顶点边缘 [英] C# Vertex Edges
问题描述
我做这个任务有一个问题：一个n-vertex图是一个蝎子，如果它有一个顶点1（蛰）连接到一个顶点2（尾部）连接一个顶点3（身体）连接到另一个顶点（脚）。有些脚可能连接到其他脚。设计一种算法，用于决定给定图形是否代表蝎子，并判断哪一行是刺，尾，身和脚。
这是我读取的数据文件：
现在如何解决它？你计算每个节点的度数。你可以在这里从邻接矩阵计算它。 （度数表示一个节点连接的节点数量，例如，对于我在那里绘制的图形，1的度数是1，0的度数是2，依此类推......）
首先找到所有节点的度数（节点表示顶点，反之亦然）。
所以，刺痛应该是一级的。现在有一个问题，我会回到它。但现在让我们不要考虑它。
尾巴是2度，它会与刺痛相连。所以，你发现一个节点与刺连接，你就完成了。这是尾巴。
与tail连接的节点（除了sting）是body。
身体的度数> = 2.所以如果有一个顶点的程度，那么这是肯定的身体。而与它相连的节点就是这样。
现在你可能会说，feets是2度，所以为什么不是tail？因为他们没有联系到刺痛（你之前计算过）
你也许会说，feets是1度，所以为什么不刺痛？因为它连接到度数大于2的某个节点，这不可能（因为尾部的度数为2）现在，这一切都很好，但考虑一个问题，如果图表是这样的话，
1-0-3-4
然后什么是蜇和什么是脚？我的答案是两个。我希望你明白我说过的话。
strong>如果需要，对图片进行澄清：
您说过，哪里有+有边缘。注意行0上的1和3。因此，0连接到1和4.我已经连接它们就像那样。连接是双向的。你可以从邻接矩阵看到。
I have a problem making this task: An n-vertex graph is a scorpion if it has a vertex 1(the sting) connected to a vertex two (the tail) connected a vertex 3 (the body) connected to the other vertexes (the feet). Some of the feet may be connected to other feet. Design an algorithm that decides whether a given drawing represents a scorpion and tell in which line is sting,tail , body and feets. This is my data file to read from: (+) is where is edge and (-) where are no edges
I'm trying to find the sting first but how basically i could search for connections with tail and body? also i have to use recursion EDIT: Ok now i habe found how much "+" there are in each line:
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");
}
}
And with recursion i'm trying to find path connections... How i should continue?
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);
}
}
}
So, I'm giving you an idea on how to solve this. I took help from this. You should take a look there. There is a hint on that site.
My approach is slightly different from theirs.
From abstract point of view, you are asking, from an adjacency matrix, determine whether the given points are like this image(aka the scorpion). (taken from that site)
Now, how the adjacency matrix convert to scorpion? Let's look at your example. I drawn the adjacency matrix and the graph by hand. I hope its not too difficult to understand.
Now how to solve it? You compute the degree for each node here. You can compute it from the adjacency matrix here. (The degree means the number of nodes one node is connected to, For example, for the graph i drawn there, the degree of 1 is 1, degree of 0 is 2 and so on...)
At first you find degree of all the nodes here(nodes means vertex and vice versa).
So, the sting should be the one with degree one. Now there is a problem with this, i'll get back to it. But for now lets not consider it.
The tail would be with degree 2. And it would be connected with the sting. So, you find the one node connected with sting and you are done. That is the tail.
The node that is connected with tail(apart from sting) is the body.
The body would be with degree >= 2. So if there is a vertex with that much degree, then that's the body for sure. And the nodes connected with it are the feets.
Now you may say, the feets are with degree 2 so why are not tail? Because they are not connected to sting.(which you have computed earlier)
You may also say, the feets are with degree 1 so why not sting? because its connected to some node that has degree > 2, which cannot be(as the tail has degree of 2)
Now thats all well and good, but consider a problem, If the graph is like this,
1-0-3-4
then what would be the sting and the what would be the feet? My answer is both. Both 1 and 4 can be leg or sting.
I hope you understand what i have said.
Clarification on the image if needed: You said, where there is a + there is an edge. Notice the + on 1 and 3 on row 0. So, 0 is connected to 1 and 4. I've connected them just like that. And the connections are bidirectional. You can see that from adjacency matrix.
这篇关于C＃顶点边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
