Scribd Logo
Upload

Welcome to Scribd!

  • 86 views

    Graphs C++

    Uploaded by

    Ayesha Fida
    This document defines and describes graph data structures and their representations. A graph consists of vertices and edges, and can be directed or undirected. Graphs can be represented using adjacency matrices or adjacency lists. Adjacency matrices store connectivity as a 2D array, while adjacency lists use linked lists of neighbors for each vertex. The document also discusses graph traversals, including breadth-first and depth-first search algorithms.

    Copyright:

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

    Graphs C++

    Uploaded by

    Ayesha Fida
    86 views36 pages
    This document defines and describes graph data structures and their representations. A graph consists of vertices and edges, and can be directed or undirected. Graphs can be represented using adjacency matrices or adjacency lists. Adjacency matrices store connectivity as a 2D array, while adjacency lists use linked lists of neighbors for each vertex. The document also discusses graph traversals, including breadth-first and depth-first search algorithms.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document defines and describes graph data structures and their representations. A graph consists of vertices and edges, and can be directed or undirected. Graphs can be represented using adjacency matrices or adjacency lists. Adjacency matrices store connectivity as a 2D array, while adjacency lists use linked lists of neighbors for each vertex. The document also discusses graph traversals, including breadth-first and depth-first search algorithms.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    86 views36 pages

    Graphs C++

    Uploaded by

    Ayesha Fida
    This document defines and describes graph data structures and their representations. A graph consists of vertices and edges, and can be directed or undirected. Graphs can be represented using adjacency matrices or adjacency lists. Adjacency matrices store connectivity as a 2D array, while adjacency lists use linked lists of neighbors for each vertex. The document also discusses graph traversals, including breadth-first and depth-first search algorithms.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 36

    Graph Data Structure

     A graph G is a pair, G = (V, E), where V is a finite nonempty set, called the set of
    vertices of G and E V x V . That is, the elements of E are pairs of elements of V.
     E is called the set of edges of G.
     G is called trivial if it has only one vertex.
     Let V(G) denote the set of vertices, and E(G) denote the set of edges of a graph G.
    If the
    elements of E are ordered pairs, G is called a directed graph or digraph; otherwise,
    G is called an undirected graph. In an undirected graph, the pairs (u, v) and (v, u)
    represent
    the same edge.
     Let G be a graph. A graph H is called a subgraph of G if V(H) ˝ V(G) and
    E(H) ˝ E(G); that is, every vertex of H is a vertex of G, and every edge in H is an
    edge in G.
     A graph can be shown pictorially. The vertices are drawn as circles, and a label
    inside the
    circle represents the vertex. In an undirected graph, the edges are drawn using
    lines. In a
    directed graph, the edges are drawn using arrows.
    Let G be an undirected graph. Let u and v be two vertices in G. Then:
     u and v are called adjacent if there is an edge from one to the other; that is, (u, v) ˛ E.
     An edge incident on a single vertex is called a loop.
     If two edges, e1 and e2, are associated with the same pair of vertices {u, v}, then e1
    and e2 are called parallel edges.
     A graph is called a simple graph if it has no loops and no parallel edges. Let e = (u,
    v) be an edge in G.
     We then say that edge e is incident on the vertices u and v. The degree of u, written
    deg(u) or d(u), is the number of edges incident with u.
     We make the convention that each loop on a vertex u contributes 2 to the degree of u.
    u is called an even (odd) degree vertex if the degree of u is even (odd).
     There is a path from u to v if there is a sequence of vertices u1, u2, . . ., un
    such that u = u1, un = v and (ui, ui+ 1) is an edge for all i = 1, 2, . . ., n - 1.
     Vertices u and v are called connected if there is a path from u to v.
     A simple path is a path in which all the vertices, except possibly the first and last
    vertices, are distinct.
     A cycle in G is a simple path in which the first and last vertices are the same.
     G is called connected if there is a path from any vertex to any other vertex.
    Graph Representation

     To write programs that process and manipulate graphs, the graphs must be stored
    —that
    is, represented—in computer memory. A graph can be represented (in computer
    memory) in several ways. We now discuss two commonly used ways: adjacency
    matrices
    and adjacency lists.
    Adjacency Matrix

     Let G be a graph with n vertices, where n > 0. Let V(G) = {v1, v2, . . ., vn}. The
    adjacency matrix AG is a two-dimensional n n matrix such that the (i, j)th entry
    of AG is 1 if there is an edge from vi to vj; otherwise, the (i, j)th entry is 0. That
    is,
     In an undirected graph, if (vi, vj) ˛ E(G), then (vj, vi) ˛ E(G), so
    AG(i, j) = 1 = AG( j, i). It follows that the adjacency matrix of an undirected graph is
    symmetric.
    Sparse Matrix
     Sparse Matrix Representations can be done in many ways following are two
    common representations:
     Array representation
     Linked list representation
    Adjacency lists

     Let G be a graph with n vertices, where n > 0. Let V(G) ={v1, v2, . . ., vn}. In the
    adjacency list representation, corresponding to each vertex, v, there is a linked list
    such that each node of the linked list contains the vertex, u, such that (v, u)
    belongs to E(G).
     Because there are n nodes, we use an array, A, of size n, such that A[i] is a
    reference variable pointing to the first node of the linked list containing the
    vertices to which vi is adjacent.

     Clearly, each node has two components, say vertex and link. The component
    vertex contains the index of the vertex adjacent to vertex i.
    Graph Traversals

     Breadth First
     Depth First
    Breadth First Traversal
    Depth First Traversal
    class iterator
    {
    Node *p;
    public:
    iterator()
    {
    p = NULL;
    }
    }

    You might also like