9.1: Introduction to Graphs

Graphs are fundamental data structures in computer science that represent relationships between objects. A graph consists of nodes (also called vertices) and edges that connect these nodes. Graphs can be used to model various real-world scenarios, such as social networks, road networks, and computer networks.

In this sub-chapter, we will introduce the concept of graphs and discuss their applications in various fields. We will learn how to represent graphs using adjacency lists and adjacency matrices and understand the differences between directed and undirected graphs.

By the end of this sub-chapter, you will be able to:

Understand the concept of graphs and their applications.
Represent graphs using adjacency lists and adjacency matrices.
Differentiate between directed and undirected graphs.

What are Graphs?

A graph is a data structure that consists of nodes (also called vertices) and edges that connect these nodes. Each node represents an object, and each edge represents a relationship between two objects.

For example, consider a social network where each person is a node, and each friendship is an edge. In this case, the graph represents the relationships between people in the network.

Similarly, a road network can be represented as a graph where each intersection is a node, and each road is an edge. In this case, the graph represents the connections between intersections in the network.

Representing Graphs

There are two common ways to represent graphs: adjacency lists and adjacency matrices.

Adjacency Lists

An adjacency list is an array of lists where each list represents the neighbors of a node. The index of the array corresponds to the node, and the list contains the nodes that are connected to it.

For example, consider the following undirected graph:

We can represent this graph using an adjacency list as follows:

graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1],
  3: [4],
  4: [3]
}

In this representation, the key of the dictionary corresponds to the node, and the value is a list of nodes that are connected to it.

Adjacency Matrices

An adjacency matrix is a 2D array where each row and column represent a node, and the value at the intersection of a row and column indicates whether there is an edge between the two nodes. If there is an edge, the value is 1; otherwise, it is 0.

For example, the adjacency matrix for the above graph is:

In this representation, the row and column indices correspond to the nodes, and the value at the intersection indicates whether there is an edge between the two nodes.

Directed and Undirected Graphs

In a directed graph, each edge has a direction, indicating that the relationship between the two nodes is one-way. In contrast, in an undirected graph, each edge has no direction, indicating that the relationship between the two nodes is two-way.

For example, consider the following directed graph:

We can represent this graph using an adjacency list as follows:

graph = {
  0: [1],
  1: [2],
  2: []
}

In this representation, the key of the dictionary corresponds to the node, and the value is a list of nodes that are connected to it. Since the graph is directed, the list contains only the nodes that are reachable from the current node.

Similarly, the adjacency matrix for the above graph is:

0 1 1
0 0 1
0 0 0

In this representation, the row and column indices correspond to the nodes, and the value at the intersection indicates whether there is an edge between the two nodes. Since the graph is directed, the value is 1 only if there is an edge from the row node to the column node.

Summary

In this sub-chapter, we introduced the concept of graphs and discussed their applications in various fields. We learned how to represent graphs using adjacency lists and adjacency matrices and understand the differences between directed and undirected graphs.

By the end of this sub-chapter, you should be able to:

Understand the concept of graphs and their applications.
Represent graphs using adjacency lists and adjacency matrices.
Differentiate between directed and undirected graphs.

In the next sub-chapter, we will explore directed and undirected graphs in more detail and learn about graph traversal algorithms, such as Depth-First Search (DFS) and Breadth-First Search (BFS).

9.2: Directed and Undirected Graphs

In the previous sub-chapter, we introduced the concept of graphs and learned how to represent them using adjacency lists and adjacency matrices. In this sub-chapter, we will explore directed and undirected graphs in more detail and learn about their differences and applications.

By the end of this sub-chapter, you will be able to:

Understand the differences between directed and undirected graphs.
Represent directed and undirected graphs using adjacency lists and adjacency matrices.
Analyze the time complexity of graph traversal algorithms for directed and undirected graphs.

Directed Graphs

In a directed graph, each edge has a direction, indicating that the relationship between the two nodes is one-way. The direction is represented by an arrow that points from the source node to the destination node.

For example, consider the following directed graph:

We can represent this graph using an adjacency list as follows:

graph = {
  0: [1],
  1: [2],
  2: []
}

Similarly, the adjacency matrix for the above graph is:

0 1 1
0 0 1
0 0 0

Undirected Graphs

In an undirected graph, each edge has no direction, indicating that the relationship between the two nodes is two-way. The edges are represented by lines that connect the nodes.

For example, consider the following undirected graph:

We can represent this graph using an adjacency list as follows:

graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1]
}

In this representation, the key of the dictionary corresponds to the node, and the value is a list of nodes that are connected to it. Since the graph is undirected, the list contains all the nodes that are connected to the current node.

Similarly, the adjacency matrix for the above graph is:

1 1 1
1 1 1
1 1 1

In this representation, the row and column indices correspond to the nodes, and the value at the intersection indicates whether there is an edge between the two nodes. Since the graph is undirected, the value is 1 if there is an edge between the two nodes, regardless of the direction.

Time Complexity of Graph Traversal Algorithms

The time complexity of graph traversal algorithms depends on the representation of the graph. For adjacency lists, the time complexity of Depth-First Search (DFS) and Breadth-First Search (BFS) is O(V + E), where V is the number of vertices and E is the number of edges. For adjacency matrices, the time complexity of DFS and BFS is O(V^2), which is less efficient than adjacency lists for sparse graphs (graphs with few edges).

Summary

In this sub-chapter, we explored directed and undirected graphs in more detail and learned about their differences and applications. We represented directed and undirected graphs using adjacency lists and adjacency matrices and analyzed the time complexity of graph traversal algorithms for directed and undirected graphs.

By the end of this sub-chapter, you should be able to:

Understand the differences between directed and undirected graphs.
Represent directed and undirected graphs using adjacency lists and adjacency matrices.
Analyze the time complexity of graph traversal algorithms for directed and undirected graphs.

In the next sub-chapter, we will learn about graph traversal algorithms, such as Depth-First Search (DFS) and Breadth-First Search (BFS), and their applications.