Nos dan un mapa de ciudades conectadas entre sí a través de líneas de cable de modo que no hay ciclo entre dos ciudades. Necesitamos encontrar la longitud máxima de cable entre dos ciudades para un mapa de ciudad dado.
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 5
Output: maximum length of cable = 12
Método 1 (DFS simple): creamos un gráfico no dirigido para el mapa de la ciudad dada y hacemos DFS de cada ciudad para encontrar la longitud máxima del cable. Durante el recorrido, buscamos la longitud total del cable para llegar a la ciudad actual y, si no se visita la ciudad adyacente, llamamos a DFS , pero si se visitan todas las ciudades adyacentes para el Node actual, actualicemos el valor de max_length si el valor anterior de max_length es menos que el valor actual de la longitud total del cable.
Implementación:
C++
// C++ program to find the longest cable length
// between any two cities.
#include<bits/stdc++.h>
using 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 traversal
void DFS(vector< pair<int,int> > graph[], int src,
int prev_len, int *max_len,
vector <bool> &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[src].size(); i++)
{
// Adjacent element
adjacent = graph[src][i];
// If node or city is not visited
if (!visited[adjacent.first])
{
// Total length of cable from src city
// to its adjacent
curr_len = prev_len + adjacent.second;
// Call DFS for adjacent city
DFS(graph, adjacent.first, curr_len,
max_len, visited);
}
// If total cable length till now greater than
// previous length then update it
if ((*max_len) < curr_len)
*max_len = curr_len;
// make curr_len = 0 for next adjacent
curr_len = 0;
}
}
// n is number of cities or nodes in graph
// cable_lines is total cable_lines among the cities
// or edges in graph
int longestCable(vector<pair<int,int> > 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 input
int main()
{
// n is number of cities
int n = 6;
vector< pair<int,int> > 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;
}
Java
// Java program to find the longest cable length
// between any two cities.
import java.util.*;
public class GFG
{
// 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 traversal
// Class containing left and
// right child of current
// node and key value
static class pair {
public int x, y;
public pair(int f, int s)
{
x = f;
y = s;
}
}
// maximum length of cable among the connected
// cities
static int max_len = Integer.MIN_VALUE;
static void DFS(Vector<Vector<pair>> graph, int src,
int prev_len, boolean[] visited)
{
// Mark the src node visited
visited[src] = true;
// 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 adjacent;
// Traverse all adjacent
for(int i = 0; i < graph.get(src).size(); i++)
{
// Adjacent element
adjacent = graph.get(src).get(i);
// If node or city is not visited
if (!visited[adjacent.x])
{
// Total length of cable from
// src city to its adjacent
curr_len = prev_len + adjacent.y;
// Call DFS for adjacent city
DFS(graph, adjacent.x, curr_len, visited);
}
// If total cable length till
// now greater than previous
// length then update it
if (max_len < curr_len)
{
max_len = curr_len;
}
// make curr_len = 0 for next adjacent
curr_len = 0;
}
}
// n is number of cities or nodes in graph
// cable_lines is total cable_lines among the cities
// or edges in graph
static int longestCable(Vector<Vector<pair>> graph, int n)
{
// call DFS for each city to find maximum
// length of cable
for (int i=1; i<=n; i++)
{
// initialize visited array with 0
boolean[] visited = new boolean[n+1];
// Call DFS for src vertex i
DFS(graph, i, 0, visited);
}
return max_len;
}
public static void main(String[] args) {
// n is number of cities
int n = 6;
Vector<Vector<pair>> graph = new Vector<Vector<pair>>();
for(int i = 0; i < n + 1; i++)
{
graph.add(new Vector<pair>());
}
// create undirected graph
// first edge
graph.get(1).add(new pair(2, 3));
graph.get(2).add(new pair(1, 3));
// second edge
graph.get(2).add(new pair(3, 4));
graph.get(3).add(new pair(2, 4));
// third edge
graph.get(2).add(new pair(6, 2));
graph.get(6).add(new pair(2, 2));
// fourth edge
graph.get(4).add(new pair(6, 6));
graph.get(6).add(new pair(4, 6));
// fifth edge
graph.get(5).add(new pair(6, 5));
graph.get(6).add(new pair(5, 5));
System.out.print("Maximum length of cable = "
+ longestCable(graph, n));
}
}
// This code is contributed by suresh07.
Python3
# Python3 program to find the longest
# cable length between any two cities.
# 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 traversal
def DFS(graph, src, prev_len,
max_len, visited):
# Mark the src node visited
visited[src] = 1
# curr_len is for length of cable
# from src city to its adjacent city
curr_len = 0
# Adjacent is pair type which stores
# destination city and cable length
adjacent = None
# Traverse all adjacent
for i in range(len(graph[src])):
# Adjacent element
adjacent = graph[src][i]
# If node or city is not visited
if (not visited[adjacent[0]]):
# Total length of cable from
# src city to its adjacent
curr_len = prev_len + adjacent[1]
# Call DFS for adjacent city
DFS(graph, adjacent[0], curr_len,
max_len, visited)
# If total cable length till
# now greater than previous
# length then update it
if (max_len[0] < curr_len):
max_len[0] = curr_len
# make curr_len = 0 for next adjacent
curr_len = 0
# n is number of cities or nodes in
# graph cable_lines is total cable_lines
# among the cities or edges in graph
def longestCable(graph, n):
# maximum length of cable among
# the connected cities
max_len = [-999999999999]
# call DFS for each city to find
# maximum length of cable
for i in range(1, n + 1):
# initialize visited array with 0
visited = [False] * (n + 1)
# Call DFS for src vertex i
DFS(graph, i, 0, max_len, visited)
return max_len[0]
# Driver Code
if __name__ == '__main__':
# n is number of cities
n = 6
graph = [[] for i in range(n + 1)]
# create undirected graph
# first edge
graph[1].append([2, 3])
graph[2].append([1, 3])
# second edge
graph[2].append([3, 4])
graph[3].append([2, 4])
# third edge
graph[2].append([6, 2])
graph[6].append([2, 2])
# fourth edge
graph[4].append([6, 6])
graph[6].append([4, 6])
# fifth edge
graph[5].append([6, 5])
graph[6].append([5, 5])
print("Maximum length of cable =",
longestCable(graph, n))
# This code is contributed by PranchalK
C#
// C# program to find the longest cable length
// between any two cities.
using System;
using System.Collections.Generic;
class GFG {
// 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 traversal
// maximum length of cable among the connected
// cities
static int max_len = Int32.MinValue;
static void DFS(List<List<Tuple<int,int>>> graph, int src, int prev_len, bool[] visited)
{
// Mark the src node visited
visited[src] = true;
// 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
Tuple<int,int> adjacent;
// Traverse all adjacent
for(int i = 0; i < graph[src].Count; i++)
{
// Adjacent element
adjacent = graph[src][i];
// If node or city is not visited
if (!visited[adjacent.Item1])
{
// Total length of cable from
// src city to its adjacent
curr_len = prev_len + adjacent.Item2;
// Call DFS for adjacent city
DFS(graph, adjacent.Item1, curr_len, visited);
}
// If total cable length till
// now greater than previous
// length then update it
if (max_len < curr_len)
{
max_len = curr_len;
}
// make curr_len = 0 for next adjacent
curr_len = 0;
}
}
// n is number of cities or nodes in graph
// cable_lines is total cable_lines among the cities
// or edges in graph
static int longestCable(List<List<Tuple<int,int>>> graph, int n)
{
// call DFS for each city to find maximum
// length of cable
for (int i=1; i<=n; i++)
{
// initialize visited array with 0
bool[] visited = new bool[n+1];
// Call DFS for src vertex i
DFS(graph, i, 0, visited);
}
return max_len;
}
static void Main() {
// n is number of cities
int n = 6;
List<List<Tuple<int,int>>> graph = new List<List<Tuple<int,int>>>();
for(int i = 0; i < n + 1; i++)
{
graph.Add(new List<Tuple<int,int>>());
}
// create undirected graph
// first edge
graph[1].Add(new Tuple<int,int>(2, 3));
graph[2].Add(new Tuple<int,int>(1, 3));
// second edge
graph[2].Add(new Tuple<int,int>(3, 4));
graph[3].Add(new Tuple<int,int>(2, 4));
// third edge
graph[2].Add(new Tuple<int,int>(6, 2));
graph[6].Add(new Tuple<int,int>(2, 2));
// fourth edge
graph[4].Add(new Tuple<int,int>(6, 6));
graph[6].Add(new Tuple<int,int>(4, 6));
// fifth edge
graph[5].Add(new Tuple<int,int>(6, 5));
graph[6].Add(new Tuple<int,int>(5, 5));
Console.Write("Maximum length of cable = "
+ longestCable(graph, n));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// Javascript program to find the longest cable length
// between any two cities.
// 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 traversal
// maximum length of cable among the connected
// cities
let max_len = Number.MIN_VALUE;
function DFS(graph, src, prev_len, visited)
{
// Mark the src node visited
visited[src] = true;
// curr_len is for length of cable
// from src city to its adjacent city
let curr_len = 0;
// Adjacent is pair type which stores
// destination city and cable length
let adjacent = [];
// Traverse all adjacent
for(let i = 0; i < graph[src].length; i++)
{
// Adjacent element
adjacent = graph[src][i];
// If node or city is not visited
if (!visited[adjacent[0]])
{
// Total length of cable from
// src city to its adjacent
curr_len = prev_len + adjacent[1];
// Call DFS for adjacent city
DFS(graph, adjacent[0], curr_len, visited);
}
// If total cable length till
// now greater than previous
// length then update it
if (max_len < curr_len)
{
max_len = curr_len;
}
// make curr_len = 0 for next adjacent
curr_len = 0;
}
}
// n is number of cities or nodes in graph
// cable_lines is total cable_lines among the cities
// or edges in graph
function longestCable(graph, n)
{
// call DFS for each city to find maximum
// length of cable
for (let i=1; i<=n; i++)
{
// initialize visited array with 0
let visited = new Array(n+1);
visited.fill(false);
// Call DFS for src vertex i
DFS(graph, i, 0, visited);
}
return max_len;
}
// n is number of cities
let n = 6;
let graph = [];
for(let i = 0; i < n + 1; i++)
{
graph.push([]);
}
// create undirected graph
// first edge
graph[1].push([2, 3]);
graph[2].push([1, 3]);
// second edge
graph[2].push([3, 4]);
graph[3].push([2, 4]);
// third edge
graph[2].push([6, 2]);
graph[6].push([2, 2]);
// fourth edge
graph[4].push([6, 6]);
graph[6].push([4, 6]);
// fifth edge
graph[5].push([6, 5]);
graph[6].push([5, 5]);
document.write("Maximum length of cable = " +
longestCable(graph, n));
// This code is contributed by divyesh072019.
</script>
Producción
Maximum length of cable = 12
Complejidad del tiempo: O(V * (V + E))
Método 2 (Eficiente: funciona solo si el gráfico está dirigido):
Podemos resolver el problema anterior en tiempo O(V+E) si el gráfico dado es dirigido en lugar de un gráfico no dirigido.
A continuación se muestran los pasos.
- Cree una array de distancia dist[] e inicialice todas sus entradas como menos infinito
- Ordena todos los vértices en orden topológico .
- Haz lo siguiente para cada vértice u en orden topológico.
- Haz lo siguiente para cada vértice adyacente v de u
- ……si (dist[v] < dist[u] + peso(u, v))
- ……..dist[v] = dist[u] + peso(u, v)
- Devuelve el valor máximo de dist[]
Dado que no hay un peso negativo, el procesamiento de los vértices en orden topológico siempre produciría una array de rutas más largas dist[] de modo que dist[u] indica la ruta más larga que termina en el vértice ‘u’.
La implementación del enfoque anterior se puede adoptar fácilmente desde aquí . Las diferencias aquí son que no hay bordes de peso negativo y necesitamos la ruta más larga en general (no las rutas más largas desde un vértice de origen). Finalmente devolvemos el máximo de todos los valores en dist[].
Tiempo Complejidad : O(V + E)
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo GeeksForGeeks. Si tiene un mejor enfoque para este problema, por favor comparta.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA