1 minute read

Graph is a collection of nodes that may or may not be connected to each other.

The nodes are actually called vertices, the connections between vertices are called edges.
So its made of vertices and edges, where vertices are just nodes that might have values, for instance integer values, and the edges are connections, things that connect the nodes to one another.

Many things in life can be represented by graphs for example, an airport, a social network or a city map where locations are a verticies and roads between locations are edges.

Important concepts in graphs.

  • Graph Cycle

    Simply put occurs in a graph when three or more vertices in the graph are connected to form a closed loop

    Note that the definition of a graph cycle is sometimes broadened to include cycles of length two or one.
    For example wikipedia page where one link, link to different pages, but finally you may end up on the page that you started.

  • Acyclic graph

    A graph that has no cycles.

  • Cyclic graph

    A graph that has at least one cycle.

  • Directed Graph

    Meaning that edges are directed and can be traversed only in one direction which is specified.
    For example from some airports you can reach a different airport but just in one way.

  • Undirected Graph

    A graph without directed edges, meaning that they can be traversed in both directions.
    For example a graph of friends would be probably undirected as one friend can reach one another.

  • Connected Graph

    Whether graph is connected, it is connected if any node is reachable from another node, or rather if there is some path between any two nodes in the graph.

    In case of a directed graph, the graph is:

    • strongly connected: if there are bidirectional connections between the vertices of every pair of vertices (i.e., for every vertex pair (x, y) you can each y from x and x from y)
    • weakly connected (if there are connections of every pair of vertices (not necessarily bidirectional)

    A graph that is not connected may be called disconnected.