Showing posts with label first. Show all posts
Showing posts with label first. Show all posts

Tuesday, February 17, 2015

Depth First Search DFS Traversal of a Graph Algorithm and Program

Most of graph problems involve traversal of a graph. Traversal of a graph means visiting each node and visiting exactly once. There are two types of traversal in graphs i.e. Depth First Search (DFS) and Breadth First Search (BFS). In this tutorial I will discuss about DFS.

Read Previous Articles:
1. Graphs: Introduction and Terminology
2. Representation of Graphs: Adjacency Matrix and Adjacency List

Depth First Search (DFS)

It is like preorder traversal of tree. Traversal can start from any vertex, say Vi . Vi is visited and then all vertices adjacent to Vi are traversed recursively using DFS.

Since, a graph can have cycles. We must avoid revisiting a node. To do this, when we visit a vertex V, we mark it visited. A node that has already been marked as visited should not be selected for traversal. Marking of visited vertices can be done with the help of a global array visited[ ]. Array visited[ ] is initialized to false (0).

Algorithm for DFS

n ← number of nodes
Initialize visited[ ] to false (0)
for(i=0;i<n;i++)
               visited[i] = 0;

void DFS(vertex i) [DFS starting from i]
{
               visited[i]=1;
               for each w adjacent to i
                              if(!visited[w])
                                             DFS(w);
}

Depth First Search (DFS) Traversal of a Graph [Algorithm and Program]

The graph shown above is taken as input in both the programs mentioned below:

C Program to implement DFS traversal on a graph represented using an adjacency matrix

#include<stdio.h>

void DFS(int);
int G[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]

void main()
{
    int i,j;
    printf("Enter number of vertices:");
    scanf("%d",&n);

    //read the adjecency matrix
    printf("
Enter adjecency matrix of the graph:");
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&G[i][j]);

    //visited is initialized to zero
    for(i=0;i<n;i++)
        visited[i]=0;

    DFS(0);
}

void DFS(int i)
{
    int j;
    printf("
%d",i);
    visited[i]=1;
    for(j=0;j<n;j++)
        if(!visited[j]&&G[i][j]==1)
            DFS(j);
}

C Program to implement DFS traversal on a graph represented using an adjacency matrix

C Program to implement DFS traversal on a graph represented using an adjacency list

#include<stdio.h>

typedef struct node
{
    struct node *next;
    int vertex;
}node;

node *G[20];    //heads of linked list
int visited[20];
int n;
void read_graph();  //create adjacency list
void insert(int,int);   //insert an edge (vi,vj) in te adjacency list
void DFS(int);

void main()
{
    int i;
    read_graph();
    //initialised visited to 0
    for(i=0;i<n;i++)
        visited[i]=0;

    DFS(0);
}

void DFS(int i)
{
    node *p;
    printf("
%d",i);
    p=G[i];
    visited[i]=1;
    while(p!=NULL)
    {
        i=p->vertex;
        if(!visited[i])
            DFS(i);
        p=p->next;
    }
}

void read_graph()
{
    int i,vi,vj,no_of_edges;
    printf("Enter number of vertices:");
    scanf("%d",&n);

    //initialise G[] with a null
    for(i=0;i<n;i++)
    {
        G[i]=NULL;
        //read edges and insert them in G[]
        printf("Enter number of edges:");
        scanf("%d",&no_of_edges);

        for(i=0;i<no_of_edges;i++)
        {
            printf("Enter an edge(u,v):");
            scanf("%d%d",&vi,&vj);
            insert(vi,vj);
        }
    }
}

void insert(int vi,int vj)
{
    node *p,*q;
    //acquire memory for the new node
    q=(node*)malloc(sizeof(node));
    q->vertex=vj;
    q->next=NULL;

    //insert the node in the linked list number vi
    if(G[vi]==NULL)
        G[vi]=q;
    else
    {
        //go to end of the linked list
        p=G[vi];
        while(p->next!=NULL)
            p=p->next;
        p->next=q;
    }

}

C Program to implement DFS traversal on a graph represented using an adjacency list
Read more »
Posted by at No comments:
Labels: , , , , , , , , , ,

Friday, January 30, 2015

Adobe Photoshop CS4 Online Training for Beginners First 3 Chapters FREE

The VTC Online University is a great site that offers high-quality software video training. Check out their Adobe Photoshop CS4 Online Training for Beginners course. Scroll down to watch the first 3 chapters for free. Just click on the video links to launch the free video tutorials. Visit the course details page for more information about this Photoshop CS4 online training course for beginners. The entire course contains a total of 9 hours worth of excellent video tutorials. Sign up for a VTC.com membership in order to view the entire course.

Adobe Photoshop CS4 Training

from VTC.com

[Become a VTC.com Member]
Get complete access to ALL the VTC Online University courses for $30/month

Adobe Photoshop CS4 Online Training for Beginners


Introduction

New in Photoshop CS4
System Requirements
RAM Requirements
Peripheral Devices
Work Files

Interface

Document Window
Toolbox
Spring-Loaded Tools
Menus
Panels
Shortcuts
Help
Arrangements

Adobe Bridge

The Bridge
Metadata
Organize
Loupe & Compare

Documents

New Document
Raster vs. Vector
Size & Resolution
Resize Documents
The Canvas
Undo & Step
Drag & Drop

Layers

Add / Delete & Merge
Layer Options
Opacity & Fills
Blend Modes pt. 1
Blend Modes pt. 2
Layer Comps
Adjustment Layers
Layer Styles
Auto Align Layers

Cropping

Crop Tool
Crop & Rotate
Crop Perspective

Navigation

Navigate
Navigator Panel

Color Tools

Color Palettes
Create Swatches
Color Picker & Eyedropper

Selections

Selection Tools
Quick Select
Magic Wand
Marquees & Strokes
Paste Into & Invert
Feather & Anti-alias
Save & Load

Transformation

Content-Aware Scale pt. 1
Content Aware Scale pt. 2
Transform
Free Transform
Warp Tool
Arbitrary Rotation

Adjustments

Adjustments Panel
Curves
Levels
Vibrance Adjustment

Color Correction

Replace Color
Variations
Match Color
Red Eye

Masks

Mask Panel
Vector Masks
Clipping Masks
Quick Mask
Layer Masks
Refine Edge

Type

Type Tools
Fonts & Colors
Type on a Path
Type as a Mask
Edit Type
Rasterize Type

Painting

Gradients
Dodge / Burn & Sponge
Smudge / Sharpen & Blur
The Eraser Tools
Define Patterns

Brushes

Mouse vs. Tablet
Brush Preview
Define Brushes
Brush Dynamics

Drawing

Pen Tool
Edit Paths
Vector Shapes

Filters & Effects

Filter Gallery
Smart Filters
Blurs
Textures
Lighting Effects
Styles
Liquefy
Fade

Smart Objects

Smart Objects pt. 1
Smart Objects pt. 2

Guides & Annotation

Guides
Notes Annotation

Camera Raw

Camera Raw pt. 1
Camera Raw pt. 2

Retouching

Retouching Tools
Clone Stamp
Clone with Two Images
Clone Source
Patch Tool
Dust & Scratches

History

History
Art History Brush
History Brush

Vanishing Point

Vanishing Point pt. 1
Vanishing Point pt. 2

Channels

The Channels Palette
Alpha Channels

Actions

Record Actions
Play Actions

Automation

Batch Rename
PDF Presentation
Droplets
Contact Sheets
Picture Package
Web Photo Gallery

Saving & Exporting

Save Documents
Flatten
Export to Illustrator
PDF

Scanning

Scan in Artwork

Output

Printing
File Formats

Web Preparation

The Slice Tool
Slice Options
Save for Web

Resources

Magazines
Websites

Project: Orbiting Mothership

Mothership Overview
Orbiting Mothership pt. 1
Orbiting Mothership pt. 2
Orbiting Mothership pt. 3
Orbiting Mothership pt. 4
Orbiting Mothership pt. 5

Course Information:


Course: Adobe Photoshop CS4
Author: Dwayne Ferguson
Release Date: 2009-01-16
Duration: 9 hrs / 141 tutorials

About VTC


The Virtual Training Company (VTC) started in Californias Silicon Valley in 1996, and is one of the leading online training providers in the web today. Theyve built up a library of more than 1000 video training courses, which you can access entirely for $30/month.

Heres what some of their satisfied customers have to say:

This site is basically going to save my semester. I will be using it beyond that though. What a great site. Worth every penny. Thank you so much for your product.
- Kevin

My company recently switched out to Outlook 2010, gave us a pamphlet of a few pages covering the very basics. We were lost! Especially coming from Groupwise/Novell. That said, Laurie Ulrich Fuller is an outstanding instructor. This has been the simplest way to explain Outlook 2010. Loved her!!! She made my life easier. Thanks a million!!!
- Celia Esquivel

Geoff Blake performed superbly on introducing Acrobat forms: clear, well-organized and instructive on the basics of the process. Bravo! I would highly recommend this course to anyone searching for a basic introduction to Acrobat forms.
- Brad B.

Over the course of a few weeks, I received approximately 60 hours of on-line Project Managent training from Vanina Mangano through VTC. The training was for Project Management certification exam and I took 3 courses PMBOK (a bootcamp like course), PMBOK Schedule and PMBOK Risk. Vanina really prepared me for the test. I particularly found the Schedule and Risk Bundles instructive in expanding my intuitive understanding of these overall processes. Vanina did a great job of performing the training and her commentary and explanations were right on. Vaninas melodic voice is easy to listen to - she motivates and encourages study. I passed the Project Management Certification on my first try after completing this course of study. Top qualities: Great Results, Personable, Good Value
- Annemarie DeMarco

I joined on the 20th August 2010 to your program and Im most impressed. I need to learn Excel for my job and at 64 years old I never thought I would ever be able to conquer spreadsheets etc. I have been practicing along with your tutorials since Saturday and I cant believe how quickly I am picking it up. The online course is worth every penny and I will be recommending you and your team for the excellent service and content to anyone who will listen. Magic! By the way Im not that great on a computer either so if I can do it, then its a doddle for anyone else!
- Barbara Richards

Are you ready to be part of this community of satisfied learners?

[Become a VTC.com Member TODAY!]

Get complete access to ALL the VTC Online University courses for $30/month


Are you ready to start your Adobe Photoshop CS4 Online Training for Beginners? Then sign up for a VTC.com membership today!
Read more »
Posted by at No comments:
Labels: , , , , , , , , , ,
Subscribe to: Posts (Atom)