Algorithms – Quick Graph Terminology
May 19, 2010 Leave a comment
This post will be brief. It just contains a load of terminology for parts of graphs, such as:
- Spanning Trees
- Back Edges
A subgraph of a given graph G, is a graph H whose edges and nodes are a subset of the edges and nodes of a the graph G.
A spanning subgraph of a given graph G, is a subgraph of G that contains all the nodes of the graph G.
A graph G is classed as ‘connected’, if for any two nodes, there is a path between them.
A strongly connected graph (Digraphs only), is a strongly connected graph, if for any two nodes i and j, we can have i reach j, and j reach i.
A forest is a graph that has no cycles
A tree is a connected forest. However, it is a connected graph that has no cycles.
A rooted tree is a tree that has an obvious start point, aka, a root node. A classic example is the Binary Tree. This is because you have to start at the root node, and can only go down, not up.
Where as, however, a free tree is a tree (graph) that has no root node.
A back edge, is an edge which connects a node to an ancestor node in a given DFS / BFS tree.
A forward edge is an edge which connects a node to a descendant node in a given DFS tree.
A cross edge is an edge which connects a node to a node which is neither an ancestor or a descendant node in a DFS and a BFS tree.
An in-place algorithm is an algorithm that uses constant memory. That is, we need the space complexity to be O(1).
We can achieve this implementing a sorting algorithm to only use, say, a single variable rather then to copy all of the data into a new list during the sort – this is O(n) space complexity.
A general purpose algorithm is an algorithm that can sort any list of item belonging to a total ordering; without restrictions.
For example, sorting algorithms that are comparison based are general purpose algorithms – such as Bubble Sort and Insertion Sort
However, algorithms that aren’t comparison based, and are distribution based aren’t general purpose. This is because they require prior knowledge about the elements to be sorted, such as their range. An example here could be the Bucket Sort.
An algorithm is stable, if for any two given item (k1, e1) and (k2, e2) we have:
- k1 == k2
- (k1, e1) precedes (k2, e2) before the sort
Then after the sort, this order is preserved, such that (k1, e1) still precedes (k2, e2) once all the items have been sorted.