Your program must prompt for the data file to be used. The first line of the fil
ID: 644259 • Letter: Y
Question
Your program must prompt for the data file to be used. The first line of the file must be the number of vertices. Then there is one line per vertex, where each line has the vertex number followed by all adjacent vertices. You may assume that the lines are in ascending order by vertex number, and the adjacent vertex numbers are also in ascending order, separated by a space.
Consider the first example above, where the graph is shown at left and the contents of the data file is shown at right:
Enter the name of the data file to use for the graph: small.txt
Smallest Dominating Sets are:
1 2
2 5
Exiting program...
Your program must prompt for the data file to be used. The first line of the file must be the number of vertices. Then there is one line per vertex, where each line has the vertex number followed by all adjacent vertices. You may assume that the lines are in ascending order by vertex number, and the adjacent vertex numbers are also in ascending order, separated by a space. Consider the first example above, where the graph is shown at left and the contents of the data file is shown at right: Enter the name of the data file to use for the graph: small.txt Smallest Dominating Sets are: 1 2 2 5 Exiting program...Explanation / Answer
# include
# include
void DFS(int i);
void BFS(int i);
int vertice[10][10];
int flag[10];
int n,e;
int main()
{
int i,j,k;
scanf("%d%d",&n,&e);
int a,b;
for (i=0;i {
scanf("%d%d",&a,&b);
vertice[a][b] = vertice[b][a] = 1;
}
for (i=0;i {
if (flag[i]==1) continue;
else printf("{ "),DFS(i),printf("} ");
}
for(i=0;i<10;i++)
flag[i] = 0;
for (i=0;i {
if (flag[i]==1) continue;
else printf("{ "),BFS(i),printf("} ");
}
}
void DFS(int i)
{
printf("%d ",i),flag[i] = 1;
int j;
for (j=0;j if (vertice[i][j]==1&&flag[j]==0)
{
DFS(j);
}
}
void BFS(int i)
{
int start,end,Q[100];
start = end = 0;
Q[end++] = i;flag[i] = 1;
int temp,j;
while (start {
temp = Q[start++];
printf("%d ",temp);
for (j=0;j if (vertice[temp][j]==1&&flag[j]==0)
{
Q[end++] = j;
flag[j] = 1;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.