Skip to main content

Graph

What is a graph?​

Graph is a non-linear data structure that consists of vertices and edges. A vertex is called a node, a point or object in the Graph and an edge is used to connect two vertices with each other. The reason why graoh is called non-linear data structre is because it allows us to have different paths to get from one vertex to another.

Graph Properties​

  • A weighted graph is a graph where the edges have values where this weight represents things such as distance, capacity or time.

  • A connected graph is when all the vertices are connected through edges. A graph that is not connected which has either isolated subgraphs or single vertices.

  • A directed graph is when the edges between vertex pair have a direction where this direction represents either hierarchy or flow.

  • An undirected graph is when the edges between vertex pair have no direction - you can traverse them in either direction.

  • A cycle is a path in a graph where you start and end at the same vertex, visiting at least one other vertex along the way. The defination chanages with slightly with dircted and undirected graphs.

    • In an undirected graph, any path of 3+ vertices that returns to the start vertex forms a cycle.
    • Must follow edges direction to form a valid cycle.

  • Play around with the below interactive visual to have a good understanding of all the graph properties.

Interactive Visualization

Graph Representations​

Adjacency Matrix Graph Representation​

Adjacency Matrix is a 2D array where each cell on index (i, j) stores information about the edge from vertex i to j. You can either store the value '1' indicating that a edge ecists or the weight value indicating the cost to go to from vertex i to j. For an undirected graph, the values in the adjaceny matrix is symmetrical as the edges can both ways where as in a directed graph, we must decide which vertices the edges go from and to and then insert the value at the correct (i, j). This approach is better when the graph size is small and memory is not a constraint.

Interactive Visualization

Adjacency List Graph Representation​

Adjacency List is an array that contains all the vertices in the graph and each vertex linked to a Linked List with the vertex's edges. For a weighted graph, each vertex pointer has a pointer to a Linked List with edges stores as i, w where i is the index of the vertex the edge goes to and w is the weight of that edge.

Interactive Visualization