# Tag Info

5

As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS). Proposition 1: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS ...

3

Let's show first that such an edge might belong to a cycle, by considering the case of a square $ab,bc,cd,da$. We will show that $ab$ could belong to BFS trees starting at arbitrary vertices. This is clear if BFS is started from $a$ or from $b$. If BFS is started from $c$, it could enqueue $a,d$ in this order; dequeue $a$; then enqueue $b$. Similarly, if BFS ...

2

I think this is best handled by contacting the lecturer, but here are four reasons. A Kain0_0 remarks, your solution is recursive, while his isn't. Didactic considerations behind this might be: Recursion is hard for some students. Perhaps it hasn't been taught at this point in the course, or is considered an unnecessary burden. Most BFS implementations in ...

2

If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order. I'll assume we have removed all useless symbols and cycles from the grammar. If it is finite and free of useless symbols and cycles, then it should not contain any recursion. Let $N(A)$ denote the number of sentences ...

1

Your algorithm doesn't work. BFS doesn't explore all paths. One of the paths you haven't explored might have much higher strength than all the ones you have explored. There exists a counterexample with only four or five nodes (depending on the exact details of how you implement the steps outlined in your overview). I'll let you have the fun of finding it....

1

To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time. It follows ...

1

BFS (or Breadth-First Search) from its name implies that it will search for the destination along the breadth. That means it looks at all the current possible routes ie nodes connected to the current one and divides itself into all of those. Basically, at every junction, it divides itself and continues down that path until it encounters the destination node. ...

1

First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are generating all paths, each path visits at most all the nodes once, so the time complexity of your algorithm would actually be O(PN) where P is the total number ...

1

First of all your question is quite confusing: There is at least one edge $w \in V$ Is it an edge or a vertex? Maybe it would be easier for you to look at some edge $(u,v) \in E$ and think about the moment in time $\tau$, when the BFS algorithm reached either $u$ or $v$ for the first time (it could reach them both at the same time).

1

The maximum degree of a vertex is $25n$, since this is the number of words which can be obtained by changing a single character. I'm not sure how you get to $26^n$. You are writing "$4$ is more than $O(n)$" (where $n=2$). This is completely meaningless, since $O(n)$ stands for a function bounded by $Cn$ for some unknown constant $C$. If you don't know the ...

1

I recommend you to take the same approach as I did to draw my conclusions: take a graphical approach to see the differences and drawbacks. For that, do the following: Comment out all print lines except print("Frontier:", frontier) Then do python program.py > version1.txt, modify your program such that it represents verison 2, and then do python program....

Only top voted, non community-wiki answers of a minimum length are eligible