In this section, I explore the graph data structure, including its definition and properties. Understanding graphs is fundamental due to their widespread applications in various domains such as computer science, geography, and network analysis.
Definition of Graphs
A graph is a collection of objects called vertices (or nodes), which are connected by edges (or arcs). Formally, a graph G is defined as G=(V,E) where V is a set of vertices and E is a set of edges, each of which connects a pair of vertices.
Motivation for Learning Graph Data Structures
Graphs are powerful tools for modeling relationships between pairs of objects. Here are a couple of practical applications:
- Road Networks (Road Maps): In this context, cities represent vertices, and the roads connecting these cities are the edges. Graphs help in finding the shortest path, optimal routes, and connectivity between different locations.
- Flight Networks: Airports in cities are the vertices, while the flight paths between these airports are the edges. Graphs assist in route planning, scheduling, and analyzing the connectivity of the flight network.
Core Terminologies in Graphs
-
Directed Edges:
- Definition: In directed graphs (digraphs), edges have an orientation. An edge from vertex A to vertex B is denoted as A→B, indicating that the connection is one-way.
Example: If there is a directed edge from A to B, you can travel from A to B, but not from B to A.
-
Undirected Edges:
- Definition: In undirected graphs, edges have no orientation. An edge between vertices A and B is denoted as A−B, indicating that the connection is bidirectional.
Example: If there is an undirected edge between A and B, you can travel both from A to B and from B to A.
-
Weighted Edges:
When each edge in a graph is assigned a weight or cost, the graph is known as a weighted graph. The weights can represent distances, costs, or any other metric.- Types:
- Weighted Undirected Graph: An undirected graph where each edge has an associated weight.
- Weighted Directed Graph: A directed graph where each edge has an associated weight.
- Types:
Additional Graph Concepts
-
End Vertices (Endpoints): Vertices that are connected by an edge. In directed edges, the first vertex is the origin, and the second vertex is the destination.
- Outgoing Edges: Edges that originate from a vertex.
- Incoming Edges: Edges that terminate at a vertex.
-
Degree of a Vertex: The number of edges incident to a vertex.
- In-degree: The number of incoming edges to a vertex.
- Out-degree: The number of outgoing edges from a vertex.
Example: If vertex B has one incoming edge and two outgoing edges, its in-degree is 1, and its out-degree is 2.
-
Path: A sequence of edges connecting a sequence of vertices. For instance, in a graph, a path from vertex A to vertex B is a route that starts at AA and ends at BB.
-
Cycle: A path that starts and ends at the same vertex. Cycles can occur in both directed and undirected graphs.
Graphs as Abstract Data Types (ADTs)
Graphs are often implemented as abstract data types, providing a set of operations for adding vertices, adding edges, and querying the graph.
These operations enable efficient graph traversal, search, and manipulation, making graphs a versatile and powerful tool in the world of computing.
By understanding these fundamental concepts, you can leverage graphs to model complex relationships and solve problems across various domains.
Graph Implementation
import numpy as np
from collections import deque
class Graph:
"""
A class to represent a directed graph using an adjacency matrix.
Attributes:
----------
_adjMat : np.ndarray
A 2D array to store edges between vertices.
_vertices : int
The number of vertices in the graph.
_visited : list
A list to keep track of visited vertices during DFS.
"""
def __init__(self, vertices):
"""
Initialize the graph with a given number of vertices.
Parameters:
----------
vertices : int
The number of vertices in the graph.
"""
self._adjMat = np.zeros((vertices, vertices))
self._vertices = vertices
self._visited = [0] * vertices
def insert_edge(self, u, v, w=1):
"""
Insert an edge from vertex u to vertex v with weight w.
Parameters:
----------
u : int
The starting vertex of the edge.
v : int
The ending vertex of the edge.
w : int, optional
The weight of the edge (default is 1).
"""
self._adjMat[u][v] = w
def delete_edge(self, u, v):
"""
Delete the edge from vertex u to vertex v.
Parameters:
----------
u : int
The starting vertex of the edge.
v : int
The ending vertex of the edge.
"""
self._adjMat[u][v] = 0
def get_edge(self, u, v):
"""
Get the weight of the edge from vertex u to vertex v.
Parameters:
----------
u : int
The starting vertex of the edge.
v : int
The ending vertex of the edge.
Returns:
-------
float
The weight of the edge.
"""
return self._adjMat[u][v]
def vertices_count(self):
"""
Get the number of vertices in the graph.
Returns:
-------
int
The number of vertices.
"""
return self._vertices
def edge_count(self):
"""
Get the number of edges in the graph.
Returns:
-------
int
The number of edges.
"""
count = 0
for i in range(self._vertices):
for j in range(self._vertices):
if self._adjMat[i][j] != 0:
count += 1
return count
def indegree(self, u):
"""
Get the in-degree of a vertex.
Parameters:
----------
u : int
The vertex for which the in-degree is to be calculated.
Returns:
-------
int
The in-degree of the vertex.
"""
count = 0
for i in range(self._vertices):
if self._adjMat[i][u] != 0:
count += 1
return count
def outdegree(self, u):
"""
Get the out-degree of a vertex.
Parameters:
----------
u : int
The vertex for which the out-degree is to be calculated.
Returns:
-------
int
The out-degree of the vertex.
"""
count = 0
for i in range(self._vertices):
if self._adjMat[u][i] != 0:
count += 1
return count
def display(self):
"""
Display the adjacency matrix of the graph.
"""
print(self._adjMat)
def bfs(self, source):
"""
Perform Breadth-First Search (BFS) starting from a given source vertex.
Parameters:
----------
source : int
The starting vertex for BFS.
"""
i = source
q = deque()
visited = [0] * self._vertices
print(i, end=' - ')
visited[i] = 1
q.append(i)
while q:
i = q.popleft()
for j in range(self._vertices):
if self._adjMat[i][j] == 1 and visited[j] == 0:
print(j, end=' - ')
visited[j] = 1
q.append(j)
def dfs(self, source):
"""
Perform Depth-First Search (DFS) starting from a given source vertex.
Parameters:
----------
source : int
The starting vertex for DFS.
"""
if self._visited[source] == 0:
print(source, end=' - ')
self._visited[source] = 1
for j in range(self._vertices):
if self._adjMat[source][j] == 1 and self._visited[j] == 0:
self.dfs(j)
# Example usage
G = Graph(7)
print('Graph Adjacency Matrix')
G.display()
G.insert_edge(0, 1)
G.insert_edge(0, 5)
G.insert_edge(0, 6)
G.insert_edge(1, 0)
G.insert_edge(1, 2)
G.insert_edge(1, 5)
G.insert_edge(1, 6)
G.insert_edge(2, 3)
G.insert_edge(2, 4)
G.insert_edge(2, 6)
G.insert_edge(3, 4)
G.insert_edge(4, 2)
G.insert_edge(4, 5)
G.insert_edge(5, 2)
G.insert_edge(5, 3)
G.insert_edge(6, 3)
print('Graph Adjacency Matrix')
G.display()
print('Number of Vertices:', G.vertices_count())
print('Number of Edges:', G.edge_count())
print('Outdegree of Vertex 2:', G.outdegree(2))
print("\n--- BFS ---")
G.bfs(0)
print("\n--- DFS ---")
G.dfs(0)