Реализация шаблонного графа на С++

[Bitter_Schokolade]

Добрый день, уважаемые форумчане!
Помогите, пожалуйста, решить следующую задачу:
необходимо реализовать шаблонный граф на С++ (в моем случае, на VS)

Реализованы:
1) матрица смежности
2) матрица инцидентности

Здесь мои наработки (кстати, с перегрузкой тоже проблема, не понимаю, как ее реализовать):

#include <iostream>
#include <vector>
using namespace std;

struct Edge
{
	int beginPoint;
	int endPoint;
	int weight;
};

struct Node
{
	vector<Node> Sm;
	vector<Edge> In;
	int Current;
};

class Graf
{
public:
	int n;
	int** m_sm;
	bool** m_in;
	int s;
	vector<Node> Nodes;
	vector<Edge> Edges;
	
public:
	Graf(vector<Node> nodes, vector<Edge>& edges)
	{
		Nodes = nodes;
		Edges = edges;
	}

	//перегрузка ==

	bool hasSmNode(Node current, Node sm)
	{
		for (int i = 0; i < current.Sm.size(); i++)
		{
			if (current.Sm[i].Current == sm)
			{
				return true;
			}
		}
		return false;
	}

	void print()
	{
		cout<<"Граф состоит из "<<Nodes.size()<<" вершин и "<<Edges.size()<<" рёбер."<<endl;
		cout<<"Вершины:"<<endl;
		for (int i = 0; i < Nodes.size(); i++)
		{
			cout<<Nodes[i].Current<<" ";
		}
		cout<<endl;
		cout<<"Рёбра:"<<endl;
		for (int i = 0; i < Edges.size(); i++)
		{
			cout<<Edges[i].beginPoint<<"-("<<Edges[i].weight<<")-"<<Edges[i].endPoint<<endl;
		}
	}

	void get_m_sm()
	{
		m_sm = new int*[Nodes.size()];
		for (int i = 0; i < Nodes.size(); i++)
		{
			m_sm[i] = new int[Nodes.size()];
		}

		for (int i = 0; i < Nodes.size(); i++)
		{
			for (int j = 0; j < Nodes.size(); j++)
			{
				m_sm[i][j]=0;
			}
		}

		for (int i = 0; i < Edges.size(); i++)
		{
			Edge e = Edges[i];
			if (e.weight>0)	
			{
				m_sm[e.beginPoint][e.endPoint] = 1;
				m_sm[e.endPoint][e.beginPoint] = 1;
				
				if (hasSmNode(Nodes[e.beginPoint], Nodes[e.endPoint]))
					Nodes[e.beginPoint].Sm.push_back(Nodes[e.endPoint]);
				
				if (hasSmNode(Nodes[e.endPoint], Nodes[e.beginPoint]))
					Nodes[e.endPoint].Sm.push_back(Nodes[e.beginPoint]);
			}
		}
	}

	void get_m_in()
	{
		m_in = new bool*[Nodes.size()];
		for (int i = 0; i < Nodes.size(); i++)
		{
			m_in[i]= new bool[Edges.size()];
		}

		for (int i = 0; i < Nodes.size(); i++)
		{
			for (int j = 0; j < Edges.size(); j++)
			{
				m_in[i][j]=0;
			}
		}

		for (int i = 0; i < Edges.size(); i++)
		{
			Edge e = Edges[i];
			m_in[e.beginPoint][i]=1;
			m_in[e.endPoint][i]=1;
		}
	}

	//печатаем матрицу смежности
	void print_sm()
	{
		cout<<"Матрица смежности:"<<endl;
		for (int i = 0; i < Nodes.size(); i++)
		{
			for (int j = 0; j < Nodes.size(); j++)
			{
				cout << m_sm[i][j];
			}
			cout << endl;
		}
	}

	//печатаем матрицу инцидентности
	void print_in()
	{
		cout<<"Матрица инцидентности:"<<endl;
		for (int i = 0; i < Nodes.size(); i++)
		{
			for (int j = 0; j < Edges.size(); j++)
			{
				cout<<m_in[i][j];
			}
			cout<<endl;
		}
	}

	~Graf()
	{
		delete [] m_in;
		delete [] m_sm;
		//Nodes = NULL;
		//Edges = NULL;
	}
};

int main()
{
	setlocale(LC_ALL, "Rus");

	Node node;
	Edge edge;

	int weight = 0;
	int _pointCount = 0;
	int _current = 0;

	vector<Node> _nodes;
	vector<Edge> _edges;

	cout << "Введите количество вершин: "; 
	cin >> _pointCount;
	for (int i=0; i < _pointCount; ++i)
	{
		cout<<"Вершина "<<i+1<<"->";
		cin>>_current;
		node.Current = _current;
		_nodes.push_back(node);

	}

	cout << "Введите веса рёбер между вершинами: "<<endl; 
	for (int i=0; i < _pointCount; ++i)
	{
		for (int j=i+1; j < _pointCount; ++j)
		{
			cout << "Вес " << i << "->" << j <<": "; 
			cin >> weight;

			if (weight != 0)
			{
				edge.beginPoint = i;
				edge.endPoint = j;
				edge.weight = weight;
				_edges.push_back(edge);
				
				_nodes[i].Sm.push_back(_nodes[j]);
				_nodes[i].In.push_back(edge);
			}
		}
	}
	
	Graf g(_nodes, _edges);
	g.print();
	g.get_m_sm();
	g.print_sm();
	g.get_m_in();
	g.print_in();

	system("pause");
	return 0;
}

Для существующего кода необходимо:
1) написать перегрузку
2) написать матрицу весов (матрица смежности, где факт наличия связи заменен весом этой связи)
3) решить задачу комивояжера (поиск кратчайшего пути между выбранными вершинами)
4) реализовать поиск в глубину
5) реализовать поиск в ширину

Очень прошу помочь! Заранее благодарна.