Directed and non-directed graphs
Directed
Graph is strongly connected if there is a path fro any vertex to any other vertex
directed
indegree = # ingoing edges
outdegree = # outgoing edges
sum are equal
non-directed
Graph is connected if there is a path between any two vertices
non-directed
Degree of v is # neighbors
sum of degree = 2 * #edges
adjacency lists
adjacency matrix
BFS
Input
Graph G given by AL
vertex v in G
Output
Array dist[1,n]
, where dist[u]
is the length of the shortest path from v
to u
function BTS(v;;G[1..n])
dist[1..n] filled with inf
dist[v] = 0
queue Q empty
push v to Q
while Q not empty
u = Q.pop()
for w in G[u]
if dist[w] = inf
dist[w] = dist[u] + 1
push w to Q
return dist
can also be done by DP






网友评论