Un gráfico es una estructura de datos que consta de los siguientes dos componentes:
1. Un conjunto finito de vértices también llamados Nodes.
2. Un conjunto finito de pares ordenados de la forma (u, v) llamado arista. El par está ordenado porque (u, v) no es lo mismo que (v, u) en el caso de un grafo dirigido (di-grafo). El par de la forma (u, v) indica que hay una arista desde el vértice u hasta el vértice v. Las aristas pueden contener peso/valor/costo.
Los gráficos se utilizan para representar muchas aplicaciones de la vida real: Los gráficos se utilizan para representar redes. Las redes pueden incluir trayectos en una ciudad o red telefónica o red de circuitos. Los gráficos también se utilizan en redes sociales como linkedIn, Facebook. Por ejemplo, en Facebook, cada persona se representa con un vértice (o Node). Cada Node es una estructura y contiene información como identificación de persona, nombre, sexo y ubicación. Ver esto para más aplicaciones de gráfico.
El siguiente es un ejemplo de un gráfico no dirigido con 5 vértices.
Las dos siguientes son las representaciones más utilizadas de un gráfico.
1. Array de Adyacencia
2. Lista de Adyacencia
Hay otras representaciones también como Array de Incidencia y Lista de Incidencia. La elección de la representación gráfica es específica de la situación. Depende totalmente del tipo de operaciones a realizar y de la facilidad de uso.
Array de adyacencia:
La array de adyacencia es una array 2D de tamaño V x V donde V es el número de vértices en un gráfico. Sea la array 2D adj[][], una ranura adj[i][j] = 1 indica que hay una arista desde el vértice i hasta el vértice j. La array de adyacencia para el gráfico no dirigido siempre es simétrica. La array de adyacencia también se utiliza para representar gráficos ponderados. Si adj[i][j] = w, entonces hay una arista del vértice i al vértice j con peso w.
La array de adyacencia para el gráfico de ejemplo anterior es:
Pros: la representación es más fácil de implementar y seguir. Eliminar un borde lleva O(1) tiempo. Consultas como si hay un borde desde el vértice ‘u’ hasta el vértice ‘v’ son eficientes y se pueden realizar O(1).
Contras: consume más espacio O(V^2). Incluso si el gráfico es escaso (contiene menos aristas), consume el mismo espacio. Agregar un vértice es O(V^2) tiempo. Calcular todos los vecinos de un vértice lleva tiempo O(V) (no eficiente).
Consulte esto para ver una implementación de Python de muestra de la array de adyacencia.
Implementación de toma de entrada para array de adyacencia
C++
#include <iostream>
using namespace std;
int main()
{
// n is the number of vertices
// m is the number of edges
int n, m;
cin >> n >> m ;
int adjMat[n + 1][n + 1];
for(int i = 0; i < m; i++){
int u , v ;
cin >> u >> v ;
adjMat[u][v] = 1 ;
adjMat[v][u] = 1 ;
}
return 0;
}
Lista de adyacencia:
se utiliza una array de listas. El tamaño de la array es igual al número de vértices. Deje que la array sea una array []. Una array de entrada[i] representa la lista de vértices adyacentes al i -ésimo vértice. Esta representación también se puede utilizar para representar un gráfico ponderado. Los pesos de los bordes se pueden representar como listas de pares. A continuación se muestra la representación de la lista de adyacencia del gráfico anterior.
Tenga en cuenta que en la implementación a continuación, usamos arrays dinámicas (vector en C++/ArrayList en Java) para representar listas de adyacencia en lugar de la lista vinculada. La implementación del vector tiene ventajas de compatibilidad con caché.
C++
// A simple representation of graph using STL
#include <bits/stdc++.h>
using namespace std;
// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex " << v
<< "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
// Driver code
int main()
{
int V = 5;
vector<int> adj[V];
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);
printGraph(adj, V);
return 0;
}
C
// A C Program to demonstrate adjacency list
// representation of graphs
#include <stdio.h>
#include <stdlib.h>
// A structure to represent an adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// A structure to represent an adjacency list
struct AdjList {
struct AdjListNode* head;
};
// A structure to represent a graph. A graph
// is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
struct Graph {
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode
= (struct AdjListNode*)malloc(
sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph
= (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of
// array will be V
graph->array = (struct AdjList*)malloc(
V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by
// making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is
// added to the adjacency list of src. The node
// is added at the beginning
struct AdjListNode* check = NULL;
struct AdjListNode* newNode = newAdjListNode(dest);
if (graph->array[src].head == NULL) {
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
else {
check = graph->array[src].head;
while (check->next != NULL) {
check = check->next;
}
// graph->array[src].head = newNode;
check->next = newNode;
}
// Since graph is undirected, add an edge from
// dest to src also
newNode = newAdjListNode(src);
if (graph->array[dest].head == NULL) {
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
else {
check = graph->array[dest].head;
while (check->next != NULL) {
check = check->next;
}
check->next = newNode;
}
// newNode = newAdjListNode(src);
// newNode->next = graph->array[dest].head;
// graph->array[dest].head = newNode;
}
// A utility function to print the adjacency list
// representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v) {
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// print the adjacency list representation of the above
// graph
printGraph(graph);
return 0;
}
Java
// Java code to demonstrate Graph representation
// using ArrayList in Java
import java.util.*;
class Graph {
// A utility function to add an edge in an
// undirected graph
static void addEdge(ArrayList<ArrayList<Integer> > adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// A utility function to print the adjacency list
// representation of graph
static void
printGraph(ArrayList<ArrayList<Integer> > adj)
{
for (int i = 0; i < adj.size(); i++) {
System.out.println("\nAdjacency list of vertex"
+ i);
System.out.print("head");
for (int j = 0; j < adj.get(i).size(); j++) {
System.out.print(" -> "
+ adj.get(i).get(j));
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Creating a graph with 5 vertices
int V = 5;
ArrayList<ArrayList<Integer> > adj
= new ArrayList<ArrayList<Integer> >(V);
for (int i = 0; i < V; i++)
adj.add(new ArrayList<Integer>());
// Adding edges one by one
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);
printGraph(adj);
}
}
Python3
"""
A Python program to demonstrate the adjacency
list representation of the graph
"""
# A class to represent the adjacency list of the node
class AdjNode:
def __init__(self, data):
self.vertex = data
self.next = None
# A class to represent a graph. A graph
# is the list of the adjacency lists.
# Size of the array will be the no. of the
# vertices "V"
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [None] * self.V
# Function to add an edge in an undirected graph
def add_edge(self, src, dest):
# Adding the node to the source node
node = AdjNode(dest)
node.next = self.graph[src]
self.graph[src] = node
# Adding the source node to the destination as
# it is the undirected graph
node = AdjNode(src)
node.next = self.graph[dest]
self.graph[dest] = node
# Function to print the graph
def print_graph(self):
for i in range(self.V):
print("Adjacency list of vertex {}\n head".format(i), end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")
# Driver program to the above graph class
if __name__ == "__main__":
V = 5
graph = Graph(V)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
graph.print_graph()
# This code is contributed by Kanav Malhotra
C#
// C# code to demonstrate Graph representation
// using LinkedList in C#
using System;
using System.Collections.Generic;
class Graph {
// A utility function to add an edge in an
// undirected graph
static void addEdge(LinkedList<int>[] adj, int u, int v)
{
adj[u].AddLast(v);
adj[v].AddLast(u);
}
// A utility function to print the adjacency list
// representation of graph
static void printGraph(LinkedList<int>[] adj)
{
for (int i = 0; i < adj.Length; i++) {
Console.WriteLine("\nAdjacency list of vertex "
+ i);
Console.Write("head");
foreach(var item in adj[i])
{
Console.Write(" -> " + item);
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
// Creating a graph with 5 vertices
int V = 5;
LinkedList<int>[] adj = new LinkedList<int>[ V ];
for (int i = 0; i < V; i++)
adj[i] = new LinkedList<int>();
// Adding edges one by one
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);
printGraph(adj);
Console.ReadKey();
}
}
// This code is contributed by techno2mahi
Javascript
<script>
// Javascript code to demonstrate Graph representation
// using ArrayList in Java
// A utility function to add an edge in an
// undirected graph
function addEdge(adj,u,v)
{
adj[u].push(v);
adj[v].push(u);
}
// A utility function to print the adjacency list
// representation of graph
function printGraph(adj)
{
for (let i = 0; i < adj.length; i++) {
document.write("<br>Adjacency list of vertex" + i+"<br>");
document.write("head");
for (let j = 0; j < adj[i].length; j++) {
document.write(" -> "+adj[i][j]);
}
document.write("<br>");
}
}
// Driver Code
// Creating a graph with 5 vertices
let V = 5;
let adj= [];
for (let i = 0; i < V; i++)
adj.push([]);
// Adding edges one by one
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);
printGraph(adj);
// This code is contributed by avanitrachhadiya2155
</script>
Adjacency list of vertex 0 head -> 1-> 4 Adjacency list of vertex 1 head -> 0-> 2-> 3-> 4 Adjacency list of vertex 2 head -> 1-> 3 Adjacency list of vertex 3 head -> 1-> 2-> 4 Adjacency list of vertex 4 head -> 0-> 1-> 3
Ventajas: ahorra espacio O(|V|+|E|) . En el peor de los casos, puede haber un número C (V, 2) de aristas en un gráfico, por lo que consume espacio O (V ^ 2). Agregar un vértice es más fácil. Calcular todos los vecinos de un vértice requiere un tiempo óptimo.
Contras: las consultas como si hay un borde desde el vértice u hasta el vértice v no son eficientes y se pueden realizar O(V).
En los problemas de la vida real, los gráficos son escasos (|E| <<|V| 2 ). Es por eso que las listas de adyacencia La estructura de datos se usa comúnmente para almacenar gráficos. La array de adyacencia hará cumplir (|V| 2 ) límite en la complejidad del tiempo para tales algoritmos.
Referencia:
http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29 Publicación
relacionada:
Representación gráfica usando STL para programación competitiva | Conjunto 1 (DFS de no ponderado y no dirigido)
Implementación de gráficos usando STL para programación competitiva | Conjunto 2 (Gráfico ponderado)
Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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