Graphs
- Graph is a non linear data structure.
- A graph is a collection of nodes(called vertices), and the connections between them, called edges.
- Graph is either Undirected or directed.
- When the edges in a graph have a direction, the graph is called a directed graph.
- The edges are called directed edges or arcs.
- Graphs are used to solve many real-life problems.
- Graphs are used to represent networks.
- The networks may include paths in a city or telephone network or circuit network.
- Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex (or node).
- Each node is a structure and contains information like person id, name, gender, locale etc.
- All of facebook is then a collection of these nodes and edges. This is because facebook uses a graph data structure to store its data.
Graph: A graph is a data structure G = {V, E} that consists of
- A collection of vertices V
- A collection of edges E, represented as ordered pairs of vertices (u, v)
Graph Terminology
- Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them.
- Path: A sequence of edges that allows you to go from vertex A to vertex B is called a path.
Graph representation as matrix called Adjacency matrix:
- An adjacency matrix is a 2D array of V x V vertices. Each row and column represents a vertex.
- If the value of any element
a[i][j]is 1, it represents that there is an edge connecting vertex i and vertex j.
Traversal: We use weight graphs and directions to find the BFS, DFS.
Applications: Using the weighted graph we can understand “Shortest path” problem which is the application of Graph.
