-
Notifications
You must be signed in to change notification settings - Fork 0
/
path.cpp
78 lines (76 loc) · 1.55 KB
/
path.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;
int stepcount = 0;
int i,j;
void dfs(int adj[][10],int r,int v)
{
int dest;
int arr[20];
int index = -1;
cout<<"\nEnter the destination vertex: ";stepcount++;
cin>>dest;stepcount++;
int visited[r];
int Stack[20],top = -1;stepcount++;
Stack[++top] = v;stepcount++;
for(i = 0; i < r; i++)
{stepcount++;visited[i] = 0;stepcount++;}
visited[v] = 1;stepcount++;
while(top != -1)
{
int u = Stack[top--];stepcount++;
arr[++index] = u;stepcount++;
int k = 0;stepcount++;
while (k < r)
{
stepcount++;
if (adj[u][k] == 1 && visited[k] == 0)
{
stepcount++;
Stack[++top] = k;stepcount++;
visited[k] = 1;stepcount++;
//arr[++index] = k;
}
stepcount++;
if(visited[dest] == 1)
{
stepcount++;
for (i = 0; i < index+1; i++)
{stepcount++;cout << arr[i]<< " "; stepcount++;}
break;
}
k++;
}
stepcount++;
stepcount++;
if (visited[dest] == 1)
{stepcount+=2; break;}
//index--;
}
stepcount++;
}
int main()
{
int mat[10][10],r,src;
cout << "\nEnter the number of vertices in the graph: ";stepcount++;
cin >> r;stepcount++;
cout << "\nEnter the adjacency matrix: \n";stepcount++;
for (i = 0; i < r; i++)
{
stepcount++;
for (j = 0; j < r; j++)
{
stepcount++;
cin >> mat[i][j];
stepcount++;
}
stepcount++;
}
stepcount++;
cout << "\nEnter the source vertex: ";stepcount++;
cin >> src;stepcount++;
stepcount++;
dfs(mat,r,src);
stepcount++;
cout << "\nThe number of steps for "<<r<<"-vertex graph is: " << ++stepcount<<endl;
return 0;
}