Graphs

Graph

• A graph G = (V, E) is a set of vertices V and edges E where each edge (u, v) is a connection between vertices

Neighbours

• Vertices u and v are neighbours if an edge (u, v) connects them

Degree

• A degree(v) is equal to the number of edges connected to v.
  • Also known as number of neighbours connected to v

Path

• Sequence of vertices connected by edges
• Path length - number of edges in a path

Cycle

• A path that starts and ends with the same vertex
• All cycles are paths but not all paths are cycles

Connectivity

• Two vertices are connected if a path exists between them
• A graph is connected when all vertices are connected

Connected Component

• A subset of vertices that is connected

Types

• Undirected graphs
• Directed graphs
• Weighted graphs
• Trees

Representations

• Graphs are represented as
  • Adjacency Matrices
  • Edge sets
  • Adjacency Lists
    • Most common representation

Algorithms

• DFS
• BFS