Searching, Sorting, Graphs Flashcards
Two searching algorithms
- linear (or sequential) search
- binary search
Sorting algorithms
- insertion sort
- quicksort
Recursion
Calling a the function inside the function
A graph is
- a collection of vertices
- connected by edges
Order of a graph
Number is vertices it has
Size of a graph
Number is edges the graph has
Degree of vertex
Number of edges incident to that vertex
Path
Is a sequence of vertices and edges (without repetition) that connects two vertices
Length of path
The number of edges in the path
Cycle
A path of min 1, starting and ending at the same vertex
Connected graph
If every pair of vertices there exists at least one path
Disconnected graph
Consists of at least two connected components
Trees
- a connected graph with no cycles
- there exists only one path between any given two vertices
Forest
Disconnected graph composed by multiple trees
Directed graph or digraph
-is a graph whose edges have a direction
Directed edges or arcs
Edges in a directed graph
Directed path
Is a path following the direction of the edges
-the endpoints are usually referred to as the source and destination
Depth first search
- can be used to find if a path exists between to vertices
- used to explore all vertices in a connected component of a graph, starting from a given source vertex v
Tree edges or discovery edges
Edges used to perform the traversal
Back edges
Edges connected that would take us back on an explored part of our path
Breadth-first search
-to explore and backtrack easily, uses a queue instead of a stack
Cross edge
Is an edge that would take is to the vertex who is not an ancestor and has been visited before
Parent, ancestor, sibling
- parent: is the previous vertex that got to the other vertex
- ancestor: original one that is in the lineage
- siblings: share a common ancestor
Weighted graphs
- used to represent the distance between two things
- also used to represent cost
Dijkstra’s algorithm
Finds the shortest possible path to get to a certain vertex
