+ Ответить в теме
Показано с 1 по 2 из 2

Тема: Реализация графа через смежные вершины

  1. #1
    martaOlegovna is on a distinguished road
    Регистрация
    21.03.2018
    Возраст
    19
    Сообщений
    1
    Вес репутации
    0

    По умолчанию Реализация графа через смежные вершины

    Здравствуйте. У меня есть задача- написать функции для графа через сопредельные вершины - добавить вершину, добавить ребро, добавить вес ребра.
    Удалить вершину, удалить ребро, удалить вес ребра
    Найти смежные ли ребра.

    Я начала разбираться но я все равно не могу найти толковый материал. Что нашла (смогла) написила. теперь хочу попросить Вас в помощи. Можете дать ссылку на исходник чтобы можно было посмотреть как на самом деле реализованы эти функции. или если код есть в книгах буду благодарна. А то я уже 2 неделю не могу ничего толкового найти.
    Спасибо.

    То что у меня есть:
    Код :
    1. #pragma once
    2. #include <vector>
    3. struct Edge
    4. {
    5. public:
    6.     Edge(int v, int w);
    7. private:
    8.     int mV;
    9.     int mW;
    10. };
    11.  
    12. struct Node
    13. {
    14. public:
    15.     Node(int x, Node* node);
    16. private:
    17.     int mX;
    18.     Node* mNode;
    19. };
    20.  
    21. class Graph
    22. {
    23. public:
    24.     Graph(int key, bool digraph);
    25.     void insert(int key);
    26.     void insertEdge(Edge edge);
    27.     void remove(int key);
    28.     void removeEdge(Edge edge);
    29.  
    30.     int V();
    31.     int E();
    32.     bool directed();
    33.    
    34. private:
    35.     int Vcnt;
    36.     int Ecnt;
    37.     bool mDigraph = false;
    38.     std::vector<std::vector<int>> mVector;
    39.     std::vector<Node*>  adjacencyLists;
    40. };
    Код :
    1. #include "Graph.h"
    2.  
    3.  
    4. Edge::Edge(int v, int w)
    5.     : mV(v)
    6.     , mW(w)
    7. {
    8. }
    9.  
    10.  
    11. Node::Node(int x, Node* node)
    12.     : mX(x)
    13.     , mNode(node)
    14. {
    15. }
    16.  
    17. Graph::Graph(int key, bool digraph)
    18.     : Vcnt(key)
    19.     , Ecnt(0)
    20.     , mDigraph(digraph)
    21.     , adjacencyLists(key)
    22. {
    23.     adjacencyLists.assign(key, 0);
    24. }
    25.  
    26. void Graph::insert(int key)
    27. {
    28. }
    29.  
    30. void Graph::insertEdge(Edge edge)
    31. {
    32.     int v = edge.mV;
    33.     int w = edge.mW;
    34.     adjacencyLists[v] = new Node(w, adjacencyLists[v]);
    35.     if (!mDigraph)
    36.         adjacencyLists[w] = new Node(v, adjacencyLists[w]);
    37.     Ecnt++;
    38. }
    39.  
    40. void Graph::remove(int key)
    41. {
    42. }
    43.  
    44. void Graph::removeEdge(Edge edge)
    45. {
    46. }
    47.  
    48. int Graph::V()
    49. {
    50.     return Vcnt;
    51. }
    52.  
    53. int Graph::E()
    54. {
    55.     return Ecnt;
    56. }
    57.  
    58. bool Graph::directed()
    59. {
    60.     return mDigraph;
    61. }

  2. По умолчанию

     
    Хотите избавиться от рекламы? Зарегистрируйтесь
  3. #2
    Moderator Куратор
    system architect
    Absurd is on a distinguished road
    Регистрация
    26.02.2004
    Адрес
    Pietari, Venäjä
    Возраст
    38
    Сообщений
    1,213
    Вес репутации
    17

    По умолчанию Re: Реализация графа через смежные вершины

    Я делаю такие структуры как и в СУБД. В вашем случае, наверное, будет так:

    1) таблица узлов с первичным ключом. В С++ обычно используют адрес объекта в оперативной памяти, он гарантированно уникален ( std::unordered_set<Node*> ).

    2) таблица ребро->вес, у нее ключ составной в виде кортежа из двух узлов (std::unordered_map< std::tuple<Node*, Node*>, int, Comparer(..), Hasher()> );. Так же надо определить компаратор и хэшер для кортежа std::tuple<Node*, Node*>

    3) Таблица узел А -> узел Б, где на каждый A допускается несколько Б, в ней первичного ключа нет и поэтому надо использовать мультимап: std::unordered_multimap<Node*, Node*>.
    2B OR NOT(2B) = FF

+ Ответить в теме

Похожие темы

  1. Создание и обход графа
    Добрый день. Может кто-то может помочь с такой задачкой на Delphi, был бы благодарен! Нужно создать граф, в вершинах которого будут буквы,...
    от Arturko в разделе Программирование на Pascal и Delphi (Object Pascal)
  2. Поиск компонент связности графа
    Помогите спецы с данной работой! Препод просто кинул мне её и сказа НЕПРАВИЛЬНО, ПЕРЕДЕЛАТЬ ПОЛНОСТЮ Лабораторная работа № 5 Поиск компонент...
    от mastar в разделе задачи на Паскале и Delphi
  3. программа,которая из точек выделяет вершины квадрата
    На плоскости заданы N точек с координатами (х1, у1), (х2, у2), ... , (хN, yN). Написать программу, которая из этих точек выделяет вершины квадрата,...
    от фед в разделе задачи на Паскале и Delphi
  4. Радиус и диаметр графа
    А вот в общем в теме сам вопрос и стоит. Какие есть стандартные алгоритмы для нахождения радиуса и максисального диаметра в графе
    от qwerqwer в разделе Алгоритмы
  5. Проблема с "Добавить в формулу смежные ячейки"
    В ключевом столбце документа есть одинаковые данные. Для того, чтобы облегчить из поиск пользуюсь "Данные->Итоги...". Все бы хорошо, но данные нужно...
    от NiTreX в разделе MS Office и VB(A).

Метки этой темы

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения