An undirected graph is a type of graph in which the edges do not have a defined direction. Instead, the edges represent a bi-directional relationship between two nodes. In this article, we will cover the basics of undirected graphs, their properties, and how to implement them in Python.

Definition of an Undirected Graph

An undirected graph is a set of nodes (also known as vertices) connected by a set of edges. Unlike directed graphs, the edges in an undirected graph do not have a direction, meaning that the relationship between nodes is symmetric. If there is an edge from node A to node B, there is also an edge from node B to node A.

Properties of Undirected Graphs

Undirected graphs have several important properties:

Implementing Undirected Graphs in Python

In Python, we can represent an undirected graph using a dictionary where the keys represent the nodes and the values represent the neighbors of each node. For example:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']

In this example, the graph has four nodes (A, B, C, and D) and six edges connecting them. Node A has edges to nodes B and C, node B has edges to nodes A, C, and D, and so on.

We can also implement an undirected graph using a class. Here’s an example:

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}

    def add_node(self, node):
        self.edges[node] = set()

    def add_edge(self, node1, node2):

In this code, we define a Graph class that has two attributes: a set of nodes and a dictionary of edges. We also define two methods: add_node and add_edge.

The add_node method adds a new node to the graph by adding it to the set of nodes and creating an empty set of edges for that node.

The add_edge method adds a new edge to the graph by adding the edge to the set of edges for both nodes.

Traversing an Undirected Graph

One common operation on undirected graphs is traversing the graph to visit all nodes. There are several algorithms for traversing a graph, such as breadth-first search (BFS) and depth-first search (DFS). In this example, we will use DFS to traverse the graph.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

In this code, we define a dfs function that takes in the graph and the starting node as arguments. We also define a visited set to keep track of the nodes we have already visited. If the visited set is not provided, we initialize it to an empty set.

We add the starting node to the visited set and print it. Then, for each neighbor of the starting node, we check if it has not been visited yet, and recursively call the dfs function on that neighbor with the updated visited set.

To use the dfs function on our example graph, we can call it like this:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
dfs(graph, 'A')

This will output:



Undirected graphs are an important type of data structure that can be used to model bi-directional relationships between nodes. In this article, we covered the definition of undirected graphs, their properties, and how to implement them in Python using a dictionary or a class. We also demonstrated how to traverse an undirected graph using depth-first search. With this knowledge, you should be able to apply undirected graphs to a variety of problems and algorithms.


  1. What is the difference between a directed graph and an undirected graph?
  1. What is the degree of a node in an undirected graph?
  1. How can I implement an undirected graph in Python?
  1. What is a cycle in an undirected graph?
  1. What is depth-first search?

Leave a Reply

Your email address will not be published. Required fields are marked *