Equivalentes hexadecimales en gráfico de valores binarios

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 = 1

Entrada: 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
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *