SHARE
TWEET

DFSGraph

arsovski Dec 15th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <queue>
  5. #include <immintrin.h>
  6.  
  7. class Vertex
  8. {
  9. public:
  10.     static int numberOfVertices;
  11.     std::list<Vertex*> neighbors;
  12.     int vertexNumber;
  13.  
  14.     Vertex()
  15.     {
  16.         this->vertexNumber = numberOfVertices;
  17.         numberOfVertices++;
  18.     }
  19.  
  20.     Vertex(int vertexNumber)
  21.     {
  22.         this->vertexNumber = vertexNumber;
  23.     }
  24.  
  25.     bool isPresent(int index)
  26.     {
  27.         for (auto neighbor : neighbors)
  28.             if (neighbor->getVertexNumber() == index)
  29.                 return true;
  30.  
  31.         return false;
  32.     }
  33.  
  34.     void addNeighbors(Vertex* index)
  35.     {
  36.         if (isPresent(index->getVertexNumber()))
  37.             return;
  38.  
  39.         this->neighbors.push_back(index);
  40.     }
  41.  
  42.     void printNeighbors()
  43.     {
  44.         for (auto neighbor : neighbors)
  45.         {
  46.             printf("%d ", neighbor->getVertexNumber());
  47.         }
  48.  
  49.         printf("\n");
  50.     }
  51.  
  52.     const int getVertexNumber()
  53.     {
  54.         return vertexNumber;
  55.     }
  56. };
  57.  
  58. int Vertex::numberOfVertices = 1;
  59.  
  60. class Graph
  61. {
  62.     std::vector<Vertex*> vertices;
  63. public:
  64.  
  65.  
  66.     Graph(int nodeCount)
  67.     {
  68.         vertices.resize(nodeCount);
  69.     }
  70.  
  71.     bool hasBeenCreated(int index)
  72.     {
  73.         for (auto vertex : vertices)
  74.         {
  75.             if (vertex != nullptr)
  76.                 if (vertex->getVertexNumber() == index)
  77.                     return true;
  78.         }
  79.  
  80.         return false;
  81.     }
  82.  
  83.     void formConnection(int vertexNumber, int neighbor)
  84.     {
  85.  
  86.         const int vertexIndex = vertexNumber - 1;
  87.         Vertex* newVertex = new Vertex(neighbor);
  88.  
  89.         if (hasBeenCreated(vertexNumber))
  90.         {
  91.             vertices[vertexIndex]->addNeighbors(newVertex);
  92.         }
  93.         else
  94.         {
  95.             vertices[vertexIndex] = new Vertex();
  96.             vertices[vertexIndex]->addNeighbors(newVertex);
  97.         }
  98.  
  99.     }
  100.  
  101.     void printGraph()
  102.     {
  103.         for (auto vertex : vertices)
  104.         {
  105.             if (vertex != nullptr)
  106.             {
  107.                 printf("Vertex %d: ", vertex->getVertexNumber());
  108.                 vertex->printNeighbors();
  109.             }
  110.         }
  111.     }
  112.  
  113.     void BFS(int from, std::vector<bool>& visited)
  114.     {
  115.         std::queue<Vertex* > nextToVisit;
  116.         visited[from-1] = true;
  117.         nextToVisit.push(vertices[from-1]);
  118.  
  119.         while (!nextToVisit.empty())
  120.         {
  121.             Vertex* nextVertex = nextToVisit.front();
  122.             nextToVisit.pop();
  123.  
  124.             printf("%d ", nextVertex->getVertexNumber());
  125.  
  126.             for (auto vertex : vertices[nextVertex->getVertexNumber()-1]->neighbors)
  127.             {
  128.                 if (!visited[vertex->getVertexNumber()-1])
  129.                 {
  130.                     nextToVisit.push(vertex);
  131.                     visited[vertex->getVertexNumber()-1] = true;
  132.                 }
  133.             }
  134.         }
  135.         printf("\n");
  136.     }
  137.  
  138.     void DFS(int from, std::vector<bool>& visited)
  139.     {
  140.         Vertex* startNode = vertices[from - 1];
  141.         visited[from - 1] = true;
  142.  
  143.         printf("%d,", startNode->getVertexNumber());
  144.  
  145.         for(auto neighbor: vertices[from-1]->neighbors)
  146.         {
  147.             if(neighbor !=nullptr)
  148.              if (!visited[neighbor->getVertexNumber() - 1])
  149.                 DFS(neighbor->getVertexNumber(), visited);
  150.         }
  151.  
  152.     }
  153.  
  154.  
  155. };
  156.  
  157.  
  158. int main()
  159. {
  160.     // allocated 4 nodes but with null
  161.     Graph* myGraph = new Graph(4);
  162.  
  163.     //TODO Make DFS AND TOPOLOGICAL
  164.     myGraph->formConnection(1, 2);
  165.     myGraph->formConnection(1, 3);
  166.     myGraph->formConnection(2, 1);
  167.     myGraph->formConnection(2, 4);
  168.     myGraph->formConnection(3, 1);
  169.     myGraph->formConnection(4, 3);
  170.  
  171.     std::vector<bool> visited(4,false);
  172.  
  173.  
  174.     //myGraph->BFS(4, visited);
  175.     myGraph->DFS(4, visited);
  176.     printf("\n");
  177.  
  178.     myGraph->printGraph();
  179.  
  180.     return 0;
  181. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top