**Tree**

**:**

**A tree is a connected graph without cycles.**

**Properties of Trees:**

- A graph is a tree if and only if there is one and only one path joining any two of its vertices.
- A connected graph is a tree if and only if every one of its edges is a bridge.
- A connected graph is a tree if and only if it has N vertices and N; 1 edges.

**Definitions :**

- A sub-graph that spans (reaches out to ) all vertices of a graph is called a spanning sub-graph.
- A sub-graph that is a tree and that spans (reaches out to ) all vertices of the original graph is called a spanning tree.
- Among all the spanning trees of a weighted and connected graph, the one (possibly more) with the least total weight is called a minimum spanning tree (MST).

**Kruskal's Algorithm :**

- Kruskal Algorithm finds the minimal cost of edges between two vertices and forms the tree.
- The total weight should be minimized
- Graph should not be looped.
- Minimal cost should be chosen initially.

**Pseudocode :**

```
KRUSKAL(G):
1 A = ∅
2
```**foreach** v ∈ G.V:
3 MAKE-SET(v)
4 **foreach** (u, v) ordered by weight(u, v), increasing:
5 **if** FIND-SET(u) ≠ FIND-SET(v):
6 A = A ∪ {(u, v)}
7 UNION(u, v)
8 **return** A

## No comments:

## Post a Comment