Hello everyone!
In the lecture of Data Structure and Algorithm, we’ll continue to learn Chapter 7 Graph. Today we’re going to learn the traversal of graph.
In a data structure, if we can systematically visit nodes,
and every node is exactly visited once, we’ll call it traversal.
For the traversal of a graph, we should consider that
there are some problems on connectivity and problems on cycles in the graph.
So how can we solve these two problems? We can add a flag bit to each node.
When we visit a node in the graph, we can mark it as being visited.
If there are cycles in the graph, if we visit a node twice
and want to visit further, we can exit the node.
For the graph is not connected, if we scan
all the nodes and check whether this node is visited.
If it is not visited, we can start a
traversal from that node. Thus, we divide the entire graph into several different connected components
in order to visit. Let’s see the framework of traversal of graph. First, we
set all the elements in flag array to not visited.
Then we consider every node in the graph as a start node.
And we check whether this node is
visited. If visited, we’ll go on checking the next node. If not
we’ll start our special traversal algorithm from it.
Let’s see the DFS process.
In each DFS, we choose to start traversal from a node, and visit it.
And then we search all the nodes
connected to the current node recursively.
We repeat this process until
all the nodes which can be reachable from the start node are visited.
And then we choose another node
which is not visited as start node to start another DFS.
Then we form a lot of connected
rooted graph. And at last, all the nodes are visited.
Let’s see the process of DFS, it’s a
recursion process. If we can visit a node from the current node, we’ll visit it. From a to b to c to f.
If there are no more nodes we can visit from the current node, we’ll change to another node in the same level.
But because when we’re back to c from f,
there are no nodes in the same level we can change to, so we’re going
back to a and change to then next
element d. Then we have finished the process of DFS.
In the framework of DFS,
first we’ll mark the current node as being visited.
And we’re now visiting this node, so we can directly print out it.
Then I’m going to check all the nodes connected to this node,
and see whether there exists nodes not being visited. If there is,
we search the node recursively.
When we visited all the nodes connected,
all the nodes in the subgraph reachable from this node
have all been visited.
At this time, we can do post process.
The post process is needed in topological sort we’ll introduce later.
As for BFS, it
starts from a node not being visited. And we’ll visit the current node
and all the nodes
connected to this node
We’ll visit all the nodes level by level like ripple,
until all the nodes reachable
from v0 have all been visited.
After all the nodes in this subgraph was visited, if there are still some nodes not being visited,
we’ll choose one from the list of nodes
as the source node and BFS again. We’ll stop when all the nodes in the graph are visited.
Let’s see the framework of BFS. First,
when we visit a node, we’ll maybe
print out it and mark it as being visited, and then put it into the queue.
When the queue is not empty, we’ll repeatedly get
nodes from the front of the queue,
and set the current node to it.
We’ll check all the nodes connected to the current node,
if there exists some nodes not being visited,
we’ll visit that node
and mark it as visited and put it into the queue for further use.
For all the search algorithm of graph, no matter DFS or BFS, every
node is visited once, and it’s the same with every edge.
Each edge in undirected graph will be visited twice,
so if adjacency list is used to store edges,
the total consumption is Θ(n+e).
For undirected graph, it’s Θ(n+2e), that’s equal to Θ(n+e).
We can see in the adjacency matrix,
the time complexity of handling these edges is Θ(n^2),
for that edges are hidden in the matrix.
For-loops are needed to scan
all the nodes and there are many zeros in the matrix.
So the time complexity is Θ(n^2), not proportional to the number of edges.
For a sparse graph,
that is the number of edges e is smaller than n^2,
obviously it’s efficient to use adjacency list to store edges.
Now we’re going to see a special kind of sort,
that is a special way to traverse the graph.
DAG, i.e. a graph that is
directed and acyclic, is the only sort of graph to topological sort.
If there are
two nodes, vi and vj, and a path between them.
In the traversal sequence,
vi should appear before vj,
if we consider vi as a prerequisite of vj,
this is actually a problem of prerequisites.
The topological sort is a operation that
serialize the graph and meet all the prerequisites.
Let’s see a problem for course schedule. If
a student, for example, can just attend one course a week
and can finish it.
And some courses should be finished before other courses.
And we can construct a graph using the prerequisites.
So how can we make a schedule for him
to attend a course after finishing all the prerequisite courses.
For example, if we want attend C3, we should finish C1 and C2.
It’s obvious that
because it’s a DAG,
there should be some node without prerequisite,
the indegree of this node is 0.
We can find all the nodes whose indegree is 0, and output it.
And we should remove all the edges starting from it.
And the indegrees of nodes all the removed edges point to should subtract 1.
And if the indegree of some node is 0 now,
we choose it for next round. So we go back to 1 and continue our process.
That’s the topological sort. Let’s see the framework of this algorithm.
First we put all the nodes whose indegrees ares 0 to the queue.
And then if the queue is not empty, we’ll choose the element from the front of the queue.
This node is connected to some other nodes.
and we all the indegrees of these node should subtract 1.
And if the indegree of some node is 0 now,
we can put it in the previous queue,
that is the queue in which all the elements can be printed out and those indegrees are all 0.
And when we finish this loop, we should check
whether there are some nodes
which is still marked as not visited.
If there are, there should be cycles in the graph.
For example, if there is a cycle with node a, b, c,
the indegress of these nodes are not 0, we can’t
break the cycle, and these nodes won’t be
printed out to our output sequence.
Then if
we use DFS for topological sort, let’s see the result.
For the DAG, we start from C1 and DFS
to C6, and there are no other nodes we can traverse from C6. At this time,
we print out C6 after visiting it.
And for C4, there is a node C7 we can traverse from it.
After we visiting C7, we can print out C4 in the post process.
We repeat the process,
and finally we’ll get a sequence. After we reverse it, we can find
this sequence is the sequence of topological sort.
The reason is that
we printing out the sequence in the post process,
that is when we print out the node,
all its prerequisite will be printing out after it.
And after we reverse it, we can get the topological sort sequence.
And the framework is like this.
At the beginning of this framework, we should
make all the nodes as not visited.
And we set up the space
for the result sequence.
And then we scan the list of nodes,
if there is a node not visited, then
we’re going to DFS it.
And then, after we finished our DFS process,
we should reverse the result sequence to get the topological sort sequence.
Let’s see the most important part of the algorithm.
The first node we visit is marked as visited.
And then we’re going to see
whether adjacent nodes are visited.
If not, we’ll DFS it recursively.
When we finish the DFS, that is we visit
all the nodes reachable from the current nodes,
we’ll do the post process.
We’ll put the node to the sequence of result.
And we should notice
that in all the algorithms of graph,
for-loops are very important.
When we find adjacent nodes from one node,
we’ll check first adjacent edge, and the for-loop
help us to get the next adjacent edge.
We’ll repeat this process when the edge is valid. And
in the framework here, we’ll
do some operation on the nodes
the edges connect to. This is a typical framework of graph.
Let’s see the time complexity of topological sort.
No matter recursive or non-recursive
This is the same as the depth first traversal of
the graph. Every node and every edge is going to be processed once,
so when using the adjacency list, the time complexity is Θ(n+e).
While the time complexity is Θ(n^2) when using the adjacency matrix.
For the algorithm of graph, we should think about some more questions.
The most import one is whether directed graph and undirected graph are all supported.
And whether the graph with cycles is supported. And also, whether unconnected graph is supported.
Moreover, we should know that whether it can support graph with negative weights.
Of course, the graph is weighted graph.
If the graph is unweighted we don’t need to consider the negative weights.
Moreover, for these question we mentioned, we should consider how to modify out algorithm to support them.
Let’s see the recursive and non-recursive versions of topological sort.
What should we consider about it?
First, it support DAG.
And there is no special requirement on the connectivity of graph. And in topological sort we don’t need to consider weighted graphs.
But we should consider the cycles in the graph.
For the non-recursive algorithm,
at last we should check whether the nodes in node list are all visited.
If not, there should be cycles.
We can’t set indegrees of nodes
in cycles to 0.
So we can’t visit the nodes in cycles.
But the framework of DFS using the post process
is a framework of non-recursive algorithm. This algorithm can’t handle
graph with cycles. We know
only DAG can be topological sorted, but
the DFS algorithm also print out a sequence for cyclic graph and tell you this is the sequence of topological sort. It’s obviously wrong.
Well, there are some questions. The first one is when implement topological sort by queue,
how can we know indegrees of all the nodes in the graph?
Do we need to do some preprocesses? And can we use
stack to implement it rather than queue? Moreover,
for the DFS framework for topological sort, can we randomly
choose the start node?
And can we use this framework to handle cyclic graphs?
If not, can you make some simple modifications to make it able to handle it?
Thank you all.