Introduction to graphs

A graph can also be a tree or any open structure.

Types of Graphs

1. Undirected Graph

2. Directed Graph

Cycles in a Graph

A cycle happens when you start from a node and return to that same node.

• Undirected Cyclic Graph

• Directed Acyclic Graph (acyclic means no cycle) - DAG

Path

Contain a lot of nodes and each of them are reachable.

• A node cannot appear twice in a path.

Degrees on Graph

The number of edges going into or out of a node is called the degree of the node. It refers to the number of edges connected to it.

Property: The total degree of the graph equals 2 times the number of edges.

Edge weights

If edge weights are not provided, we assume each edge has a unit weight.

Input to a Graph

Given n and m:

• Determine if the graph is directed or undirected.

• n represents the number of nodes.

• m represents the number of edges.

Example:
n = 5 nodes
m = 6 edges

5 6
n lines represent edges
2 1
1 3
2 4
3 4
2 5
4 5

2 Ways of Representation

• Adjacency Matrix

• Adjacency List

Adjacency Matrix

adj[n+1][n+1]

Space - (N x N)

        for(int i=0; i<m; i++){
            adj[u][v] = 1;
            adj[v][u] = 1;
        }

Adjacency List

We use an array for a 1-based graph and create an array of adj[n+1].

        for(int i=0; i<m; i++){
            adj[u].add(v);
            adj[v].add(u);
        }

Directed graph

        for(int i=0; i<m; i++){
            adj[u].add(v);
        }

Space of Undirected - O(2xN)

Space of Directed - O(N)

Weighted graph

        for(int i=0; i<m; i++){
            adj[u].add(v);
            adj[v].add(u);
        }