Graphs (Data Structure): Two Marks Important Questions and Answers

Data Structures using C ++

Chapter 7: Graphs

Two Marks Questions with Answers

 

1. Define graph.

Answer:  

A graph is a collection of two sets of V and E where V is finite non empty set of vertices and E is a finite non empty set of edges.

Vertices are nothing but the nodes in the graph and two adjacent vertices are joined by edges.

The graph is denoted by G = {V,E}

2. What are the storage representation of the graph?

Answer:

The graph can be represented by using arrays or linked list.

1. The adjacency matrix is a storage representation of the graph by which the graph is stored in two dimensional arrays.

2. The adjacency list is a storage representation of a graph by which the graph is stored in linked list.

3. What are the applications of graph?

Answer:

The graph theory is used widely in the computer science very widely. The applications of graph theory are ‒

1. In computer networking such as Local Area Network (LAN), Wide Area Networking (WAN) internetworking the graph is used.

2. In telephone cabling graph theory is effectively used.

3. In job scheduling algorithms the graph is used.

4. Prove that the number of odd degeree vertices in a connected graph should be even.

Answer:  

To prove this, consider connected graphs with odd degree vertices.

degree = 1

number of vertices = 2

degree = 2

number of vertices = 3

degree = 3

 number of vertices = 4

This figures show clearly that in a connected graph there are even number of vertices with odd degree.

5. Differentiate between trees and graphs.

Answer:

Graph

1. Graph is a non‒linear data structure.

2. It is a collection of vertices/nodes and edges.

3. Each node can have any number of edges.

4. There is no unique node called root in graph.

5. A cycle can be formed.

6. Applications : For finding shortest path in networking graph is used

Tree

1. Tree is a non‒linear data structure.

2. It is a collection of nodes and edges.

3. General trees consist of the nodes having any number of child nodes. But in case of binary trees every node can have at the most two child nodes.

4. There is a unique node called root in trees.

 5. There will not be any cycle.

6. Applications : For game trees, decision trees, the tree is used.

6. When does a graph becomes a tree?

Answer:

A graph becomes a tree when

• It contains an unique node which has no incoming(incident) edge but have all the outgoing edges. This node will become the root of the tree.

• Remaining nodes of the graph have at the most one incoming edges (these will become the internal nodes).

• There must be some nodes in the graph having no outgoing edge at all(these will then become the leaf nodes).

• The graph should be connected.

7. What is meant by adjacency matrix ?

Answer:

Adjacency matrix is a method of representation of a graph using two dimensional matrix. For example ‒ If the edge is present between two vertices then the value in adjacency matrix is set to 1 otherwise 0.

8. What is strongly connected components? Explain.

Answer:

A directed graph is said to be strongly connected if for every pair of vertex there exists a path.

There exists a path from V₁ to V₃ as well as from V₃ to V₁.

9. Write the template for depth first search ?

Answer:

void Graph::DFS(int v1)

{

   int v2;

   cout<<endl;<<v1;

   v[v1]=TRUE;

   for(v2=0;v2<n;v2++)

      if(g[v1][v2] = =TRUE && v[v2]= =FALSE)

         DFS(v2);

}

10. Give the representation of network of cities (Chennai, Delhi, Kolkata and Mumbai) as weighted graph.

Answer:

11. How a graph is represented?

Answer:

A graph can be represented using 1. Adjacency list and 2. Adjacency list. In the adjacency matrix representation the matrix is used while in adjacency list the linked list is used to represent the graph.

12. When a graph is said to be connected?

Answer:

An undirected graph is said to be connected if for every pair of distinct vertices V_i and V_j in V(G) there is an edge V_i to V_j in G.

Note that there is path from any two vertices.

For example:

• V₁ ‒ V₂

• V₂ ‒ V₁

• V₃ ‒ V₁

• V₄ ‒ V₃ ‒ V₁

• V₁ ‒ V₃

• V₂ ‒ V₁ ‒ V₃

• V₃ ‒ V₁ ‒ V₂

• V₄ ‒ V₂

• V₁ ‒ V₄

• V₂ ‒ V₄

• V₃ ‒ V₄

• V₄ ‒ V₃

13. Differentiate between breadth first and depth first

Answer:

Breadth first search

1. BFS is simple to implement.

2. BFS will perform poor is for large numbers of vertices in graph.

3. BFS requires more memory.

4. BFS will find the shortest path if the weight on the links are uniform.

5. BFS is not useful in sorting application.

6. This algorithm works in single stage. The visited vertices are removed from the queue and then displayed at once.

Depth first search

1. DFS is complex to implement as it may suffer from infinite loop problem.

2. DFS will perform better in case of large complex graph.

3. DFS requires less memory.

4. DFS can not obtain shortest path.

5. DFS is used in topological sorting.

6. This algorithm works in two stages ‒ in the first stage the visited vertices are pushed onto the stack and later on when there is no vertex further to visit those are popped‒off.

14. What is a graph? List two ways to represent a graph.

A graph is a collection of two sets V and E where V is a finite non‒empty set of vertices and E is a finite non‒empty set of edges.

• Vertices are nothing but the nodes in the graph.

• Two adjacent vertices are joined by edges.

• Any graph is denoted as G = (V, E}.

• There are several representations of graphs, but we will discuss the two commonly used representations called

■ Adjacency Matrix

■ Adjacency Lists

Let us see each one by one.