无环连通图T=(V, E)的直径是图中所有顶点之间最短路径的最大值，试设计一个算法求T的直径，并分析算法的时间复杂度。用邻接表作为存储结构；引入一个辅助数组保存各顶点的度；执行删除过程并修正各个顶点的度。用C语言代码示例

为了求解无环连通图 \( T = (V, E) \) 的直径，我们可以采用中心节点法（也称作Floyd-Warshall with center node或Johnson's algorithm变种）。该算法的基本思路是从每个顶点出发找到到其他所有顶点的最短路径，然后选取直径最大的两个距离作为直径。

以下是算法步骤：

1. 初始化：
- 遍历图，创建一个邻接表表示图的边关系，同时初始化一个辅助数组 `degree` 记录每个顶点的度数。
- 创建一个二维数组 `distance` 存储从起点到终点的最短路径长度，默认值设为无穷大，除了对角线元素设为0（表示每个顶点到自身的距离）。

2. 找中心节点：
- 首先选择一个中心节点 `center`，通常选择拥有最大度数的顶点，因为这样的节点可能与其他节点连接最多。
- 更新 `distance`：从中心节点开始，遍历所有邻居，更新它们到其他节点的最短路径。

3. 删除中心节点后的更新：
- 对于每个非中心节点，更新其到其他节点的最短路径：如果通过中心节点比直接相连更短，则更新路径。
- 同时，减小中心节点的度数，因为它不再作为中间跳转点。

4. 最终直径计算：
- 可能需要再次查找当前剩余节点中最大度数的顶点，作为新的中心节点，继续上述步骤，直到所有节点都被考虑过一次。最后一次迭代得到的最长路径就是直径。

以下是简单的C语言伪代码示意：

typedef struct Node {
    int vertex;
    List<Edge> neighbors;
} Node;

void init_graph(Node* nodes, int num_nodes);
void find_diameter(Node* center, Node** nodes, int num_nodes, int** distance);

int main() {
    // 初始化图
    Node* nodes = ...;
    int num_nodes = ...;
    init_graph(nodes, num_nodes);

    // 初始化度数数组
    int degree[num_nodes];

    // 主循环寻找直径
    for (int i = 0; i < num_nodes; ++i) {
        int max_degree_index = ...;  // 获取当前度数最大节点的索引
        Node* center = &nodes[max_degree_index];
        find_diameter(center, nodes, num_nodes, distance);

        // 更新中心节点度数
        degree[max_degree_index]--;
        // 可能需要调整中心节点
    }

    int diameter = ...;  // 最长路径即为直径
    return diameter;
}

时间复杂度分析：
- 初始化阶段和更新中心节点的最短路径的时间复杂度为 O(V^2)，其中 V 是顶点的数量。
- 因为中心节点的选择可能是动态变化的，所以总的时间复杂度取决于实际执行的迭代次数，但理论上不会超过 O(V log V)。