trjhtr

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;

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)
: Vv

 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) : idc, colorclr 

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.

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.)

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.