3.1 Concept and terminologies:
A graph is a collection of vertices (or nodes) and edges that connect them. The vertices represent entities or objects, and the edges represent the relationship or connection between them. In a graph, an edge can be directed or undirected, weighted or unweighted.
Some common terminologies used in graphs are:
- Vertex (or node): It is an entity or object in the graph.
- Edge: It is a connection between two vertices that represents a relationship or connection.
- Directed graph: It is a graph where each edge has a direction, i.e., it goes from one vertex to another in a particular direction.
- Undirected graph: It is a graph where each edge does not have a direction, i.e., it connects two vertices without any specific direction.
- Weighted graph: It is a graph where each edge has a weight or a value associated with it.
- Path: It is a sequence of vertices in which each vertex is connected to the next vertex by an edge.
- Cycle: It is a path in which the first and last vertices are the same.
- Degree of a vertex: It is the number of edges incident on a vertex.
- Adjacent vertices: Two vertices are said to be adjacent if there is an edge connecting them.
3.2 Graph Representation:
There are different ways to represent a graph. Some common graph representations are:
- Adjacency matrix: It is a 2D array where the rows and columns represent the vertices, and the entries represent the edges between them. If there is an edge between vertex i and vertex j, then the entry A[i][j] will be 1, otherwise 0. In a weighted graph, the entries will represent the weight of the edges.
- Adjacency list: It is a list of lists where each element of the list represents a vertex, and the list associated with each vertex contains the vertices to which it is adjacent.
- Inverse adjacency list: It is similar to the adjacency list, but the roles of rows and columns are reversed.
- Adjacency multilist: It is a linked list where each node represents a vertex, and the node contains a pointer to the list of vertices to which it is adjacent.
3.3 Graph Traversals:
Graph traversal is the process of visiting all the vertices of a graph in a systematic way. There are two commonly used traversal algorithms:
- Breadth-first search (BFS): It starts at a given vertex and visits all the vertices in the graph by exploring all the vertices at the same level before moving to the next level. It uses a queue data structure to keep track of the vertices to be visited next.
- Depth-first search (DFS): It starts at a given vertex and explores as far as possible along each branch before backtracking. It uses a stack data structure to keep track of the vertices to be visited next.
Here is the implementation of BFS and DFS algorithms in Python:
```
# BFS algorithm
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
# DFS algorithm
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
```
3.4 Applications of Graph:
Graphs have numerous applications in computer science and other fields. Some common applications of graphs are:
3.4.1 Topological Sorting:
Topological sorting is a technique used to sort the vertices of a directed acyclic graph (DAG) in a linear ordering. This ordering satisfies the constraint that if there is a directed edge from vertex u to vertex v, then u must come before v in the ordering. This technique is useful in applications where the order of execution of tasks is important, such as in job scheduling or in compiling source code. Topological sorting can be done using depth-first search or breadth-first search algorithms.
3.4.2 Use of Greedy Strategy in Minimal Spanning Trees (Prim's and Kruskal's algorithm):
Minimal Spanning Tree (MST) is a subgraph of an undirected weighted graph that connects all the vertices together with minimum possible total edge weight. The two main algorithms used to find MST are Prim's and Kruskal's algorithm. Both algorithms use a greedy strategy that makes the locally optimal choice at each step to find the globally optimal solution. Prim's algorithm starts from a single vertex and grows the tree by selecting the minimum weight edge that connects the tree to a vertex outside the tree. Kruskal's algorithm starts with a forest of single vertex trees and adds edges to the forest in increasing order of weight until all vertices are in the same tree.
3.4.3 Single source shortest path - Dijkstra's algorithm:
Dijkstra's algorithm is a graph search algorithm that finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. The algorithm maintains a set of vertices whose shortest distance from the source vertex is known, and at each step adds the vertex with the minimum distance to this set. It then updates the distances of its neighbors to reflect the newly discovered shortest path. Dijkstra's algorithm is efficient for sparse graphs with positive edge weights and can be implemented using a priority queue.
3.4.4 Dynamic programming strategy, All pairs shortest path - Floyd Warshall algorithm:
The Floyd Warshall algorithm is a dynamic programming approach to finding the shortest path between all pairs of vertices in a weighted graph. The algorithm builds a table of the minimum distances between pairs of vertices, and updates it iteratively by considering intermediate vertices along the path. The algorithm has a time complexity of O(n^3) and can handle negative edge weights.
3.4.5 Use of graphs in social networks:
Graphs are commonly used to model social networks, where each node represents a person or entity and each edge represents a relationship or interaction between them. Social network analysis involves the study of the structure and dynamics of these graphs, including identifying key nodes, communities, and patterns of behavior. Graph algorithms can be used to analyze and visualize social networks, and to make predictions about future behavior based on the observed patterns. Applications of social network analysis include marketing, epidemiology, and political science.
0 Comments