Data structure cheat sheet: Difference between revisions
Jump to navigation
Jump to search
Hoppinglife (talk | contribs) |
Hoppinglife (talk | contribs) |
||
| 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 == | ||