Удаление вершины с графа

185
01 июля 2018, 08:30
#include "stdafx.h"
#include<iostream>
#include<list>
using namespace std;

class Graph
{
    int V;    
    list<int> *adj;

    void DFSUtil(int v, bool visited[]);
public:
    Graph(int V);   
    void addEdge(int v, int w); 
    void DFS(int v); 
    void print();
    void deleteVertex(int v);
};
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
    adj[w].push_back(v);
}

void Graph::print() {
    for (int v = 0; v < V; v++) {
        cout << "List: " << v << endl;
        for (auto x : adj[v])
            cout << "-->" << x;
        cout << endl;
    }
}
void Graph::deleteVertex(int v)
{
    //adj[v].remove();
}

void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true;
    cout << v << " ";
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

void Graph::DFS(int v)
{
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
    DFSUtil(v, visited);
}
int main()
{
    int size;
    cout << "Enter count of Vertex" << endl;
    cin >> size;
    Graph g(size);
    int firstVertex, secondVertex;
    int answer = 1, i = 0;
    while (answer != 0 && i < size - 1) {
        i++;
        cout << "Enter conected Vertex: \n";
        cin >> firstVertex;
        cin >> secondVertex;
        cout << "Do you want to continue? 1 yes 0 - no" << endl;
        cin >> answer;
        cout << "\nCurrent i is" << i << endl;
        g.addEdge(firstVertex, secondVertex);
    }
    g.deleteVertex(2);
    g.DFS(0);
    cout << endl;
    g.print();
    return 0;
}

Как реализовать правильно функцию удаления вершины? Если возможно помогите кодом

Answer 1

1.Вызываем функцию удаления вершины

2.В функции ищем нашу вершину,которую хотим удалить

3.Запоминаем смежные ей вершины(их же максимум 2?)

4.Делаем одно общее ребро для смежных вершин

5.Удаляем вершину из графа (...delete()...)

READ ALSO
Неявное подключение DLL С++ WINAPI

Неявное подключение DLL С++ WINAPI

Пару часов назад писал с вопросом о явном подключении и с горем пополам разобрался, спасибо всем, кто помогСейчас встал вопрос о неявном подключении...

186
С++ Мультисет Итератор

С++ Мультисет Итератор

Нужно вывести первые 3 элемента, но согласно моей лямбда-сортировке

549
Перевыделение памяти с++, такое возможно?

Перевыделение памяти с++, такое возможно?

Недавно задали лабораторную домой по с++Перерыл почти весь интернет но ответ на один вопрос так и не нашёл

195