Graph: Introduction | Representation of Graph: Adjacency Matrix | Data Structure & Algorithm | #cs

A graph G is defined as an ordered set (V, E), where V(G) represents the set of vertices and E(G) represents the edges that connect these vertices.

Graph Terminology 1. Adjacent nodes or neighbours For every edge, e = (u, v) that connects nodes u and v, the nodes u and v are the end-points and are said to be the adjacent nodes or neighbours. 2. Degree of a node Degree of a node u, deg(u), is the total number of edges containing the node u. If deg(u) - 0, it means that u does not belong to any edge and such a node is known as an isolated node. 3. Regular graph It is a graph where each vertex has the same number of neighbours. That is, every node has the same degree. A regular graph with vertices of degree k is called a k-regular graph or a regular graph of degree k. 4. Path A path P written as P=( v0,v1,v2, ..., vN), of length n from a node u to v is defined as a sequence of (n+1) nodes. 5. Closed path A path p is known as a closed path if the edge has the same end-points. That is, if V0 = Vn. 6. Simple path A path p is known as a simple path if all the nodes in the path are distinct with an exception that v. may be equal to v.. If v.. v., then the path is called a closed simple path. 7. Cycle A path in which the first and the last vertices are same. A simple cycle has no repeated edges or vertices (except the first and last vertices). 8. Connected graph A graph is said to be connected if for any two vertices (u, v) in v there is a path from u to v. That is to say that there are no isolated nodes in a connected graph. A connected graph that does not have any cycle is called a tree. Therefore, a tree is treated as a special graph. 9.Complete graph A graph G is said to be complete if all its nodes are fully connected. That is, there is a path from one node to every other node in the graph. A complete graph has n(n-1)/2 edges, where n is the number of nodes in G. 10. Labelled graph or weighted graph A graph is said to be labelled if every edge in the graph is assigned some data. In a weighted graph, the edges of the graph are assigned some weight or length. The weight of an edge denoted by w(e) is a positive value which indicates the cost of traversing the edge. 11. Multiple edges Distinct edges which connect the same end-points are called multiple edges. That is, e (u, v) and e' (u, v) are known as multiple edges of G. 12. Loop An edge that has identical end-points is called a loop. That is, e = (u, v). 13. Multi-graph A graph with multiple edges and/or loops is called a multi-graph. 14. Size of a graph The size of a graph is the total number of edges in it. DIRECTED GRAPHS A directed graph G, also known as a digraph, is a graph in which every edge has a direction assigned to it. An edge of a directed graph is given as an ordered pair (u, v) of nodes in G. For an edge (u,v), • The edge begins at u and terminates at v. • u is known as the origin or initial point of e. Correspondingly, v is known as the destination or terminal point of e. • u is the predecessor of v. Correspondingly, v is the successor of u. • Nodes u and v are adjacent to each other. REPRESENTATION OF GRAPHS There are two common ways of storing graphs in the computer's memory. They are: • Sequential representation by using an adjacency matrix. • Linked representation by using an adjacency list that stores the neighbours of a node using a linked list. In this video, we will discuss Sequential representation by using an adjacency matrix schemes in detail. Adjacency Matrix Representation An adjacency matrix is used to represent which nodes are adjacent to one another. By definition, two nodes are said to be adjacent if there is an edge connecting them. In a directed graph G, if node V is adjacent to node U, then there is definitely an edge from U to V. That is, if V is adjacent to U, we can get from U to V by traversing one edge. For any graph G having n nodes, the adjacency matrix will have the dimension of n x n. In an adjacency matrix, the rows and columns are labelled by graph vertices. An entry aij in the adjacency matrix will contain 1, if vertices vi and vj, are adjacent to each other. However, if the nodes are not adjacent, aij, will be set to zero. Since an adjacency matrix contains only 0's and 1's, it is called a bit matrix or a Boolean matrix. The entries in the matrix depend on the ordering of the nodes in G. Therefore, a change in the order of nodes will result in a different adjacency matrix.

For more detail click here