Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Queue:
- def __init__(self, n):
- self.S = [None] * n
- self.n = n
- self.elements = 0
- self.head = 0
- def enqueue(self, x):
- self.S[(self.head + self.elements) % self.n] = x
- self.elements += 1
- def dequeue(self):
- a = self.S[self.head]
- self.head = (self.head + 1) % self.n
- self.elements -= 1
- return a
- def is_empty(self):
- return self.elements == 0
- class pkt:
- def __init__(self, nr):
- self.nr = nr
- self.visited = False
- self.d = -1
- self.parent = None
- class graf:
- def __init__(self):
- self.arr = []
- def BFS(G, s):
- Q = Queue(len(G))
- Graf = graf()
- F = [[] for _ in range(len(G))]
- for i in range (len(G)):
- F[i] = [None] * (2)
- for i in range(len(G)):
- x = pkt(i)
- Graf.arr.append(x)
- Graf.arr[s].d = 0
- Graf.arr[s].visited = True
- Q.enqueue(Graf.arr[s])
- while not Q.is_empty():
- u = Q.dequeue()
- for i in range(len(G)):
- if G[u.nr][i] == 1: # znaczy że z wierzchołka u idzie krawędz do wierzchołka i
- if not Graf.arr[i].visited:
- Graf.arr[i].visited = True
- Graf.arr[i].d = u.d + 1
- Graf.arr[i].parent = u.nr
- Q.enqueue(Graf.arr[i])
- for i in range(len(G)):
- F[i][0]=Graf.arr[i].parent
- F[i][1]=Graf.arr[i].d
- return F
- G = [[0, 1, 1, 0],
- [0, 0, 0, 1],
- [0, 1, 0, 1],
- [0, 0, 0, 0]]
- print( BFS(G,0) )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement