Introduction to Graphs

What is a Graph?

A graph is a data structure that consists of a set of nodes (or vertices) and a set of edges that connect pairs of nodes. Graphs are used to represent networks of communication, data organization, computational devices, and more.

Directed Graphs (Digraphs)

In a directed graph, edges have a direction, going from one vertex to another. This is useful for representing one-way relationships such as web page links or flight routes.

      // Directed Graph Example
      class DirectedGraph {
          private Map> adjList = new HashMap<>();
          
          void addEdge(String source, String destination) {
              adjList.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
          }
          
          List getNeighbors(String node) {
              return adjList.getOrDefault(node, Collections.emptyList());
          }
      }
      

Undirected Graphs

In an undirected graph, edges have no direction. They simply connect two vertices, indicating a two-way relationship. This type of graph is often used to represent social networks or road maps.

      // Undirected Graph Example
      class UndirectedGraph {
          private Map> adjList = new HashMap<>();
          
          void addEdge(String node1, String node2) {
              adjList.computeIfAbsent(node1, k -> new ArrayList<>()).add(node2);
              adjList.computeIfAbsent(node2, k -> new ArrayList<>()).add(node1);
          }
          
          List getNeighbors(String node) {
              return adjList.getOrDefault(node, Collections.emptyList());
          }
      }
      

Weighted Graphs

Weighted graphs assign a weight or cost to each edge. This is commonly used in scenarios where we need to find the shortest path or minimum spanning tree, such as in network routing.

      // Weighted Graph Example
      class WeightedGraph {
          private Map> adjList = new HashMap<>();
          
          void addEdge(String source, String destination, int weight) {
              adjList.computeIfAbsent(source, k -> new HashMap<>()).put(destination, weight);
          }
          
          Map getNeighbors(String node) {
              return adjList.getOrDefault(node, Collections.emptyMap());
          }
      }
      

Cyclic Graphs

A cyclic graph contains at least one cycle, which is a path of edges and vertices wherein a vertex is reachable from itself. Cycles are important in detecting deadlocks in operating systems or circular dependencies in software.

      // Cyclic Graph Example
      class CyclicGraph {
          private Map> adjList = new HashMap<>();
          
          void addEdge(String node1, String node2) {
              adjList.computeIfAbsent(node1, k -> new ArrayList<>()).add(node2);
          }
          
          boolean hasCycle() {
              // Cycle detection logic here
              return false; // Placeholder
          }
      }
      

Acyclic Graphs

An acyclic graph is one that does not contain any cycles. Directed Acyclic Graphs (DAGs) are particularly useful in representing structures with dependencies, such as task scheduling.

      // Acyclic Graph Example
      class AcyclicGraph {
          private Map> adjList = new HashMap<>();
          
          void addEdge(String source, String destination) {
              adjList.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
          }
          
          boolean isAcyclic() {
              // Acyclic check logic here
              return true; // Placeholder
          }
      }