Graph परिचय

एक graph friends का एक map जैसा है: हर person एक dot है और हर friendship दो dots को connect करती एक line है।

In this page:

What is a Graph
Vertices and Edges
Directed Graph
Undirected Graph
Graph Uses

Syntax

markup

graph = {
    'A': ['B', 'C'],    # A -> B, A -> C
    'B': ['C'],
    'C': []
}

What is a Graph

एक graph vertices (nodes भी कहलाते हैं) और उनके pairs को connect करती edges से बनी एक structure है, objects के बीच relationships model करने के लिए उपयोग होती है — एक tree के विपरीत, एक graph में कोई required hierarchy नहीं और इसमें cycles, कई paths, या disconnected pieces हो सकते हैं।

उदाहरण: What is a Graph

#include <iostream>
using namespace std;
int main() {
	int vertices = 5;
	int edges[][2] = {{0,1},{1,2},{2,0},{3,4}};
	cout << "Graph: " << vertices << " vertices, " << 4 << " edges, contains a cycle (0-1-2-0)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int vertices = 5;
		int[][] edges = {{0,1},{1,2},{2,0},{3,4}};
		System.out.println("Graph: " + vertices + " vertices, " + edges.length + " edges, contains a cycle (0-1-2-0)");
	}
}

vertices = 5
edges = [(0,1),(1,2),(2,0),(3,4)]
print(f"Graph: {vertices} vertices, {len(edges)} edges, contains a cycle (0-1-2-0)")

#include <stdio.h>
int main() {
	int vertices = 5;
	int edges[4][2] = {{0,1},{1,2},{2,0},{3,4}};
	printf("Graph: %d vertices, 4 edges, contains a cycle (0-1-2-0)", vertices);
	return 0;
}

Vertices and Edges

Vertices model की जा रही individual entities represent करते हैं — people, cities, web pages, tasks — जबकि edges उन entities में से दो के बीच एक relationship या connection represent करते हैं, जैसे एक friendship, एक road, एक link, या एक dependency।

उदाहरण: Vertices and Edges

#include <iostream>
using namespace std;
int main() {
	string people[] = {"Alice", "Bob", "Carol"};
	cout << people[0] << " -- friendship --> " << people[1];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] people = {"Alice", "Bob", "Carol"};
		System.out.println(people[0] + " -- friendship --> " + people[1]);
	}
}

people = ["Alice", "Bob", "Carol"]
print(f"{people[0]} -- friendship --> {people[1]}")

#include <stdio.h>
int main() {
	char* people[] = {"Alice", "Bob", "Carol"};
	printf("%s -- friendship --> %s", people[0], people[1]);
	return 0;
}

Directed Graph

एक directed edge एक specific vertex से दूसरे की ओर point करता है, मतलब relationship सिर्फ एक तरफ जाता है (जैसे एक one-way street या social media पर एक follows relationship) — destination से वापस source तक travel करना implied नहीं है।

उदाहरण: Directed Graph

#include <iostream>
using namespace std;
int main() {
	cout << "Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice");
	}
}

print("Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice")

#include <stdio.h>
int main() {
	printf("Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice");
	return 0;
}

Undirected Graph

एक undirected edge दो vertices को symmetrically connect करता है, relationship दोनों directions में equally होते हुए (जैसे एक mutual friendship या एक two-way road) — source और destination के बीच कोई distinction नहीं।

उदाहरण: Undirected Graph

#include <iostream>
using namespace std;
int main() {
	cout << "Alice -- friend -- Bob: the edge holds equally in both directions";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Alice -- friend -- Bob: the edge holds equally in both directions");
	}
}

print("Alice -- friend -- Bob: the edge holds equally in both directions")

#include <stdio.h>
int main() {
	printf("Alice -- friend -- Bob: the edge holds equally in both directions");
	return 0;
}

Graph Uses

Graphs असली systems की एक बहुत बड़ी range model करने के लिए उपयोग होते हैं: road networks, computer networks, social connections, task dependencies, और भी बहुत कुछ — यह पहचानना कि कोई problem असल में 'objects और उनके बीच relationships' है आमतौर पर एक संकेत है कि एक graph सही model है।

उदाहरण: Graph Uses

#include <iostream>
using namespace std;
int main() {
	string uses[] = {"road networks", "computer networks", "social connections", "task dependencies"};
	for (string u : uses) cout << u << "; ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] uses = {"road networks", "computer networks", "social connections", "task dependencies"};
		for (String u : uses) System.out.print(u + "; ");
	}
}

uses = ["road networks", "computer networks", "social connections", "task dependencies"]
print("; ".join(uses))

#include <stdio.h>
int main() {
	char* uses[] = {"road networks", "computer networks", "social connections", "task dependencies"};
	for (int i = 0; i < 4; i++) printf("%s; ", uses[i]);
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Merge K Sorted Lists Next Lesson → Graph Representation