learnings
Programming
Data Structures
Graphs

Graphs

Graphs are a collection of nodes and edges. They are used to represent networks and relationships between objects. Graphs are used to model real-world problems such as social networks, transportation networks, and computer networks.

Overview of Graphs

  1. Structure: A graph G consists of a set of vertices (or nodes) V and a set of edges E connecting these vertices. An edge can connect two vertices in undirected graphs or have a direction in directed graphs.

  2. Types of Graphs:

  • Undirected Graph: Edges have no direction. The edge (u, v) is identical to (v, u).
graph LR;
    A <--> B
    A <--> C
    B <--> C
    C <--> D
  • Directed Graph (Digraph): Edges have directions. The edge (u, v) is different from (v, u).
graph LR;
    A -->|directed| B
    A -->|directed| C
    B -->|directed| C
    C -->|directed| D
  • Weighted Graph: Each edge has an associated weight or cost.
graph LR;
    A -->|5| B
    A -->|3| C
    B -->|2| C
    C -->|4| D
  • Unweighted Graph: Edges do not have weights.
graph LR
    E <--> F
    E <--> G
    F <--> H
    G <--> H
    H <--> I
    I <--> J
    H <--> K
    J <--> K
    I <--> L
    J <--> M
    J <--> N
  1. Representation:
  • Adjacency Matrix: A 2D array where the element at matrix[i][j] is true if there is an edge from vertex i to vertex j.
     (0)(1)(2)(3)(4) ← vertices (i)
(0)  [0, 1, 1, 0, 0]
(1)  [1, 0, 1, 1, 0]
(2)  [1, 1, 0, 0, 1]
(3)  [0, 1, 0, 0, 0]
(4)  [0, 0, 1, 0, 0]
 ↑️ vertices (j)
  • Adjacency List: An array or list where the element at index i contains a list of vertices adjacent to vertex i.
0: [1, 2]
1: [0, 2, 3]
2: [0, 1, 4]
3: [1]
4: [2]
  1. Properties: Graphs can be cyclic (contain cycles) or acyclic (do not contain cycles), connected or disconnected, sparse (few edges) or dense (many edges).

Common Operations and Their Big O Notation

The complexity of graph operations can vary significantly based on the graph representation (adjacency list vs. adjacency matrix) and the graph’s properties (e.g., sparse vs. dense).

Operation Time Complexity (Adjacency List) Time Complexity (Adjacency Matrix) Comments
Add Vertex O(1) O(V^2) Adding a vertex is more complex in a matrix due to resizing.
Add Edge O(1) O(1) Adding an edge is straightforward in both representations.
Remove Vertex O(V + E) O(V^2) Removing a vertex requires updating all edges.
Remove Edge O(E) O(1) Removing an edge is more complex in a list.
Find Adjacent Nodes O(V) O(1) Finding all adjacent nodes varies significantly.
Check if Edge Exists O(V) O(1) Checking for an edge’s existence is faster in a matrix.

Code representation

graph.go
// Graph represents a directed graph using an adjacency list.
type Graph struct {
	vertices map[int][]int
}

// NewGraph creates a new empty graph.
func NewGraph() *Graph {
	return &Graph{
		vertices: make(map[int][]int),
	}
}

// AddVertex adds a new vertex to the graph.
func (g *Graph) AddVertex(vertex int) {
	if _, exists := g.vertices[vertex]; !exists {
		g.vertices[vertex] = []int{}
	}
}

// AddEdge adds a directed edge from vertex1 to vertex2.
func (g *Graph) AddEdge(vertex1, vertex2 int) {
	if _, exists := g.vertices[vertex1]; !exists {
		g.AddVertex(vertex1)
	}
	g.vertices[vertex1] = append(g.vertices[vertex1], vertex2)
}

// PrintGraph prints the graph in adjacency list format.
func (g *Graph) PrintGraph() {
	for vertex, neighbors := range g.vertices {
		fmt.Printf("%d -> ", vertex)
		for _, neighbor := range neighbors {
			fmt.Printf("%d ", neighbor)
		}
		fmt.Println()
	}
}
TreesHash Tables