# Graph implementation

## Graphs Implementation In Python

Graphs are a fundamental data structure in computer science that represent a collection of nodes and edges. Nodes typically represent entities, and edges represent relationships between these entities. Graphs can be directed or undirected, and edges can have weights.

There are several ways to implement graphs in Python. I’ll provide a basic implementation using a class-based approach for an undirected graph.

`Step By Step Implementation Of Graph`

Creating and working with a graph involves several steps. I’ll outline a step-by-step approach for creating and interacting with a basic undirected graph in Python.

Step 1: Define the Graph Class

`class Graph:    def __init__(self):        self.graph = {}    def add_node(self, node):        if node not in self.graph:            self.graph[node] = []    def add_edge(self, node1, node2):        self.add_node(node1)        self.add_node(node2)        self.graph[node1].append(node2)        self.graph[node2].append(node1)    def display(self):        for node in self.graph:            print(f"{node}: {', '.join(map(str, self.graph[node]))}")`

Step 2: Create an Instance of the Graph

`g = Graph()`

Step 3: Add Nodes to the Graph

`g.add_node(1)g.add_node(2)g.add_node(3)g.add_node(4)`

Step 4: Add Edges to the Graph

`g.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(2, 4)g.add_edge(3, 4)`

Step 5: Display the Graph

`g.display()`

The output should be:

`1: 2, 32: 1, 43: 1, 44: 2, 3`

Step 6: Implement Graph Traversal (Optional)

You can implement depth-first search (DFS) or breadth-first search (BFS) to traverse the graph:

`def dfs(graph, start, visited=None):    if visited is None:        visited = set()    print(start)    visited.add(start)    for neighbor in graph[start]:        if neighbor not in visited:            dfs(graph, neighbor, visited)# Example DFS traversaldfs(g.graph, 1)`

Step 7: Extend Functionality (Optional)

Depending on your needs, you can extend the Graph class to handle directed graphs, weighted edges, shortest path algorithms, or other graph-related operations.

### Implementation Of Graph in Python

let’s go through the implementation of a simple undirected graph in Python using an adjacency list. We’ll start with the basic structure of the graph and then add functionality to add nodes, add edges, and display the graph.
`class Graph:    def __init__(self):        self.graph = {}    def add_node(self, node):        """Add a node to the graph."""        if node not in self.graph:            self.graph[node] = []    def add_edge(self, node1, node2):        """Add an undirected edge between two nodes."""        if node1 in self.graph and node2 in self.graph:            self.graph[node1].append(node2)            self.graph[node2].append(node1)        else:            print(f"One or both of the nodes ({node1}, {node2}) do not exist in the graph.")    def display(self):        """Display the graph as an adjacency list."""        for node in self.graph:            print(f"{node}: {', '.join(map(str, self.graph[node]))}")# Example usage:g = Graph()# Add nodesg.add_node(1)g.add_node(2)g.add_node(3)g.add_node(4)# Add edgesg.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(2, 4)g.add_edge(3, 4)# Display the graphg.display()`

#### Applications of Graphs:

Graphs have a wide range of applications, including:

• Social networks
• Transportation systems
• Recommendation systems
• Network analysis
• And many more

#### Graph Algorithms :

Various graph algorithms are used for solving specific problems.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others