Prerrequisito : Gráfico y sus representaciones
En este artículo, discutiremos la representación de la lista de adyacencia de Graph usando ArrayList en Java.
A continuación se muestra la representación de la lista de adyacencia del gráfico anterior.
La idea es usar ArrayList de ArrayLists .
// Java code to demonstrate Graph representation
// using ArrayList in Java
import java.util.*;
class Test {
static void addEdge(ArrayList<ArrayList<Integer> > adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
static void printAdjacencyList(ArrayList<ArrayList<Integer> > adj)
{
for (int i = 0; i < adj.size(); i++) {
System.out.println("Adjacency list of " + i);
for (int j = 0; j < adj.get(i).size(); j++) {
System.out.print(adj.get(i).get(j) + " ");
}
System.out.println();
}
}
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);
printAdjacencyList(adj);
}
}
Producción:
Adjacency list of 0 1 4 Adjacency list of 1 0 2 3 4 Adjacency list of 2 1 3 Adjacency list of 3 1 2 4 Adjacency list of 4 0 1 3
Implementación similar usando una clase separada para Graph.
// Java code to demonstrate Graph representation
// using ArrayList in Java
import java.util.*;
class Graph {
ArrayList<ArrayList<Integer> > adj;
int V;
Graph(int v)
{
V = v;
adj = new ArrayList<ArrayList<Integer> >(V);
for (int i = 0; i < V; i++)
adj.add(new ArrayList<Integer>());
}
void addEdge(int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
void printAdjacencyList()
{
for (int i = 0; i < adj.size(); i++) {
System.out.println("Adjacency list of " + i);
for (int j = 0; j < adj.get(i).size(); j++) {
System.out.print(adj.get(i).get(j) + " ");
}
System.out.println();
}
}
}
class Test {
public static void main(String[] args)
{
// Creating a graph with 5 vertices
int V = 5;
Graph g = new Graph(V);
// Adding edges one by one.
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printAdjacencyList();
}
}
Producción:
Adjacency list of 0 1 4 Adjacency list of 1 0 2 3 4 Adjacency list of 2 1 3 Adjacency list of 3 1 2 4 Adjacency list of 4 0 1 3