CS 310 graphs

What is a graph?

A set of nodes joined by a set of edges

What is a weighted graph?

Graph for which each edge has an associated weight

What is a directed graph?

Graph where each edge points from one vertex to another

What is an undirected graph?

Graph where edges are unordered pairs of vertices

What is a path?

A sequence of vertices such that there is an edge from each vertex to its successor

When is a path simple?

If all the vertices on it are distinct

What is the path length in a weighted graph?

Sum of the edge weights in the path

What is the degree of a vertex?

Number of edges incident on a vertex

For directed graphs, what is the out-degree of a vertex?

Number of edges leaving a vertex

For directed graphs, what is the in-degree of a vertex?

Number of edges entering a vertex

What is a simple graph?

Graph without multiple edges, directed in the same direction or undirected, connecting a single pair of vertices or self-loops

When is an undirected graph connected?

If any two nodes are connected by a path

When is a directed graph strongly connected?

If there is a directed path from any node to any other node

When is a graph sparse?

If the number of edges is about equal to the number of vertices

When is a graph dense?

When the number of edges is about equal to the number of vertices squared

What is a complete graph?

A graph in which every pair of vertices is adjacent

Given |V| nodes, how many edges are there in a complete, undirected graph?

|V|*(|V| - 1)/2 edges

Given |V| nodes, how many edges are there in a complete, directed graph?

|V|*(|V| - 1) edges

Given |V| nodes, how many edges are there in a complete, undirected graph with self-edges?

(|V|²)/2 edges

Given |V| nodes, how many edges are there in a complete, directed graph with self-edges?

|V|² edges

How does an adjacency list representation of a graph work?

There is a linked list for every vertex, where each linked list contains a vertex’s adjacent vertices

What is the extra space complexity for an adjacency list representation of a graph? Why?

O(|V| + |E|), as the linked list includes list heads for each vertex, and the representation will include all the edges

What are the advantages of an adjacency list representation of a graph?

Saves space for sparse graphs, O(degree(v)) time to visit edges that start at v

What are the disadvantages of an adjacency list representation of a graph?

Must traverse entire linked list of v to check for existence of an edge starting at v, which O(degree(v)) time

How does an adjacency matrix representation of a graph work?

|V| x |V| matrix, where if two vertices share an edge, their matrix element is 1, and is 0 otherwise

What are the advantages of the adjacency matrix representation of a graph?

Saves space on pointers for dense graphs, can check for the existence of an edge in O(1) time

What is the disadvantage of the adjacency matrix representation of a graph?

O(|V|) time to visit at the edges that start at v, as the whole row must be traversed

What is breadth-first search?

Traversal that visits a starting vertex, then discovers all vertices at distance k from s before discovering any vertices at distance k + 1 from s

How does breadth-first search implement the frontier?

Using a FIFO queue

Other than traversing a graph, what can breadth-first search do?

Compute the shortest distance from s to any reachable node

What is the runtime complexity of breadth-first search using an adjacency list representation of a graph?

O(|V| + |E|)

What is the runtime complexity of breadth-first search using an adjacency matrix representation of a graph?

O(|V|²)

What is the coloring method for breadth- and depth-first search?

Nodes are colored white, gray, and black to indicate undiscovered, frontier, and fully explored nodes, respectively

What is a key limitation of breadth-first search that depth-first search does not have?

May fail to reach all nodes for directed or unconnected graphs

What is depth-first search?

Traversal method that visits a starting vertex, then visits every vertex along each path starting from that vertex to the path’s end before backtracking

What is the runtime complexity of depth-first search using an adjacency list representation of a graph?

O(|V| + |E|)

What is the runtime complexity of depth-first search using an adjacency matrix representation of a graph?

O(|V|²)

What does Dijkstra’s Algorithm do?

Determines the shortest path from a start vertex to each vertex in a graph

What is the runtime complexity of Dijkstra’s Algorithm when the number of edges dominate the number of vertices?

O(|E|log|V|)

What is the runtime complexity of Dijkstra’s Algorithm when the number of edges are less than/similar to the number of vertices?

O((|V| + |E|)(log|V|))

What does Kruskal’s Algorithm do?

Determines the subset of a graph’s edges that connect all the graph’s vertices with the minimum possible sum of edge weights

What is the space complexity of Kruskal’s Algorithm?

O(|E| + |V|)

What is the runtime complexity of Kruskal’s Algorithm?

O(|E|log|E|)