A graph is a set of vertices connected by zero or more edge.

• weight - "weight" of an edge. can also be interpreted as the length of an edge.
• unweighted graph - term where the edge of a graph does not have weight.
• weighted graph - term where the edge of a graph has weight.
• undirected edge - term to say if an edge is bidirectional.
• directed edge - term to say if an edge is one-way.
• path - a sequence of one or more edges passed to link two vertices.
• connected - a graph where there is at least one path for each vertex pair.
• cycle - a path starting and ending at the same vertex without traversing the same two edges.
• tree - an undirected connected graph that does not have a cycle.
• root - vertex with the lowest depth.
• ancestor - set of vertex passed in a path from root to a vertex.
• parent - ancestor of the node that has the highest depth.
• child - set of vertex connected to an edge and not an ancestor.

There are 3 ways that are often used to represent a graph, namely

1. Adjacency Matrix

   Adjacency Matrix is a representation of a graph that use a $V*V$ matrix. On each indexes of the matrix, these values represents:

   • 0 if there is no edge that connects vertex i with vertex j.
   • 1 if there is an unweighted edge that connects vertex i with vertex j.
   • weight if there is a weighted edge that connects vertex i with vertex j.

   For example, an adjacency matrix that represents the graph above is written as:

   0 1 0 0 1 0
   1 0 1 0 1 0
   0 1 0 1 0 0
   0 0 1 0 1 1
   1 1 0 1 0 0
   0 0 0 1 0 0

2. Adjacency List

   The drawbacks of adjacency matrix is unnecessary usage of memory that use $V^2$ of memory blocks. Adjacency List offers graph representation that use less memory. The idea of Adjacency List is storing only the list of vertex that is connected to the parent vertex through an edge. This is an implementation of Adjacency List:

   vector< int > adjList[V];
   
   //inserting edge a-b
   adjList[a].push_back(b);
   adjList[b].push_back(a);

   for weighted graph we could use pair<int,int> to store adjacent vertex and their weight. This is an implementation for weighted graph:

   vector< pair<int,int> > adjList[V];
   
   // inserting edge a-b with c as weight
   adjList[a].push_back(make_pair(b,c));
   adjList[b].push_back(make_pair(a,c));

   The use of this method is highly recommended to represent a graph due to efficiency from memory usage and running time during graph traversal.

   For example, an adjacency list that represents the graph above is written as:

   1: 2 5
   2: 1 3 5
   3: 2 4
   4: 3 5 6
   5: 1 2 4
   6: 4

3. Edge List

   The idea of this method is by store a list of edges in a graph. We could use static data structure or a dynamic one such as vector. Implementation could use struct or pair<pair<int,int>,int> to store all those vertex that are connected by the edge and weight of the edge.
   This is an implementation of edge list:

   vector< pair<pair<int,int>,int> > edgeList;
   
   // inserting edge a-b with c as weight
   edgeList.push_back(make_pair(make_pair(a,b),c));

   For an unweighted graph we could use only pair<int,int>.

   For example, an edge list that represents the graph above is written as:

   1, 2
   1, 5
   2, 3
   2, 5
   3, 4
   4, 5
   4, 6

   This method is useful for kruskal algorithm.

In some cases, we don't need a special data structure to store a graph so that it can be traced or operated. These cases occur if the graph is implicit graph.

2 The general form of implicit graph, namely:

1. A graph with implicit edges

   • Example 1:

     As you often encounter in recursion modules at the basics of programming, a grid that contains the character '.' or '#' where we cannot visit grids containing '#'. (Figure A)
     Unconsciously, this is a graph where the vertex is the position containing '.' with an edge connects the two '.' touching each other. (Figure B)
     It can be seen that we don't need any of the 3 techniques to represent graphs as previously described.

   • Example 2:

     A graph that is formed based on the movement of the horse pawns in a chess game. We can think of the tiles on chess as vertices of the graph, as well as an edge connecting 2 tiles if the tile can be visited by performing the pawn move. (Figure C)

2. A graph with an edge that follows a rule

   • Example:

     A graph with N vertices ([1..N]) where there is an edge connecting $i$ and $j$ if $(i+j)$ is prime. (Figure D)

To Graf Traversal >