A graph is a data structure consisting of a set of vertices (nodes) and a set of edges that define the relationships between these vertices. Mathematically, a graph G is represented as G = (V, E), where:

• V is a finite, non-empty set of vertices.
• E is a finite set of relationships between vertices. For an undirected graph, an edge is represented as an unordered pair (x, y), meaning the relationship is bidirectional. For a directed graph, an edge is an ordered pair <x, y>, representing a directed connection from vertex x to vertex y.

Key Graph Terminology:

• Vertex (Node): An individual element within a graph. Vertices can be denoted as vi.

• Edge: A connection between two vertices. An edge ek connecting vertices vi and vj can be represented as (vi, vj) for undirected graphs or <vi, vj> for directed graphs.

• Directed vs. Undirected Graphs: In a directed graph, edges have a specific direction (e.g., <x, y> is distinct from <y, x>). In an undirected graph, edges are bidirectional (e.g., (x, y) is the same as (y, x)).

• Complete Graph: An undirected graph with n vertices is complete if every pair of distinct vertices is connected by a unique edge (n*(n-1)/2 edges total). A directed graph is complete if for every pair of distinct vertices, there's an edge in both directions (n*(n-1) edges total).

• Degree of a Vertex: The number of edges incident to a vertex. In directed graphs, this is split into:

  • In-degree: The number of edges pointing towards the vertex.
  • Out-degree: The number of edges originating from the vertex.

  The total degree is the sum of in-degree and out-degree. For undirected graphs, the degree is simply the count of connected edges.

• Path: A sequence of vertices connected by edges.

• Path Length: For unweighted graphs, it's the number of edges in the path. For weighted graphs, it's the sum of the weights of the edges in the path.

• Simple Path: A path where all vertices are distinct.

• Cycle (Circuit): A path that starts and ends at the same vertex.

• Subgraph: A graph formed by a subset of vertices and a subset of edges from a larger graph.

• Connected Graph (Undirected): A graph where there is a path between every pair of vertices.

• Strongly Connected Graph (Directed): A directed graph where for every pair of vertices vi and vj, there exists a path from vi to vj AND a path from vj to vi.

• Spanning Tree: A subgraph that connects all vertices together, without any cycles, and with the minimum possible number of edges (n-1 edges for n vertices).

Graph Storage Structures

Graphs can be stored using two primary methods: the adjacency matrix and the adjacency list. Both methods focus on representing the vertices and their connections.

Adjacency Matrix Representation

An adjacency matrix uses a 2D array to represent the graph. The array's dimensions are determined by the number of vertices. Each cell matrix[i][j] indicates the relationship (or absence thereof) between vertex i and vertex j.

• For unweighted graphs, a value of 1 typically signifies an edge, and 0 signifies no edge.
• For weighted graphs, the cell stores the weight of the edge if one exists; otherwise, it might store infinity or a sentinel value indicating no connection.
• In an undirected graph, the adjacency matrix is symmetric (matrix[i][j] == matrix[j][i]). The sum of elements in row i (or column i) corresponds to the degree of vertex i.
• In a directed graph, the matrix is not necessarily symmetric. The sum of elements in row i represents the out-degree of vertex i, and the sum of elements in column i represents the in-degree.

Advantages: Quick checking of connectivity between two vertices.
Disadvantages: Can be space-inefficient for sparse graphs (many vertices, few edges) due to storing many zeros. Finding paths can be complex.

Implemantation Details (Adjacency Matrix)

A class can be implemented to manage the adjacency matrix. Key components include:

• An array to store vertex identifiers.
• A 2D array (matrix) to store edge information (weights or connection status).
• A boolean flag to indicate if the graph is directed.

The constructor initializes the matrix, often filling it with a value representing infinity (e.g., Integer.MAX_VALUE) to signify no initial connections.

import java.util.Arrays;

public class AdjacencyMatrixGraph {
   private char[] vertices;
   private int[][] adjacencyMatrix;
   private boolean isDirected;
   private static final int INFINITY = Integer.MAX_VALUE;

   public AdjacencyMatrixGraph(int numVertices, boolean directed) {
       if (numVertices <= 0) {
           throw new IllegalArgumentException("Number of vertices must be positive.");
       }
       this.vertices = new char[numVertices];
       this.adjacencyMatrix = new int[numVertices][numVertices];
       this.isDirected = directed;

       // Initialize matrix with INFINITY
       for (int i = 0; i < numVertices; i++) {
           Arrays.fill(this.adjacencyMatrix[i], INFINITY);
           // A vertex is not connected to itself unless explicitly added
           this.adjacencyMatrix[i][i] = 0; // Self-loops often represented by 0 weight
       }
   }

   // Method to populate the vertex array
   public void setVertices(char[] vertexLabels) {
       if (vertexLabels.length != vertices.length) {
           throw new IllegalArgumentException("Number of vertex labels must match the graph size.");
       }
       System.arraycopy(vertexLabels, 0, this.vertices, 0, vertices.length);
   }

   // Get the index of a vertex by its label
   public int getVertexIndex(char label) {
       for (int i = 0; i < vertices.length; i++) {
           if (vertices[i] == label) {
               return i;
           }
       }
       return -1; // Vertex not found
   }

   // Add an edge between two vertices with a given weight
   public void addEdge(char sourceLabel, char destinationLabel, int weight) {
       int sourceIndex = getVertexIndex(sourceLabel);
       int destinationIndex = getVertexIndex(destinationLabel);

       if (sourceIndex == -1 || destinationIndex == -1) {
           throw new IllegalArgumentException("One or both vertices not found.");
       }
       if (weight < 0) {
            throw new IllegalArgumentException("Edge weight cannot be negative for this implementation detail.");
       }


       adjacencyMatrix[sourceIndex][destinationIndex] = weight;
       if (!isDirected) {
           // For undirected graphs, add the edge in both directions
           adjacencyMatrix[destinationIndex][sourceIndex] = weight;
       }
   }

   // Calculate the degree of a vertex
   public int getDegree(char label) {
       int index = getVertexIndex(label);
       if (index == -1) {
           throw new IllegalArgumentException("Vertex not found.");
       }

       int degree = 0;
       // Sum outgoing edges (row sum)
       for (int j = 0; j < vertices.length; j++) {
           if (adjacencyMatrix[index][j] != INFINITY && adjacencyMatrix[index][j] != 0) { // Exclude self-loops if not counted
               degree++;
           }
       }

       if (isDirected) {
           // Sum incoming edges (column sum), excluding the current vertex
           for (int i = 0; i < vertices.length; i++) {
                if (i != index && adjacencyMatrix[i][index] != INFINITY && adjacencyMatrix[i][index] != 0) {
                   degree++;
               }
           }
       }
       // Note: This calculation might need adjustment based on how self-loops are treated.
       // For standard definitions, self-loops usually add 2 to the degree in undirected graphs.
       // This implementation counts an edge once per connection.
       return degree;
   }

   // Print the graph representation
   public void displayGraph() {
       System.out.print("   ");
       for (char vertexLabel : vertices) {
           System.out.print(vertexLabel + " ");
       }
       System.out.println();

       for (int i = 0; i < vertices.length; i++) {
           System.out.print(vertices[i] + " ");
           for (int j = 0; j < vertices.length; j++) {
               if (adjacencyMatrix[i][j] == INFINITY) {
                   System.out.print("∞ ");
               } else {
                   System.out.print(adjacencyMatrix[i][j] + " ");
               }
           }
           System.out.println();
       }
   }

    // Example Usage:
    public static void main(String[] args) {
        // Undirected Graph Example
        AdjacencyMatrixGraph undirectedGraph = new AdjacencyMatrixGraph(4, false);
        undirectedGraph.setVertices(new char[]{'A', 'B', 'C', 'D'});
        undirectedGraph.addEdge('A', 'B', 5);
        undirectedGraph.addEdge('A', 'C', 3);
        undirectedGraph.addEdge('B', 'C', 2);
        undirectedGraph.addEdge('C', 'D', 4);

        System.out.println("Undirected Graph (Adjacency Matrix):");
        undirectedGraph.displayGraph();
        System.out.println("Degree of A: " + undirectedGraph.getDegree('A')); // Expected: 2
        System.out.println("Degree of C: " + undirectedGraph.getDegree('C')); // Expected: 3

        System.out.println("\n---------------------------\n");

        // Directed Graph Example
        AdjacencyMatrixGraph directedGraph = new AdjacencyMatrixGraph(4, true);
        directedGraph.setVertices(new char[]{'X', 'Y', 'Z', 'W'});
        directedGraph.addEdge('X', 'Y', 1);
        directedGraph.addEdge('Y', 'Z', 2);
        directedGraph.addEdge('Z', 'X', 3);
        directedGraph.addEdge('X', 'Z', 4); // Another edge from X

        System.out.println("Directed Graph (Adjacency Matrix):");
        directedGraph.displayGraph();
        System.out.println("Degree of X: " + directedGraph.getDegree('X')); // Expected: 3 (1 out to Y, 1 out to Z, 1 in from Z)
        System.out.println("Degree of Y: " + directedGraph.getDegree('Y')); // Expected: 2 (1 in from X, 1 out to Z)
    }
}
   

Adjacency List Representation

An adjacency list uses an array where each element points to a linked list (or similar structure) of nodes. Each node in the linked list represents an edge originating from the vertex at the corresponding array index.

• Each entry in the main array corresponds to a vertex.
• The linked list at index i contains nodes representing edges starting from vertex i.
• Each node in the linked list typically stores the destination vertex, the edge weight, and a pointer to the next node in the list.

For undirected graphs: If there's an edge between vi and vj, vertex vj will appear in the list for vi, and vi will appear in the list for vj.

For directed graphs: If there's an edge from vi to vj, vj appears only in the list for vi. The number of nodes in the list for vertex vi directly gives its out-degree.

Advantages: More space-efficient for sparse graphs. Traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) are often more efficient.

Disadvantages: Checking connectivity between two arbitrary vertices can take longer (proportional to the degree of the source vertex).

Implemantation Details (Adjacency List)

A common implementation uses an ArrayList where each element is either null or the head of a linked list. A static inner class can define the structure of a node in the linked list.

import java.util.ArrayList;
import java.util.List;

public class AdjacencyListGraph {

   // Represents an edge in the adjacency list
   static class EdgeNode {
       int destinationIndex;
       int weight;
       EdgeNode next;

       public EdgeNode(int destinationIndex, int weight) {
           this.destinationIndex = destinationIndex;
           this.weight = weight;
           this.next = null;
       }
   }

   private char[] vertexLabels;
   private List<edgenode> adjacencyLists; // List of linked lists, one for each vertex
   private boolean isDirected;
   private static final int UNCONNECTED = -1; // Placeholder for no connection in degree calculation

   public AdjacencyListGraph(int numVertices, boolean directed) {
       if (numVertices <= 0) {
           throw new IllegalArgumentException("Number of vertices must be positive.");
       }
       this.vertexLabels = new char[numVertices];
       this.adjacencyLists = new ArrayList<>(numVertices);
       this.isDirected = directed;

       // Initialize each list in the adjacencyLists
       for (int i = 0; i < numVertices; i++) {
           adjacencyLists.add(null); // Initially, each vertex has an empty adjacency list
       }
   }

   // Method to populate the vertex label array
   public void setVertexLabels(char[] labels) {
       if (labels.length != vertexLabels.length) {
           throw new IllegalArgumentException("Number of labels must match the graph size.");
       }
       System.arraycopy(labels, 0, this.vertexLabels, 0, vertexLabels.length);
   }

   // Get the index of a vertex by its label
   public int getVertexIndex(char label) {
       for (int i = 0; i < vertexLabels.length; i++) {
           if (vertexLabels[i] == label) {
               return i;
           }
       }
       return -1; // Vertex not found
   }

   // Helper method to add an edge to the list (used internally)
   private void addEdgeToList(int sourceIndex, int destinationIndex, int weight) {
       // Prevent adding duplicate edges between the same pair of vertices in the same direction
       EdgeNode current = adjacencyLists.get(sourceIndex);
       while (current != null) {
           if (current.destinationIndex == destinationIndex) {
               // Edge already exists, could update weight or ignore
               // For simplicity, we ignore adding duplicates here.
               return;
           }
           current = current.next;
       }

       // Add new edge using head insertion
       EdgeNode newNode = new EdgeNode(destinationIndex, weight);
       newNode.next = adjacencyLists.get(sourceIndex);
       adjacencyLists.set(sourceIndex, newNode);
   }

   // Add an edge between two vertices
   public void addEdge(char sourceLabel, char destinationLabel, int weight) {
       int sourceIndex = getVertexIndex(sourceLabel);
       int destinationIndex = getVertexIndex(destinationLabel);

       if (sourceIndex == -1 || destinationIndex == -1) {
           throw new IllegalArgumentException("One or both vertices not found.");
       }
        if (weight < 0) {
            throw new IllegalArgumentException("Edge weight cannot be negative for this implementation detail.");
       }


       addEdgeToList(sourceIndex, destinationIndex, weight);

       if (!isDirected) {
           // For undirected graphs, add the reverse edge as well
           addEdgeToList(destinationIndex, sourceIndex, weight);
       }
   }

   // Calculate the degree of a vertex
   public int getDegree(char label) {
       int index = getVertexIndex(label);
       if (index == -1) {
           throw new IllegalArgumentException("Vertex not found.");
       }

       int degree = 0;
       // Count outgoing edges (edges originating from this vertex)
       EdgeNode current = adjacencyLists.get(index);
       while (current != null) {
           degree++;
           current = current.next;
       }

       if (isDirected) {
           // For directed graphs, we also need to count incoming edges (in-degree)
           // This requires iterating through all other vertices' adjacency lists
           for (int i = 0; i < vertexLabels.length; i++) {
               // Skip the current vertex's own list
               if (i == index) continue;

               EdgeNode incomingEdgeChecker = adjacencyLists.get(i);
               while (incomingEdgeChecker != null) {
                   if (incomingEdgeChecker.destinationIndex == index) {
                       degree++; // Found an incoming edge
                   }
                   incomingEdgeChecker = incomingEdgeChecker.next;
               }
           }
       }
       // Note: This definition of degree counts each edge once. For undirected graphs,
       // this correctly represents the degree. For directed graphs, it sums in-degree and out-degree.
       return degree;
   }


   // Print the graph representation
   public void displayGraph() {
       for (int i = 0; i < vertexLabels.length; i++) {
           System.out.print(vertexLabels[i] + " -> ");
           EdgeNode current = adjacencyLists.get(i);
           if (current == null) {
               System.out.print("null");
           }
           while (current != null) {
               System.out.print("(" + current.destinationIndex + ":" + current.weight + ") -> ");
               current = current.next;
           }
           System.out.println("null");
       }
   }

    // Example Usage:
    public static void main(String[] args) {
        // Undirected Graph Example
        AdjacencyListGraph undirectedGraph = new AdjacencyListGraph(4, false);
        undirectedGraph.setVertexLabels(new char[]{'A', 'B', 'C', 'D'});
        undirectedGraph.addEdge('A', 'B', 5);
        undirectedGraph.addEdge('A', 'C', 3);
        undirectedGraph.addEdge('B', 'C', 2);
        undirectedGraph.addEdge('C', 'D', 4);

        System.out.println("Undirected Graph (Adjacency List):");
        undirectedGraph.displayGraph();
        // Note: getDegree calculation for adjacency list needs careful implementation
        // to correctly sum in-degree and out-degree for directed graphs,
        // and handle undirected graph representation where edges appear twice.
        // The provided getDegree sums list length + checks incoming for directed.
        System.out.println("Degree of A: " + undirectedGraph.getDegree('A')); // Expected: 2 (A-B, A-C)
        System.out.println("Degree of C: " + undirectedGraph.getDegree('C')); // Expected: 3 (C-A, C-B, C-D)

        System.out.println("\n---------------------------\n");

        // Directed Graph Example
        AdjacencyListGraph directedGraph = new AdjacencyListGraph(4, true);
        directedGraph.setVertexLabels(new char[]{'X', 'Y', 'Z', 'W'});
        directedGraph.addEdge('X', 'Y', 1); // X -> Y
        directedGraph.addEdge('Y', 'Z', 2); // Y -> Z
        directedGraph.addEdge('Z', 'X', 3); // Z -> X
        directedGraph.addEdge('X', 'Z', 4); // X -> Z

        System.out.println("Directed Graph (Adjacency List):");
        directedGraph.displayGraph();
        // For directed graph, getDegree sums out-degree (list length) and in-degree (searched from others)
        System.out.println("Degree of X: " + directedGraph.getDegree('X')); // Expected: 3 (Out: X->Y, X->Z. In: Z->X)
        System.out.println("Degree of Y: " + directedGraph.getDegree('Y')); // Expected: 2 (In: X->Y. Out: Y->Z)
    }
}
   </edgenode>