Dado un gráfico no dirigido de valor binario con V vértices y E aristas, la tarea es encontrar los equivalentes hexadecimales de todos los componentes conectados del gráfico. Se puede considerar que un gráfico con valores binarios tiene solo números binarios (0 o 1) como valores de vértice.
Ejemplos:
Entrada: E = 4, V = 7
Salida:
String = 0 1 Equivalente hexadecimal = 1
String = 0 0 0 Equivalente hexadecimal = 0
String = 1 1 Equivalente hexadecimal = 3
Explicación:
En el caso del primer componente conectado, la string binaria es [0, 1]
Por lo tanto, el string = «01» y número binario = 01
Entonces, el equivalente hexadecimal = 1Entrada: E = 6, V = 10
Salida:
String = 1 Equivalente hexadecimal = 1
String = 0 0 1 0 Equivalente hexadecimal = 2
String = 1 1 0 Equivalente hexadecimal = 6
String = 1 0 Equivalente hexadecimal = 2
Enfoque: la idea es utilizar el recorrido transversal de búsqueda en profundidad para realizar un seguimiento de los componentes conectados en el gráfico no dirigido, como se explica en este artículo. Para cada componente conectado, se muestra la string binaria y el valor hexadecimal equivalente se calcula a partir del valor binario como se explica en este artículo y se imprime.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find // hexadecimal equivalents of // all connected components #include <bits/stdc++.h> using namespace std; // Function to traverse the undirected // graph using the Depth first traversal void depthFirst(int v, vector<int> graph[], vector<bool>& visited, vector<int>& storeChain) { // Marking the visited // vertex as true visited[v] = true; // Store the connected chain storeChain.push_back(v); for (auto i : graph[v]) { if (visited[i] == false) { // Recursive call to // the DFS algorithm depthFirst(i, graph, visited, storeChain); } } } // Function to create map between binary // number and its equivalent hexadecimal void createMap(unordered_map<string, char>* um) { (*um)["0000"] = '0'; (*um)["0001"] = '1'; (*um)["0010"] = '2'; (*um)["0011"] = '3'; (*um)["0100"] = '4'; (*um)["0101"] = '5'; (*um)["0110"] = '6'; (*um)["0111"] = '7'; (*um)["1000"] = '8'; (*um)["1001"] = '9'; (*um)["1010"] = 'A'; (*um)["1011"] = 'B'; (*um)["1100"] = 'C'; (*um)["1101"] = 'D'; (*um)["1110"] = 'E'; (*um)["1111"] = 'F'; } // Function to return hexadecimal // equivalent of each connected // component string hexaDecimal(string bin) { int l = bin.size(); int t = bin.find_first_of('.'); // Length of string before '.' int len_left = t != -1 ? t : l; // Add min 0's in the beginning // to make left substring length // divisible by 4 for (int i = 1; i <= (4 - len_left % 4) % 4; i++) bin = '0' + bin; // If decimal point exists if (t != -1) { // Length of string after '.' int len_right = l - len_left - 1; // Add min 0's in the end to // make right substring length // divisible by 4 for (int i = 1; i <= (4 - len_right % 4) % 4; i++) bin = bin + '0'; } // Create map between binary // and its equivalent hex code unordered_map<string, char> bin_hex_map; createMap(&bin_hex_map); int i = 0; string hex = ""; while (1) { // Extract from left, // substring of size 4 and add // its hex code hex += bin_hex_map[bin.substr(i, 4)]; i += 4; if (i == bin.size()) break; // If '.' is encountered add it // to result if (bin.at(i) == '.') { hex += '.'; i++; } } // Required hexadecimal number return hex; } // Function to find the hexadecimal // equivalents of all connected // components void hexValue( vector<int> graph[], int vertices, vector<int> values) { // Initializing boolean array // to mark visited vertices vector<bool> visited(10001, false); // Following loop invokes // DFS algorithm for (int i = 1; i <= vertices; i++) { if (visited[i] == false) { // Variable to hold // temporary length int sizeChain; // Container to store // each chain vector<int> storeChain; // DFS algorithm depthFirst(i, graph, visited, storeChain); // Variable to hold each // chain size sizeChain = storeChain.size(); // Container to store // values of vertices of // individual chains int chainValues[sizeChain + 1]; // Storing the values of // each chain for (int i = 0; i < sizeChain; i++) { int temp = values[storeChain[i] - 1]; chainValues[i] = temp; } // Printing binary chain cout << "Chain = "; for (int i = 0; i < sizeChain; i++) { cout << chainValues[i] << " "; } cout << "\t"; // Converting the array // with vertex // values to a binary string // using string stream stringstream ss; ss << chainValues[0]; string s = ss.str(); for (int i = 1; i < sizeChain; i++) { stringstream ss1; ss1 << chainValues[i]; string s1 = ss1.str(); s.append(s1); } // Printing the hexadecimal // values cout << "Hexadecimal " << "equivalent = "; cout << hexaDecimal(s) << endl; } } } // Driver Program int main() { // Initializing graph in the // form of adjacency list vector<int> graph[1001]; // Defining the number of // edges and vertices int E, V; E = 4; V = 7; // Assigning the values // for each vertex of the // undirected graph vector<int> values; values.push_back(0); values.push_back(1); values.push_back(1); values.push_back(1); values.push_back(0); values.push_back(1); values.push_back(1); // Constructing the // undirected graph graph[1].push_back(2); graph[2].push_back(1); graph[3].push_back(4); graph[4].push_back(3); graph[4].push_back(5); graph[5].push_back(4); graph[6].push_back(5); graph[5].push_back(6); graph[6].push_back(7); graph[7].push_back(6); hexValue(graph, V, values); return 0; }
Java
// Java implementation to find // hexadecimal equivalents of // all connected components import java.io.*; import java.util.*; class GFG{ // Function to traverse the undirected // graph using the Depth first traversal static void depthFirst(int v, List<List<Integer>> graph, boolean[] visited, List<Integer> storeChain) { // Marking the visited // vertex as true visited[v] = true; // Store the connected chain storeChain.add(v); for(int i : graph.get(v)) { if (visited[i] == false) { // Recursive call to // the DFS algorithm depthFirst(i, graph, visited, storeChain); } } } // Function to create map between binary // number and its equivalent hexadecimal static void createMap(Map<String, Character> um) { um.put("0000", '0'); um.put("0001", '1'); um.put("0010", '2'); um.put("0011", '3'); um.put("0100", '4'); um.put("0101", '5'); um.put("0110", '6'); um.put("0111", '7'); um.put("1000", '8'); um.put("1001", '9'); um.put("1010", 'A'); um.put("1011", 'B'); um.put("1100", 'C'); um.put("1101", 'D'); um.put("1110", 'E'); um.put("1111", 'F'); } // Function to return hexadecimal // equivalent of each connected // component static String hexaDecimal(String bin) { int l = bin.length(); int t = bin.indexOf('.'); // Length of string before '.' int len_left = t != -1 ? t : l; // Add min 0's in the beginning to make // left substring length divisible by 4 for(int i = 1; i <= (4 - len_left % 4) % 4; i++) bin = '0' + bin; // If decimal point exists if (t != -1) { // Length of string after '.' int len_right = l - len_left - 1; // Add min 0's in the end to make right // substring length divisible by 4 for(int i = 1; i <= (4 - len_right % 4) % 4; i++) bin = bin + '0'; } // Create map between binary and its // equivalent hex code Map<String, Character> bin_hex_map = new HashMap<String, Character>(); createMap(bin_hex_map); int i = 0; String hex = ""; while (true) { // One by one extract from left, substring // of size 4 and add its hex code hex += bin_hex_map.get(bin.substring(i, i + 4)); i += 4; if (i == bin.length()) break; // If '.' is encountered add it // to result if (bin.charAt(i) == '.') { hex += '.'; i++; } } // Required hexadecimal number return hex; } // Function to find the hexadecimal // equivalents of all connected // components static void hexValue(List<List<Integer>> graph, int vertices, List<Integer> values) { // Initializing boolean array // to mark visited vertices boolean[] visited = new boolean[1001]; // Following loop invokes DFS algorithm for(int i = 1; i <= vertices; i++) { if (visited[i] == false) { // Variable to hold // temporary length int sizeChain; // Container to store each chain List<Integer> storeChain = new ArrayList<Integer>(); // DFS algorithm depthFirst(i, graph, visited, storeChain); // Variable to hold each chain size sizeChain = storeChain.size(); // Container to store values // of vertices of individual chains int[] chainValues = new int[sizeChain + 1]; // Storing the values of each chain for(int j = 0; j < sizeChain; j++) { int temp = values.get( storeChain.get(j) - 1); chainValues[j] = temp; } // Printing binary chain System.out.print("Chain = "); for(int j = 0; j < sizeChain; j++) { System.out.print(chainValues[j] + " "); } System.out.println(); System.out.print("\t"); // Converting the array with // vertex values to a binary // string String s = ""; for(int j = 0; j < sizeChain; j++) { String s1 = String.valueOf( chainValues[j]); s += s1; } // Printing the hexadecimal // values System.out.println("Hexadecimal " + "equivalent = " + hexaDecimal(s)); } } } // Driver code public static void main(String[] args) { // Initializing graph in the // form of adjacency list @SuppressWarnings("unchecked") List<List<Integer>> graph = new ArrayList(); for(int i = 0; i < 1001; i++) graph.add(new ArrayList<Integer>()); // Defining the number // of edges and vertices int E = 4, V = 7; // Assigning the values for each // vertex of the undirected graph List<Integer> values = new ArrayList<Integer>(); values.add(0); values.add(1); values.add(1); values.add(1); values.add(0); values.add(1); values.add(1); // Constructing the undirected graph graph.get(1).add(2); graph.get(2).add(1); graph.get(3).add(4); graph.get(4).add(3); graph.get(4).add(5); graph.get(5).add(4); graph.get(6).add(5); graph.get(5).add(6); graph.get(6).add(7); graph.get(7).add(6); hexValue(graph, V, values); } } // This code is contributed by jithin
Python3
# Python3 implementation to find # hexadecimal equivalents of # all connected components # Function to traverse the undirected # graph using the Depth first traversal def depthFirst(v, graph, visited, storeChain): # Marking the visited # vertex as true visited[v] = True # Store the connected chain storeChain.append(v) for i in graph[v] : if not visited[i] : # Recursive call to # the DFS algorithm depthFirst(i, graph, visited, storeChain) # Function to create map between binary # number and its equivalent hexadecimal def createMap(um): um["0000"] = '0' um["0001"] = '1' um["0010"] = '2' um["0011"] = '3' um["0100"] = '4' um["0101"] = '5' um["0110"] = '6' um["0111"] = '7' um["1000"] = '8' um["1001"] = '9' um["1010"] = 'A' um["1011"] = 'B' um["1100"] = 'C' um["1101"] = 'D' um["1110"] = 'E' um["1111"] = 'F' # Function to return hexadecimal # equivalent of each connected # component def hexaDecimal(bn): l = len(bn) t = bn.find('.') # Length of string before '.' len_left = t if t != -1 else l # Add min 0's in the beginning # to make left substring length # divisible by 4 for i in range(1,((4 - len_left % 4) % 4)+1): bn = '0' + bn # If decimal point exists if (t != -1) : # Length of string after '.' len_right = l - len_left - 1 # Add min 0's in the end to # make right substring length # divisible by 4 for i in range(1,((4 - len_right % 4) % 4)+1): bn = bn + '0' # Create map between binary # and its equivalent hx code bin_hex_map=dict() createMap(bin_hex_map) i = 0 hx = "" while (True) : # Extract from left, # substring of size 4 and add # its hx code hx += bin_hex_map[bn[i: i+4]] i += 4 if (i == len(bn)): break # If '.' is encountered add it # to result if (bn[i] == '.') : hx += '.' i+=1 # Required hexadecimal number return hx # Function to find the hexadecimal # equivalents of all connected # components def hexValue(graph, vertices, values): # Initializing boolean array # to mark visited vertices visited=[False]*10001 # Following loop invokes # DFS algorithm for i in range(1,vertices+1): if not visited[i]: # Variable to hold # temporary length sizeChain=0 # Container to store # each chain storeChain=[] # DFS algorithm depthFirst(i, graph, visited, storeChain) # Variable to hold each # chain size sizeChain = len(storeChain) # Container to store # values of vertices of # individual chains chainValues=[-1]*(sizeChain + 1) # Storing the values of # each chain for i in range(sizeChain): temp = values[storeChain[i] - 1] chainValues[i] = temp # Printing binary chain print("Chain =",end=" ") for i in range(sizeChain) : print(chainValues[i],end=" ") print("\t",end="") # Converting the array # with vertex # values to a binary string s=[] for i in range(sizeChain): s.append(str(chainValues[i])) s=''.join(s) # Printing the hexadecimal # values print("Hexadecimal equivalent =",hexaDecimal(s)) # Driver Program if __name__=='__main__': # Initializing graph in the # form of adjacency list graph=[[] for _ in range(1001)] # Defining the number of # edges and vertices E = 4 V = 7 # Assigning the values # for each vertex of the # undirected graph values=[] values.append(0) values.append(1) values.append(1) values.append(1) values.append(0) values.append(1) values.append(1) # Constructing the # undirected graph graph[1].append(2) graph[2].append(1) graph[3].append(4) graph[4].append(3) graph[4].append(5) graph[5].append(4) graph[6].append(5) graph[5].append(6) graph[6].append(7) graph[7].append(6) hexValue(graph, V, values)
Javascript
// JavaScript implementation to find // hexadecimal equivalents of // all connected components // Function to traverse the undirected // graph using the Depth first traversal function depthFirst(v, graph, visited, storeChain) { // Marking the visited // vertex as true visited[v] = true; // Store the connected chain storeChain.push(v); for (const i of graph[v]) { if (!visited[i]) { // Recursive call to // the DFS algorithm depthFirst(i, graph, visited, storeChain); } } } // Function to create map between binary // number and its equivalent hexadecimal function createMap(um) { um["0000"] = '0'; um["0001"] = '1'; um["0010"] = '2'; um["0011"] = '3'; um["0100"] = '4'; um["0101"] = '5'; um["0110"] = '6'; um["0111"] = '7'; um["1000"] = '8'; um["1001"] = '9'; um["1010"] = 'A'; um["1011"] = 'B'; um["1100"] = 'C'; um["1101"] = 'D'; um["1110"] = 'E'; um["1111"] = 'F'; } // Function to return hexadecimal // equivalent of each connected // component function hexaDecimal(bn) { var l = bn.length; var t = bn.indexOf('.'); // Length of string before '.' if (t != -1) len_left = t; else len_left = l; // Add min 0's in the beginning // to make left substring length // divisible by 4 for (var i = 1; i < ((4 - len_left % 4) % 4)+1; i++) bn = '0' + bn; // If decimal point exists if (t != -1) { // Length of string after '.' len_right = l - len_left - 1; // Add min 0's in the end to // make right substring length // divisible by 4 for (var i = 1; i < ((4 - len_right % 4) % 4)+1; i++) bn = bn + '0'; } // Create map between binary // and its equivalent hx code var bin_hex_map= {}; createMap(bin_hex_map); i = 0; hx = ""; while (true) { // Extract from left, // substring of size 4 and add // its hx code hx += bin_hex_map[bn.substring(i, i+4)]; i += 4; if (i == bn.length) break; // If '.' is encountered add it // to result if (bn[i] == '.') { hx += '.'; i+=1; } } // Required hexadecimal number return hx; } // Function to find the hexadecimal // equivalents of all connected // components function hexValue(graph, vertices, values) { // Initializing boolean array // to mark visited vertices var visited= new Array(10001).fill(false); // Following loop invokes // DFS algorithm for (var i = 1; i <= vertices; i++) { if (!visited[i]) { //Variable to hold // temporary length var sizeChain=0; //Container to store // each chain var storeChain=[]; //DFS algorithm depthFirst(i, graph, visited, storeChain); // Variable to hold each // chain size var sizeChain = storeChain.length; // Container to store // values of vertices of // individual chains var chainValues = new Array(sizeChain + 1).fill(-1); // Storing the values of // each chain for (var i = 0; i < sizeChain; i++) { var temp = values[storeChain[i] - 1]; chainValues[i] = temp; } // Printing binary chain process.stdout.write("Chain = "); for (var i = 0; i < sizeChain; i++) process.stdout.write(chainValues[i] + " "); process.stdout.write("\t"); // Converting the array // with vertex // values to a binary string var s=[]; for (var i = 0; i < sizeChain; i++) s.push(chainValues[i].toString()); s = s.join(''); //Printing the hexadecimal // values console.log("Hexadecimal equivalent =",hexaDecimal(s)); } } } // Driver Program //Initializing graph in the // form of adjacency var graph = []; for (var i = 0; i < 10001; i ++) graph.push([]); // Defining the number of // edges and vertices var E = 4; var V = 7; // Assigning the values // for each vertex of the // undirected graph var values=[]; values.push(0); values.push(1); values.push(1); values.push(1); values.push(0); values.push(1); values.push(1); // Constructing the // undirected graph graph[1].push(2); graph[2].push(1); graph[3].push(4); graph[4].push(3); graph[4].push(5); graph[5].push(4); graph[6].push(5); graph[5].push(6); graph[6].push(7); graph[7].push(6); hexValue(graph, V, values); //this code is contributed by phasing17
Chain = 0 1 Hexadecimal equivalent = 1 Chain = 1 1 0 1 1 Hexadecimal equivalent = 1B
Complejidad temporal: O(V 2 )
El algoritmo DFS requiere una complejidad O(V + E), donde V, E son los vértices y las aristas del gráfico no dirigido. Además, el equivalente hexadecimal se obtiene en cada iteración, lo que requiere una complejidad O(V) adicional para calcular. Por lo tanto, la complejidad general es O(V 2 ) .
Espacio Auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por PratikBasu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA