Graphs and Abstract Data Types

Planar graph

Graph with non-crossing edges when drawn

Breadth-first search (BFS)

Graph search using a queue for traversal

Single-Source Shortest Paths (SSSP)

Finding shortest paths from a source vertex

Non-linear list

List with elements having more than one successor

Graph

Set of nodes and edges connecting pairs of nodes

Cycle

Path starting and ending at the same vertex

Weakly connected graph

Directed graph with at least 2 unconnected vertices

Directed acyclic graph (DAG)

Directed graph without cycles

Dense graph

Graph with edges close to the number of vertices

Shortest path problem

Finding shortest path between two vertices

Tree

Non-linear list with at most one predecessor

Vertex

Node in a graph

Edge

Connection between two vertices

Path

Sequence of adjacent vertices

Vertex degree

Number of lines incident to a vertex

Outdegree

Number of lines leaving a vertex

Indegree

Number of lines entering a vertex

Directed graph

Graph with edges having a direction

Undirected graph

Graph with bidirectional edges

Loop

Special cycle with an arc starting and ending at the same vertex

Connected graph

Graph where all vertices have a path between them

Strongly connected graph

Directed graph with paths between every pair of vertices

Disjoint graph

Graph with unconnected vertices

Weighted graph

Graph with edges assigned values

Sparse graph

Graph with few edges compared to vertices

Adjacency matrix

Matrix showing connections between vertices

Adjacency list

List showing adjacent vertices for each vertex

Topological sort

Linear ordering of vertices in a DAG

Depth-first search (DFS)

Graph search using a stack for traversal

Traveling Salesman Problem

Finding shortest route visiting each city once

Minimum spanning tree

Spanning tree with minimum total edge weight

Bellman-Ford algorithm

Algorithm for Single-Source Shortest Paths

Prim's algorithm

Greedy algorithm for finding Minimum Spanning Tree