Conteúdo do Curso
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
Graph Implementation
Now we will consider 3 types of graph implementation in Python.
Implementation using graphviz library
Graphviz is a powerful library for creating and visualizing graphs. It provides a simple and intuitive interface for generating graph visualizations, making it ideal for displaying complex graph structures.
import graphviz
class Graph:
def __init__(self):
self.graph = graphviz.Graph()
def add_vertex(self, vertex):
self.graph.node(str(vertex))
def add_edge(self, from_vertex, to_vertex):
self.graph.edge(str(from_vertex), str(to_vertex))
def get_neighbors(self, vertex):
neighbors = []
for edge in self.graph.body:
if edge.startswith(f'{vertex}" ->'):
neighbor = edge.split('-> ')[1].split(' [')[0]
neighbors.append(neighbor)
return neighbors
Implementation using adjacency matrix
An adjacency matrix is a square matrix used to represent a graph. In this matrix, rows and columns correspond to vertices (or nodes) in the graph, and the presence or absence of edges between vertices is represented by the values of the matrix elements.
This implementation provides a compact and efficient representation of graph data, especially for dense graphs with many connections.
Note
In a weighted graph, the values in the adjacency matrix can represent the weights of the edges. The matrix value may be either zero or infinity when there is no edge between vertices.
class Graph:
def __init__(self, size):
self.size = size
self.matrix = np.zeros((size, size), dtype=int)
def add_edge(self, from_vertex, to_vertex):
self.matrix[from_vertex][to_vertex] = 1
self.matrix[to_vertex][from_vertex] = 1
def add_vertex(self):
self.size += 1
new_matrix = np.zeros((self.size, self.size), dtype=int)
new_matrix[:self.size-1, :self.size-1] = self.matrix
self.matrix = new_matrix
def find_neighbors(self, vertex):
neighbors = []
for i in range(self.size):
if self.matrix[vertex][i] == 1:
neighbors.append(i)
return neighbors
Implementation using Python dictionary
Graph implementation using a dictionary is a popular approach in Python. In this implementation, the dictionary's keys represent the graph's vertices (or nodes), and the values represent each vertex's neighbors (or adjacent vertices). This allows for efficient access to the neighbors of a given vertex.
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, from_vertex, to_vertex):
if from_vertex in self.graph and to_vertex in self.graph:
self.graph[from_vertex].append(to_vertex)
self.graph[to_vertex].append(from_vertex) # For undirected graph
def get_neighbors(self, vertex):
if vertex in self.graph:
return self.graph[vertex]
else:
return []
Obrigado pelo seu feedback!