Graphs - CS A200 Data Structures

Vocabulary flashcards covering fundamental graph data structure terminology, types of edges/graphs, path/cycle definitions, and common computer science representations (Adjacency Matrix/List).

Graph

A data structure that consists of a set of vertices (or nodes) and a set of edges (relations) between pair of vertices.

Edges

Represent paths or connections between vertices; represented as line segments joining the vertices.

Vertices

Also known as nodes; represented as points or labeled circles.

Undirected edge

An edge that does not indicate direction, allowing travel in either direction along the edge.

Directed edge

An edge that has a direction, where travel is only possible from the origin ($v_1$) to the destination ($v_2$).

Self-loop edge

An edge (undirected or directed) that originates and ends at the same vertex.

Parallel edges

Two undirected edges with the same end vertices, or two directed edges with the same origin and destination.

Adjacent vertices

Vertices that have an edge connecting one to the other.

Directed graph (digraph)

A graph in which every edge has a direction.

Undirected graph

A graph in which no edge has a direction.

Simple graph

A graph that has no parallel edges and no self-loops.

Weight

A value associated with each edge in a graph representing distance, energy consumption, cost, or other metrics.

Weighted graph

A graph where each edge has an associated weight.

Unweighted graph

A graph where edges do not have associated weights; it may be considered a weighted graph where all edges have a weight of $1$.

Degree of a vertex

The number of edges connected to a vertex.

In-degree

In a directed graph, the number of incoming edges to a vertex.

Out-degree

In a directed graph, the number of outgoing edges from a vertex.

Path

A sequence of vertices in which every vertex is adjacent to the next one, beginning and ending with a vertex.

Simple path

A path such that all its vertices and edges are distinct.

Length of a path

The sum of all of the edges that make up the path (e.g., the path SFO-ORD-PVD has a length of $1843 + 849 = 2692$).

States

Vertices that represent possible configurations in a graph representation of a game.

Cycle

A circular sequence of alternating vertices and edges (a circular path) where the start and end vertices are identical.

Simple cycle (Undirected)

A path $\{v_0, v_1, \dots, v_k\}$ where $v_0 = v_k$, $k \geq 3$, and vertices $v_1, v_2, \dots, v_k$ are distinct.

Simple cycle (Directed)

A path $\{v_0, v_1, \dots, v_k\}$ where $v_0 = v_k$, the path contains at least one edge, and vertices $v_1, v_2, \dots, v_k$ are distinct.

Adjacency matrix

A square grid ($n \times n$) of true/false values stored in a two-dimensional array, where the component at row $i$ and column $j$ is true if an edge exists from vertex $i$ to vertex $j$.

Adjacency list

A representation of a graph with $n$ vertices using $n$ different linked lists; for each entry $j$ in list $i$, there is an edge from $i$ to $j$.

Sparse graph

A graph where each vertex has only a few edges; an adjacency list is preferred over an adjacency matrix for this type due to space efficiency.