Here's one last topic, I'd like to cover in this unit.
And again, it's related to the analysis of graphs and paths,
and using variance of depth-first and breadth-first search to answer questions about the graph.
Here's a little graph that I drew and one thing that we might notice is that,
everybody is connected to everybody else, but there is this sort of weak edge.
This is the weakest link, hello.
If this edge were to be removed from the graph, like so,
the number of components in the graph has just gone up by one.
Now, that was the only edge in this graph that has that property.
There's other edges that if we take them out, things are still connected.
So, in some social networks, it's useful to know, are there any edges in this graph?
Are there any pairs of people in the graph that are connected
that if they were to say, stop being friends, there would be disconnection in the network as a whole.
Let's put this edge back in and label the edges, sorry, label the
nodes of the graph so we can talk about them.
And we're going to carry an algorithm back to 1974 by Robert Tarjan.
Tarjan is responsible for some of the most amazing graph algorithms.
A lot of which are based on the ideas of building trees,
spanning trees using depth-first and breadth-first search.
Back in college, my friend ??? and I used to refer to him as Tarjan, Lord of the trees.
So the basic idea of this algorithm is we pick any node in the graph.
Let's say B, and we start to build a tree starting from B, and here's how we do it.
Starting from B, we look at all the neighbors of B which in this case are A and C,
and we haven't build any of them into the graph yet, so we can add them into the graph.
And now, we do essentially a search just as we're doing before, consisted of A and C.
So from A, we look at the neighbors of A. The neighbors of A are B and C.
Now, the BA edge is already in there, but the BC edge is not.
So, we're going to add a special kind of edge because this is an edge
between two nodes that are already existing.
We'll call this a non-tree edge.
So, what we're going to do is we're going to take this entire graph and express it essentially as a tree,
but some of the edges aren't going to be part of the tree.
We're going to have to add them in separate, all right.
So, that takes care of all the neighbors of B and the neighbors of C.
We have B which the edges are already in there
and we also have an edge to E which we haven't seen yet.
We add that edges and then we proceed from E.
Now, E has three edges back to C which we already have and also to D and G.
Those are new nodes, so we build them in with three edges
and we continue our search now, let's say from D and D has two neighbors, E and F.
E is already in there but we can add in F at the tree edge.
We look back at G, G has neighbors F and E.
The E one is in there and the F one is not, so we add that non-tree edge in there,
Because F is already in the diagram but that edge was no not.
And then from F, there is connection to D and G and those were already in the graph.
So basically, what we've done now is we rewrote the original graph as a rooted tree.
So starting with some node and then proceeding downward
and then any edges that don't really fit that pattern we put in is, we put that dotted lines.
So, we rewritten the graph as a tree and the next thing we need to know is post order the nodes.
Now, post ordering is something you can do to any tree structure,
and it basically involves assigning a number, a sequential number
to each of the nodes in the--in the tree and post order means is,
what we do, is to assign a number to a node,
we first make sure that all the children on its left are numbered.
All the children on its right are numbered, children and descendant.
Direct children also and their children's children and then the node itself gets a number after that.
So, these number is going to come from first numbering A,
well A has--and then-and then everything below C and then we can number B itself.
A's number comes from neighboring--numbering it's children, which it doesn't have any,
so it can get whatever the next number is, which in this case is 1, all right.
So back to B, we have to label all the--all the children on it's left and all the children on it's right.
We haven't done that yet, so let's do a numbering starting from C.
Well C, before it gets a number, has to have all it's children numbered
and we can see that they don't have numbers yet, so we have to proceed down the tree.
E needs a number. Well, E can't get it's number until it's children have been numbered
but those haven't been numbered yet, so let's number those.
D--D should get a number but first it's children have to get a number.
This is a, you know, children first sort of scheme. These children has one child and that's F.
For F to get a number, it's children, oh it doesn't have any children yet.
All right, so F can get the next available number and in this case, it's 2.
So now that, that's finish, D can get a number because all it's children are numbered.
So, D gets the next available number and that's 3.
E, no E still can't be numbered because it's children haven't been all numbered yet.
We have to go to G first. G has no children, so it can get the next available number.
Now, E can get a number. Post order in this case is, post meaning after.
After all the kids, the node itself can get numbered.
There's also pre-order and in-order, but we're just looking at post order for this algorithm.
All right, now C, all it's children have been numbered, so now C can get it's number.
B, all its children have been numbered, so now B can get it's number.
So we've now post ordered all the nodes in the graph.
So, just to make sure that you're understanding that process, here's a different tree.
This time, the branching factors are a little different in some places.
And I want you to post order this tree
and then type in this box the number assigned to node P once you've done that.