Programa Java para Representar Gráficos Usando Lista Vinculada

Las estructuras de datos se dividen en dos categorías Estructuras de datos lineales y estructuras de datos no lineales. La principal desventaja de la estructura de datos lineales es que no podemos organizar los datos de la estructura de datos lineales de manera jerárquica, por eso en el campo de la informática usamos estructuras de datos no lineales. La estructura de datos no lineales más utilizada es Graphs and Trees, ambas estructuras de datos se pueden implementar utilizando estructuras de datos lineales. En este artículo, discutiremos cómo representar gráficos usando la lista enlazada.

Los gráficos consisten en un conjunto finito de vértices (o Nodes) y un conjunto de aristas que conectan un par de Nodes. Los gráficos se representan de dos maneras diferentes. Un método utiliza la representación de lista de adyacencia y el segundo es la representación de array de adyacencia. La representación de lista de adyacencia se usa principalmente debido a la asignación de memoria dinámica mediante la representación de lista.

Los gráficos son de dos tipos:

• Gráficos dirigidos: en esta disposición de gráficos, cada Node está dirigido a un vértice y se denomina gráficos dirigidos.
• Gráficos no dirigidos: en esta disposición de gráficos, dos Nodes están conectados mediante un vértice bidireccional que se denomina gráficos no dirigidos.

Representación de gráficos no dirigidos: el número máximo de un vértice en los gráficos no dirigidos es n*(n-1) donde n es el número total de Nodes presentes en los gráficos no dirigidos.

La representación LinkedList de gráficos no dirigidos es la siguiente:

 En gráficos no dirigidos, dos Nodes están conectados en vértice bidireccional. Podemos usar las colecciones Array List y Linked List para representar los gráficos no dirigidos. En Linked List, la manipulación de los datos es más rápida que Array List porque Array List usa internamente la array dinámica para almacenar los datos, mientras que Linked List usa Doubly Linked List que es más rápido en la operación de manipulación pero no en el acceso a los elementos.

Implementación: aquí discutiremos ambos tipos de gráficos para implementar lo mismo. 

Ejemplo 1

// Java Program to Implement the Unidirectional Graph
// Using Linked List
 
// Importing required classes from packages
import java.io.*;
import java.util.*;
 
// Main class
class GFG {
 
    // Method 1
    // To make pair of nodes
    static void
    addEdge(LinkedList<LinkedList<Integer> > Adj, int u,
            int v)
    {
        // Creating bi-directional vertex
        Adj.get(u).add(v);
        Adj.get(v).add(u);
    }
 
    // Method 2
    // To print the adjacency list
    static void
    printadjacencylist(LinkedList<LinkedList<Integer> > adj)
    {
        for (int i = 0; i < adj.size(); ++i) {
 
            // Printing the head
            System.out.print(i + "->");
 
            for (int v : adj.get(i)) {
                // Printing the nodes
                System.out.print(v + " ");
            }
 
            // Now a new lin eis needed
            System.out.println();
        }
    }
 
    // Method 3
    // Main driver method
    public static void main(String[] args)
    {
 
        // Creating vertex
        int V = 5;
 
        LinkedList<LinkedList<Integer> > adj
            = new LinkedList<LinkedList<Integer> >();
        for (int i = 0; i < V; ++i) {
            adj.add(new LinkedList<Integer>());
        }
 
        // Inserting nodes
        // Custom input node elements
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 4);
        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 1, 4);
        addEdge(adj, 2, 3);
        addEdge(adj, 3, 4);
 
        // Printing adjacency list
        printadjacencylist(adj);
    }
}

0->1 4 
1->0 2 3 4 
2->1 3 
3->1 2 4 
4->0 1 3 

Ahora saltemos al siguiente tipo de gráficos que es nuestra representación de gráficos dirigidos usando Lista enlazada . En grafos dirigidos, dos Nodes están conectados en un vértice unidireccional.

Ejemplo 2

// Java Program to Implement the Directed Graph
// Using Linked List
 
// Importing standard classes from respectively packages
import java.io.*;
import java.util.*;
 
// Main class
class GFG {
 
    // Method 1
    // To make pair of nodes
    static void
    addEdge(LinkedList<LinkedList<Integer> > Adj, int u,
            int v)
    {
        // Creating unidirectional vertex
        Adj.get(u).add(v);
    }
 
    // Method 2
    // To print the adjacency List
    static void
    printadjacencylist(LinkedList<LinkedList<Integer> > adj)
    {
        for (int i = 0; i < adj.size(); ++i) {
 
            // Printing the head
            if (adj.get(i).size() != 0) {
                System.out.print(i + "->");
                for (int v : adj.get(i)) {
 
                    // Printing the nodes
                    System.out.print(v + " ");
                }
 
                // A new line is needed
                System.out.println();
            }
        }
    }
 
    // Method 3
    // Main driver method
    public static void main(String[] args)
    {
        // Creating vertex
        int V = 5;
 
        LinkedList<LinkedList<Integer> > adj
            = new LinkedList<LinkedList<Integer> >();
 
        for (int i = 0; i < V; ++i) {
            adj.add(new LinkedList<Integer>());
        }
        // Inserting nodes
        // Custom input elements
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 4);
        addEdge(adj, 1, 2);
 
        // Printing adjacency List
        printadjacencylist(adj);
    }
}

0->1 4 
1->2