Removing an edge from an adjacency list

Question

I implemented a graph using an adjacency list, I am now trying to implement a removeEdge function. I was able to do this with an adjacency matrix but its a bit confusing to me what to do.

This is what I have so far but the erase part is wrong so just need some help on what to do.

/*
 * C++ Program to Implement Adjacency List Graph Implementationn UNDIRECTED
 */
#include <iostream>
#include <vector>


const int V = 5;
std::vector<int> adj[V];


void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void removeEdge(int u, int v) {
    adj[u].erase(v);
    adj[v].erase(u);
}

void print() {
    for (int v = 0; v < V; ++v) {
        std::cout << "\n Adjacency list of vertex "
            << v << "\n head ";
        for (auto x : adj[v])
            std::cout << "-> " << x;
    }
    std::cout << "\n";
}

int main() {
    int V = 5;

    addEdge(0, 1);
    addEdge(0, 4);
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 3);
    addEdge(3, 4);

    print();

    removeEdge(2, 3);

    print();

    std::cin.get();
}

If any have some suggestions I would really appreciate it.

Look at the documentation for [vector::erase](https://en.cppreference.com/w/cpp/container/vector/erase). The parameter is supposed to be an iterator, not an integer. — PaulMcKenzie, Oct 01 '18 at 00:38
@PaulMcKenzie Okay well in general is my implementation wrong (holding constant the deleteEdge function)? — , Oct 01 '18 at 00:41
The `erase` is wrong, regardless of what you're attempting to implement. You should at least [get that part right](https://stackoverflow.com/questions/875103/how-do-i-erase-an-element-from-stdvector-by-index?rq=1) — PaulMcKenzie, Oct 01 '18 at 00:43
@PaulMcKenzie Could you give me some hints? Should I just declare an iterator to get the job done? — , Oct 01 '18 at 00:56
If you want to erase the nth element in a vector, you pass an iterator to the nth element. Example -- erase element at index 3 -- `v.erase(v.begin() + 3);` — PaulMcKenzie, Oct 01 '18 at 00:57
@PaulMcKenzie so essentially something like this void removeEdge(int u, int v) { adj[u].erase(adj->begin() + v); adj[v].erase(adj->begin() + u); } — , Oct 01 '18 at 00:59
You want to erase an item in the `adj[u]` vector, then the iterator to the first element is `adj[u].begin()`, not `adj->begin()`. — PaulMcKenzie, Oct 01 '18 at 01:05

score 2 · Accepted Answer · edited Oct 01 '18 at 02:41

2

Use iterator to find an element what you want to remove. After that, use erase method to remove it.

void removeEdge(int u, int v) {
   // remove edge from u to v
   vector<int>::iterator it  = std::find(adv[u].begin(), adv[u].end(), v);
   adv[u].erase(it);
   // remove edge from v to u
   it  = std::find(adv[v].begin(), adv[v].end(), u);
   adv[v].erase(it);
}

edited Oct 01 '18 at 02:41

1201ProgramAlarm

32,384
7
42
56

answered Oct 01 '18 at 01:11

TaQuangTu

2,155
2
16
30

Removing an edge from an adjacency list

1 Answers1