Graph user input

general
,
1

I am not able take user input for graph. Please look into my code and help me.
I searched it on google. But on every place they giving input in code not at run time
#include
#include
using namespace std;
class Graph{
int V;
vector *adj{};
void DFSUtil(int v, bool visited[]);
public:
explicit Graph(int V);
void addEdge(int v, int w);
void DFS(int v);
};

Graph::Graph(int V){
this->V = V;
adj = new vector[V];
}
void Graph::addEdge(int v, int w){
adj[v].push_back(w);
adj[w].push_back(v);
}

void Graph::DFSUtil(int v, bool visited[]){
visited[v] = true;
cout << v << " ";
vector::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(){
Graph g(4);
int u=0; cin>>u;
int a=0, b=0;
for(int i=0; i<u; i++){
cin>>a>>b;
g.addEdge(a, b);
}
// g.addEdge(0, 1);
// g.addEdge(0, 2);
// g.addEdge(1, 2);
// g.addEdge(2, 0);
// g.addEdge(2, 3);
// g.addEdge(3, 3);

cout << "Following is Depth First Traversal"
        " (starting from vertex 2) \n";
g.DFS(2);

return 0;

}

2

Format your code using triple ’ ` ’

Example

```
Write Code here...

```
1 Like
3

@anon73162591 now look into my code

#include<iostream>
#include <vector>
#include <iomanip>

using namespace std;
class Graph{
    int V;
    vector<int> *adj{};
    void DFSUtil(int v, bool visited[]);
public:
    explicit Graph(int V);
    void addEdge(int v, int w);
    void DFS(int v);
};

Graph::Graph(int V){
    this->V = V;
    adj = new vector<int>[V];
}
void Graph::addEdge(int v, int w){
    adj[v].push_back(w);
    adj[w].push_back(v);
}

void Graph::DFSUtil(int v, bool visited[]){
    visited[v] = true;
    cout << v << " ";
    vector<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(){
    Graph g(4);
    int u=0; cin>>u;
    int a=0, b=0;
    for(int i=0; i<u; i++){
        cin>>a>>b;
        g.addEdge(a, b);
    }
//    g.addEdge(0, 1);
//    g.addEdge(0, 2);
//    g.addEdge(1, 2);
//    g.addEdge(2, 0);
//    g.addEdge(2, 3);
//    g.addEdge(3, 3);

    cout << "Following is Depth First Traversal"
            " (starting from vertex 2) \n";
    g.DFS(2);

    return 0;
}
4

How you are going to take input depends upon the question. But the basic idea used in representing a graph in code is same.
Refer to this:-
Graph Representation
Also, try to solve the problem given at the end. (The Edge Existence one)

1 Like
5

if you are doing competitive programming using this and understanding this will take a lot of time.
Simply use adjacency list method by using

vector<int>ADJ[MAX];
int a=0;
cin>>a>>b;
ADJ[a].push_back(b);

this is a very crude example but you will find this easier to implement rather than using a GFG template

2 Likes
6 
//
// Created by harioimdeo on 20/02/20.
//

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int nodes=0, edges=0;
    cin>>nodes>>edges;
    vector<int> adj[nodes];
    int s=0, e=0;
    for(int i=0; i<edges; i++){
        cin>>s>>e;
        adj[s].push_back(e);
// uncommenting  the next line causing error
//        adj[e].push_back(s);
    }
    for(int i=0; i<nodes; i++){
        for(int j : adj[i]){
            /*if(j==adj[i].size()-1)*/ cout<<j<<" ";
//                else cout<<adj[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Still I am getting segmentation fault.

7

Array indexing starts at 0.
So change,

adj[s].push_back(e);
adj[e].push_back(s);

into

adj[s-1].push_back(e);
adj[e-1].push_back(s);
2 Likes
8

adj[s-1].push_back(e-1) and adj[e-1].push_back(s-1)

1 Like
9

What i use is

map< int,vector<int> > adj;

it’s much flexible and guarantees no segmentation fault

3 Likes
10

this is a nice method xD

12

awesome

13

@anon73162591 how to print adjacency list after using the syntx you menstioned

14 
for(auto x:adj){
       cout << x.first << "->";
       for(int y:x.second){
             cout << y << " ";
       }
       cout << endl;
}
1 Like