Graphs can be represented in various ways in code, depending on the requirements and use cases. Each representation has its own advantages and disadvantages, and understanding them is essential for efficiently working with graphs.
One commonly used representation of a graph is the adjacency matrix. In this representation, a matrix of size V x V is used, where V is the number of vertices in the graph. The value at matrix position (i, j) represents the weight of the edge between vertices i and j. If there is no edge between the vertices, the value at that position is usually set to infinity or a special value to indicate the absence of an edge.
1// Adjacency Matrix representation of a graph
2
3class Main {
4 public static void main(String[] args) {
5 int V = 5; // Number of vertices
6 int[][] adjacencyMatrix = new int[V][V];
7
8 // Add edges
9 adjacencyMatrix[0][1] = 1;
10 adjacencyMatrix[1][2] = 1;
11 adjacencyMatrix[2][3] = 1;
12 adjacencyMatrix[3][4] = 1;
13 adjacencyMatrix[4][0] = 1;
14
15 // Print adjacency matrix
16 for (int i = 0; i < V; i++) {
17 for (int j = 0; j < V; j++) {
18 System.out.print(adjacencyMatrix[i][j] + " ");
19 }
20 System.out.println();
21 }
22 }
23}Another common representation is the adjacency list. In this representation, each vertex in the graph is associated with a list of its adjacent vertices. This representation is more memory-efficient when the graph has a large number of vertices but relatively fewer edges.
1// Adjacency List representation of a graph
2
3class Graph {
4 int V;
5 ArrayList<ArrayList<Integer>> adjacencyList;
6
7 public Graph(int v) {
8 V = v;
9 adjacencyList = new ArrayList<>(V);
10
11 for (int i = 0; i < V; i++) {
12 adjacencyList.add(new ArrayList<>());
13 }
14 }
15
16 public void addEdge(int src, int dest) {
17 adjacencyList.get(src).add(dest);
18 adjacencyList.get(dest).add(src); // Uncomment this line for undirected graph
19 }
20
21 public void printGraph() {
22 for (int i = 0; i < V; i++) {
23 System.out.print(i + " -> ");
24 for (int j = 0; j < adjacencyList.get(i).size(); j++) {
25 System.out.print(adjacencyList.get(i).get(j) + " ");
26 }
27 System.out.println();
28 }
29 }
30}
31
32// Usage
33
34class Main {
35 public static void main(String[] args) {
36 int V = 5; // Number of vertices
37 Graph graph = new Graph(V);
38
39 // Add edges
40 graph.addEdge(0, 1);
41 graph.addEdge(1, 2);
42 graph.addEdge(2, 3);
43 graph.addEdge(3, 4);
44 graph.addEdge(4, 0);
45
46 // Print adjacency list
47 graph.printGraph();
48 }
49}These are just a few examples of how graphs can be represented in code. Depending on the specific use case, other representations such as edge list, incidence matrix, or adjacency set might be more suitable and efficient.