Graphs Flashcards
What is a graph?
A set of nodes (the points) and edges (lines connecting one point to another).
What is a weight?
A representation of some kind of cost (such as distance) associated with the edges of a graph.
What is a directed graph/digraph?
A graph where all of the edges are directed.
What is a path through a graph?
A sequence of vertices connected by edges (following the arrows if the graph is directed).
What is a cycle?
A path that begins and ends at the same node.
What is a complete graph?
A graph where every node is connected to every other node.
What is a directed acylic graph?
A directed graph which contains no cycles.
When should an adjacency matrix be used to represent a graph?
When there are a large number of edges.
What is an adjacency matrix?
Essentially, a table showing where edges exist and what their weights are.
When should an adjacency list be used to represent a graph?
When there are few edges to the graph - when it is sparse.
What does sparse mean?
That there are few edges to the graph.
