differentiate between BFS and DFS?

BFS vs DFS

Breadth First Search (also known as BFS) is a search method used to broaden all the nodes of a particular graph. It accomplishes this task by searching every single solution in order to examine and expand these nodes (or a combination of sequences therein). As such, a BFS does not use a heuristic algorithm (or an algorithm that searches for a solution through multiple scenarios). After all the nodes are obtained, they are added to a queue known as the First In, First Out queue. Those nodes that have not been explored are ’stored’ in a container marked ‘open’; once explored they are transported to a container marked ‘closed’.

Depth First Search (also known as DFS) is a search method that burrows deeper into a child node of a search until a goal is reached (or until there is a node without any other permutations or ‘children’). After one goal is found, the search backtracks to a previous node that has gone with a solution, repeating the process until all the nodes have been successfully searched. As such, nodes continue to be put aside for further exploration – this is called non-recursive implementation.

The features of the BFS are space and time complexity, completeness, proof of completeness, and optimality. Space complexity refers to the proportion of the number of nodes at the deepest level of a search. Time complexity refers to the actual amount of ‘time’ used for considering every path a node will take in a search. Completeness is, essentially, a search that finds a solution in a graph regardless of what kind of graph it is. The proof of the completeness is the shallowest level at which a goal is found in a node at a definite depth. Finally, optimality refers to a BFS that is not weighted – that is a graph used for unit-step cost.

A DFS is the most natural output using a spanning tree – which is a tree made up of all vertices and some edges in an undirected graph. In this formation, the graph is divided into three classes: Forward edges, pointing from a node to a child node; back edges, pointing from a node to an earlier node; and cross edges, which do not do either one of these.

Summary:

1. A BFS searches every single solution in a graph to expand its nodes; a DFS burrows deep within a child node until a goal is reached.

2. The features of a BFS are space and time complexity, completeness, proof of completeness, and optimality; the most natural output for a DFS is a spanning tree with three classes: forward edges, back edges, and cross edges.

explain the Kruskal's algorithm with an example? or -> prove that Kruskal's algorithm finds a minimal spanning tree?

Kruskal's Algorithm

Kruskal's Algorithm for computing the minimum spanning tree is directly based on the generic MST algorithm. It builds the MST in forest. Initially, each vertex is in its own tree in forest. Then, algorithm consider each edge in turn, order by increasing weight. If an edge (u, v) connects two different trees, then (u, v) is added to the set of edges of the MST, and two trees connected by an edge (u, v) are merged into a single tree on the other hand, if an edge (u, v) connects two vertices in the same tree, then edge (u, v) is discarded.

Outline of Kruskal's Algorithm

Start with an empty set A, and select at every stage the shortest edge that has not been chosen or rejected, regardless of where this edge is situated in graph.

I    Kruskal's algorithm implemented with disjoint-sets data structure.

Disjoint-Sets Data Structure

• Make_Set (v)
  Create a new set whose only member is pointed to by v. Note that for this operation v must already be in a set.
• FIND_Set
  Returns a pointer to the set containing v.
• UNION (u, v)
  Unites the dynamic sets that contain u and v into a new set that is union of these two sets.

MST_KRUSKAL (G, w)

1.      A ← {}    // A will ultimately contains the edges of the MST

2.      for each vertex v in V[G]

3.          do Make_Set (v)

4.      Sort edge of E by nondecreasing weights w

5.      for each edge (u, v) in E

6.          do if FIND_SET (u) ≠ FIND_SET (v)

7.              then A = AU{(u, v)}

8.                  UNION (u, v)

9.      Return A

Analysis

The for-loop in lines 5-8 per forms 'Union' and 'find' operations in O(|E|) time. When the disjoint-set forest implementation with the weighted union and path compression heuristic is used, the O(|E|) 'union' and 'find' operators involved in the for-loop in lines 5-8 will have worst-case time O(|E| lg * |E|). Kruskal's algorithm requires sorting the edge of E in line 4. We know that the fastest comparison-based sorting algorithm will need (|E| lg |E|) time to sort all the edges. The time for sorting all the edges of G in line 4 will dominates the time for the 'union' and 'find' operations in the for-loop in lines 5-8. When comparison-based sorting algorithm is used to perform sorting in line 4. In this case, the running time of Kruskal's algorithm will be O(|E| lg |E|).

In summary, Kruskal's algorithm as given in the CLR, pp 505 requires O(E lg E) time

• O(V) time to initialize.
• O(E lg E) time to sort edges by weight
• O(E α (E, V)) = O(E lg E) time to process edges.

If all edge weights are integers ranging from 1 to |V|, we can use COUNTING_SORT (instead of a more generally applicable sorting algorithm) to sort the edges in O(V + E) = O(E) time. Note that V = O(E) for connected graph. This speeds up the whole algorithm to take only O(E α (E, V)) time; the time to process the edges, not the time to sort them, is now the dominant term. Knowledge about the weights won't help speed up any other part of the sort in line 4 uses the weight values.

If the edges weights are integers ranging from 1 to constant W, we can again use COUNTING_SORT, which again runs in O(W + E) = O(E) time. Note taht O(W + E) = O(E) because W is a constant. Therefore, the asymptotic bound of the Kruskal's algorithm is also O(E α (E, V)).

II    Kruskal's algorithm implemented with priority queue data structure.

MST_KRUSKAL (G)

1.      for each vertex v in V[G] do

2.          define set S(v) ← {v}

3.      Initialize priority queue Q that contains all edges of G, using the weights as keys.

4.      A ← { }         // A will ultimately contains the edges of the MST

5.      While A has less than n-1 edges do

6.      Let set S(v) contains v and S(u) contain u

7.      IF S(v) != S(u) then     Add edge (u, v) to A     Merge S(v) and S(u) into     one set i.e., union

8.      Return A

Analysis

• The edge weight can be compared in constant time.
• Initialization of priority queue takes O(E log E) time by repeated insertion.
• At each iteration of while-loop, minimum edge can be removed in O(log E) time, which is O(log V), since graph is simple.
• The total running time is O((V + E) log V), which is O(E lg V) since graph is simple and connected.

Example    Step by Step operation of Kurskal's algorithm.

Step 1.  In the graph, the Edge(g, h) is shortest. Either vertex g or vertex h could be representative. Lets choose vertex g arbitrarily.

what are the differences between posterior & prior analysis?

Definition:
The phrase a priori is a Latin term which literally means before (the fact). When used in reference to knowledge questions, it means a type of knowledge which is derived without experience or observation. Many consider mathematical truths to be a priori, because they are true regardless of experiment or observation. For example:
2 + 2 = 4
The above is a statement which can be known a priori.
When used in reference to arguments, it means an argument which argues solely from general principles and through logical inferences.
The term a posteriori literally mean after (the fact). When used in reference to knowledge questions, it means a type of knowledge which is derived through experience or observation. Today, the term empirical has generally replaced this. Many empiricists, like Locke and Hume, have argued that all knowledge is essentially a posteriori and that a priori knowledge simply isn't possible.
The distinction between a priori and a posteriori is closely related to the distinctions between analytic / synthetic and necessary / contingent.

Analyticity and necessity

[edit] Relation to the analytic-synthetic

For more details on this topic, see Analytic-synthetic distinction.

Several philosophers reacting to Kant sought to explain a priori knowledge without appealing to, as Paul Boghossian explains, "a special faculty...that has never been described in satisfactory terms."^[3] One theory, popular among the logical positivists of the early twentieth century, is what Boghossian calls the "analytic explanation of the a priori."^[3] The distinction between analytic and synthetic propositions was first introduced by Kant. While Kant's original distinction was primarily drawn in terms of conceptual containment, the contemporary version of the distinction primarily involves, as Quine put it, the notions of "true by virtue of meanings and independently of fact."^[4] Analytic propositions are thought to be true in virtue of their meaning alone, while a priori synthetic propositions are thought to be true in virtue of their meaning and certain facts about the world. According to the analytic explanation of the a priori, all a priori knowledge is analytic; so a priori knowledge need not require a special faculty of pure intuition, since it can be accounted for simply by one's ability to understand the meaning of the proposition in question. In short, proponents of this explanation claimed to have reduced a dubious metaphysical faculty of pure reason to a legitimate linguistic notion of analyticity.

However, the analytic explanation of a priori knowledge has undergone several criticisms. Most notably, the American philosopher W. V. O. Quine (1951) argued that the analytic-synthetic distinction is illegitimate (see Quine's rejection of the analytic-synthetic distinction). Quine states: "But for all its a priori reasonableness, a boundary between analytic and synthetic statements simply has not been drawn. That there is such a distinction to be drawn at all is an unempirical dogma of empiricists, a metaphysical article of faith."^[5] While the soundness of Quine's critique is highly disputed, it had a powerful effect on the project of explaining the a priori in terms of the analytic.

[edit] Relation to the necessary/contingent

The metaphysical distinction between necessary and contingent truths has also been related to a priori and a posteriori knowledge. A proposition that is necessarily true is one whose negation is self-contradictory (thus, it is said to be true in every possible world). Consider the proposition that all bachelors are unmarried. Theoretically, its negation, the proposition that some bachelors are married, is incoherent, because the concept of being unmarried (or the meaning of the word "unmarried") is part of the concept of being a bachelor (or part of the definition of the word "bachelor"). To the extent that contradictions are impossible, self-contradictory propositions are necessarily false, because it is impossible for them to be true. Thus, the negation of a self-contradictory proposition is supposed to be necessarily true. By contrast, a proposition that is contingently true is one whose negation is not self-contradictory (thus, it is said that it is not true in every possible world). As Jason Baehr states, it seems plausible that all necessary propositions are known a priori, because "[s]ense experience can tell us only about the actual world and hence about what is the case; it can say nothing about what must or must not be the case."^[6]

Following Kant, some philosophers have considered the relationship between aprioricity, analyticity, and necessity to be extremely close. According to Jerry Fodor, "Positivism, in particular, took it for granted that a priori truths must be necessary...."^[7] However, since Kant, the distinction between analytic and synthetic propositions had slightly changed. Analytic propositions were largely taken to be "true by virtue of meanings and independently of fact",^[8] while synthetic propositions were not—one must conduct some sort of empirical investigation, looking to the world, to determine the truth-value of synthetic propositions.

Aprioricity, analyticity, and necessity have since been more clearly separated from each other. The American philosopher Saul Kripke (1972), for example, provided strong arguments against this position. Kripke argued that there are necessary a posteriori truths, such as the proposition that water is H₂O (if it is true). According to Kripke, this statement is necessarily true (since water and H₂O are the same thing, they are identical in every possible world, and truths of identity are logically necessary) and a posteriori (since it is known only through empirical investigation). Following such considerations of Kripke and others (such as Hilary Putnam), philosophers tend to distinguish more clearly the notion of aprioricity from that of necessity and analyticity.

Kripke's definitions of these terms, however, diverge in subtle ways from those of Kant. Taking these differences into account, Kripke's controversial analysis of naming as contingent and a priori would best fit into Kant's epistemological framework by calling it "analytic a posteriori".^[9]

Thus, the relationship between aprioricity, necessity, and analyticity is not easy to discern. However, most philosophers at least seem to agree that while the various distinctions may overlap, the notions are clearly not identical: the a priori/a posteriori distinction is epistemological, the analytic/synthetic distinction is linguistic, and the necessary/contingent distinction is metaphysical.^[10]