*Graph Data Structure*

*Define Graph in Data Structure?*

*A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E which is the set of edges of the graph, and a mapping from the set for edge E to a set of pairs of elements of V. It can also be represented as G=(V, E).*

*Define adjacent nodes in Data Structure?*

*Any two nodes which are connected by an edge in a graph are called adjacent nodes. For example, if and edge e is associated with a pair of nodes (u,v) where u, v, then we say that the edge x connects the nodes u and v.*

*Name the different ways of representing a graph in Data Structure?*

*a. Adjacency matrix*

*b. Adjacency list*

*What are the two traversal strategies used in traversing a graph in Data Structure?*

*a. Breadth first search*

*b. Depth first search*

*What is an acyclic graph in Data Structure?*

*A simple diagram which does not have any cycles is called an acyclic graph in Data Structure.*

*What is topological sort?*

*A topological sort is an ordering of vertices in a directed acyclic graph,such that if there is a path from vi then vj appears after vi in the ordering.*

*What is single source shortest path problem?*

*Given as an input a weighted graph, G=(V,E) and a distinguished vertex, 's' find the shortest weighted path from 's' to every other vertex in G.*

*Mention some shortest path problems.*

*a. Unweighted shortest paths*

*b. Dijikstra‟s algorithm*

*c. All-pairs shortest paths*

*What are the algorithms used to find the minimum spanning tree?*

*a. Prim's algorithm*

*b. Kruskal's algorithm*

*Thanks*

*Mukesh Rajput*
## No comments:

## Post a Comment

Thanks

Mukesh Rajput