Facebook

graphs

Dijkstra’s algorithm

Dijkstra’s algorithm is way of finding shortest path from a source vertex to sink in a given connected and weighted graph. It is somewhat similar to Prim’s algorithm and it works for directed as well as undirected graphs. The step by step process is specified below : Source vertex is chosen and marked. Mark distances at all… read more »

Kruskal’s Algorithm

Kruskal’s algorithm is a greedy technique  used to find minimum spanning tree from the graph.It works on edges rather than on vertices in connected weighted graph.MST is obtained by finding global optimal choice. Technique Mark the minimum weight edge in the graph and mark the respective vertices. Now,mark the next minimum value in the graph. If there… read more »

Prim’s algorithm

Prim’s algorithm is a greedy algorithm as it  finds the global optimum answer from collecting locally optimum choices.It finds the minimum spanning tree and works for weighted,connected and undirected graph.Minimum spanning tree is a graph is edge weighted graph whose weight is smaller than any other spanning tree.A minimum spanning tree is obtained by combining all… read more »

Depth First Search in Graphs

DFS technique is used to traverse graphs.Any vertex is chosen as the starting vertex .Element is pushed into stack.One adjacent vertex is randomly picked from adjacent vertices.It is marked and pushed it into stack.If adjacent unvisited neighbors are present then same process is followed otherwise element is popped off from the stack.Now,again one element is… read more »

Breadth First Search in Graphs

Breadth First Search is a technique to visit all the nodes of graph in a well-defined way.This technique can be applied  to  directed,undirected,weighted or unweighted  graph.Queues are used as a data structure to store elements. BFS traverses all the nodes and edges of graph. BFS in graph with m vertices and n edges takes O(n+m) time…. read more »

Representation of Graphs

Graphs can be represented by Adjacency Matrix by Sequential Representation Linked Representation by using an adjacency list that stores neighbors of a node using linked list. Adjacency Matrix It represents which nodes are adjacent to each other i.e. which nodes have edge connecting between them. Rows and Columns are labeled by graph vertices. a is… read more »

Graphs

A graph is a collections of vertices/nodes and edges(arcs).It is like a tree structure with a difference that it does not have any parent-child relationship between nodes.Instead,any complex relationships are possible between the nodes.A Graph G(Fig 1) is defined as an ordered set (V,E),where V(G) is the set of vertices and E(G) represents the edges… read more »

Sidebar