Graphs
1.1 FIND PATH
#define SIZE 1001
int MAT[SIZE][SIZE];
int SORT[SIZE];
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
class CStack
{
public:
CStack()
: m_nTop(-1)
, m_nCycleIndex(-1)
{}
void Push(int nValue)
{
m_arrStack[++m_nTop] = nValue;
}
int Pop() {
int nValue = m_arrStack[m_nTop];
--m_nTop;
return nValue;
}
int Peep() const {
return m_arrStack[m_nTop];
}
int IsEmpty() const {
if(-1 == m_nTop) return true;
return false;
}
void PrintPath()
{
cout << "Path: ";
for(int i = m_nTop; i >= 0; i--) {
cout << m_arrStack[i] << " ";
}
cout << endl;
}
void PrintCycle(int nNodes)
{
cout << "Path: ";
for(int i = m_nCycleIndex; i <= m_nTop; i++) {
SORT[m_arrStack[i]] = 1;
}
for(int i = 1; i <= nNodes; i++) {
if (0 != SORT[i]) {
cout << i << " ";
}
}
cout << endl;
}
int m_nTop;
int m_nCycleIndex;
int m_arrStack[SIZE];
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
class CVertexInfo
{
public:
CVertexInfo()
: m_nParent(-1)
, m_bVisited(false)
{}
void Reset()
{
m_nParent = -1;
m_bVisited = false;
}
int m_nParent;
bool m_bVisited;
};
class CFindPaths
{
public:
CFindPaths(int N, int E)
: m_nNode(N)
, m_nEdge(E)
{
for(int r = 1; r <= m_nNode; r++) {
SORT[r] = 0;
for(int c = 1; c <= m_nNode; c++) {
MAT[r][c] = 0;
}
}
}
void Insert()
{
for(int e = 0; e < m_nEdge; e++) {
int from, to;
cin >> from >> to;
MAT[from][to] = 1;
}
}
void Print()
{
for(int r = 1; r <= m_nNode; r++) {
for(int c = 1; c <= m_nNode; c++) {
cout << MAT[r][c] << " ";
}
cout << endl;
}
}
void Run(int nStart, int nEnd)
{
dfs(nStart, nEnd);
}
protected:
bool dfs(int nStart, int nEnd)
{
// Start by pushing the first vertex and mark it visited
m_objStack.Push(nStart);
m_objVI[nStart].m_bVisited = 1;
while(false == m_objStack.IsEmpty()) {
int nVertex = m_objStack.Peep();
if(nVertex == nEnd) {
m_objStack.PrintPath();
break;
}
// Flag to check if the Vertex has edges
bool bPop = true;
// Lookup breadth-wise and find edge
for(int nChild = 1; nChild <= m_nNode; nChild++) {
if (1 == MAT[nVertex][nChild]) {
// If not visited then add to stack
if(!m_objVI[nChild].m_bVisited) {
bPop = false;
m_objStack.Push(nChild);
m_objVI[nChild].m_bVisited = 1;
break;
}
}
}
// Pop if there is not edges from the vertex
if(bPop) {
m_objStack.Pop();
}
};
return false;
}
private:
int m_nNode, m_nEdge;
CStack m_objStack;
CVertexInfo m_objVI[SIZE];
};
int main()
{
freopen("Graph_FindPath.txt", "r", stdin);
for(int t = 1; t <= 2; t++) {
cout << ">>> Test Case: " << t << endl;
int a, b;
cin >> a >> b;
CFindPaths obj(a, b);
obj.Insert();
obj.Print();
cin >> a >> b;
obj.Run(a, b);
}
return 0;
}
Input
4 5
1 2 1 3 3 1 3 4 4 4
1 4
5 6
1 2 2 3 3 1 1 4 4 5 5 1
3 5
Index
DFS
BFS
Highest Used Segments
Dijikstra
Floyd Warshall
Prims
Ford Fulkerson