This post represents a brief introduction to graph algorithms. When study I usually use to use paper and write a summary for what I read to better understand, analyze, and memorize what I am studying.
Instead of using paper, this time, I decided to use my nice little blog as someone else can benefit from it. Reference of the definitions and books are provided at the end of this post.
My mind, on the other hand, better works by visualizing things so I’ve done my best to draw pictures of the definitions mentioned in this post.
1- Graph: graph G = (V, E) consists of a set of vertices, V, and a set of edges, E.
- Each edge is a pair (v, w), where v, w ∈ V. Edges are sometimes referred to as arcs.
- There are two type of graphs, directed and undirected.
- Directed graphs are called digraphs.
- Vertex w is adjacent to v if and only if (v, w) ∈ E. In other words if the w and v are connected with only one edge. The edge E is consisted of w and v.
- In an undirected graph E is represented either by (v,w) or (w,v), the direction is both ways, it is undirected right ?
- In a directed graph (v,w) is a different edge than (w,v).
- An edge can have a weight or sometimes called cost. In a geographical map this can represent the distance between two points, for example.
2- Path: A path in a graph is a sequence of vertices w 1 , w 2 , w 3 , . . . , w N such that (w i , w i+1 ) ∈ E for 1 ≤ i < N.
- The length of such a path is the number of edges on the path, which is equal to N − 1
- There is always a path from every vertex to itself and its length is 0, this is intuitive.
- loop, this represents an edge (v, v) i.e a path from a vertex to itself.
- A simple path is a path such that all vertices are distinct, except that the first and last could be the same. (wiki definition: a simple path is a path in a graph which does not have repeating vertices)
3- Cycle: A cycle in a directed graph is a path of length at least 1 such that w 1 = w N ; this cycle is simple if the path is simple. In other, more intuitive words a cycle is a path that ends at the same vertex that it started from.
- The is no cycles in an undirected graph, why is that? well because very edge is considered as a a cycle as it has both way from v -> w and from w->v.
- A directed graph is acyclic if it has no cycles
- A directed acyclic graph is sometimes referred to by its abbreviation, DAG
4- Some more points :
- An undirected graph is connected if there is a path from every vertex to every other vertex.
- A directed graph which is connected (there is a path from every vertex to every other vertex) is called strongly connected.
- If a directed graph is not strongly connected (there is NO a path from every vertex to every other vertex), but the underlying graph the one without direction to the arcs or in other words the same graph after removing directions of edges is connected, then the graph is said to be weakly connected. In other words, a directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
- A complete graph is a graph in which there is an edge between every pair of vertices