Graph

What is a Graph

A graph is a dynamic data structure that can represent non-linear relationships betweens different items.

What does a graph consist of

Graph

In a graph, a node is the thing that is linked, an edge is the thing that makes the connection and a cycle is defined as a path that begins and ends at the same node. As shown in the image below. A cycle exists between nodes D, C, and E.

Directed Graph

A directed graph is one with arrows pointing in only one direction. Even if some nodes are bidirectional, if others are still directional, the graph is referred to as directed.

Undirected Graphs

A bidirectional graph is an undirected graph. This is a diagram with arrow heads on both ends. They can also be depicted without arrows and just lines connecting them.

A weighted graph

A weighted graph is a graph with edges that has numerical numbers.

The numerical values can represent certain aspects within each node between the two. For example, it can represent the distance in metres between the nodes. The nodes in this case may represent different locations. It could also show, on a scale of 1-10, how much person A likes person B. If you were developing a social app, a weighted graph could be useful; the numbers would represent how much Person A likes Person B. It may be used by social media apps to determine which people's posts you see the most.

Graph Algorithm using a dictionary

//creating the dictionary for the graph
public static Dictionary<string,Dictionary<
string, int>> friends = new
 Dictionary<string,Dictionary<string, int>>();
//creating a new entry in the dictionary
friends.Add("steve", new Dictionary<string, int>());
adding values to the key "steve"
friends["steve"].Add("andrae", score);
friends["steve"].Add("emma", score);
 
 
 

Adjacency matrix

The edges and edges with weights shown above have two of each node, with the starting nodes switched. This is due to the fact that it is an undirected graph; in a directed graph, you would only enter one of the pairs.

The image below is an adjacency matrix of the graph above, which shows how weights and nodes are connected. The adjacency matrix can also be composed of only 0s and 1s. In that case, the adjacency matrix would represent which nodes are connected rather than the weights. In that case t he number 1 would indicate that they are linked and the number 0 would show that they are not linked.

The matrix is read from column to row. Node A to B has a weight of 1.The weight of Node A to B is one. Nodes B to C have a weight of 4, and so on. Because it is an undirected graph, the matrix displays both pairs of nodes with weights, e.g. (B,A) and (A,B). You would only show one of them if it were a directed graph.

Adjacency List

This is another method of displaying weighted graphs. The nodes on the left are connected with the corresponding weights to those on the right.

The Pro and Con of the matrix

Pro - Adding new edges and nodes to the adjacency matrix is simple.

Con - It's bad for sparse graphs as it leaves a lot of space. In an algorithm, this would mean memory wasted. The bigger the graph the worse it becomes

Pros and Cons of the adjacency list.

Pro - It's good for sparse graphs since not as much space is left compared to the adjacency matrix. In an algorithm it would be memory efficient.

Con - It's not as easy to read as the adjacency matrix.

To learn about graph Traversing click here or to read about different topics, click here