Scribd Logo
Upload

Welcome to Scribd!

  • 10 views

    Graph Basic Terminology

    Uploaded by

    Manjula Ravichandran

    Copyright:

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

    Graph Basic Terminology

    Uploaded by

    Manjula Ravichandran
    10 views21 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    10 views21 pages

    Graph Basic Terminology

    Uploaded by

    Manjula Ravichandran

    Copyright:

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

    UNIT IV :

    Basic terminology – Representation of Graph-


    Graph traversal – Graph Algorithms

    Introduction to Graph in Data


    Structure
    What Are Graphs in Data Structure?
    ✓ Graphs are non-linear data structures
    comprising a finite set of nodes and
    edges.
    ✓ The edges connect any two nodes in
    the graph, and the nodes are also
    known as vertices.
    Basics
    • A non-linear data structure is one where the elements are not
    arranged in sequential order.
    • For example, an array is a linear data structure, it is arranged
    one after the other.
    • Traverse all the elements of an array in a single run.
    • It is not the case in non-linear data structures. The elements
    are arranged in a multiple levels (hierarchical pattern).
    • Graphs are non-linear.
    Basic
    • The next word to pay attention is finite.
    • The graph to have a finite and countable number of
    nodes.
    • This is a rather non-agreeable term.
    • Essentially, a Graph may have an infinite number of
    nodes and still be finite.
    Real-World Example
    • The best example of graphs in the
    real world is Facebook.
    • Each person on Facebook is a
    node and is connected through
    edges.
    • Thus, A is a friend of B.
    • B is a friend of C, and so on.
    Graph Terminologies
    1. Graph Representation:
    • A graph is represented as a pair of
    sets (V, E).
    • V is the set of vertices or nodes.
    • E is the set of Edges.
    • In the above example,
    V = { A, B, C, D, E }
    E = { AB, AC, AD, BE, CD, DE }
    Graph Terminologies

    2. Node or Vertex: The elements of a


    graph are connected through edges.
    3. Edges: A path or a line between two
    vertices in a graph.
    4. Adjacent Nodes: Two nodes are called
    adjacent if they are connected through an
    edge.
    Node A is adjacent to nodes B, C, and D in
    the above example, but not to node E.
    Graph Terminologies
    5. Path: Path is a sequence of edges between
    two nodes.
    It is essentially a traversal starting at one
    node and ending at another.
    Thus, in the example above, there are
    multiple paths from node A to node E.
    Path(A, E) = { AB, BE }
    OR
    Path(A, E) = { AC, CD, DE }
    OR
    Path(A, E) = { AD, DE }
    Types of Graphs in Data Structures
    1. Finite Graph
    The graph G=(V, E) is called a finite
    graph if the number of vertices and
    edges in the graph is limited in
    number
    2. Infinite Graph
    The graph G=(V, E) is called a
    finite graph if the number of
    vertices and edges in the graph
    is interminable.
    3. Trivial Graph
    A graph G= (V, E) is trivial if it contains only a
    single vertex and no edges.

    4. Simple Graph
    If each pair of nodes or vertices in a
    graph G=(V, E) has only one edge, it is a
    simple graph. One edge connecting two
    vertices.(one-to-one interactions between
    two elements).
    5. Multi Graph
    Numerous edges between a pair of
    vertices in a graph G= (V, E), is referred
    as a multigraph.
    There are no self-loops in a Multigraph.
    6. Null Graph
    It's a reworked version of a trivial graph.
    If several vertices but no edges connect
    them, a graph G= (V, E) is a null graph.
    7. Complete Graph
    ✓ Graph G= (V, E) is a simple graph and it is
    complete.
    ✓ Using the edges, n number of vertices must
    be connected.
    ✓ It's known as a full graph because each
    vertex's degree must be n-1.
    8. Pseudo Graph
    If a graph G= (V, E) contains a self-loop
    besides other edges, it is a pseudograph.
    9. Regular Graph
    If a graph G= (V, E) is a simple graph with
    the same degree at each vertex, it is a
    regular graph.
    10. Weighted Graph
    A graph G= (V, E) is called a labeled or
    weighted graph, each edge has a value or
    weight representing the cost of traversing
    that edge.
    11. Directed Graph
    A directed graph also referred to as a
    digraph, is a set of nodes connected by
    edges, each with a direction.
    12. Undirected Graph
    ✓ It comprises a set of nodes and edges has
    no direction.
    ✓ Undirected graph can form with a finite
    number of vertices and edges.
    13. Connected Graph
    ✓ path between one vertex of a graph
    to any other vertex,
    ✓ is called connected graph.

    14. Disconnected Graph


    ✓ no edge linking the vertices,
    ✓ the null graph as a disconnected graph.
    15. Cyclic Graph
    ✓ graph contains at least one graph
    cycle,
    ✓ it is considered to be cyclic graph.
    16. Acyclic Graph

    ✓ When there are no cycles in a graph,


    it is called an acyclic graph.
    17. Directed Acyclic Graph
    ✓ a directed acyclic graph (DAG),
    is a graph with directed edges
    but no cycle.
    18. Subgraph
    The vertices and edges of a
    graph that are subsets of another
    graph are known as a subgraph.
    Step 1

    Get the Gear

    Step 2
    GETTING
    Get Started
    TO GREAT
    Step 3

    Practice a Lot
    THANK YOU

    You might also like