Grafik Veri Yapısı ve Algorithms (Misal)

Veri Yapısında Grafik Nedir?

A graph is a non-linear data structure that consists of vertices and edges, where vertices contain the information or data, and the edges work as a link between a pair of vertices.

It is used to solve real-world problems like finding the best route to the destination location and the route for telecommunications and social networks. Users are considered a node in the Graph, and the wires are the edges connecting the users.

Kenarlar E olarak ve köşeler V olarak temsil edilirse, G grafiği köşeler ve kenarlar kümesi olarak yazılabilir, örneğin: G (V, E).

Veri Yapısındaki Grafik Örneği

Here is a simple example of a graph data structure:

It is a simple undirected graph (one kind of Graph). Here the set of vertices is: {A, B, C, D, E, F}. Two vertices create an edge. For example, A and B are linked with an edge. However, A and F are not linked with any edges.

Veri Yapısında Grafik Terminolojileri

The following are some important terms used in the graph data structure:

Dönem	Açıklama
Tepe	Each data element is called a vertex or a node. In the above image, A, B, C, D & E are the vertices.
Kenar (Yay)	Connecting links between two nodes or vertices are called an edge (Arc). It has two ends and is represented as (startingVertex, endingVertex).
Yönlendirilmemiş Kenar	Çift yönlü bir kenardır.
Yönlendirilmiş Kenar	Tek yönlü bir kenardır.
Ağırlıklı Kenar	An edge with a value on it.
derece	In a Graph, the number of edges connected to a vertex is called a degree.
Lisans	Bir tepe noktasına bağlanan gelen kenarların toplam sayısı.
Yüksek Derece	Bir tepe noktasına bağlı giden kenarların toplam sayısı.
Kendi kendine döngü	Bir kenar, iki uç noktası çakışıyorsa kendi kendine döngü olarak adlandırılır.
komşuluk	Vertices are said to be adjacent if an edge is connected between them.

Veri Yapısındaki Grafik Türleri

İşte en yaygın olanların listesi veri yapısındaki grafik türleri:

• Yönlendirilmiş grafik
• Yönsüz Grafik
• Ağırlıklı Grafik
• Çift Yönlü Grafik
• Sonsuz Grafik
• Boş Grafik
• Önemsiz Grafik
• Çoklu Grafik
• Grafiği Tamamla
• Bağlı Grafik
• Döngüsel Grafik
• Yönlendirilmiş Asiklik Grafik (DAG)
• Döngü Grafiği
• İki Parçalı Grafik
• Euler Grafiği
• Hamilton Grafiği

How to Represent a Graph in Data Structure?

A graph is commonly stored in memory using one of two representations. The choice affects how much memory the graph uses and how fast common operations run.

• Komşuluk Matrisi: A two-dimensional V × V array where cell [i][j] is 1 (or the edge weight) if an edge exists between vertex i and vertex j, and 0 otherwise. It allows O(1) edge lookup but uses O(V²) space, making it best for dense graphs.
• Komşuluk Listesi: An array of lists where each vertex stores a list of its neighbouring vertices. It uses O(V + E) space and is efficient for sparse graphs, which is why most real-world graphs use it.

You can read more about these in the adjacency list and matrix representation of a graph öğretici.

Grafik Veri Yapısının Uygulamaları

A graph has many use cases. There are a lot of algorithms that use Graphs. Here are some of the applications of the Graph:

• Google Maps uses graphs to find the intersection of two roads and calculate the distance between two locations. For example, Dijkstra, for finding the shortest distance between the source and destination location.
• Facebook uses Graphs to find the mutual friends of the users. Its algorithm considers each user as a node of a graph.
• For resource allocation, a DAG (Directed Acyclic Graph) is used. It checks the dependency of the resources.
• MKS Google Arama motorları, web sitelerinin sıralamasını oluşturmak için grafikler kullanır.
• Bir haritaping Cihaz, grafik veri yapısını kullanır.
• A yönlendirici and its protocol use the Graph to learn the path to the destination.

SSS