Summary of Class 15 DAG -- Topological Sorting (USACO 4.4)
“To improve is to change; to be perfect is to change often.”
― Winston S. Churchill
Version Control (or Revision control or source control):
Version Control System (VCS)
Concurrent Version System (CVS)
Subversion (SVN)
git command:
git add . (or file)
git commit -m "msg"
git push origin <branch-name>
Review of SCC, DFS, BFS
SCC:
A digraph is strongly connected if every two vertices are mutually reachable.
A strong component of a digraph G is a maximal strongly connected subdigraph of G. Equivalently, a strong component is a subdigraph induced on a maximal set of mutually reachable vertices.
Graph DFS: stack-based: (for loop with visited vertices)
tree edge,
forward edge
back edge
cross edge
Graph BFS: queue-based: (for loop with visited vertices)
if all vertices with in-degree 0 are queued, we can do it without for loop.
DAG - directed acyclic graph
A directed acyclic graph (DAG), is a finite directed graph with no directed cycles. That is, it consists of finitely many vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again.
DFS based Topological Sorting
My explanation:
1. visited all the vertices which I can reach, and put me on top of those vertices
2. Print all node from top to bottom.
Kahn’s algorithm for Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
Fact:
A DAG G has at least one vertex with in-degree 0 and one vertex with out-degree 0.
Detailed steps:
1: Compute in-degree for each of the vertex present in the DAG and initialize the count of visited nodes as 0.
2: Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue operation)
3: Repeatly remove a vertex from the queue (Dequeue operation)
while(!q.empty()):
Increment count of visited nodes by 1.
for (all its neighboring nodes):
Decrease in-degree by 1
If in-degree of a neighboring nodes is reduced to zero, then add it to the queue
4: If count of visited nodes is not equal to the number of nodes in the graph then the topological sort is not possible for the given graph.
My explanation:
1. queue all vertices with degree 0; (like initialization)
2. decrease in-degree if there is a connection and push the vertex with 0 (like processing)
All Topological Sorts of a Directed Acyclic Graph
backtracking method:
1. Initialize all vertices as unvisited.
2. Now choose vertex which is unvisited and has zero indegree and decrease indegree of all those vertices by 1 (corresponding to removing edges) now add this vertex to result and call the recursive function again and backtrack.
3. After returning from function reset values of visited, result and indegree for enumeration of other possibilities.
base case:
all vertices are visited
Key point of programming: (understand backtracking)
1. how to represent the result (vector of vector, or other data structure
2. based on Kahn's algorithm, but you can see it is a layered structure (sometimes layer is not very clear when there are multiple vertices with 0 at same time)
3. when there is a vertex with in-degree 0 and unvisited, process it by removing the edge (not really remove it, but decrease the in-degree)
3.1. After processing it, increase the in-degree (like adding the edge back, but there is no add-edge operation)
DP:
sum set
edit distance
Comments
Post a Comment