我必须用 C 语言分析一个 m 元树 - 即使用 BFS。
有些要求我暂时没有成功实现：
1.求树的直径。
2. 给定树中的两个顶点 - 找到它们之间的最短简单路径。
至于 1 - 我浏览了 Stack 中的主题 - 并且看到了一些对我来说不是很清楚的实现(不幸的是不是 C 语言(......使用BFS两次计算直径的某种方法，从随机顶点开始...我不确定第二个 BFS 是否必须"记住"第一个 BFS 中访问过的阵列。
至于 2 -我真的不知道如何处理，但我相信我可以在这里以某种方式使用 BFS。
-
此外，我必须在 O(n^2( 时间复杂度中实现这两个要求。
-
除此之外，我必须找到树的最大和最小高度。
-
至于最大高度 - 我已经实现了 BFS(不确定它是否绝对正确(，据我所知，它处理这个最大高度。
-
至于最小高度 - 我不知道如何找到它。
以下是我的顶点结构和 BFS 实现：
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;
}
我的困难和疑惑是粗体的，任何帮助将不胜感激。
首先，这种性质的问题更适合CS Stack Exchange，但无论如何，我都会尽力提供帮助
对于您的第一个问题(求直径(，请注意树的最长路径必须以树中最深的节点(即叶子(开始(或结束(。BFS帮助您找到所有节点的深度，从而帮助您找到最深的节点。你能从那里弄清楚如何找到这条路的尽头吗？提示：考虑查找图形最深层节点的过程。
你似乎对BFS的工作原理存在误解：请注意，跟踪访问过的节点的目的是避免穿过后边缘 - 也就是说，避免循环 - 这在树中是不可能的。 但假设，即使你确实维护了这样一个"访问"数组(例如，如果你希望你的算法处理循环图(，为什么它会在不同的BFS调用之间共享？
至于第二个问题：BFS找到图中节点和起始节点之间的距离(从根调用时也称为"深度"(。特别是，这些是最短路径(在未加权图上(
其余粗体问题的答案也是相关的，关键是在一个非加权图中 - BFS 允许您找到与起始节点的最短路径/最小距离(有关更多详细信息，请参阅算法教科书(