#008 DS&A - Graphs

Graphs

graph theory is in general an algebra class to study relationships between things , in computer science the most common use is the networking.

Representation of Graphs

first representation is adjacency matrix ever case represent the link between point and another as example a doesn't have a relation with it self , while a have relation with b and a doesn't have direct relation with c

another popular representation is linked list

every node have pointer to nodes that connects to.

a dense graph it's a graph that have lot of connections between it nodes.

if the dense isE=O(v^2) where E is the number of edges and v is the number of vertexes , and it mean that graph had lot of connection between them self , in other words matrix is almost all 1 .

let's say we need a similar network for any social platform , the linked list make more sense because we are not going to connect with all in the network just with few friends.

and the order of linked list is O(V+2E) which is <O(v^2)

BFS and DFS

Visited mean that I visit or print it.

Explored mean that I explore all the connections that she made (Neighbors).

you can use array for check visited nodes , for explorer there algorithms that use Queue or Stack, the one that use Queue is called BFS (Breadth First Search) and the one that use the stack called DFS (Depth First Search)

BFS will traverse the tree like this

DFS will traverse the tree like this

BFS algorithm

// the graph G and array visited[] are global
// visited[] is initialized to 0
BFS(v)
{
    u = v;
    visited[u] = 1;
    repeat
    {
        for all vertices w adj to u do
        {
            if(visited == 0)
            {
                add w to q;
                visited[w] = 1;
            }
        }

        if q is empty then return;
        delete the next element u from q;
    }
}

graph G

visited array is initialized to 0

queue q

first iteration u=1 and vertices w adj to u are w={2,3} , so visited and queue will be

after adding it to the queue 2 will be marked as visited

visited array is initialized to 0

now we finish from 2 we need to go to 3 because we have a for loop here to go to all adjacent of 1 which they are {2,3}

now we finish the for loop q is not empty so we are going to delete the next element from q which is 2 , now our u become 2 and neighbors of 2 are w={1,4,5} since 1 is visited we are not going to visit it again and we do same logic as before until we reach an empty q which mean all are visited and explored.

BFS analysis on linkedlist

the queue implementation will take space complexity of O(v)

the linkedlist will take O(v+E)

BFS analysis on adjacency matrix implementation

if we have 8 vertexes it mean we need a matrix of 8x8 size , the array and Queue implementation of it each will have space complexity of O(v) where v is number of vertexes , and the time complexity is T(v^2)

Breadth First Traversal using BFS

in order to know if the graph is connected , it mean all the nodes are in same graph

those can be separated into 2 graphs U and G there at least one node that doesn't have intersection from U with V

to traverse those two sub graphs

BFT(G,n)
{
    // this loop to fill the array with not visited yet
    for i=1 to n do
        visited[i] = 0
    // this will visit every node that is not visited yet
    for i=1 to n do
        if(visited[i]==0) then BFS(i) //BFS not BFT !!!!!
}

let each case represent a Node

the first 4 boxes are the U graph with 4 nodes , he will start from 1 and mark from 1->4 as visited , then he will break.

after this it will start with V and do same thing.

time complexity is O(E+V) and space complexity O(V)

DFS Algorithm

DFS(v)
{
    visited[v] = 1;
    for each vertex w adj to v do
    {
        if(visited[w] == 0) then
            DFS(w);
    }
}

in DFS we start with a point and explore it , if the next node in it not explored we leave the previous node and explore the new node.

initializing the visited array is done in the program that called the function , and we take it in count when we calculate the time complexity.

as we see every time we have an unvisited node we fully explore it neighbors. if all the neighbors are visited we go back into old neighbors.

Analysis of DFS and DFT

space complexity of DFS is O(V) , the worst case if the graph is chain , because all the nodes will be on the stack in same time. So space complexity for DFS and BFS is O(v) , time complexity is O(E)+O(V) for the linked list representation where O(V) is time to initialize the visited array and O(V^2) for matrix representation , same as BFS .

DFT will be the same as BFT instead of calling BFS we call DFS .