Skip to content

Latest commit

 

History

History
139 lines (116 loc) · 5.52 KB

GRAPH.md

File metadata and controls

139 lines (116 loc) · 5.52 KB

Main
 next(Graph Traversal)

Graph Terminologies


❇️ Introduction to Graph

A graph is a mathematical representation of a set of objects and the connections or relationships between them. It consists of two main components: vertices (also known as nodes) and edges. It a non-linear data structure

graph = nodes + edges

  • Vertices represents the entities, vertices are also known as vertex or nodes.
  • Edges represents the relationship between the entities. An edge can be directed or undirected.

Mathematicaly we can also say that a graph G is an ordered pair of a set V of vertices and set E of edges

G = ( V, E )

In computer science, graphs are commonly used in data structures, such as trees and networks, and in algorithms, such as search algorithms and pathfinding algorithms. They are also used in machine learning and artificial intelligence.

🏴‍☠️ Types of Graph

1️⃣ Undirected Graph

It is a graph G in which the edges does'nt have any direction.

Undirected graph

aij = aji

2️⃣ Directed Graph

It is a graph G in which the edges possess direction.

Directed graph

aij ≠ aji

3️⃣ Weighted Graph

It can be directed or undirected graph G edges have a numerical value(weight).

  • Weighted Directed Graph: A directed graph with edge weight or A weighted and directed graph is where edges have a direction and a numerical value!

  • Weighted unDirected Graph: An undirected graph with edge weight


4️⃣ Cyclic Graph

A graph that contains at least one cycle is known as a cyclic graph.



5️⃣ Acyclic Graph

A graph that contains zero cycles is known as an acyclic graph.


Note:

A cycle in context of graph occures when number of vertices are connected to one another in a closed chain of edjes.

6️⃣ Directed aCyclic Graph (DAG)

A directed aCyclic graph ia one that is directed, but does not contain ANY cycles. These are also called DAG's for short.


Note:

  • A DAG is the backbone of applications that handle scheduling for system of tasks, which needs to be processed in an order.
  • It is the concept behind Dependency Graphs.
  • It is used to represent a State Machine for objects that don't have " reversible " states.

7️⃣ Degree of a Vertex

It is the number of edges that are connected to it. It is a measure of how many neighbors a vertex has in the graph.


8️⃣ Degree of a Graph

It is the highest degree exhibited by one of the vertex in G.


9️⃣ Connected Graph

A connected graph is a graph where there exists a path between any two vertices in the graph. In other words, there are no isolated vertices in a connected graph.


🔟 Disconnected Graph

If a graph is not connected, it is called a disconnected graph.


Note:

  • A graph is said to be strongly connected if there is a directed path between every pair of vertices.
  • A directed path in a graph is a sequence of vertices connected by directed edges, where the edges have a specific direction from one vertex to another. The path starts at one vertex and ends at another, following the direction of the edges along the way. A directed path represents a directed connection between two vertices in a directed graph.

🚩 Representation

  1. Adjacency Matrix
  2. Adjacency List (not needed now..)

1️⃣ Adjacency Matrix

  • In case of an undirected graph, we need to show that there is an edge from vertex i to vertex j and vice versa. In code, we assign adj[i][j] = 1 and adj[j][i] = 1 .

  • In case of a directed graph, if there is an edge from vertex i to vertex j then we just assign adj[i][j]=1 .

  • In case of weighted directed graph:

next(Graph Traversal)