Algorithms – Quick Graph Terminology

This post will be brief. It just contains a load of terminology for parts of graphs, such as:

• Spanning Trees
• Back Edges
• etc…

Subgraph

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.

 

Spanning Subgraph

A spanning subgraph of a given graph G, is a subgraph of G that contains all the nodes of the graph G.

 

Connected

A graph G is classed as ‘connected’, if for any two nodes, there is a path between them.

http://en.wikipedia.org/wiki/Connected_graph 

 

Strongly Connected

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.

http://en.wikipedia.org/wiki/Connected_graph

 

Forest

A forest is a graph that has no cycles

 

Tree

A tree is a connected forest. However, it is a connected graph that has no cycles.

 

Rooted Tree

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.

 

Free Tree

Where as, however, a free tree is a tree (graph) that has no root node.

 

Back Edges

A back edge, is an edge which connects a node to an ancestor node in a given DFS / BFS tree.

 

Forward Edges

A forward edge is an edge which connects a node to a descendant node in a given DFS tree.

 

Cross Edges

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.

 

In-Place

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.

 

General Purpose

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.

 

Stability

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.