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

3. 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]

4. 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).

Code representation

// 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()
	}
}