Types of Graphs
Graphs are incredibly versatile and can be used to model various types of relationships and connections. In this section, we will explore some of the common types of graphs.
1. Directed Graphs
A directed graph, also known as a digraph, is a type of graph in which edges have a specific direction. These edges represent a one-way relationship between nodes. For example, consider a graph that represents a transportation network. Each node represents a city, and the directed edges represent one-way roads between cities.
1if __name__ == '__main__':
2 # Example code to create a directed graph
3 class DirectedGraph:
4 def __init__(self):
5 self.graph = {}
6
7 def add_edge(self, source, destination):
8 if source not in self.graph:
9 self.graph[source] = []
10 self.graph[source].append(destination)
11
12 # Create a directed graph object
13 dg = DirectedGraph()
14
15 # Add edges to the graph
16 dg.add_edge('A', 'B')
17 dg.add_edge('B', 'C')
18 dg.add_edge('C', 'D')
19
20 print('Directed Graph:', dg.graph)2. Undirected Graphs
An undirected graph is a graph in which edges do not have a specific direction. The edges represent bidirectional relationships between nodes. For example, consider a graph that represents a social network. Each node represents a person, and the edges represent friendships between people.
1if __name__ == '__main__':
2 # Example code to create an undirected graph
3 class UndirectedGraph:
4 def __init__(self):
5 self.graph = {}
6
7 def add_edge(self, source, destination):
8 if source not in self.graph:
9 self.graph[source] = []
10 self.graph[source].append(destination)
11
12 if destination not in self.graph:
13 self.graph[destination] = []
14 self.graph[destination].append(source)
15
16 # Create an undirected graph object
17 ug = UndirectedGraph()
18
19 # Add edges to the graph
20 ug.add_edge('A', 'B')
21 ug.add_edge('B', 'C')
22 ug.add_edge('C', 'D')
23
24 print('Undirected Graph:', ug.graph)3. Weighted Graphs
A weighted graph is a graph in which each edge is assigned a weight or cost. These weights can represent various factors such as distances, costs, or capacities. Weighted graphs are commonly used in applications such as route planning, network analysis, and optimization problems.
1if __name__ == '__main__':
2 # Example code to create a weighted graph
3 class WeightedGraph:
4 def __init__(self):
5 self.graph = {}
6
7 def add_edge(self, source, destination, weight):
8 if source not in self.graph:
9 self.graph[source] = []
10 self.graph[source].append((destination, weight))
11
12 # Create a weighted graph object
13 wg = WeightedGraph()
14
15 # Add edges to the graph
16 wg.add_edge('A', 'B', 5)
17 wg.add_edge('B', 'C', 10)
18 wg.add_edge('C', 'D', 15)
19
20 print('Weighted Graph:', wg.graph)4. Cyclic Graphs
A cyclic graph is a graph that contains at least one cycle, which is a path that starts and ends at the same node. Cyclic graphs can be problematic in certain algorithms as they can result in infinite loops. It's important to detect and handle cycles appropriately in such cases.
1if __name__ == '__main__':
2 # Example code to create a cyclic graph
3 class CyclicGraph:
4 def __init__(self):
5 self.graph = {}
6
7 def add_edge(self, source, destination):
8 if source not in self.graph:
9 self.graph[source] = []
10 self.graph[source].append(destination)
11 self.graph[destination] = [source]
12
13 # Create a cyclic graph object
14 cg = CyclicGraph()
15
16 # Add edges to the graph
17 cg.add_edge('A', 'B')
18 cg.add_edge('B', 'C')
19 cg.add_edge('C', 'A')
20
21 print('Cyclic Graph:', cg.graph)These are just a few examples of the types of graphs that exist. Depending on the problem at hand, you may need to use a specific type of graph or a combination of multiple types to accurately model the relationships and connections.
xxxxxxxxxxif __name__ == '__main__': # Python code here # Example code to create an undirected graph class Graph: def __init__(self): self.graph = {} def add_edge(self, source, destination): if source not in self.graph: self.graph[source] = [] self.graph[source].append(destination) if destination not in self.graph: self.graph[destination] = [] self.graph[destination].append(source) # Create a graph object g = Graph() # Add edges to the graph g.add_edge('A', 'B') g.add_edge('B', 'C') g.add_edge('C', 'D') g.add_edge('D', 'E') print('Graph:', g.graph)