求出三叉树的直径-C

Question

我必须使用C来分析C中的一元树-即使用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;
}
我的困难和疑惑以粗体显示，其中一些帮助将不胜感激。

我必须使用BFS分析C中的一元树。有一些我暂时无法实现的要求：1.找到树的直径。 2.给定树中的两个顶点-...

Answer 1

首先，这种性质的问题更适合CS Stack Exchange，但无论如何我都会尽力帮助

对于您的第一个问题（确定直径），请注意，树的最长路径必须以树中最深的节点（叶子）开始（或结束）。 BFS帮助您找到所有节点的深度，从而帮助您找到最深的节点。您能从那里找到如何找到所述路径的终点吗？提示：考虑寻找图的最深节点的过程。