WikiGalaxy
Graph Representation
Adjacency Matrix
The adjacency matrix is a 2D array of size VxV where V is the number of vertices in a graph. Each cell in the matrix indicates whether there is an edge between two vertices.
int[][] adjacencyMatrix = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
// 0 - No edge, 1 - Edge exists
Adjacency List
An adjacency list represents a graph as an array of lists. The index of the array represents a vertex, and each element in its list represents the other vertices that are connected to it.
List> adjacencyList = new ArrayList<>();
for (int i = 0; i < V; i++) {
adjacencyList.add(new ArrayList<>());
}
adjacencyList.get(0).add(1);
adjacencyList.get(0).add(3);
// Add edges similarly
Edge List
An edge list is a collection of edges, where each edge is represented by a pair of vertices. This representation is efficient for storing sparse graphs.
List edgeList = new ArrayList<>();
edgeList.add(new int[]{0, 1});
edgeList.add(new int[]{0, 3});
// Add more edges similarly
Incidence Matrix
The incidence matrix is a matrix of size VxE where V is the number of vertices and E is the number of edges. Each row represents a vertex and each column represents an edge.
int[][] incidenceMatrix = {
{1, 0, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 1}
};
// 1 indicates vertex is part of the edge
Weighted Graph using Adjacency Matrix
A weighted graph can be represented using an adjacency matrix where the value at matrix[i][j] is the weight of the edge from vertex i to vertex j.
int[][] weightedMatrix = {
{0, 2, 0, 1},
{2, 0, 3, 0},
{0, 3, 0, 4},
{1, 0, 4, 0}
};
// Non-zero values indicate edge weights
Weighted Graph using Adjacency List
In a weighted graph using an adjacency list, each node points to a list of pairs, where each pair contains a neighbor and the weight of the edge connecting them.
List>> weightedAdjList = new ArrayList<>();
for (int i = 0; i < V; i++) {
weightedAdjList.add(new ArrayList<>());
}
weightedAdjList.get(0).add(new Pair<>(1, 2));
weightedAdjList.get(0).add(new Pair<>(3, 1));
// Add more weighted edges similarly
Directed Graph using Adjacency List
A directed graph can be represented using an adjacency list, where each list contains only the vertices directed out from the vertex represented by the index.
List> directedAdjList = new ArrayList<>();
for (int i = 0; i < V; i++) {
directedAdjList.add(new ArrayList<>());
}
directedAdjList.get(0).add(1);
directedAdjList.get(0).add(3);
// Add more directed edges similarly
Undirected Graph using Adjacency List
In an undirected graph, the adjacency list contains each vertex twice - once for each direction of the edge.
List> undirectedAdjList = new ArrayList<>();
for (int i = 0; i < V; i++) {
undirectedAdjList.add(new ArrayList<>());
}
undirectedAdjList.get(0).add(1);
undirectedAdjList.get(1).add(0);
// Add more undirected edges similarly
Graph using Edge List with Weights
A graph with weights can be represented using an edge list where each edge is a triplet containing two vertices and the weight of the edge.
List weightedEdgeList = new ArrayList<>();
weightedEdgeList.add(new int[]{0, 1, 2});
weightedEdgeList.add(new int[]{0, 3, 1});
// Add more weighted edges similarly
Graph using Adjacency Set
In an adjacency set representation, each vertex maintains a set of adjacent vertices, which is efficient for checking the presence of a specific edge.
Map> adjacencySet = new HashMap<>();
for (int i = 0; i < V; i++) {
adjacencySet.put(i, new HashSet<>());
}
adjacencySet.get(0).add(1);
adjacencySet.get(0).add(3);
// Add more edges similarly
