C++实现无向图添加边使首尾顶点最短路径最长

首先，我们需要表示图的数据结构。一个简单的方法是使用邻接列表来表示图。我们可以使用一个数组来存储图的顶点，每个顶点都有一个链表来存储与之相邻的顶点。\n\ncpp\n#include \"iostream\"\n#include \"list\"\n#include \"queue\"\nusing namespace std;\n\nclass Graph {\n int V; // 顶点的个数\n list<int>* adj; // 邻接列表\n\npublic:\n Graph(int V); // 构造函数\n void addEdge(int v, int w); // 添加边\n int longestPath(); // 计算最长路径\n int BFS(int v, bool visited[]); // 广度优先搜索\n};\n\nGraph::Graph(int V) {\n this->V = V;\n adj = new list<int>[V];\n}\n\nvoid Graph::addEdge(int v, int w) {\n adj[v].push_back(w);\n adj[w].push_back(v);\n}\n\nint Graph::BFS(int v, bool visited[]) {\n int maxDist = 0;\n\n // 创建一个队列用于广度优先搜索\n queue<int> q;\n\n visited[v] = true;\n q.push(v);\n\n while (!q.empty()) {\n int curr = q.front();\n q.pop();\n\n // 遍历当前顶点的所有相邻顶点\n for (auto it = adj[curr].begin(); it != adj[curr].end(); ++it) {\n // 如果相邻顶点未被访问，则将其标记为已访问，并将其加入队列\n if (!visited[*it]) {\n visited[*it] = true;\n q.push(*it);\n maxDist = max(maxDist, *it);\n }\n }\n }\n\n return maxDist;\n}\n\nint Graph::longestPath() {\n int maxDist = 0;\n bool* visited = new bool[V];\n\n // 遍历第一个连通块的所有顶点，并计算每个顶点到最后一个顶点的最长路径\n for (int i = 0; i < V; i++) {\n if (!visited[i]) {\n maxDist = max(maxDist, BFS(i, visited));\n }\n }\n\n delete[] visited;\n return maxDist;\n}\n\nint main() {\n int V = 5; // 图的顶点个数\n Graph g(V);\n\n // 添加边\n g.addEdge(0, 1);\n g.addEdge(1, 2);\n g.addEdge(2, 3);\n g.addEdge(3, 4);\n\n // 添加额外的边\n g.addEdge(0, 4);\n\n cout << \"最长路径的长度为：\" << g.longestPath() << endl;\n\n return 0;\n}\n\n\n在上面的代码中，我们使用了广度优先搜索（BFS）来计算从第一个顶点到最后一个顶点的最长路径。首先，我们创建一个 visited 数组来标记顶点是否已被访问。然后，我们从第一个顶点开始，将其标记为已访问并加入队列。接下来，我们开始广度优先搜索，遍历队列中的每个顶点的相邻顶点。如果相邻顶点未被访问，则将其标记为已访问并加入队列。在遍历过程中，我们记录下每个顶点到最后一个顶点的最大值，以找到最长路径的长度。\n\n最后，我们在 main 函数中创建一个图，并添加边。然后，我们调用 longestPath 函数来计算最长路径的长度，并输出结果。