Graphs and Trees : Part 1

I was getting bored ...a day is a very long thing ...I watched movie, played ...but still the day was not ending .

So I picked up one book which was lying on my table about data structures and started reading it.

Book is pretty good, rather than having coded examples it was more on theory.

I directly started with Trees and Graphs , since I don't think apart from embedded devices anywhere else list are used extensively.

The real world data is all in graphs and trees.

Family relations , roads in a city , if you want to categorize your friends in different categories, your wardrobe if you want to pick something based on color, weather and with whom you are going out.

Just imagine if you want to write code for these you can't do that using list. You have need graphs , trees and other complex data types.


So without further ado , lets start it

First with theory in brief  and then programs ...which i highly doubt will be made .


Directed Graph  : having directional edge  . Also known as Digraph.
Undirected Graph : not having directional edge
 Mixed Graph : having combination of above two.

MultiGraph : having more than one edge connection two nodes or in case of directed graph having more than one edge having same direction between two nodes.
Simple Graph : which is not multigraph.

Weights of edges can mean many things , depending on question or scenario.

Outdegree means number of edges going out from a node and Indegree means number of edges coming in.
Total degree =  indegree + outdegree

So we can have

simple directed graph
multi directed graph
simple undirected graph
multi undirected graph


Simple Path : Path in which the edges are distinct
Elementary Path : Path in which the nodes are distinct.

All elementary path are simple, but opposite is not true

Acyclic and cyclic graphs are quite evident from there names.



Directed Tree :  is acyclic simple digraph, in which one node has indegree 0 called as root node.

Other nodes in tree are leaf node and branch nodes.  Leaf node has outdegree 0.

Level of a node is its distance from the root .
Height is distance of root from farthest leaf node
Degree of a node is number of subtrees of it , or simply number of outdegree of that node

M-ary tree :  Directed Tree in which outdegree of each node is equal or less than M.

If outdegree of each node is M , then complete M-ary tree.

Bin-ary Tree which we sees everyday.

Now we will end this post with a diagram of tree and how we represent that in computers .

1st representation Using brackets we can input data

(v0(v7(v8)(v9(v10)))(v1(v2(v5)(v6))(v3)(v4)))

2nd method using intergers 0....M-1  for M-ary tree

v0 0
v7 00
v1 01
v8 000
v9 001
v2 010
v3 011
v4 012
v5 0100
v6 0101

But  there can be some issues as we see for v0 ,v7,v8

3rd one and easy to have algo working   to define struct


typedef struct {
int node_value;
int number of children;
tree **child_trees;
}tree;

here child_trees will have pointer to array of child_tree in which all child nodes will be present.

Note while assigning value we can assign values of child nodes from left to right  or  right to left depending on our preference.


// Below is sample code //

#include<stdio.h>
#include<stdlib.h>



/********************************************

Ex        0
    1     2       3
************************************************/


 struct tree{
int node_value;
int num_child;
struct tree **child;
}tree;

 void print(struct tree*);

int main()
{

struct tree *root_node = (struct tree*)malloc(sizeof(struct tree)*1);

root_node->node_value =0;
root_node->num_child =3;
root_node->child = NULL;


struct tree **child = (struct tree **)malloc(sizeof(struct tree *)*3);
struct tree *child_temp = (struct tree *)malloc(sizeof(struct tree)*1);
child[0] = child_temp;
child_temp = (struct tree *)malloc(sizeof(struct tree)*1);
child[1] = child_temp;
child_temp = (struct tree *)malloc(sizeof(struct tree)*1);
child[2] = child_temp;

child[0]->node_value =1;
child[0]->num_child =0;
child[0]->child = NULL;

child[1]->node_value =2;
child[1]->num_child =0;
child[1]->child = NULL;

child[2]->node_value =3;
child[2]->num_child =0;
child[2]->child = NULL;

root_node->child = child;

struct tree* temp = root_node;

print(temp);
}

void print(struct tree*temp)
{
printf("%d \n",temp->node_value);

for(int i=0;i<temp->num_child;i++)
{
print(temp->child[i]);

}
}