Algorithms

What is a graph?

A graph is a data structure used to represent relationships between objects.

Graphs are widely used in algorithms, such as searching (DFS, BFS), shortest path algorithms (Dijkstra's, A*), and in solving problems like finding cycles or detecting connected components.

It consists of two main components:

  • Nodes (or Vertices): These are the entities or points in the graph.
  • Edges: These are the connections between the nodes. An edge represents a relationship between two nodes. There are different types of graphs depending on the properties of the nodes and edges:

Directed vs. Undirected Graphs:

  • Directed Graph (Digraph): Edges have a direction, meaning the relationship between two nodes is one-way. For example, a link from A to B doesn’t necessarily mean there’s a link from B to A.
  • Undirected Graph: Edges have no direction, meaning the relationship between two nodes is two-way. If there’s a link between A and B, it works both ways.

Weighted vs. Unweighted Graphs:

  • Weighted Graph: Edges have weights or costs associated with them. For example, in a road map, the weight of an edge could represent the distance or travel time between two cities (nodes).
  • Unweighted Graph: Edges don’t have weights. The mere existence of an edge shows that two nodes are connected.

Cyclic vs. Acyclic Graphs:

  • Cyclic Graph: There’s at least one path in the graph where you can start at a node and follow edges to eventually return to the same node.
  • Acyclic Graph: No cycles exist; you can’t return to a starting node by following the edges.

Use Cases

  • Social Networks: People (nodes) connected by friendships (edges).
  • Navigation Systems: Locations (nodes) connected by roads (edges with weights like distance or time).
  • Dependency Graphs: Tasks (nodes) and the dependencies between them (edges).
  • Computer Networks: Computers (nodes) connected via communication channels (edges).