Why is DFS O(m+n)

The basic algorithm for BFS:

set start vertex to visited

load it into queue

    while queue not empty

        for each edge incident to vertex

             if its not visited

                 load into queue

                 mark vertex

So I would think the time complexity would be:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

where v is vertex 1 to n




Then the sum

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

can be rewritten as

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

and the first group is O(N) while the other is O(E).

Increasing Stack Size in Visual Studio for Stack Overflow

For one of the questions in the Data Structures Program, Strongly Connected Components, there is a problem. The solution overflow:



It took me quite some time to find a solution to the stack overflow problem. I'm writing this to help everyone else facing the same problem. I saw a couple topics about this problem, but none of them offered a solution. My apologies in case I have missed it and this is a duplicate topic.

I've successfully solved the assignment using C++ with Visual Studio. To adjust the stack size you need to open Project -> "Your project's name" Properties. A dialog box opens. Find "Linker" on the left side. Now click "System". You need to change "Stack Reserve Size" and "Stack Commit Size". I put both to 400 million (it will probably work with a much lower number) and got my program to work.

Linux Question:

-Wl,-stack_size,0x10000000,-stack_addr,0xc0000000

Benchmark Code time

using this for C++ now:

#include <time.h>

double start = clock();

//Code Here

double time = (clock() - start)/ double(CLOCKS_PER_SEC)*1000; //Time in ms

std::cout << "Execution Time is: \t" << time << "ms" << std::endl;

Good Papers from Data Structures Class

1. Locality of Reference (Lists Vs Vectors)
http://en.wikipedia.org/wiki/Locality_of_reference

2. Least Recently Used Cache Algorithm

3. 

When to use Map Data Structure Over Vector

1) When an element is deleted from vector, all the elements below it have to be moved up.
When and element is inserted to vector, all the elements below it have to be moved down.

If you ave many add's and deleted in a program in a sequential list. It might be advantageous to cobnsider map. Map finds the element in logN time

2) When you ave sorted but you might not have all the elemnets in sequence.

e.g., you have edges of vertices 1,2,5,10 etc., it is better to store them in map.

Storing them in vector, you have store edges of 3,4,67,8,9 as empty.

Kosaraju Algorithm of DFS

Computing Strongly Connected Components:

http://scienceblogs.com/goodmath/2007/10/30/computing-strongly-connected-c/