Graph Introduction

Vertices · Edges · Representations

1:00

Graphs — vertices, edges, direction, weights, degree, paths, cycles, connected components, and the two standard representations (adjacency matrix and adjacency list).

By the end, you can

Define graph, vertex, and edge, and write the formal notation G = (V, E).
Distinguish directed from undirected edges and weighted from unweighted graphs, and give a real-world example of each.
Compute the degree of a vertex and apply the Handshaking Lemma to verify edge counts.
Identify in-degree and out-degree for vertices in a directed graph.
Determine whether a sequence of vertices is a valid path, a walk, or a cycle.
Count the connected components of a graph.
Fill in an adjacency matrix for a small graph and explain its symmetry for undirected graphs.
Describe the adjacency list representation and state when each representation is preferred.
Explain why every tree is a graph but not every graph is a tree.

Up next in Trees, Hashing & Graphs