Graphs

• Difficulty: easy

A Graph is a collection of vertices and edges that connect all or some of those vertices together.

A Graph may be directed or undirected. In a directed graph each edge has a direction (like a one-way street). You may access an end-node from a start-node but not the other way around. In undirected graphs the edges don't have a specific direction (like a two-way street) and thus every two vertices that are connected together have access to each other.

What is a vertex?#

A vertex is a basic unit used in graphs to represent data. The terms "node" and "vertex" are used interchangeably to describe how data is represented in graphs. Vertices (the plural form of vertex) are connected by edges.

Another way of illustrating the difference between directed and undirected graphs is to think about social networks. If each vertex is a "user", then in a directed graph each edge would a "follow" relationship -- you may follow someone but the doesn't mean the other person follows you back. Whereas in an undirected graph the edge would be like a "friend" relationship -- if someone is in your friend list then it automatically means that you're in that person's friend list too.

In the example above we have three different graphs that all have vertices and edges. All of the graphs have a set of vertices {A, B, C, D} and all of the graphs have a set of edges. The undirected graph has a set of vertices: {AB, BC, AC, CD} . The directed graph also has a set of vertices: {AB, BC, CB, AC, CD} Notice that for directed graph to connect vertices B and C together in both directions there are two edges BC and CB in the set.

If two vertices are connected to each other by one edge, we call these vertices adjacent or neighbors. In the undirected graph above, for example, the vertices A and B are neighbors as well as the vertices A and C. But the vertices B and D are not neighbors since these vertices are connected via more than one edge (B is connected to C which is connected to D).

The sequence of edges between two vertices is called a path. In the directed graph above there is no path from D to A but there is a path from A and D and the path is the set of edges: {AC, CD}.

All vertices in a graph do not need to be connected. When there are vertices that are unreachable we call this type of graph a disconnected graph. If every pair of vertices in a graph has an edge, it is called a connected graph.

Graphs can also have cycles. If a graph doesn't have cycles it is called acyclic graph.

A weighted graph is a graph where each edge has a weight associated with it. Depending on the context, the edge weight may represent different concepts like "distance", "traffic", "cost", "resistance" and so on.

Application#

• Maps applications use graphs to compute shortest paths between vertices (addresses, cities, locations).

• Social networks use graphs for friends suggestion algorithms.

• Package managers use graphs to calculate correct order of installing packages based on their dependencies.

• Search engines use graphs to analyze page relevance. In graphs used by search engines, the web-page is a vertex and the link from this web-page to another is directed edge.

• Network providers use graphs to analyze network traffic and security. In this case each vertex has an IP address and every edge represent the network packets that flow between different IP addresses.

Graph Representation#

Graphs are normally being represented as adjacency lists or adjacency matrices. Let's take the graphs from the beginning of this chapter as an example.

Adjacency Matrix#

The graph with n vertices may also be represented as an adjacency matrix of size n × n of binary values (0 or 1). In such matrix the value 1 at position (i, j) means that there is an edge between vertices i and j. Otherwise if the value is 0 there is no edge between those vertices.

Undirected graph adjacency matrix example

For undirected graphs the adjacency matrix will be symmetrical.

Directed graph adjacency matrix example

For directed graph the adjacency matrix may not be symmetrical.