CSSE 230: Graph Analysis Homework

1. (15 points) Analyze the worst-case runtime of the following algorithm. Express the big-Oh runtime in terms of V and E, where applicable.

   
   procedure DFS_iterative(G, v) is
     let S be a stack
       S.push(v)
         while S is not empty do
           v = S.pop()
           if v is not labeled as discovered then label v as discovered
   	  for all edges from v to w in G.adjacentEdges(v) do
               S.push(w)
   

2. (15 points) Analyze the worst-case runtime of the following algorithm. Express the big-Oh runtime in terms of V and E, where applicable.

   
     procedure BFS(G, root) is
       let Q be a queue
       label root as explored
       Q.enqueue(root)
       while Q is not empty do
          v := Q.dequeue()
          if v is the goal then return v
          for all edges from v to w in G.adjacentEdges(v) do
            if w is not labeled as explored then
               label w as explored
               w.parent := v
               Q.enqueue(w)