Intro to Graphs

A graph is an abstract representation of a complex system such as networks, human relationships, and any organization.
A graph is very important because it can represent and simplify any complex relationships in a visual format.
It is pretty amazing that messy applied problems often could be described with simple and classical graph properties.

In this post, I am going to discuss some popular graphs and brief examples.

Graph Examples

A graph G can be represented as a set of vertices and edges which can be said as G = (V, E)
Now, let’s take a look at various graphs and their properties.

Undirected vs. Directed Graph

A graph G = (V, E) is undirected if an edge between two vertices is equally applicable.
In other words, if you can travel from one vertex to another vertex in both directions with one edge it’s an undirected graph.
If not, it is a directed graph.
In an undirected graph, you can visit A from B, C, D whereas there isn’t any vertex that can visit A in a directed graph.

Weighted vs. Unweighted Graph

If each edge in a graph is assigned with numerical value then it is considered as a weighted graph.
Each edge may have different weights and therefore the costs of visiting node may be different even if the number of edges are the same.
If each edge in a graph is not assigned with numerical value then it is an unweighted graph. (All edges are assumed to be of equal weight)

As you can see above graph, the shortest path from A to C in the unweighted graph is edge A, C.
However, the story is different in weighted graph.
Since it costs 10 to use direct path it is cheaper to visit B and then C which is 5 (4 + 1)

Cyclic vs. Acyclic Graph

An acyclic graph does not have any cycles.
There is a cycle in a graph if you can visit a vertex and come back to the same vertex while traversing.

In the above cyclic graph example you can see that starting from vertex A you can visit C, B, and can come back to A which is a cycle.
But there isn’t any cycle in the acyclic graph.

Code Example

Now, let’s discuss what kind of data structure we can use in order to represent a graph.
First, we need information about all the vertices and edges associated with each vertex.
In that sense, it would be reasonable to define a user-defined type for each edge.
And each vertex will know which edges are associated with it.

Here is a sample code representing data structure for a graph.
There could be many other ways as this is just one way to represent it.

struct Edge
{
    // destination vertex id for this edge
    // it could be any other data structure to represent destination
    int vertexId;
    
    // weight of the edge if application. 0 means unweighted.
    int weight;
};

struct Vertex
{
    // all the edges associated with this vertex
    vector<Edge> edges;    
};

struct Graph
{
    // here I use index of each vertex as vertex id for simplicity
    // but you can use your own way to represent it differently.
    vector<Vertex> vertices;
    
    // is this directed graph?
    bool directed;
};

Conclusion

There are many other types such as simple vs non-simple, sparse vs dense and etc which are not discussed here.
I just wanted to show very basic concepts of important graphs and their properties.