https://upload.wikimedia.org/wikipedia/commons/8/8b/Social_Network_Visualization.png

What are graphs?

The Definition

A Graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected Graph or a set of ordered pairs for a directed Graph. These pairs are known as edges, arcs, or lines for an undirected Graph and as arrows, directed edges, directed arcs, or directed lines for a directed Graph. The vertices may be part of the Graph structure, or may be external entities represented by integer indices or references. From Wikipedia

AGraph data structure is generalization of trees. Like trees, graphs have nodes (vertices) that are connected to each other via edges (arcs). However, unlike trees, graphs have nodes that can point to any number of nodes.

There are two kinds of graphs, directed and undirected:

Directed graphs contain edges that are directed from one node to another whereas Undirected graphs contain edges that have no direction. All nodes in a directed graph may only be traversed by following the assigned directions on each edge, but with an undirected graph, the nodes can be traversed in both directions.

http://images.slideplayer.com/26/8569085/slides/slide_2.jpg

The Vocabulary

In the above diagram, the directed graph (left, a) can be described as follows:

1. A and B are two of 6 vertices in the graph
2. A and B are adjacent (neighbors) as they are joined together by an edge (this is also true for the undirected graph (right, b))
3. A is a predecessor (source) of B because A is the vertex from which the edge is directed.
4. B is a successor (target) of A because B is the vertex to which the edge is directed
5. There is a path from vertex A to F: A → B → E→ F. This path is acyclic as the path itself does not traverse back to the same vertex.
6. In the undirected graph (right, b), B → C → E →B is a cyclic path as the vertex, B, has been repeated.

The Use Cases

In general, graphs are helpful to hold information within each node and demonstrate relationship between the information through the use of edges. Wanting the ability to capture and determine the flow of information are generally the main reasons that informs developers to use Graph data structure. Some common use cases for graphs are:

• Demonstrations of Social Networks (facebook, Twitter, Instagram…)
• Planning and making school semester course schedules based on pre-requisite, core, and major courses.
• Generating and inspecting Computer Networks
• Generating and Maps
• Airline flight planning, with added weight to the graph (such as distance, flight time, or cost) one can use graphs to calculate the best fit flight based on any or all of the above factors.
• Games — determining the transition between one game state to another. Helping determine game strategies by predicting possible moves.

The Representation

The two main ways to represent a graph are :

https://www.geeksforgeeks.org/wp-content/uploads/adjacency_list_representation.png

Adjacency List: Every vertex on the graph is listed in an object as keys, these keys are associated to an array of vertices, which represent the connection (edges) each vertex has. This method can be viewed as storing the list of edges. In this way, additional data can be stored on the vertices and edges.

http://mathworld.wolfram.com/images/eps-gif/AdjacencyMatrix_1002.gif

Adjacency Matrix: Data are stored in a two-dimensional matrix. The rows represent the predecessor and columns represent the successor. If there are connections between a predecessor and successor, values within the two-dimensional matrix will change from 0 to 1. Any additional data about the edges or vertices must be stored externally.

The Big O

Adjacency list

• Storage (Space Complexity) — O(|V|+|E|) We will need to generate an object with keys as vertices and values in the form of arrays that contain the edges. `
• Add Vertex — O(1) — constant time for look up in an object
• Add Edge — O(1) — constant time for look up in an object and inserting to the end of an array
• Query — O(|V|) — we will have to traverse through the entirety of the object (all the keys) to find whether an edge exists.

Adjacency matrix

• Storage — O(|V|²) — two arrays are generated to store all the vertices
• Add Vertex — O(|V|²) — need to traverse through the entirety of the matrix (two-dimensional array) to add
• Add Edge — O(1) — constant time for look up of the two vertices between an edge as they are represented at certain indices in the matrix.
• Query — O(1) — constant time for look uphich can also be used to determine reachability, and can be used to find shortest paths in unweighted graphs

Comparison from The Algorithm Design Manual, Skiena — second Edition — page 152

The Sample Graph

Directed graph source — self

The Code

The following code will recreate above graph example using the adjacency list representation.

The longest shortestPath Algorithm written…

TL:DR

• A graph is a set of nodes and a set of edges. `
• There are two kinds of graphs: directed and undirected.
• High-level operations include:
• breadth-first search, which can also be used to if path exists, and can be used to find shortest paths in unweighted graphs

More Reads

AVL Trees & Where To Find (Rotate) Them

The Trials And Tribulations Of The Traveling Salesman

A* search algorithm - Wikipedia

Dijkstra's algorithm - Wikipedia

This story is published in The Startup, Medium’s largest entrepreneurship publication followed by 291,182+ people.

Subscribe to receive our top stories here.