Graph algorithms

Question 1

graph basic definition

Answer 1

A graph is an abstract notation used to represent the connection between pairs of objects. It can be used to represent networks: systems of roads, airline flights from city to city, how the Internet is connected, or social connectivity on Facebook, Twitter, etc. We use some standard graph algorithms to solve these otherwise difficult problems.

Question 2

2 basic components of a graph

Answer 2

Node/Vertex and Edge

Question 3

Node/Vertex

Answer 3

It is the entity that has a name, known as the key, and other information related to that entity.

Question 4

Edge

Answer 4

expresses the relationship between two nodes

Question 5

Ways to represent a graph

Answer 5

Adjacency list and adjacency matrix

Question 6

Adjacency list

Answer 6

An adjacency list is used to represent a finite graph. The adjacency list representation allows you to iterate through the neighbors of a node easily. Each index in the list represents the vertex and each node that is linked with that index represents its neighboring vertices.

Question 7

Adjacency matrix

Answer 7

An adjacency matrix is a square matrix labeled by graph vertices and is used to represent a finite graph. The entries of the matrix indicate whether the vertex pair is adjacent or not in the graph.

In the adjacency matrix representation, you will need to iterate through all the nodes to identify a node’s neighbors.

Question 8

Types of graph in terms of structure

Answer 8

Directed graph and undirected graph

Question 9

Directed graph

Answer 9

The directed graph is the one in which all edges are directed from one vertex to another.

Question 10

Undirected graph

Answer 10

The undirected graph is the one in which all edges are not directed from one vertex to another.

Question 11

Mathematical notation of graphs

Answer 11

The set of vertices of graph GG is denoted by V(G)V(G), or just VV if there is no ambiguity.

An edge between vertices uu and is written as {u, v}u,v. The set of edges of GG is denoted E(G)E(G), or just EE if there is no ambiguity.

Example:
vertex set V = [1, 2, 3, 4, 5, 6].

The edge set E = [[1, 2], [1, 5], [2, 3], [2, 5], [3, 4], [4, 5], [4, 6]].

Question 12

Path in a graph

Answer 12

A path in a graph G = (V, E) is a sequence of vertices v1, v2, …, vk, with the property that there are edges between vivi and vi+1vi+1. We say that the path goes from v1v1 to vkvk. The sequence 6, 4, 5, 1, 26,4,5,1,2 defines a path from node 66 to node 22. Similarly, other paths can be created by traversing the edges of the graph. A path is simple, if its vertices are all different.

Question 13

Cycle in a graph

Answer 13

A cycle is a path v1, v2, …, vk for which

k > 2k>2,
the first k - 1k−1 vertices are all different, and
v1 = vkv1=vk`

Question 14

What is a connected graph

Answer 14

For every pair of vertices, u and v there exists an edge between u and v

Question 15

Implementation of AdjNode and graph class

Answer 15

class AdjNode:
“””
A class to represent the adjacency list of the node
“””

    def \_\_init\_\_(self, data):
        """
        Constructor
        :param data : vertex
        """
        self.vertex = data
        self.next = None

class Graph:
“””
Graph Class ADT
“””

    def \_\_init\_\_(self, vertices):
        """
        Constructor
        :param vertices : Total vertices in a graph
        """
        self.V = vertices
        self.graph = [None] * self.V

    # Function to add an edge in an undirected graph

def add_edge(self, source, destination):
    """
    add edge
    :param source: Source Vertex
    :param destination: Destination Vertex
    """

        # Adding the node to the source node
        node = AdjNode(destination)
        node.next = self.graph[source]
        self.graph[source] = node