/* related posts with thumb nails */

### Trees, Graphs:

1. What are Binary Trees? What are the advantages of Binary trees?

A Binary tree is a non-linear data structure in which each node has maximum of two child nodes.

2. What are the advantages of binary tree:

Searching in a binary tree becomes faster

Binary tree provides 6 traversals.

Two of six traversals give sorted order of the elements

Maximum and minimum elements can be directly picked up

It is used for graph traversals and to convert an expression to postfix and prefix forms.

3. What are binary-tree traversals?

Binary tree provides six traversals, which include “in order”, “post order” and “pre order” traversals

4. What are Graphs? Explain types of graphs.

A graph is a collection of vertices or nodes, which are joined as pairs by lines or edges. Formally, a graph G = (V, E) is an ordered pair of finite sets of Vertices and Edges.

5. What are types of Graphs? The types of graphs are listed below:

1. Directed Graph: A graph in which each edge is directed is called Directed graph.

2. Undirected graph: A graph in which each edge is undirected is called an undirected graph.

3. Connected graph: A graph G is connected if there is a path between every pair of vertices.

4. Sub graph: sub graph is a graph in which vertex and edge sets are subsets of those of G.

5. Complete Graph: A graph G is said to be complete if every vertex V is adjacent to every other vertex V in G. A complete graph with ‘n’ vertices has ‘n (n-1)/2’ edges.

6. Weighted graph: A graph ‘G’ is weighted, if each edge in G is assigned a nonnegative numerical value (cost or weight).

7. Connected directed graph or strongly connected graph: A directed graph G is said to be connected, or strongly connected, if for each pair of vertices (v1, v2) there is a path from v1 to v2 and v2 to v1.

6. What is a complete graph?

A graph G is said to be complete if every vertex V is adjacent to every other vertex V in G. A complete graph with ‘n’ vertices has ‘n (n-1)/2’ edges. For example. The following graph is an example for complete graph because it has 4 nodes and 6 ( ‘n (n-1)/2’ here, n=4 ) edges.

7. What are the applications of graphs?

Analysis of electrical networks

Study of molecular structure

The representation of airlines routes

Networks

Topological sort

Finding shortest paths

8. How do you represent a Graph?

A graph can be mainly represented in two ways.

1. Adjacency Matrix (this uses a double dimensional array)

9. Explain Graph traversals. (OR) Explain Depth first and Breadth First Search methods.

There are mainly two methods for traversing in a graph, Depth first and Breadth first traversals.

1. Depth First Search (DFS): It uses a STACK to hold the nodes that are waiting to be processed. First we examine the starting node ‘A’. Then we examine each node along a path ‘P’, which begins at A. i.e. we process one of the neighbors of ‘A’ and continue along the path. After coming to the end of ‘P’, we back track on ‘P’ until we can continue along another path.

2. Breadth First Search (BFS): It uses QUEUE to hold nodes that are waiting to be processed. First we examine the starting node A. Then we examine all the neighbors of A. And, we continue with the other nodes in the same manner. No node is processed more the once.

10.Differentiate Graph and Tree.

# Tree

Graph

A tree is a data structure in which each node is attached to one or more nodes as children

A graph is a collection of vertices or nodes, which are joined as pairs by lines or edges

This is a non linear data structure

This is a non linear data structure

All the trees can be graphs

All the graphs are not trees

It provides six different traversals

It provides two different traversals

It is undirected and connected

It can be directed or undirected; can be connected or not-connected

It cannot be cyclic

It can be cyclic or acyclic

11. What is a spanning tree?

A spanning tree is a subgraph of G (where G is undirected connected graph), is a tree, and contains all the vertices of G.

12. What is a minimum spanning tree?

A minimum spanning tree is a spanning tree, but has weights associated with the edges, and the total weight of the tree (the sum of the weights of its edges) is at a minimum.

Related Topics: