求出一叉树的直径-C [英] Finding the diameter of m-ary tree - C
问题描述
我必须使用C来分析C语言中的一元树.
I have to analyze an m-ary tree in C - using namely BFS.
有一些我暂时无法实现的要求:
There are some requirements I don't succeed to implement for a while:
1.找到树的直径.
2.给定树中的两个顶点-找到它们之间的最短简单路径.
关于1-我研究了Stack中的主题-并看到了一些对我不太清楚的实现(不幸的是，在C中不是)...一种通过两次使用BFS来计算直径的方法，从随机顶点... 我不确定第二个BFS是否必须记住"第一个BFS中的已访问数组.
As for 1 - I went through the topics in Stack - and have seen some implementations (not in C unfortunately) which are not very clear to me... Some way of calculating the diameter by using BFS twice, starting from a random vertex... I'm not sure if the second BFS has to "remember" the visited array from the first BFS.
关于2-我真的不知道该如何处理，但是我相信我可以在这里使用BFS.
As for 2 - I really don't know how to approach to that, but I believe I can use somehow BFS here.
-
此外，我必须在O(n ^ 2)时间复杂度中实现这两个要求.
Moreover, I have to implement these two requirements in O(n^2) time complexity.
除此之外，我还必须找到树的最大和最小高度.
Besides that, I have to find the maximal and minimal heights of the tree.
至于最大高度-我已经实现了BFS(不确定是否绝对正确).据我所知，BFS可以处理此最大高度.
As for the maximal height - I have implemented BFS (not sure it's absolutely correct) which to my understanding, deals with this maximal height.
至于最小高度-我不知道如何找到它.
这是我的顶点结构和BFS实现:
Here are my vertex struct and BFS implementations:
typedef struct Vertex {
size_t key;
size_t amountOfNeighbors; // The current amount of neighbors
size_t capacity; // The capacity of the neighbors (It's updating during run-time)
struct Vertex* parent;
struct Vertex** neighbors; // The possible parent and children of a vertex
} Vertex;
Vertex* bfs(Vertex* allVertices, size_t numOfVertices, Vertex* startVertex, size_t* pathDistance) {
if (startVertex -> neighbors == NULL) { // In case we have only one vertex in the graph
*pathDistance = 0;
return startVertex;
}
Queue* q = (Queue*)malloc((sizeof(size_t) * numOfVertices));
int* visited = (int*)malloc(sizeof(int) * numOfVertices);
for (size_t i = 0; i < numOfVertices; i++) {
visited[i] = 0; // Mark all the vertices as unvisited
}
size_t lastVertex = 0; // Actually indicates the furthermost vertex from startVertex
*pathDistance = 0; // The number of edges between lastVertex and startVertex
enqueue(q, startVertex->key);
visited[startVertex->key] = 1; // Mark as visited
while (!queueIsEmpty(q)) {
unsigned int currentVertex = dequeue(q); // The key of the current vertex
Vertex* s = &allVertices[currentVertex];
size_t currentAmountOfNeighbors = 0; // Detects the number of processed neighbors of the current vertex
for (Vertex **child = s->neighbors; currentAmountOfNeighbors < s->amountOfNeighbors; currentAmountOfNeighbors++) {
if (!visited[(*(child))->key]) {
visited[(*(child))->key] = 1;
enqueue(q, (*(child))->key);
child++; // TODO Validate it's a correct use of memory!
}
}
*pathDistance += 1; // Another layer passed
lastVertex = peekQueue(q);
}
Vertex* furtherMostVertexFromS = &allVertices[lastVertex];
free(q);
q = NULL;
return furtherMostVertexFromS;
}
我的困难和疑惑以粗体显示，其中的任何帮助将不胜感激.
My difficulties and wondering are in bold and any help with some of them will be appreciated.
推荐答案
首先，这种性质的问题更适合 CS Stack Exchange a>，但无论如何我都会尽力帮助
Firstly, questions of this nature are more appropriate to the CS Stack Exchange, but I'll try to help regardless
对于第一个问题(确定直径)，请注意，树的最长路径必须以树中最深的节点(叶子)开始(或结束). BFS帮助您找到所有节点的深度，从而帮助您找到最深的节点.您能从那里找到如何找到所述路径的终点吗?提示:考虑一下查找图的最深节点的过程.
For your first question(finding the diameter), note that the longest path of the tree must begin(or end) with the deepest node in the tree(which is a leaf). BFS helps you find the depths of all nodes, and thus help you find the deepest node. Can you figure from there how to find the end of said path? Hint: Think about the procedure for finding the deepest node of a graph.
您对BFS的工作方式似乎有误解:请注意，跟踪访问的节点的目的是避免越过后端-即避免循环-这在BFS中是不可能的.一颗树. 但是假设，即使您确实维护了这种访问过的"数组(例如，如果您希望算法处理循环图)，为什么还要在不同的BFS调用之间共享它呢?
There seems to be a misunderstanding on your part about how BFS works: Note that the point of keeping track of visited nodes, is to avoid crossing through back-edges - that is, to avoid cycles - which aren't possible in a tree. But hypothetically, even if you do maintain such a 'visited' array (e,g if you want your algorithm to handle cyclic graphs), why would it be shared between different BFS invocations?
关于第二个问题:BFS查找图形中的节点与起始节点之间的距离(从根调用时也称为深度").特别是，这些是最短的路径(在未加权的图中)
As for the second question: BFS finds the distances between nodes in the graph and the starting node(also called 'depth' when called from root). In particular, these are the shortest paths(on an unweighted graph)
其余大胆问题的答案也都相关，关键要点是在一个不带权的原始图中-BFS可以让您找到距起始节点的最短路径/最小距离(有关详细信息，请咨询算法教科书)对此
The answer to the rest of your bolded questions are also related, the key takeway is that in an acylic, unweighted graph - BFS lets you find the shortest path/minimal distance from the starting node (consult an algorithms textbook for more details on that)
这篇关于求出一叉树的直径-C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
