Scribd Logo
Upload

Welcome to Scribd!

  • 181 views

    DATA STRUCTURE USING C' PPT On Graph

    Uploaded by

    vasunews
    The document discusses different representations of graphs using data structures in C including adjacency matrix, adjacency list, and multi-list representations. It describes adjacency matrix as an N by N matrix where element Aij is 1 if there is an edge from vertex Vi to Vj and 0 otherwise. Adjacency list stores each vertex in a list along with a linked list of its adjacent vertices. The document also covers graph traversal methods like breadth-first and depth-first traversal, explaining that breadth-first traversal visits all nodes adjacent to the starting node before going further while depth-first traversal proceeds level-by-level along paths from start to end.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd

    DATA STRUCTURE USING C' PPT On Graph

    Uploaded by

    vasunews
    181 views12 pages
    The document discusses different representations of graphs using data structures in C including adjacency matrix, adjacency list, and multi-list representations. It describes adjacency matrix as an N by N matrix where element Aij is 1 if there is an edge from vertex Vi to Vj and 0 otherwise. Adjacency list stores each vertex in a list along with a linked list of its adjacent vertices. The document also covers graph traversal methods like breadth-first and depth-first traversal, explaining that breadth-first traversal visits all nodes adjacent to the starting node before going further while depth-first traversal proceeds level-by-level along paths from start to end.

    Original Title

    44224241-DATA-STRUCTURE-USING-‘C’-ppt-on-graph

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses different representations of graphs using data structures in C including adjacency matrix, adjacency list, and multi-list representations. It describes adjacency matrix as an N by N matrix where element Aij is 1 if there is an edge from vertex Vi to Vj and 0 otherwise. Adjacency list stores each vertex in a list along with a linked list of its adjacent vertices. The document also covers graph traversal methods like breadth-first and depth-first traversal, explaining that breadth-first traversal visits all nodes adjacent to the starting node before going further while depth-first traversal proceeds level-by-level along paths from start to end.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    181 views12 pages

    DATA STRUCTURE USING C' PPT On Graph

    Uploaded by

    vasunews
    The document discusses different representations of graphs using data structures in C including adjacency matrix, adjacency list, and multi-list representations. It describes adjacency matrix as an N by N matrix where element Aij is 1 if there is an edge from vertex Vi to Vj and 0 otherwise. Adjacency list stores each vertex in a list along with a linked list of its adjacent vertices. The document also covers graph traversal methods like breadth-first and depth-first traversal, explaining that breadth-first traversal visits all nodes adjacent to the starting node before going further while depth-first traversal proceeds level-by-level along paths from start to end.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 12

    SHALINI MISHRA B.

    TECH (IT) 090102067


    DATA STRUCTURE USING C PRESENTATION ON GRAPH REPRESENTATION

    INTRODUCTION
    GRAPH IS A MATHEMATICAL STRUCTURE AND FINDS ITS APPLICATIONS IN MANY AREAS OF INTEREST IN WHICH PROBLEM NEED TO BE SOLVED USING COMPUTERS. THUS THIS MATHEMATICAL STRUCTURE MUST BE REPRESENTED IN SOME KIND OF DATA STRUCTURE.

    THREE REPRESENTATIONS ARE USED

    1. ADJACENCY MATRIX 2. ADJACENT MATRIX 3. MULTI-LIST

    ADJACENT MATRIX ADJACENCY MATRIX FOR A GRAPH=(V, E) WITH N VERTICES, IS AN N*N MATRIX OF BITS, SUCH THAT AIJ = 1, IF THERE IS AN EDGE FROM VI TO VJ AND AIJ =0 , IF THERE IS NO SUCH EDGE SO A(I,J)={1 IF AND ONLY IF EDGE (VI,VJ) IS IN EG { 0 OTHERWISE

    ADJACENCY MATRIX FOR THE UNDIRECTED GRAPH

    ADJACENCY LIST REPRESENTATION:IN THIS REPRESENTATION WE STORE A GRAPH AS A LINKED STRUCTURE. WE STORE ALL THE VERTICES IN A LIST AND THEN FOR EACH VERTEX, WE HAVE A LINKED LIST OF ITS ADJACENT VERTICES. ADJACENCY LIST REPRESENTATION OF THE UNDIRECTED GRAPH . LIST OF ALL NODES I.E
    1 2 3 4 5 6

    GRAPH TRAVERSAL
    IT MEANS VISITING ALL THE NODES OF THE GRAPH. IT MAY BE NEEDED IN MANY APPLICATION AREAS AND THERE MAY BE MANY METHODS FOR VISITING THE VERTICES OF THE GRAPH. THERE ARE TWO TYPES OF GRAPH TRAVERSAL METHODS:1. BREADTH FIRST TRAVERSAL 2. DEPTH FIRST TRAVERSAL

    BREATH FIRST TRAVERSAL:ONE MODE IS SELECTED AS THE START POSITION. IT IS VISITED AND MARKED , THEN ALL UNVISITED NODES ADJACENT TO THE NEXT NODE ARE VISITED AND MARKED IN SOME SEQUENTIAL ORDER. ORDER 1,2,3,4,5,6,7,8 . THE SEQUENCE 1,3,2,6,5,4,7,8 IS ALSO VALID IN BREATH FIRST TRAVERSAL VISITING ORDER.
    4

    2 1 5 3 6

    FLOW CHART OF BREADTH FIRST SEARCH:Visit & mark the first node of graph Put the first node into the queue

    yes
    done

    NO

    Is the queue empty?


    Remove a node from the queue Point to the first entry in that nodes adjacency list At the end of the adjacency list?

    yes

    NO

    Has the node alaredy been visited

    Put the node on the queue & mark it . Its now been visited

    Move to the next node the adjacency list

    DEPTH FIRST TRAVERSAL:IT PROCEEDS LEVEL BY LEVEL , DEPTH FIRST TRAVERSAL FOLLOW FIRST A PATH FROM STARTING NODES TO AN ENDING NODE, THEN ANOTHER PATH FROM START TO THE END.

    THANK YOU

    You might also like