Please help with this question about graphs(Algorithms). Thank you! Give pseudo-
ID: 3687556 • Letter: P
Question
Please help with this question about graphs(Algorithms). Thank you!
Give pseudo-code for the following problems, making sure to state all the relevant data structures and representations that you assume. Give a linear-time algorithm for determining whether a given graph is bipartite. Give an O(V)-time algorithm for determining whether a given graph contains a cycle. Note that your algorithm should run in the allotted time for all graphs, whether sparse or dense. Give an algorithm to find the minimum number of edges that must be removed from a given undirected graph in order to make it acyclic. The diameter of a tree T is the length of the longest path between two nodes in T. Describe an efficient algorithm for computing the diameter of T with V nodes and E edges.Explanation / Answer
a.
function graph-coloring(G)
Input: Graph G Output: returns true if the graph is bipartite
false otherwise
for all v V:
visited(v)= false
color(v) = GREY
while s V : visited(s) = f alse
visited(s) = true
color(s) = WHITE
S = [s] (stack containing v)
while S is not empty
u = pop(S)
for all edges (u,v) E:
if visited(v) = false:
visited[v] = true
push(S,v)
if color(v) = GREY
if color(u) = BLACK:
color(v) = WHITE
if color(u) = WHITE:
color(v) = BLACK
else if color(v) = WHITE:
if color(u) 6= BLACK:
return false
else if color(v) = BLACK:
if color(u) 6= WHITE:
return false
return true
b.
c.
procedure BellmanFord(list vertices, list edges, vertex source)
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges:// Try relaxing the edge from u to v
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance: // uv gets relaxed
v.distance := u.distance + uv.weight
d.