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

- 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.

- 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.

- How can I implement an undirected graph in Python?

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

- 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.

- 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.