Graphs Flashcards
What are the two parts of a node?
A value of some generic type.
A reference to the next node in the sequence.
What is a graph?
Like a binary tree, but an node in a graph may be connected to any other node.
Graphs also use special terminology – each node is a vertex.
Connections between vertices are edges. Two vertices connected by an edge are neighbors.
What is an edge?
May be identified by the vertices that it connects, ie Eab.
What is a path?
A series of edges that connect two vertices together.
What is a connected component?
If a path exists between two vertices in a graph, they are said to be a part of the same connected component.
What is the difference between undirected and directed graphs?
Undirected connections work in both directions.
Directed are connected in one direction.
What is an adjacency list?
Each vertex keeps track of the other vertices to which it is connected in a
data structure, e.g. a list.
An adjacency list can be diagrammed
using a simple table.
○ The first column lists all of the vertices in the graph.
○ The second column lists the vertices to which each vertex is connected (its neighbors).
What is breadth first search?
An algorithm that attempts to find a path between two vertices in a graph is called a search.
A BFS examines all of the immediate neighbors of a vertex first before going any deeper into the graph.
It searches all of the neighbors that are one edge from the starting vertex first. Then the neighbors that are two edges. And so on until it finds the end or runs out of neighbors.
A BFS uses a queue to insure that the vertices are visited in breadth-first order.
It uses a set or a hashmap to keep track of visited vertices.
What is depth first search?
Rather than explore all of the neighbors of a node first, a DFS follows edges along a path deeper into the graph.
● If it arrives at the goal, it stops.
● If it arrives at a vertex that is not the goal and does not have any unexplored neighbors, it returns back along its path only as far as necessary to find a vertex with unexplored neighbors.
A DFS can be implemented using a stack or by using recursion.
What is Dijkstra’s algorithm?
an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks.
