Faça uma função para obter todos os nós adjacentes (vizinhos) a um nó do grafo, dado que o grafo é representado por uma matriz de adjacências.
Passo 1
O enunciado pede uma função para, dado um grafo representado por uma matriz de adjacência, retornar todos os nós vizinhos de um nó especificado. O conteúdo é estruturas de grafos e operações sobre matrizes de adjacência.
Para resolver, vamos usar a propriedade de que, na matriz de adjacência, a linha correspondente ao nó contém 1 (ou valor não‐zero) nas colunas dos seus vizinhos. Assim, basta percorrer essa linha e coletar os índices onde há arestas.
Para resolver, vamos usar a propriedade de que, na matriz de adjacência, a linha correspondente ao nó contém 1 (ou valor não‐zero) nas colunas dos seus vizinhos. Assim, basta percorrer essa linha e coletar os índices onde há arestas.
Passo 2
Primeiro, garantimos que o índice do nó está dentro dos limites da matriz. Se o grafo tem n nós, os índices válidos vão de 0 a n−1.
Depois, percorremos todos os possíveis nós j de 0 até n−1, verificando se o elemento matriz[node][j] é diferente de zero. Se for, significa que existe aresta de node para j, logo j é vizinho de node.
Depois, percorremos todos os possíveis nós j de 0 até n−1, verificando se o elemento matriz[node][j] é diferente de zero. Se for, significa que existe aresta de node para j, logo j é vizinho de node.
Passo 3
Por fim, retornamos a lista construída com todos os vizinhos encontrados.
Resposta
def get_neighbors(adj_matrix, node):
# Verifica se o nó está dentro dos limites
n = len(adj_matrix)
if node < 0 or node >= n:
raise IndexError(“Índice de nó inválido”)
# Verifica se o nó está dentro dos limites
n = len(adj_matrix)
if node < 0 or node >= n:
raise IndexError(“Índice de nó inválido”)
neighbors = []
# Percorre a linha do nó na matriz de adjacência
for j in range(n):
if adj_matrix[node][j] != 0:
neighbors.append(j)
return neighbors