**Weighted Graphs:** A weighted graph is defined as a graph whose each edge have some weight (value).

**Weight of a Graph:** Sum of weights(values) of all edges in a graph is known as weight of the graph.

**Connected Components:** In an undirected graph, a connected component is defined as a subset of vertices which are mostly reachable from one another. A graph having one connected component known as connected graph, i.e. each vertex is reachable from another.

**Subgraph:** Subgraph is defined as the subset of vertices and edges that forms a graph.

**Tree: **Tree is a connected graph without any cycle and loop.

**Forest:** A **forest** may be defined as an undirected and disconnected, acyclic **graph. A** disjoint collection of trees is also known as **forest**. Each component of a **forest** is tree.

**Weakly Connected component: **Connected graph which is not strongly connected, i.e some vertex are not connected to every vertex known as weakly connected graph.

**Graph Representations: **There are numerous ways of representing a graph:

- Incidence list
- Incidence matrix
- Adjacency List
- Adjacency Matrix

**Example: Consider the following graph G.**

Adjacency List representation of above graph G:

- v1: v2, v3, v4, v5
- v2: v1, v3
- v3: v1, v2, v4, v5
- v4: v1, v3, v5
- v5: v1, v3, v4

Adjacency Matrix representation of above graph G:

Incidence list representation of above graph G:

{(1, 2, (1, 5), (1, 3), (1, 4), (4, 5), (3, 5), (3, 4), (2, 3)}

Incidence matrix representation of above graph G:

**Graph Traversals:** Graph traversals defined as a process of traversing (or searching, reaching) all vertices in graph. If the graph is connected then only we can reach to all vertices of graph. While traversing we will never visits a vertex more than once.

To search a node (or traverse a node) we use bread first search(bfs) and depth first search (dfs) algorithm.

**Depth first search (DFS) Algorithm**

**Step 1:** Visit one vertex, you can choose any vertex as the starting node (if start vertex not mentioned in question). And push that vertex to the Stack.

**Step 2:** find another undiscovered adjacent nodes of the top element of the stack and visit any one of them (in any particular order).

**Step 3:** Repeat Step 2 until there is no undiscovered vertex(node) left.

**Step 4:** Pop out the element from the top of the Stack and Repeat Step 2, 3 and 4 till the stack becomes empty.

DepthFirst(Vertex v){

mark v as Visited

for each neighbor w of v {

if (w is not visited){

add edge (v,w) to tree T

DepthFirst(w)

}

}

}

By using DFS traversal, only some edges will be traversed and these edges will form a tree, which will known as **depth-first-search tree** of graph G, and the edges of this tree are known as **tree edges**. The edges of G can be described into three parts:

**Back edges**points a child node to one of its ancestors in the DFS tree.**Forward edges**point from a node to one of its child or descendants.**Cross edges**point from a node to a previously visited node that is neither its ancestor nor descendant.

**Applications of DFS**

- To find strongly connected components of graph
- To find bridges in graph
- Minimum spanning tree
- To check if graph has a cycle
- Topological sorting

**Analysis of the DFS:**The running time complexity of the DFS algorithm is O(|V|+|E|).

**Breadth First Search Algorithm**

**Step 1:**Visit the start vertex (node), you can choose any node as the start node(if it is not given in the question). And add that node into a queue.

**Step 2:**Repeat the below steps until the queue becomes empty.

**Step 3:**Remove the head element of the queue and while staying at the vertex, visit all connected vertices and then add them into queue one by one (choose any order to visit all the connected vertices).

**Step 4:**When you visit all the connected vertices. Repeat Step 3.

Breadth-First-Search (G) { initialize a queueQunmark all vertices inGfor all verticesainG{ if (ais unmarked) { enqueue (Q,a) while (!empty (Q) {b= dequeue (Q) if (bis unmarked) { markbvisitb// print or whatever for all verticescadjacent fromb{ enqueue (Q,c) } } } } }}

**Applications of BFS**

- To find all nodes within one connected component
- To check if graph has a cycle
- Diameter of Tree
- To find shortest path between two nodes u and v
- To test bipartite-ness of a graph

**Analysis of BFS:**The running time complexity of the BFS algorithm is O(|V|+|E|).

**Graph Applications:**

- Electronic circuits
- Task scheduling
- Route mapping
- Packet routing in Networks

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

## Click Here to Avail GATE CSE Test Series!

**Thanks**

**#DreamStriveSucceed**

## Comments

write a comment