Graph theory Flashcards
What is a graph?
A set of vertices or nodes connected by edges or arcs which can have weights and directions.
What is a tree?
A connected, undirected graph with no cycles
What is an adjacency matrix?
A square matrix used to represent a graph.
Why are adjacency matrices sometimes not suitable?
In a very large or sparse graph, many of the values in the matrix will be 0. In this case you would use an adjacency list. Adjacency lists are also appropriate when edges are rarely changed.
What is a simple graph?
An unweighted, undirected graph containing no graph loops or multiple edges
What is meant by the valency of a node?
The number of other nodes it’s connected to
How is an adjacency list created?
A list of the nodes is created, and each node in the list links to a dictionary containing all the nodes connected to the aforementioned node. If the graph was not weighted, there would be no need for dictionaries and each node could just point to a list of adjacent nodes (there is no weight to store).
What are the 2 ways of traversing a graph?
Depth first: child nodes are visited before sibling nodes. This type of uses a stack.
Breadth first: sibling nodes are visited before child nodes. This type uses a queue.
What is the difference between a stack and a queue?
In a stack, items are added and removed from the same end of the stack. In a queue, items are removed from the front and added to the back
What are the operations of a stack?
pop, push and peek
What are the operations of a queue?
Enqueue and dequeue
Describe the depth-first search algorithm
Mark the starting node of the graph as visited and push it onto the stack
While the stack is not empty
Peek at top node on the stack
If there is an unvisited child of that node
Mark the child as visited and push the child node onto the stack
Else
Pop the top node off the stack
Describe the breadth-first search algorithm
Mark the starting node of the graph as visited and enqueue it into the queue
While the queue is not empty
Dequeue the next node from the queue to become the current node
While there is an unvisited child of the current node
Mark the child as visited and enqueue the child node into the queue
Breadth-first uses
Shortest path for an unweighted graph
Depth-first uses
Navigating a maze
