Chinese In North America(北美华人e网)

注册
发新话题 回复该主题

11#

Graph: Topology

Topology algorithms are pretty much all about DFS post-order (reaching to the leaf nodes, processing children before processing current node), aiming to identify structures, depths, connections of graphs.

Typical use scenarios include:

·       Finding shortest path

·       Finding distances along

·       Comparing of graph structure

Isomorphism

AHU algorithm uses “(“ and “)” to represent the structure (NOT the value) of tree nodes into a single string.

Sequence of operation

1.     Find “centers” of graph structure. Note that there can be multiple centers of the same graph.

a.     “center” means “the shortest path to all leaf nodes”

2.     Encode with DFS post order. Note that the child’s returned string shall be sorted lexicographically (with sort(stringV.begin(), stringV.end())

3.     Merge children’ string, wrap with “(“ and “)”

4.     For two trees, each of them can have multiple “centers”. Pick a center from one tree, but compare it with the other tree’s AHU strings with all centers iterated.


LCA: least common ancestor

There are a number of algorithms, including Tarjan’s offline. Below is an Eulerian tour/RMQ query example.

Eulerian tour

The key part is to build two arrays, size N = 2 * number of nodes + 1. This is because all nodes are visited twice other than the root (ASSUMING we have a left/right tree)

·       One array represents the depth of each node, which correlates to ancestor in parent/child relationship

o  The index of each element is the visit order to this node

o  The value of each array element is the depth

·       One array represents the sequence of visit, which represents the order of traversing all nodes

o  The index of each element is the visit order to this node, same as the depth queue.

o  The value of each element is node unique ID.

·       The requirement is to index each node with unique ID.


Sequence of operation

1.     Build depth & order arrays

a.     DFS pre-order AND post-order. This means the current node’s ID is appended to both DEPTH_ARRAY & VISIT_SEQ_ARRAY before & after EACH child.

2.     Cross reference

a.     Use unique node ID to find index from visit array. There can be multiple entries for each node since one single node can be visited multiple times

b.     Find min/max of the visit index

c.     Use visit index region in DEPTH_ARRAY and find min_level

d.     cross reference back from min_depth->visit order->node ID, which is the LCA node.

TOP
agree
0
disagree
0
12#

Topological sort

This is very useful to determine dependencies for events/programs/courses. Node parent->child edge can be modeled to present logical relationship.

The key note: topological orders are not unique!

Tree (in format of TreeNode) can use “cherry pick leaf nodes” (BFS into queue, and reserve order); graph (in connected edge format) can use DFS with a “visited” array. Note that not all nodes are connected with each other in graph, and thus this is an iterative process until all nodes are visited.

1.     Initialize a VISITED_ARRAY (size == N)

2.     Initialize a ORDER_ARRAY (size == N) and each element value is node’s ID

3.     Pick any node as START_NODE

4.     DFS post-order from START_NODE and save to a temp ordering array

5.     Copy temp ordering array to ORDER_ARRAY

6.     If there are unvisited nodes, repeat from step 3



Leetcode

630/207/210/1462

TOP
agree
0
disagree
0
13#

值得注意的地方:


1。考虑到graph的direction。如果是directional,生成edgeMap的时候,from parent to child。如果是non-directional,edgeMap加上parent to child, and child to parent.

2。考虑到graph可能包含cyclic dependency,用visited(vector<bool>, pre mark) 代表“a node is in the path before processing the current node", 用inList(vector<bool>, post mark)代表”a node has been marked as a child & already put to topOrderList"。如果只用visited,会导致stack overflow.

3。有些问题是找到2个nodes之间是否有联系。这时候就不能用topOrder 表示结构关系,用connectionMatrix代表reachability合适。

TOP
agree
0
disagree
0
14#

Shortest Path for DAG


The general solution for various SSSP issue is to keep an array MIN_DISTANCE_ARRAY (size == N) and run iteratively from any nodes to “relax” the distance to destination node.

·       Might also need to allocate a correspondent array for PREV_NODE

It is almost a “dynamic programming” model, since the distance to a node is “referred” from previously identified shorted path.

1.     Push the “start node distance == 0” into the array

2.     Loop from index = 0 for all nodes

3.     Get the edge cost from the current node to its child nodes

a.     “check and relax” the recorded distance in MIN_DISTANCE_ARRAY

4.     Find the next node (the first one picked is always the start node)

a.     It varies by algorithm which “next node” to choose

5.     Mark the node as VISITED once it’s picked by step 3. We don’t come to this node again, and the value of this node in MIN_DISTANCE_ARRAY is considered final.

TOP
agree
0
disagree
0
15#

SSSP based on Topological sort


With the ORDER_ARRAY by hand, it is easy to find the shorted path because we always know which node to pick in the next step. Therefore, step 4.a is simply to use the next node in ORDER_ARRAY

Note that this can be used to solve LONGEST path (NP hard) by inverting all weights with -1.

TOP
agree
0
disagree
0
16#

Dijkstra


The requirement is NOT to contain a negative edge; or, the algorithm loops forever.

Since there is no already-made ORDER_ARRAY, a priority_queue (based on min distance) is needed on the side in order to determine which node to be picked. Note that priority_queue is based on “largest node in the front”, we need to tweak the comparison function.

This is just like a BFS queue, except that when we take a node out from this queue, it always contains the smallest weight/distance.


Typical/Lazy

·       Step 4.a use a priority_queue; loop until this loop size == 0

·       Push calculated new values into the queue

·       A node is marked “visited” AFTER this is selected as the “from” node & all of its “to” nodes are relaxed

·       When “taking a min node”, compare this with the current MIN_DISTANCE_ARRAY. Drop if smaller, since a node can be visited from many paths.


Exit early with destination node

The worst condition is to visit ALL nodes before claiming the MIN_DISTANCE_ARRAY is final. However, in Step 5, if the current “from” node is the destination node, we can exit.

TOP
agree
0
disagree
0
17#

Bellman Ford


Not as ideal as Dijkstra; however, if there is a negative edge, Bellman Ford is the choice to find it.

Basic steps is roughly the same; however, this algorithm shall repeat twice (each iteration for all nodes loop) in order to identify nodes involved in a negative weight cycle.


Floyd Warshall


This is a classical DP-based solution, which gives the entire shortest path in two loops.

Similar to Bellman Ford, this runs the logic twice, in order to identify negative cycles.

The input is connection matrix (N*N), rather than the usually connection edges.

TOP
agree
0
disagree
0
18#

职场历史故事:Leetcode-18楼

TOP
agree
0
disagree
0
19#

notes都放这里,chats版的leetcode截图,还是放那边。华人网的dedup 功能不知道好不好,我就不重复发截图了。


谢谢大家,希望对大家有帮助。leetcode我买了一年,不过,应该不会继续碰这个了。我的下一段路程开始。


职场历史故事:Leetcode-19楼

TOP
agree
0
disagree
0
20#

LZ谢谢你,收藏了!

TOP
agree
0
disagree
0
发新话题 回复该主题