Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    Graphs Lab

    Uploaded by

    l227437

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Graphs Lab

    Uploaded by

    l227437
    1 views3 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    1 views3 pages

    Graphs Lab

    Uploaded by

    l227437

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 3

    Graphs Lab

    Objective:
    The objective of this experiment is to implement graph using adjacency matrix and adjacency
    list.
    Introduction:
    Graph is a data structure that consists of following two components:
     A finite set of vertices also called as nodes.
     A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is
    not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates that there
    is an edge from vertex u to vertex v. The edges may contain weight.

    Graphs are used to represent many real life applications as they can be used to represent networks. The
    networks may include paths in a city or telephone network or circuit network.

    An example of undirected graph with 5 vertices is shown in Figure 12.1.

    Figure 12.1

    Graph representations:
    Following two are the most commonly used representations of graph.
     Adjacency Matrix
     Adjacency List

    There are other representations also like, Incidence Matrix and Incidence List. The choice of the graph
    representation is situation specific. It totally depends on the type of operations to be performed and ease
    of use.

    AdjacencyMatrix:
    Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D
    array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency
    matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted
    graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
    The graph shown in Figure 12.1 is represented using adjacency matrix in Figure 12.2:

    Figure 12.2

    Adjacency Matrix Representation of the above graph

    Exercise 1: Implement the following Graph ADT using Adjacency matrix representation of graph
    #ifndef GRAPH_H
    #defineGRAPH_H

    classGraph
    {
    public:
    //part1: constructor initializes adjacency matrix
    Graph(int numVertex);
    //part2: returns the number of vertices in the graph
    int GetNumVertices();
    //part3: returns the number of edges in the graph
    int numberOfEdges();
    //part4: inserts edge going from one vertex to another
    void insertEdge(int frmVertex, int toVertex);
    //part5: removes edge going from one vertex to another
    void removeEdge((int frmVertex, int toVertex);
    //part6: returns the degree of the node passed
    int degree(int vertex);

    //part7: outputs the order in which vertices are visited during DFS
    //Starting from node s.
    void depthfirstSearch(int s);

    //part8: outputs the order in which vertices are visited during BFS
    //Starting from node s.
    void breadthfirstSearch(int s);

    private:
    int **adj_matrix;
    int numVertices;

    };
    #endif
    You may test your implementation using the following client
    //Following is a sample client
    #include<iostream>
    #include"Graph.h"
    usingnamespace std;
    int main()
    {
    Graph *g; //creating an object of graph with 5 vertices
    g=new Graph(5);

    //inserting edges in the graph


    g->inserEdge(0,1);
    g->inserEdge(0,4);
    g->inserEdge(1,0);
    g->inserEdge(1,2);
    g->inserEdge(1,3);
    g->inserEdge(1,4);
    g->inserEdge(2,1);
    g->inserEdge(2,3);
    g->inserEdge(3,1);
    g->inserEdge(3,2);
    g->inserEdge(3,4);
    g->inserEdge(4,0);
    g->inserEdge(4,1);
    g->inserEdge(4,3);

    //display total number of edges


    cout<<”Number of edges are “<<g->numberOfEdges()<<endl;

    //display degree of vertex number 4


    cout<<”Degree of vertex “<<g->degree(4)<<endl;

    cout<<”Output for Depth first search starting from vertex 0 “<<endl;


    g->depthfirstSearch(0);
    cout<<”Output for Breadth first search starting from vertex 0 “<<endl;
    g->breadthfirstSearch(0);
    return 0;
    }

    You might also like