Рубрики

Граф и его представления

График представляет собой структуру данных, которая состоит из следующих двух компонентов:
1. Конечное множество вершин, также называемых узлами.
2. Конечное множество упорядоченной пары вида (u, v), называемой ребром. Пара упорядочена, потому что (u, v) не совпадает с (v, u) в случае ориентированного графа (диграфа). Пара формы (u, v) указывает, что существует ребро от вершины u до вершины v. Ребра могут содержать вес / значение / стоимость.

Графики используются для представления многих реальных приложений. Графики используются для представления сетей. Сети могут включать в себя пути в городской или телефонной сети или в окружной сети. Графики также используются в социальных сетях, таких как connectedIn, Facebook. Например, в Facebook каждый человек представлен вершиной (или узлом). Каждый узел является структурой и содержит такую информацию, как идентификатор человека, имя, пол и локаль. Смотрите это для большего количества приложений графа.

Ниже приведен пример неориентированного графа с 5 вершинами.

Следующие два являются наиболее часто используемыми представлениями графа.
1. Матрица смежности
2. Список смежности
Есть и другие представления, такие как Матрица заболеваемости и Список заболеваемости. Выбор представления графа зависит от конкретной ситуации. Это полностью зависит от типа выполняемых операций и простоты использования.

Матрица смежности:
Матрица смежности — это двумерный массив размером V x V, где V — количество вершин в графе. Пусть двумерный массив будет adj [] [], слот adj [i] [j] = 1 указывает на наличие ребра от вершины i до вершины j. Матрица смежности для неориентированного графа всегда симметрична. Матрица смежности также используется для представления взвешенных графиков. Если adj [i] [j] = w, то существует ребро от вершины i до вершины j с весом w.

Матрица смежности для приведенного выше примера графа:

Плюсы: представление легче реализовать и следовать. Удаление края занимает O (1) время. Запросы, например, есть ли ребро от вершины 'u' до вершины 'v', эффективны и могут быть выполнены O (1).

Минусы: потребляет больше места O (V ^ 2). Даже если граф разрежен (содержит меньше ребер), он занимает то же место. Добавление вершины — O (V ^ 2) время.
Пожалуйста, посмотрите это для примера реализации матрицы смежности на Python.

Список смежности:
Используется массив списков. Размер массива равен количеству вершин. Пусть массив будет массивом []. Массив записей [i] представляет список вершин, смежных с i- й вершиной. Это представление также можно использовать для представления взвешенного графика. Веса ребер могут быть представлены в виде списков пар. Ниже приведено представление списка смежности приведенного выше графа.

Обратите внимание, что в приведенной ниже реализации мы используем динамические массивы (vector в C ++ / ArrayList в Java) для представления списков смежности вместо связанного списка. Векторная реализация имеет преимущества кеша.

C ++

// Простое представление графа с использованием STL
#include<bits/stdc++.h>

using namespace std;

  
// Вспомогательная функция для добавления ребра в
// неориентированный граф.

void addEdge(vector<int> adj[], int u, int v)

{

    adj[u].push_back(v);

    adj[v].push_back(u);

}

  
// Вспомогательная функция для печати списка смежности
// представление графа

void printGraph(vector<int> adj[], int V)

{

    for (int v = 0; v < V; ++v)

    {

        cout << "\n Adjacency list of vertex "

             << v << "\n head ";

        for (auto x : adj[v])

           cout << "-> " << x;

        printf("\n");

    }

}

  
// Код драйвера

int main()

{

    int V = 5;

    vector<int> adj[V];

    addEdge(adj, 0, 1);

    addEdge(adj, 0, 4);

    addEdge(adj, 1, 2);

    addEdge(adj, 1, 3);

    addEdge(adj, 1, 4);

    addEdge(adj, 2, 3);

    addEdge(adj, 3, 4);

    printGraph(adj, V);

    return 0;

}

С

// Программа AC для демонстрации списка смежности
// представление графиков
#include <stdio.h>
#include <stdlib.h>

  
// Структура для представления узла списка смежности

struct AdjListNode

{

    int dest;

    struct AdjListNode* next;

};

  
// Структура для представления списка смежности

struct AdjList

{

    struct AdjListNode *head; 

};

  
// Структура для представления графа. График
// это массив списков смежности.
// Размер массива будет V (количество вершин
// в графе)

struct Graph

{

    int V;

    struct AdjList* array;

};

  
// Служебная функция для создания нового узла списка смежности

struct AdjListNode* newAdjListNode(int dest)

{

    struct AdjListNode* newNode =

     (struct AdjListNode*) malloc(sizeof(struct AdjListNode));

    newNode->dest = dest;

    newNode->next = NULL;

    return newNode;

}

  
// Вспомогательная функция, которая создает граф из V вершин

struct Graph* createGraph(int V)

{

    struct Graph* graph = 

        (struct Graph*) malloc(sizeof(struct Graph));

    graph->V = V;

  

    // Создать массив списков смежности. Размер

    // массив будет V

    graph->array = 

      (struct AdjList*) malloc(V * sizeof(struct AdjList));

  

    // Инициализируем каждый список смежности как пустой

    // сделать голову как NULL

    int i;

    for (i = 0; i < V; ++i)

        graph->array[i].head = NULL;

  

    return graph;

}

  
// Добавляем ребро в неориентированный граф

void addEdge(struct Graph* graph, int src, int dest)

{

    // Добавить ребро из src в dest. Новый узел

    // добавлен в список смежности src. Узел

    // добавлено в начале

    struct AdjListNode* newNode = newAdjListNode(dest);

    newNode->next = graph->array[src].head;

    graph->array[src].head = newNode;

  

    // Поскольку граф не является направленным, добавьте ребро из

    // dest to src также

    newNode = newAdjListNode(src);

    newNode->next = graph->array[dest].head;

    graph->array[dest].head = newNode;

}

  
// Вспомогательная функция для печати списка смежности
// представление графа

void printGraph(struct Graph* graph)

{

    int v;

    for (v = 0; v < graph->V; ++v)

    {

        struct AdjListNode* pCrawl = graph->array[v].head;

        printf("\n Adjacency list of vertex %d\n head ", v);

        while (pCrawl)

        {

            printf("-> %d", pCrawl->dest);

            pCrawl = pCrawl->next;

        }

        printf("\n");

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // создаем график, приведенный выше

    int V = 5;

    struct Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);

    addEdge(graph, 0, 4);

    addEdge(graph, 1, 2);

    addEdge(graph, 1, 3);

    addEdge(graph, 1, 4);

    addEdge(graph, 2, 3);

    addEdge(graph, 3, 4);

  

    // выводим список смежности представленного выше графа

    printGraph(graph);

  

    return 0;

}

Джава

// Java-программа для демонстрации списка смежности
// представление графиков

import java.util.LinkedList;

  

public class GFG 

{

    // Пользовательский класс для представления графа.

    // Граф - это массив списков смежности.

    // Размер массива будет V (количество вершин

    // в графе)

    static class Graph

    {

        int V;

        LinkedList<Integer> adjListArray[];

          

        // конструктор

        Graph(int V)

        {

            this.V = V;

              

            // определяем размер массива как

            // количество вершин

            adjListArray = new LinkedList[V];

              

            // Создать новый список для каждой вершины

            // так, что соседние узлы могут быть сохранены

            for(int i = 0; i < V ; i++){

                adjListArray[i] = new LinkedList<>();

            }

        }

    }

      

    // Добавляем ребро в неориентированный граф

    static void addEdge(Graph graph, int src, int dest)

    {

        // Добавить ребро из src в dest.

        graph.adjListArray[src].add(dest);

          

        // Поскольку граф не является направленным, добавляем ребро из dest

        // к src также

        graph.adjListArray[dest].add(src);

    }

       

    // Вспомогательная функция для печати списка смежности

    // представление графа

    static void printGraph(Graph graph)

    {       

        for(int v = 0; v < graph.V; v++)

        {

            System.out.println("Adjacency list of vertex "+ v);

            System.out.print("head");

            for(Integer pCrawl: graph.adjListArray[v]){

                System.out.print(" -> "+pCrawl);

            }

            System.out.println("\n");

        }

    }

       

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        // создаем график, приведенный на рисунке выше

        int V = 5;

        Graph graph = new Graph(V);

        addEdge(graph, 0, 1);

        addEdge(graph, 0, 4);

        addEdge(graph, 1, 2);

        addEdge(graph, 1, 3);

        addEdge(graph, 1, 4);

        addEdge(graph, 2, 3);

        addEdge(graph, 3, 4);

       

        // выводим представление списка смежности

        // приведенный выше график

        printGraph(graph);

    }

}
// Этот код предоставлен Sumit Ghosh

python3

«»»
Программа Python для демонстрации смежности
представление списка графа
«»»

  
# Класс для представления списка смежности узла

class AdjNode:

    def __init__(self, data):

        self.vertex = data

        self.next = None

  

  
# Класс для представления графа. График
# - список списков смежности.
# Размер массива будет нет. из
# вершины "V"

class Graph:

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [None] * self.V

  

    # Функция для добавления ребра в неориентированный граф

    def add_edge(self, src, dest):

        # Добавление узла в исходный узел

        node = AdjNode(dest)

        node.next = self.graph[src]

        self.graph[src] = node

  

        # Добавление исходного узла к месту назначения как

        # это неориентированный граф

        node = AdjNode(src)

        node.next = self.graph[dest]

        self.graph[dest] = node

  

    # Функция для печати графика

    def print_graph(self):

        for i in range(self.V):

            print("Adjacency list of vertex {}\n head".format(i), end="")

            temp = self.graph[i]

            while temp:

                print(" -> {}".format(temp.vertex), end="")

                temp = temp.next

            print(" \n")

  

  
# Драйвер программы для приведенного выше класса графа

if __name__ == "__main__":

    V = 5

    graph = Graph(V)

    graph.add_edge(0, 1)

    graph.add_edge(0, 4)

    graph.add_edge(1, 2)

    graph.add_edge(1, 3)

    graph.add_edge(1, 4)

    graph.add_edge(2, 3)

    graph.add_edge(3, 4)

  

    graph.print_graph()

  
# Этот код предоставлен Канав Малхотра


Выход:

 
 Adjacency list of vertex 0
 head -> 1-> 4

 Adjacency list of vertex 1
 head -> 0-> 2-> 3-> 4

 Adjacency list of vertex 2
 head -> 1-> 3

 Adjacency list of vertex 3
 head -> 1-> 2-> 4

 Adjacency list of vertex 4
 head -> 0-> 1-> 3

Плюсы: экономит пространство O (| V | + | E |). В худшем случае в графе может быть число ребер C (V, 2), что потребляет пространство O (V ^ 2). Добавить вершину проще.

Рекомендуемые посты:

Граф и его представления

0.00 (0%) 0 votes