Module 4 : Knowing Graphs

Introduction to Graphs

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

Terminology

• weight - "weight" of an edge. can also be interpreted as the length of an edge.
• un / weighted graph - term where the edge of a graph has / does not have weight.
• un / directed edge - term to say if an edge is bidirectional / 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.

How to represent a graph

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

1. Adjacency Matrix We can represent a graph using a 2-dimensional array Adjmat [V][V] where AdjMat [i][j] is 1 if there is a edge connecting vertex i and vertex j and 0 if it doesn't exist. The value of AdjMat[i][j] can also be weight from a edge to weighted graph. For example, the adjacency matrix for the graph in the example is as follows:

txt 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 main problem with using an adjacency matrix is ​​that it consumes as much as $V^2$ of memory for a graph with as many vertices as $V$ so it is not possible for a large graph. The solution to this problem is to use the Adjacency List. The idea of ​​representing using the Adjacency List is to simply keep a list of other vertices that have an edge connected to a vertex. The implementation can be done using a vector like the following:

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

for weighted graph we can use pair <int,int> as content of Adjacency List to store adjacent vertex and their weight. Here's an implementation for a weighted graph:

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

The use of this method in representing graphs is highly recommended because it is very efficient in memory usage and the time complexity of traversing.

3. Edge List The idea of ​​representing a graph using this method is to save all the existing lists in a graph. Storage can be done in a static or dynamic array such as vector The implementation can use a struct containing the vertex at the end of the edge and its weight. Another alternative if lazy creates a struct is to use a pair <pair <int,int>,int> to store the required information. Examples of implementation are as follows:

``cpp vector <pair<pair<int,int>,int>> edgeList;

// inserts edge a-b with weight c edgeList.push_back(make_pair(make_pair(a, b),c)); ``

For unweighted graph we can change the contents of the vector to pair<int,int>. This method is very useful in the Kruskal algorithm to find the Minimum Spanning Tree of a graph Note: even though it looks a little more complicated, I prefer the option of using pairs because actually using structs is more lazy. ehe.

Implicit Graph

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.