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:

• Connectivity: An undirected graph is connected if there is a path between any two nodes in the graph.
• Degree: The degree of a node in an undirected graph is the number of edges connected to that node.
• Cycle: A cycle is a path in the graph that starts and ends at the same node and does not visit any other node more than once.

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.nodes.add(node)
        self.edges[node] = set()

    def add_edge(self, node1, node2):
        self.edges[node1].add(node2)
        self.edges[node2].add(node1)

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()
    visited.add(start)
    print(start)
    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:

A
B
C
D

Conclusion

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.

FAQs

1. What is the difference between a directed graph and an undirected graph?

• In a directed graph, the edges have a direction, while in an undirected graph, they do not.

2. What is the degree of a node in an undirected graph?

• The degree of a node is the number of edges connected to that node.

3. How can I implement an undirected graph in Python?

• You can use a dictionary or a class to represent an undirected graph in Python.

4. What is a cycle in an undirected graph?

• A cycle is a path in the graph that starts and ends at the same node and does not visit any other node more than once.

5. What is depth-first search?

• Depth-first search is a graph traversal algorithm that visits all the nodes in a graph by exploring as far as possible along each branch before backtracking.