Skip to main content
Practice

What is a Graph?

A graph is a data structure consisting of a set of vertices (nodes) connected by edges.

Graphs are highly useful for modeling network structures and are used to solve various real-world problems.

For example, social networks, computer networks, and road networks can all be represented as graphs.


Key Terms​

  1. Node(Vertex):

    • The basic unit of a graph, representing a position.

    • Examples: cities, checkpoints, individual computers in a network, etc.

  2. Edge:

    • A line connecting two nodes.

    • Edges can be 'undirected' (can move in both directions between nodes) or 'directed' (can move only in one direction).

  3. Weight(Cost):

    • The 'weight' assigned to an edge represents the cost or distance of movement between two nodes.

    • Not all edges need to have weights.

  4. Adjacency List:

    • A method of storing a list of other nodes connected to each node.

    • Memory-efficient and useful for quickly finding nodes directly connected to a given node.

  5. Adjacency Matrix:

    • A 2D array used to represent the connections between nodes.

    • Allows for quick verification of connections between nodes but uses more memory.

  6. Directed Graph:

    • A graph with directional edges.

    • Examples: links between web pages, one-way streets.

  7. Undirected Graph:

    • A graph with non-directional edges.

    • Examples: Facebook friend relationships, two-way roads.

  8. Cycle:

    • A structure where nodes are connected in a circular fashion.

    • A graph without cycles is called an 'acyclic graph.'

  9. Connected:

    • A graph is 'connected' if all its nodes are either directly or indirectly connected to each other.

    • If one can reach all other nodes starting from any node, the graph is considered fully connected.

  10. Tree:

    • A connected graph without cycles.

    • All trees are graphs, but not all graphs are trees.

    • Trees are often used to represent hierarchical structures.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.