Data structure cheat sheet: Difference between revisions
Jump to navigation
Jump to search
Hoppinglife (talk | contribs) |
Hoppinglife (talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 109: | Line 109: | ||
Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix. | Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix. | ||
=== Traverse === | === Traverse === | ||
=== | * BFS is the simplest traverse one can conduct on a graph. Useful to do the basic shortest path discoveries. | ||
=== | * DFS is useful for establishing strongly connected components. It can also be used to classify edges in the graph (tree edge, back, forward, cross). | ||
=== Topological sort and Strongly Connected Components === | |||
* As each vertex is finished, insert it into the front of a linked list. | |||
* For directional graphs, its strongly connected graph can be computed in the following way: 1) do a DFS to establish topological order, 2) do the DFS on the transposed graph using the order in reverse order of its finishing time. | |||
=== Minimum Spanning Trees === | |||
* Kruskal: add the lowest edge that connected different components. <math>O(E lg V)</math> | |||
* Prim: find the light edge between the sites. <math>O(E lg V)</math> | |||
=== Shortest Paths === | |||
* Bellman-Ford: relax each edge V times, O(VE). | |||
* DAG can be done in O(V+E) time, by looking at it in topological order. | |||
* Dijkstra: relax all the edges of the newly visited node. O(V^2) | |||
== Dynamic Programming == | == Dynamic Programming == | ||
| Line 118: | Line 128: | ||
== Searching == | == Searching == | ||
=== Depth-first search / backtracking === | |||
=== Breath-first search === | |||
== Mathematical Problems == | == Mathematical Problems == | ||