Question 1

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?

Accepted Answer

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

Question 2

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?

Accepted Answer

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

Question 3

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.

Accepted Answer

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)

Question 4

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.

Accepted Answer

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)

Question 5

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});`

Accepted Answer

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

Course: Computer science theory > Unit 1

Analysis of breadth-first search

Want to join the conversation?