Data structures & algorithmsLesson 1 of 1 in the course Graph algorithms

Graph ADTs: Representations, Partitioning, and Core Algorithms

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

Graphs are a flexible way to represent relationships between entities. They are used to model networks such as roads, friendships, and computer connections. This lesson introduces the parts of a graph, its common operations, and the main ways to store it.

A graph is an abstract data type that represents graph-theory concepts in a computer program. It consists of a finite set of vertices and a set of edges connecting pairs of vertices. Vertices are also called nodes or points; edges may also be called links or lines.

All flashcards

What are the basic components of a graph?
A graph has a finite set of vertices and a set of edges connecting pairs of vertices.
How do directed and undirected edges differ?
An undirected edge is an unordered pair; a directed edge is an ordered pair.
What kinds of values can a graph associate with edges?
An edge may have a label or numeric attribute, such as cost, capacity, or length.
How do BFS and DFS differ?
BFS explores outward in layers; DFS follows a path deeper before backtracking.
What does Dijkstra's algorithm compute?
Shortest paths from a chosen source in a graph with nonnegative edge weights.

Quiz questions

  1. What is the defining difference between an undirected edge and a directed edge?Answer: An undirected edge is an unordered pair; a directed edge is an ordered pair.
  2. What is a key goal when partitioning a graph for distributed-memory processing?Answer: Balance partition sizes while limiting communication between processing elements.
  3. In a 2D grid partition with prp_r rows and pcp_c columns, how many communication partners can a processing element have?Answer: pr+pc−1p_r+p_c-1
  4. Which statement about edge weights is true for Dijkstra's algorithm?Answer: Zero-weight edges are permitted if no edge has negative weight.
  5. In a directed graph, what does neighbors(G, x) usually return?Answer: Vertices reached by outgoing edges from x.

Based on the Wikipedia article Graph (abstract data type), licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Data structures & algorithms

All Data structures & algorithms lessons
Data structures & algorithmsMerge Sort: Algorithms, Complexity, Variants, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsBinary Heaps: Ordering, Array Operations, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsBinary Search Trees: Ordering, Operations, Height, and Uses5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsTrie Structure, Operations, Compression, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsSorting Algorithms: Correctness, Stability, Methods, and Trade-offs5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsAVL Trees: Balance, Rotations, Updates, and Set Operations5 flashcards · 5 quiz questions · 4 gamesPlay free →