Imprimir lista de adyacencia para un gráfico dirigido

Una lista de adyacencia se utiliza para representar gráficos. Aquí, para cada vértice en el gráfico, tenemos una lista de todos los otros vértices a los que el vértice en particular tiene una arista.

Problema: Dada la lista de adyacencia y el número de vértices y aristas de un gráfico, la tarea es representar la lista de adyacencia para un gráfico dirigido.

Ejemplos:

Entrada: V = 3, bordes[][]= {{0, 1}, {1, 2} {2, 0}}
 

Salida:   0 -> 1
                1 -> 2
                2 -> 0
Explicación: 
La salida representa la lista de adyacencia para el gráfico dado. 

Entrada: V = 4, aristas[][] = {{0, 1}, {1, 2}, {1, 3}, {2, 3}, {3, 0}}
 

Salida:   0 -> 1
                1 -> 2 3
                2 -> 3
                3 -> 0
Explicación: 
La salida representa la lista de adyacencia para el gráfico dado. 

 

Enfoque (usando STL ): la idea principal es representar el gráfico como una array de vectores de modo que cada vector represente la lista de adyacencia de un solo vértice. Usando STL, el código se vuelve más simple y más fácil de entender. 

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to add edges
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
}
 
// Function to print adjacency list
void adjacencylist(vector<int> adj[], int V)
{
    for (int i = 0; i < V; i++) {
        cout << i << "->";
        for (int& x : adj[i]) {
            cout << x << " ";
        }
        cout << endl;
    }
}
 
// Function to initialize the adjacency list
// of the given graph
void initGraph(int V, int edges[3][2], int noOfEdges)
{
    // To represent graph as adjacency list
    vector<int> adj[V];
 
    // Traverse edges array and make edges
    for (int i = 0; i < noOfEdges; i++) {
 
        // Function call to make an edge
        addEdge(adj, edges[i][0], edges[i][1]);
    }
 
    // Function Call to print adjacency list
    adjacencylist(adj, V);
}
 
// Driver Code
int main()
{
    // Given vertices
    int V = 3;
 
    // Given edges
    int edges[3][2] = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
 
    int noOfEdges = 3;
 
    // Function Call
    initGraph(V, edges, noOfEdges);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
  // Function to add edges
  static void addEdge(Vector<Integer> adj[], int u, int v)
  {
    adj[u].add(v);
  }
 
  // Function to print adjacency list
  static void adjacencylist(Vector<Integer> adj[], int V)
  {
    for (int i = 0; i < V; i++) {
      System.out.print(i+ "->");
      for (int x : adj[i]) {
        System.out.print(x+ " ");
      }
      System.out.println();
    }
  }
 
  // Function to initialize the adjacency list
  // of the given graph
  static void initGraph(int V, int edges[][], int noOfEdges)
  {
 
    // To represent graph as adjacency list
    @SuppressWarnings("unchecked")
    Vector<Integer> adj[] = new Vector[3];
    for(int i =0;i<adj.length;i++) {
      adj[i] = new Vector<>();
    }
    // Traverse edges array and make edges
    for (int i = 0; i < noOfEdges; i++) {
 
      // Function call to make an edge
      addEdge(adj, edges[i][0], edges[i][1]);
    }
 
    // Function Call to print adjacency list
    adjacencylist(adj, V);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Given vertices
    int V = 3;
 
    // Given edges
    int edges[][] = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
 
    int noOfEdges = 3;
 
    // Function Call
    initGraph(V, edges, noOfEdges);
 
  }
}
 
// This code is contributed by gauravrajput1

Python3

# Python program for the above approach
 
# Function to add edges
def addEdge(adj, u, v):
    adj[u].append(v)
   
# Function to print adjacency list
def adjacencylist(adj, V):
     
    for i in range (0, V):
        print(i, "->", end="")
         
        for x in  adj[i]:
            print(x , " ", end="")
       
        print()
     
# Function to initialize the adjacency list
# of the given graph
def initGraph(V, edges, noOfEdges):
 
    adj = [0]* 3
     
    for i in range(0, len(adj)):
        adj[i] = []
   
    # Traverse edges array and make edges
    for i in range(0, noOfEdges) :
 
         # Function call to make an edge
        addEdge(adj, edges[i][0], edges[i][1])
     
 
    # Function Call to print adjacency list
    adjacencylist(adj, V)
   
# Driver Code
   
# Given vertices
V = 3
 
# Given edges
edges =  [[0, 1 ],  [1, 2 ],  [2, 0 ]]
 
noOfEdges = 3;
 
# Function Call
initGraph(V, edges, noOfEdges)
 
# This code is contributed by AR_Gaurav

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to add edges
  static void addEdge(List<int> []adj, int u, int v)
  {
    adj[u].Add(v);
  }
 
  // Function to print adjacency list
  static void adjacencylist(List<int> []adj, int V)
  {
    for (int i = 0; i < V; i++) {
      Console.Write(i+ "->");
      foreach (int x in adj[i]) {
        Console.Write(x+ " ");
      }
      Console.WriteLine();
    }
  }
 
  // Function to initialize the adjacency list
  // of the given graph
  static void initGraph(int V, int [,]edges, int noOfEdges)
  {
 
    // To represent graph as adjacency list  
    List<int> []adj = new List<int>[3];
    for(int i = 0; i < adj.Length; i++) {
      adj[i] = new List<int>();
    }
     
    // Traverse edges array and make edges
    for (int i = 0; i < noOfEdges; i++) {
 
      // Function call to make an edge
      addEdge(adj, edges[i,0], edges[i,1]);
    }
 
    // Function Call to print adjacency list
    adjacencylist(adj, V);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    // Given vertices
    int V = 3;
 
    // Given edges
    int [,]edges = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
 
    int noOfEdges = 3;
 
    // Function Call
    initGraph(V, edges, noOfEdges);
 
  }
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// javascript program for the above approach
 
    // Function to add edges
    function addEdge( adj , u , v) {
        adj[u].push(v);
    }
 
    // Function to print adjacency list
    function adjacencylist(adj , V) {
        for (var i = 0; i < V; i++) {
            document.write(i + "->");
            for (var x of adj[i]) {
                document.write(x + " ");
            }
            document.write("<br/>");
        }
    }
 
    // Function to initialize the adjacency list
    // of the given graph
    function initGraph(V , edges , noOfEdges) {
 
        // To represent graph as adjacency list
 
        var adj = Array(3);
        for (var i = 0; i < adj.length; i++) {
            adj[i] = Array();
        }
        // Traverse edges array and make edges
        for (i = 0; i < noOfEdges; i++) {
 
            // Function call to make an edge
            addEdge(adj, edges[i][0], edges[i][1]);
        }
 
        // Function Call to print adjacency list
        adjacencylist(adj, V);
    }
 
    // Driver Code
     
        // Given vertices
        var V = 3;
 
        // Given edges
        var edges = [ [ 0, 1 ], [ 1, 2 ], [ 2, 0 ]];
 
        var noOfEdges = 3;
 
        // Function Call
        initGraph(V, edges, noOfEdges);
 
 
// This code is contributed by gauravrajput1
</script>
Producción: 

0->1 
1->2 
2->0

 

Publicación traducida automáticamente

Artículo escrito por maitreyeepaliwal 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 *