Lekcja – Zapis grafu za pomocą macierzy
V = ['Princess', 'Dwarf1', 'Dwarf2', 'King', 'Queen', 'Hunter']
E = [
['Princess', 'Dwarf1'], ['Princess', 'Dwarf2'], ['Dwarf1', 'Dwarf2'],
['Princess', 'King'], ['Princess', 'Queen'], ['Princess', 'Hunter'],
['King', 'Queen'], ['King', 'Hunter'], ['Queen','Hunter']
]
matrix = [
[0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0],
[1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 1, 0]
]
def who_knows_person(person, V, matix):
friends = []
idx = V.index(person)
for i in range(len(V)):
if matrix[idx][i] == 1:
friends.append(V[i])
return friends
print(who_knows_person('Princess', V, matrix))
print('-'*30)
V = [1, 2, 3, 4]
E = [(1,2), (1,3),(2,4),(3,4)]
matrix = [
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
# show nodes reachable from node start
start = 1
for i in range(len(V)):
if matrix[V.index(start)][i] == 1:
print(V[i])
print([V[i] for i in range(len(V)) if matrix[V.index(start)][i] == 1])
Lab
V = ["mouse", "keyboard", "computer", "monitor","printer", "scanner"]
E = [ (0,2), (1,2), (2,3), (2,4), (5,2)]
def translate_to_matrix(V, E):
# create empty matrix
matrix = []
for row in range(len(V)):
matrix.append([0 for _ in range(len(V))])
for i1, i2 in E:
matrix[i1][i2] = 1
return matrix
my_matrix = translate_to_matrix(V, E)
for row in my_matrix:
print(row)
# second option:
V = ["mouse", "keyboard", "computer", "monitor", "printer"]
E = [ {0,2}, {1,2}, {2,3}, {2,4}]
def translate_to_matrix(V, E):
matrix = []
for v1 in range(len(V)):
matrix.append( [ 1 if {v1, v2} in E else 0 for v2 in range(len(V)) ] )
return matrix
my_matrix = translate_to_matrix(V, E)
for row in my_matrix:
print(row)