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 = {}

self.edges[node] = set()

``````

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()
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.
1. 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.
1. How can I implement an undirected graph in Python?
• You can use a dictionary or a class to represent an undirected graph in Python.
1. 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.
1. 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.