Main content
Computer science theory
Analysis of breadth-first search
How long does breadth-first search take for a graph with vertex set and edge set ? The answer is time.
Let's see what time means. Assume for the moment that , which is the case for most graphs, especially those for which we run breadth-first search. Then . Because we ignore constant factors in asymptotic notation, we see that when , really means . If, however, we have , then , and so really means . We can put both cases together by saying that really means . In general, if we have parameters and , then really means .
(Note, by the way, that a graph is connected if there is a path from every vertex to all other vertices. The minimum number of edges that a graph can have and still be connected is . A graph in which is called a free tree.)
How is it that breadth-first search runs in time? It takes time to initialize the distance and predecessor for each vertex ( time, actually). Each vertex is visited at most one time, because only the first time that it is reached is its distance time visiting vertices.
null
, and so each vertex is enqueued at most one time. Since we examine the edges incident on a vertex only when we visit from it, each edge is examined at most twice, once for each of the vertices it's incident on. Thus, breadth-first search spends This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Want to join the conversation?
- I'm a little confused as to why most graphs have more edges than vertices? Based on my understanding of a graph, a single edge (in a simple graph) connects two vertices, so why would there be more edges than vertices on average?(9 votes)
- Assume we are talking about a connected graph. i.e. from any vertex in the graph I am able to eventually reach all the other vertices in the graph by following edges.
A simple way we could connect n vertices with edges is start from the first vertex and add an edge going to the next vertex, then from the second vertex add an edge going to the 3rd vertex, ... from the n-1 vertex add an edge going to the nth vertex.
We would already have n-1 edges !
In fact for ALL planar graphs with non-crossing edges we have the Euler characteristic which says:
V+F-E=2
where V=# of vertices, F=# of faces, E=# of edges
We always have at least one face, the outer face.
So for our planar graph we have:
V+F-E=2
E = V+F-2
So a minimally connected planar graph, with no cycles (F=1) has:
E= V + 1 - 2= V -1
So if we include just 2 more edges than the most minimally connected graph possible we have more edges than vertices
Most interesting graphs we deal with are connected and contain cycles so often the graphs we work with have more edges than vertices.
Hope this makes sense(26 votes)
- Could someone please elaborate on what is a free tree?
I find the description in this page a little confusing.
*A graph in which ∣E∣=∣V∣−1|E| = |V|-1∣E∣=∣V∣−1 is called a free tree.)*
I have searched the web but all I have been able to find is that a free tree is a tree without a root, no mention of formulas involving |E| or |V|.
By the way I don't understand either this other statement:
*(Note, by the way, that a graph is connected if there is a path from every vertex to all other vertices. The minimum number of edges that a graph can have and still be connected is ∣V∣−1.*
If I think of four vertexes shaped like a square, the minimum number of vertexes that can joing each node to all other vertexes is 4 sides + 2 diagonals = 6 that != 4 - 1
What is there that I am missing?(5 votes)- If you can get from vertex A to vertex B by travelling over a sequence of edges, then we say that there is a path between them.
i.e. a path is an alternating sequence of vertices and edges that tells you the edges you have to traverse to get to from vertex A to vertex B
If there is a path between every pair of vertices, then we say the graph is connected. This does not mean that every vertex has an edge connecting it to every other vertex.
e.g.
This graph is connected:1 - 2
| |
3 - 4
e.g.
A path from vertex 1 to vertex 2 is: 1, (1,2), 2
A path from vertex 1 to vertex 3 is: 1, (1,3), 3
A path from vertex 1 to vertex 4 is: 1, (1,2), 2, (2,4), 4
A path from vertex 2 to vertex 3 is: 2, (2,4), 3, (3,4), 4
A path from vertex 2 to vertex 4 is: 2, (2,4), 4
A path from vertex 3 to vertex 4 is: 3, (3,4), 4
Since it is an undirected graph, a path from vertex A to vertex B can be reversed to obtain a path from vertex B to vertex A.
So, we have shown that there is a path between every pair of vertices.
This graph is not connected:1 - 2 5 - 6
| |
3 - 4
No matter how hard you try, you can't find a path between vertex 1 and vertex 5. Thus the graph is not connected.
A cycle is a path with no repeated edges, that repeats a vertex more than once.
This graph is connected and has a cycle:1 - 2
| |
3 - 4
A cycle: 1, (1,2), 2, (2,4), 4, (3,4), 3, (1,3), 1 (It starts and ends at vertex 1)
This graph is connected and does not have any cycles:1 - 2
|
3 - 4
|
5
A connected graph with no cycles is called a tree.
A tree is a minimally connected graph.
For a tree : |E| = |V| - 1
This is true for any tree, not just free trees.
Where the article says:
"A graph in which |E| = |V|-1 is called a free tree."
it should say:
"A connected graph in which |E| = |V|-1 is called a tree."
With regards to free trees:
Some people will distinguish between rooted trees and free trees.
In a free tree no vertex is specified as the root.
In a rooted tree, you pick a vertex as a root, and let all the other vertices hang below it.
This gives the idea of depth. The root at the top has the lowest depth, and vertices at the bottom have the highest depth.
It also gives the idea of a parent-child relation ship between neighbours (if a single edge connects vertices they are neighbours)
The neighbour above a vertex is its parent. The neighbours below a vertex are its children.
Neighbours at the same depth in a tree are siblings.
Suppose we have this tree:1 - 2 - 3 - 5
| |
6 4
|
7 - 8
|
9
We could make it into a rooted tree by choosing vertex 1 as a root and letting the other vertices hang below it:1
/ \
6 2
/ /
7 3
/ \ / \
9 8 4 5
Vertex 6 and vertex 2 are the children of vertex 1 and vertex 1 is the parent of both vertex 6 and vertex 2.
Vertex 6 is the sibling of vertex 2 (since they are at the same depth).
The rooted version has advantages over the free tree representation, including simpler searching and tree traversal.
Hope this makes sense(33 votes)
- Why BFS take a lot of space than DFS, although their space complexity is same? and why we implement BFS by only using queue? plzzzz tell me(3 votes)
- Is My understanding true,
* This is O(max(V,E)) because we are using an adjacency list to represent as a graph.
* If the graph is represented as adjacency matrix time complexity will be Θ(V^2), O(V*E)
* and if the graph, parent-child dependency is represented using links its O(V)
Please correct me if am wrong.(1 vote)- BFS on adjacency list is:
O(V+E) which is equivalent to O(max(V,E))
Why? Basically visit every vertex then look at every
edge attached to that vertex. So, we see every vertex once and every directed edge once.
For BFS on adjacency matrix: O(V^2)
Why? Basically visit every vertex then look at every
edge attached to that vertex. But to find edges attached to the vertex in the adjacency matrix we have to look at the entire row which has a width of V. So V * V or V^2.
O(V * E) while technically correct, in that O(V* E) is larger than O(V^2), is not the tightest bound that can be given. (It would not be the best answer). Remember that E can be as large as V * V.
And if it is BFS on a graph with parent child dependency i.e. representing a tree, you visit every node once giving you O(V)(3 votes)
- Regarding to the running time O(V+E) I suppose is in this way because for each vertex it's taking some edges (not all the edges) and this is the reason why is V+E but in a weird case that each vertex has the same quantity of edges. Should be O(V*E)? I believe this case wouldn't be a graph but it's just a doubt I have. Thanks in advance.(1 vote)
- Suppose each vertex has the same number of edges x, then x = E/V
The algorithm visits each vertex and examines its x edges
So the algorithm would examine V * x edges
But V * x = V * E/V = E, so it would still be O(V+E)(3 votes)
- At a loss for why I keep receiving a property error for predecessor (then again, I'm novice to JavaScript ). I'm assuming the way I'm trying to access the property is the issue. Please see the below. (Deleted the lower half of the code to focus on my issue; ellipse'd the other portion of code to avoid spoilers)
/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
this.items = [];
};
Queue.prototype.enqueue = function(obj) {
this.items.push(obj);
};
Queue.prototype.dequeue = function() {
return this.items.shift();
};
Queue.prototype.isEmpty = function() {
return this.items.length === 0;
};
/*
* Performs a breadth-first search on a graph
* @param {array} graph - Graph, represented as adjacency lists.
* @param {number} source - The index of the source vertex.
* @returns {array} Array of objects describing each vertex, like
* [{distance: _, predecessor: _ }]
*/
var doBFS = function(graph, source) {
var bfsInfo = [];
//Sets all nodes' distance and predecessor to null
for (var i = 0; i < graph.length; i++) {
bfsInfo[i] = {
distance: null,
predecessor: null };
}
bfsInfo[source].distance = 0; //Vertex 3 has no distance from a predecessor
var queue = new Queue();
queue.enqueue(source);
// Traverse the graph
// As long as the queue is not empty:
// Repeatedly dequeue a vertex u from the queue.
//
// For each neighbor v of u that has not been visited:
// Set distance to 1 greater than u's distance
// Set predecessor to u
// Enqueue v
//
// Hint:
// use graph to get the neighbors,
// use bfsInfo for distances and predecessors
while (!queue.isEmpty()) {
var u = queue.dequeue(); // u = 3
for (var i = 0; i < graph.length; i++) {
var v = graph[u][i]; //neighbor = graph[3][0] = 2 = v
if(bfsInfo[v].predecessor === null){
….
}
}
}
return bfsInfo;
};(2 votes) - how can I prove that space required by BFS is linear function while BFS is exponential function?(2 votes)
- why does the l.e. is= to i.L.m what does that equal to time?(1 vote)
- Why does the major l.e and l.m form do that equals to the time?(1 vote)
- What's wrong with my code ?
/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
this.items = [];
};
Queue.prototype.enqueue = function(obj) {
this.items.push(obj);
};
Queue.prototype.dequeue = function() {
return this.items.shift();
};
Queue.prototype.isEmpty = function() {
return this.items.length === 0;
};
/*
* Performs a breadth-first search on a graph
* @param {array} graph - Graph, represented as adjacency lists.
* @param {number} source - The index of the source vertex.
* @returns {array} Array of objects describing each vertex, like
* [{distance: _, predecessor: _ }]
*/
var doBFS = function(graph, source) {
var bfsInfo = [];
for (var i = 0; i < graph.length; i++) {
bfsInfo[i] = {
distance: null,
predecessor: null };
}
bfsInfo[source].distance = 0;
var queue = new Queue();
queue.enqueue(source);
// Traverse the graph
while (!queue.isEmpty()) {
var vertex = queue.dequeue();
for (var u=0;u<graph[vertex].length;u++) {
var neighbor = graph[vertex][u];
if (bfsInfo[neighbor].predecessor === null) {
if(neighbor !== bfsInfo[vertex].predecessor){
bfsInfo[neighbor].distance = bfsInfo[vertex].distance + 1;
bfsInfo[neighbor].predecessor = vertex;
queue.enqueue(neighbor);
}
}
}
}
// As long as the queue is not empty:
// Repeatedly dequeue a vertex u from the queue.
//
// For each neighbor v of u that has not been visited:
// Set distance to 1 greater than u's distance
// Set predecessor to u
// Enqueue v
//
// Hint:
// use graph to get the neighbors,
// use bfsInfo for distances and predecessors
return bfsInfo;
};
var adjList = [
[1],
[0, 4, 5],
[3, 4, 5],
[2, 6],
[1, 2],
[1, 2, 6],
[3, 5],
[]
];
var bfsInfo = doBFS(adjList, 3);
for (var i = 0; i < adjList.length; i++) {
println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}
Program.assertEqual(bfsInfo[0], {distance: 4, predecessor: 1});
Program.assertEqual(bfsInfo[1], {distance: 3, predecessor: 4});
Program.assertEqual(bfsInfo[2], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[3], {distance: 0, predecessor: null});
Program.assertEqual(bfsInfo[4], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[5], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[6], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[7], {distance: null, predecessor: null});(1 vote)- You should only need one if statement inside the for loop.
The two nested if statements that are in the code above will not work on a general graph
i.e. it is only meeting the asserts on this graph by chance, not because the if statements are correct.
Think about how we can tell if we have visited a node or not. Double check to make sure that method doesn't have problems when you look at the source node.
Good Luck(2 votes)
- Can anyone tell me what's wrong with my code?
var Queue = function() {
this.items = [];
};
Queue.prototype.enqueue = function(obj) {
this.items.push(obj);
};
Queue.prototype.dequeue = function() {
return this.items.shift();
};
Queue.prototype.isEmpty = function() {
return this.items.length === 0;
};
/*
* Performs a breadth-first search on a graph
* @param {array} graph - Graph, represented as adjacency lists.
* @param {number} source - The index of the source vertex.
* @returns {array} Array of objects describing each vertex, like
* [{distance: _, predecessor: _ }]
*/
var doBFS = function(graph, source) {
var bfsInfo = [];
for (var i = 0; i < graph.length; i++) {
bfsInfo[i] = {
distance: null,
predecessor: null };
}
bfsInfo[source].distance = 0;
var queue = new Queue();
queue.enqueue(source);
// Traverse the graph
// As long as the queue is not empty:
// Repeatedly dequeue a vertex u from the queue.
while(!queue.isEmpty){
var vertex = queue.dequeue();
for(var i = 0; i<graph[vertex].length; i++){
var toVertex = graph[vertex][i];
if(bfsInfo[toVertex].distance === null){
bfsInfo[toVertex].distance = bfsInfo[vertex].distance +1;
bfsInfo[toVertex].predecessor = vertex;
queue.enqueue(toVertex);
}
}
}
// For each neighbor v of u that has not been visited:
// Set distance to 1 greater than u's distance
// Set predecessor to u
// Enqueue v
//
// Hint:
// use graph to get the neighbors,
// use bfsInfo for distances and predecessors
return bfsInfo;
};
var adjList = [
[1],
[0, 4, 5],
[3, 4, 5],
[2, 6],
[1, 2],
[1, 2, 6],
[3, 5],
[]
];
var bfsInfo = doBFS(adjList, 3);
for (var i = 0; i < adjList.length; i++) {
println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}(1 vote)queue.isEmpty
is a function so to call it you need to usequeue.isEmpty()
(1 vote)