Graph

 Graph

Graphs are non linear data structure. A graph is made up of sets of nodes and lines. Nodes are called vertices. Lines are called edges. Lines are used to connect nodes. 

Types of Graph

(1) Undirected Graph

An undirected graph has edges that have no direction. Undirected graph also called an undigraph.

 

(2) Directed Graph

A directed graph has edges  that are unidirectional. Directed graph also called digraph.

 

 (3) Weighted Graph

 A weighted graph has weights associated with each edge. The weight can represent distances costs.

 

(4) Complete Graph

A complete graph if there is an edge between every pair of vertices. In complete graph every node should be connected to all other nodes.

 

(5) Acyclic Graph

A directed graph that has no cycles are called acyclic graph.

 

Terminologies of a Graph

  • Degree of Node

        The number of edges that a node contains is called degree of the node.

 

       Here A has a degree of 3 node D has a degree of 2 node.

  • Out degree

        The number of edges beginning from a node is called the out degree of the node.

 

    •         Outdegree of A is 3.
    •        Outdegree of F is 0.

  • In degree

        The number of edges ending at a node is called in degree.

 


    •         Indegree of E is 3.
    •         Indegree of F is 2.

  • Source node (Start node)

        The node that has a positive out degree but zero in degree.

 

        Node A is the source node. Outdegree is 3 and indegree is 0.

  • Sink node (End node)

        The node that has a positive in degree but zero out degree.

    •         Node E is the sink node.
    •         Indegree is 3 and outdegree is 0.

  • Path

        A list of nodes of a graph where each node has an edge from it to the next node is          called the path.

  • Length

        The number of edges in a path of a graph is called length of the graph.

  • Loop Edge

        An edge A is said to be a loop edge if it has the same node at its tail and head.

 

Representation of a Graph

  • Adjacency Matrix

        It is a table which represents the edges between vertices of the graph.

 

 

A 

B 

C 

D 

A 

0 

1 

1 

1 

B 

0 

0 

0 

1 

C 

0 

0 

0 

1 

D 

0 

0 

1 

0 

  • Adjacency List

        This is any array of linked list, one for each vertex. Each linked list contains all of the     vertices that are adjacent to a given vertex.

  

 

Traversing of a Graph

(1) BFS

BFS stand for Breadth first search. Breadth first search uses FIFO queue. It start several paths at a time and advance in each one step at a time.

Example 

 

BFS = A ,B ,C ,D ,E ,F ,G ,H

 

BFS = 1 ,3 ,4 ,2 ,7 ,9

(2) DFS

DFS stand for Depth first search. Depth first search uses LIFO stack. In DFS , once a possible path is found it continue search until the end of the path.

Example

 

DFS = A ,B ,D ,H ,E ,C ,F ,G

 

DFS = 1 ,3 ,2 ,4 ,7 ,9


Comments

Post a Comment

If you have any doubts, please let me know

Popular Posts

Computer Abbreviation

Topic Outline Introduction to computer abbreviation Abbreviation of system unit component  Abbreviation of storage devices  Abbreviation of input and output devices  Abbreviation of data communication and computer network Abbreviation of Programming Languages Abbreviation of Operating System and Networks  In this lecture, we will discuss the different Computer Abbreviations. Introduction to Computer & Information technology   Abbreviation   Full-Form   1   Computer     Common Operating Machine Particularly Used for Technological and Education Research   2   IPC   Information Processing Cycle   3   IT   Information Technology   4   PC   Personal Computer   5   CPU   Central Processing Unit   6   USB   Universal Serial Bus   7   ENIAC   Electronical Numerical Integrator and Calculator   8   EDVAC   Electronic Discrete Variable Autom...
Read more

Transport Layer

Image
  Topic Outline Transport Layer TCP Function of TCP UDP Difference between TCP and UDP Transport Layer The Transport layer is essentially responsible for delivering data to the appropriate application on the host computer. It receives requests from the application layer protocols and passes them down to the internet network layer. Two most commonly used transport layer protocols are the connection TCP and connection UDP. TCP  Transmission Control Protocol End to End communication for user processes. Processes can communicate in a simple stream of binary data. Each byte of data will arrive in the order it was sent. If some part of the data cannot be received this will be made explicit by an error being passed to the user code. Functions of TCP   (1) Data Transfer TCP transfer a continuous stream of bytes. TCP itself decides how to segment the data and it may forward the data at its own convenience. (2) Reliability TCP assigns a sequence number to each byte transmitted and ...
Read more

Introduction to Database

 Topic Outline Introduction to Database  Types of Data Metadata Components of Database Environment Application Program Range of Database applications Types of Users Types of Data Different types of data are as follow: Numeric Data It consists of numeric digits from 0 to 9 like 22, 58, 1123, or -123. The numeric data may be, either positive or negative. Alphabetic Data It consists of alphabetic letters from A to Z, a to z, and blank spaces. For example, "Computer", "Software", "IT", and "Automata" etc. Image Data Image data includes graphs, pictures, drawings,, and charts. Image data is more comprehensive.  Alphanumeric Data It consists of numeric digits (0 to 9) , letters (A- to Z) and all special characters (+, -, @, $, #) etc. Audio Data This data includes music, speech, and any type of sound. Video Data This data is a set of full-motion images played at a high speed. It is used to display actions and movement. Metadata The metadata can be defi...
Read more

Types of database

Topic Outline Types of Database Object-Oriented Database Centralized Database Decentralized Database Distributed Database Hierarchical Database Personal Database Cloud Database Multi-Dimensional Database Operational Database Relational Database  1:Object-Oriented Database Object-oriented database stores data in the form of objects. An object is an item that can contain data and functions. For example, an object employee may contain data about an employee such as Employee ID, Name, Address, Phone Number, etc. It may also contain functions to process the data such as printing the record of an employee, calculating salary, etc. Characteristics The object-oriented data model must be able to provide complex object representation. The object-oriented data model must be extensible. It means it provides support for defining new data types and methods. The object-oriented data model must support encapsulation or information hiding. The object-oriented data model must exhibit inheritance. In...
Read more

Threads in operating system

Image
  Topic Outline Threads Difference between thread and process Types of Threads Kernel Level Thread User Level Thread Multithreading Advantages Resource Sharing Responsiveness Utilization of Multiprocessor Architecture Multithreading Models Many to One Model One to One Model Many to Many Model Threads Thread is a basic unit of CPU utilization. Thread is also called a lightweight process. Thread is a process within a process but it does not have its own process control block. In a process, multiple threads are created. In a process, multiple threads allow multiple executions.   The thread consists of the following things. Thread ID Register Program counter Stack Difference between threads and process. Threads   Process   In threads no system  call  is  involved .   In a process system call is  involved .   Thread  is  a  lightweight  process.   The Process is  heavyweight .  If  the th...
Read more

Display devices

Image
  Topic Outline Display devices Types Cathode Ray Tube Flat Panel Display Emissive Display LED OLED Gas Plasma Non-Emissive Display LCD A display device is an output device. It is used to represent information in the form of text, graphics, images, and video. The display for a desktop computer is a monitor. Mobile computers and devices integrate the display in the same physical case. Some displays have touch screens such as mobile phones and laptops etc. The output displayed by a display device is called soft copy. Display devices are available in different sizes. For example When we write any document on the computer, it is a soft copy of the document. When we get a print of this document, it is a hard copy of the document. Types Types of display devices are as follows. (1) Cathode Ray Tube A cathode-ray tube creates an image on the screen by using a beam of electrons. Cathode ray tube consists of one or more guns. These guns fire a beam of electrons inside the screen. The monitor...
Read more

Shortcut keys of computer

Important Shortcut keys of Computer Shortcut keys are an easier and quicker method of executing the commands in the computer system. When we work on the computer, different shortcut keys are used. Some important shortcut keys are as follow: Short cut keys   Working   Ctrl+ C   Copy the select item   Ctrl+ V   Paste the item   Ctrl+ X   Cut the select item   Ctrl+ Del   Cut the select item   Ctrl+ A   Select all text   Ctrl+ Home   Go to beginning of the document   Ctrl+ End   Go to end of the document   Ctrl +( left arrow)   Move one word to the left at a time   Ctrl +( right arrow)   Move one word to the right at a time   Ctrl +( Plus key)   Adjusts width in window explorer   Ctrl +( Minus key)   Adjust width in window explorer   Ctrl+ Alt+ Del   Windows task manager   Ctrl+ Ecs   Bring up the start menu   Ctrl+F4   Close window in progra...
Read more

History of Computer

Image
  Topic Outline History of computer Abacus John Napier's Bone Blaise Pascal Von Leibnitz Charles Xavier Joseph Charles Babbage Herman Hollerith Atanasoff George Boole Mark 1 Computer ENIAC  EDVAC UNIVAC Commercial Computer History of computer Today those computers that we are used behind this many efforts of different peoples. An Abacus computing device was used for addition and subtraction. John Napier Bones created the slide rule to perform mathematical calculations. Blaise Pascal invented the mechanical machine for adding and subtracting. Von Leibnitz also invented the calculating machine that was used for division and multiplication. Charles Xavier invented the machine that could perform addition, subtraction, multiplication, and division.  Charles Babbage invented a difference engine and an analytical engine. A brief history is available below👇. The computer was invented because 'necessity is the mother of invention'. A brief history behind the invention of the comp...
Read more