本文共 2914 字,大约阅读时间需要 9 分钟。
原文地址:
已知一个城市连接图,它们之间是通过电缆连接的,这样的话任意两个城市之间都没有环路。我们需要在已知的这个城市图中找到两个城市之间最大长度的电缆。
Input : n = 6 1 2 3 // Cable length from 1 to 2 (or 2 to 1) is 3 2 3 4 2 6 2 6 4 6 6 5 5Output: maximum length of cable = 12
Method 1 (Simple DFS)
方法 1(简单的深度优先搜寻(DFS))我们可以为这个已知的城市地图建立一个无向图,对于每一个城市都去做DFS并找到最长的电缆。在遍历的过程中,我们寻找可以达到当前城市的最长电缆,如果它的相邻城市不能访问的话,那么就调用DFS,但是如果当前节点所有的相邻城市都访问过了,如max_length以前的值比现在的总长度要小,那么就更新max_length的值。
// C++ program to find the longest cable length// between any two cities.#includeusing namespace std;// visited[] array to make nodes visited// src is starting node for DFS traversal// prev_len is sum of cable length till current node// max_len is pointer which stores the maximum length// of cable value after DFS traversalvoid DFS(vector< pair > graph[], int src, int prev_len, int *max_len, vector &visited){ // Mark the src node visited visited[src] = 1; // curr_len is for length of cable from src // city to its adjacent city int curr_len = 0; // Adjacent is pair type which stores // destination city and cable length pair < int, int > adjacent; // Traverse all adjacent for (int i=0; i > graph[], int n){ // maximum length of cable among the connected // cities int max_len = INT_MIN; // call DFS for each city to find maximum // length of cable for (int i=1; i<=n; i++) { // initialize visited array with 0 vector< bool > visited(n+1, false); // Call DFS for src vertex i DFS(graph, i, 0, &max_len, visited); } return max_len;}// driver program to test the inputint main(){ // n is number of cities int n = 6; vector< pair > graph[n+1]; // create undirected graph // first edge graph[1].push_back(make_pair(2, 3)); graph[2].push_back(make_pair(1, 3)); // second edge graph[2].push_back(make_pair(3, 4)); graph[3].push_back(make_pair(2, 4)); // third edge graph[2].push_back(make_pair(6, 2)); graph[6].push_back(make_pair(2, 2)); // fourth edge graph[4].push_back(make_pair(6, 6)); graph[6].push_back(make_pair(4, 6)); // fifth edge graph[5].push_back(make_pair(6, 5)); graph[6].push_back(make_pair(5, 5)); cout << "Maximum length of cable = " << longestCable(graph, n); return 0;}
输出:
Maximum length of cable = 12
时间复杂度:O(V * (V + E))
方法2(更加有效的)
我们可以在 O(V+E)的时间内解决这个问题。下面就是具体的步骤。
1)建立一个距离矩阵dist[],用无限小初始化矩阵的每一个单元。
2)对所有的定点进行拓扑排序。 3)按照拓扑排序的顺序访问每一个定点u。 …..Do following for every adjacent vertex v of u ………..if (dist[v] < dist[u] + weight(u, v)) ……………dist[v] = dist[u] + weight(u, v) 4)返回dist[]中的最大值因为图中没有负的权重,所以以拓扑顺序处理定点总是会产生最长路径矩阵dist[],这样dist[u]就是到顶点‘u’的最长路径。
以上的实现方法可以很容易地应用到这个问题。不同点就是边的权重都是非负的,我们需要找到的是整体的最长路径(而不是从开始节点的最长路径)。最后我们返回dist[]中所有值的最大值。
时间复杂度:O(V + E)
转载地址:http://wwhii.baihongyu.com/