RaresDumitrica

Graph complex

Jan 17th, 2019
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3.  
  4. using namespace std;
  5.  
  6. struct Graph {
  7.     int V;
  8.     set<int, greater<int> >* adjList;
  9. };
  10.  
  11. // A utility function that creates a graph of V vertices
  12. Graph* createGraph(int V)
  13. {
  14.     Graph* graph = new Graph;
  15.     graph->V = V;
  16.  
  17.     // Create an array of sets representing
  18.     // adjacency lists.  Size of the array will be V
  19.     graph->adjList = new set<int, greater<int> >[V];
  20.  
  21.     return graph;
  22. }
  23.  
  24. // Adds an edge to an undirected graph
  25. void addEdge(Graph* graph, int src, int dest)
  26. {
  27.     // Add an edge from src to dest.  A new
  28.     // element is inserted to the adjacent
  29.     // list of src.
  30.     graph->adjList[src].insert(dest);
  31.  
  32.     // Since graph is undirected, add an edge
  33.     // from dest to src also
  34.     graph->adjList[dest].insert(src);
  35. }
  36.  
  37. // A utility function to print the adjacency
  38. // list representation of graph
  39. void printGraph(Graph* graph)
  40. {
  41.     for (int i = 0; i < graph->V; ++i) {
  42.         set<int, greater<int> > lst = graph->adjList[i];
  43.         cout << endl << "Adjacency list of vertex "
  44.              << i << endl;
  45.  
  46.         for (auto itr = lst.begin(); itr != lst.end(); ++itr)
  47.             cout << *itr << " ";
  48.         cout << endl;
  49.     }
  50. }
  51.  
  52. // Searches for a given edge in the graph
  53. void searchEdge(Graph* graph, int src, int dest)
  54. {
  55.     auto itr = graph->adjList[src].find(dest);
  56.     if (itr == graph->adjList[src].end())
  57.         cout << endl << "Edge from " << src
  58.              << " to " << dest << " not found."
  59.              << endl;
  60.     else
  61.         cout << endl << "Edge from " << src
  62.              << " to " << dest << " found."
  63.              << endl;
  64. }
  65.  
  66. // Driver code
  67. int main()
  68. {
  69.     // Create the graph given in the above figure
  70.     int V = 5;
  71.     struct Graph* graph = createGraph(V);
  72.     addEdge(graph, 0, 1);
  73.     addEdge(graph, 0, 4);
  74.     addEdge(graph, 1, 2);
  75.     addEdge(graph, 1, 3);
  76.     addEdge(graph, 1, 4);
  77.     addEdge(graph, 2, 3);
  78.     addEdge(graph, 3, 4);
  79.  
  80.     // Print the adjacency list representation of
  81.     // the above graph
  82.     printGraph(graph);
  83.  
  84.     // Search the given edge in the graph
  85.     searchEdge(graph, 2, 1);
  86.     searchEdge(graph, 0, 3);
  87.  
  88.     return 0;
  89. }
Add Comment
Please, Sign In to add comment