1
\$\begingroup\$

After studying from Introduction to Algorithm and taking help from internet I have written a program. I don't know much about C++11. Please help me to optimize this program with better functions and better runtime.

Note: I have used adjacency matrix instead of adjacency list and I don't know whether I have used it in correct way.

#include <iostream>
#include <vector>

class Graph
{
  int V; //no of Vertices
  enum class Color { WHITE, GRAY, BLACK };

  struct Vertex
  {
  char id;
  Color color;
  Vertex(char c, Color clr) : id(c), color(clr) {}
  };
  std::vector< std::vector<int> > adjMatrix; //adjacency Matrix
  std::vector<Vertex> vertices;

public:
  Graph(int);
  void addEdge(int, int);
  void DFS(int);
};

Graph::Graph(int v)
{
  V = v;
  adjMatrix.resize(V, std::vector<int>(V));
  for(int i = 0; i < V; i++)
  {
    vertices.push_back( Vertex('A'+i, Color::WHITE));
    for(int j = 0; j < V; j++)
    {
      adjMatrix[i][j] = 0;
    }
   }
}

void Graph::addEdge(int a, int b)
{
  adjMatrix[a][b] = 1;
}

void Graph::DFS(int u)
{
  vertices[u].color = Color::GRAY;
  std::cout << vertices[u].id <<" ";

  for(int i = u; i < V; i++)
  {
    for(int j = 0; j < V; j++)
    {
      if(adjMatrix[i][j] == 1)
      {
        if(vertices[j].color == Color::WHITE)
        DFS(j);
      }
    }
  }
  vertices[u].color = Color::BLACK; //blacken u, it is finished
}

int main()
{
  Graph grp(4);
  grp.addEdge(0, 1);
  grp.addEdge(1, 2);
  grp.addEdge(2, 3);
  grp.addEdge(2, 1);
  grp.addEdge(0, 3);

  grp.DFS(2);
  return 0;
}
\$\endgroup\$

3 Answers 3

3
\$\begingroup\$

Reduce Complexity, Follow SRP
In both this question and the Binary Search Tree in C++ struct definitions have been embedded within the class definitions. This goes against good object oriented programming principles, specifically the Single Responsibility Principle. One of the basics of object oriented programing is to be able to reuse objects in multiple programs. Each object should be defined separately so that one builds up a library of objects/files that can be reused. In C++ a struct is a class where all members are public, since they are classes they should be defined on their own.

In this program it would be better if there be three header files and possibly two source files, one for Graph and one for Vertex. Vertex may not need a C++ source file since it is fairly simple. The color class also deserves it's own header file. In the Binary Search Tree question Node should be defined separately from BinaryTree.

You might also want to look into SOLID programming principles (the S is the Single Responsibility Principle).

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows: A class should have only one reason to change.

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

Inconsistent Indentation
The contents of the struct Vertex are not indented and they should be.

Inconsistent Naming Conventions
The naming of variables and functions is inconsistent, there are well named functions and variables such as adjMatrix, addEdge(), id and color, and then there are names such as V and DFS(). It might be better to name V as verticyCount or maxVirtecies and DFS() as depthFirstSearch().

Inconsistent Initialization in Constructors
The constructor for Vertex uses C++ initialization for it's variables, but the Graph constructor does. It might be better if Graph was written as :

Graph::Graph(int v)
: V{v}
{
    adjMatrix.resize(V, std::vector<int>(V));
    for(int i = 0; i < V; i++)
    {
        vertices.push_back( Vertex('A'+i, Color::WHITE));
        for(int j = 0; j < V; j++)
        {
            adjMatrix[i][j] = 0;
        }
    }
}

Please note that the call to std::vector.resize() is not necessary in this constructor. C++ implementations generally include a base allocation of memory for constructors and as the vector grows or shrinks, resize will be called implicitly. Also note that operators such as + should be separated by spaces to make the code more readable.

        vertices.push_back(Vertex('A' + i, Color::WHITE));

In the initialization of Vertex, braces should be preferred to parens:

    Vertex(char c, Color clr) : id{c}, color{clr} {}

The use of parens is supported for backwards compatibility on some C++ compilers, however, it is obsolete.

The two other answers concerns about the DFS() function are valid, you can find a fast working Breath First Search recursive implementation in the KnightMovesImplementation.cpp file, function bool KnightMovesImplementation::CalculatePath(KMMove CurrentMove) in this question.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Graph::Graph(int v): V(v), adjMatrix(v, std::vector<int>(v)) then you can get rid of the resize. And the j loop can go away, too, since the resize zero-initialized all those ints. if v is potentially large, I'd include a vertices.reserve call before the i loop. The use of parenthesis in initializers is part of the language, so all conforming compilers must support it. \$\endgroup\$ Jan 7, 2018 at 17:32
  • \$\begingroup\$ @1201ProgramAlarm thanks, I learn something new every day. \$\endgroup\$
    – pacmaninbw
    Jan 7, 2018 at 17:37
  • 1
    \$\begingroup\$ I understood SRP that I have to design class which is responsible for specific task but I am unable to write code which follows SRP. Can you write it? I don't know advanced C++ so I didn't understand KnightMovesImplementation.cpp \$\endgroup\$
    – coder
    Jan 8, 2018 at 8:11
2
\$\begingroup\$

When you add an edge a -> b you do not add a corresponding b -> a. This makes your Graph a directed graph. Was that your intent?

You have no mechanism for setting all the colors. You need to either rotate color settings (change the values of black/white/grey) or add some kind of "set-everything-to-white" method. Otherwise, you can only DFS one time. ;-)

You may wish to use std::vector<bool> instead of <int> in order to save space. For a 4x4 matrix this won't be a problem, but if you get called on to use a 64k x 64k matrix, space will be an issue.

Your DFS algorithm seems wrong. I don't understand why there are two loops plus recursion. With recursion and a matrix, you only need one loop.

Here's an example I found on a different post:

    5
   / \
  7   3
 /\   /\
4  1 6  2

What do you think the output sequence should be, starting from 5?

I think it would look like: 5, 3, 2, 6, 7, 1, 4 since you scan from 0..size in your adjacency matrix. (That is, 5 would find 3 before 7, etc.)

\$\endgroup\$
2
  • \$\begingroup\$ I think this line vertices.push_back( Vertex('A'+i, Color::WHITE)); set everything to white initially. I have used two loops to know where is 1 in adjacency matrix. \$\endgroup\$
    – coder
    Jan 7, 2018 at 6:17
  • \$\begingroup\$ @coder Yes, you set the colors to white initially. But that means you only get one DFS. After that, you'll need to reset them to white again. For knowing where there is a 1 in the adjacency matrix, remember that you are processing a particular vertex, so you already know one coordinate. You get called with int u as a parameter. So the only question is, what other vertices are linked with u? That means you should need just one loop. (You will recurse into another call to DFS with the new vertex v, so the stack frame is your second "loop".) \$\endgroup\$
    – aghast
    Jan 7, 2018 at 19:21
2
\$\begingroup\$
void dfs(int node) {
    if (visit[node]==1) return;
    if (visit[node]==2){
        b=0;
        return;
    }
    visit[node] = 2;
    for (int i = 0; i < v[node].size(); i++)dfs(v[node][i]);
    ans.push_back(node);
    visit[node]=1;
}

Here is a sample dfs code. I guess you really shouldn't loop so many times in your answer. Logic here is basically what Austin mentioned above.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.