Question

In: Computer Science

Language: Java or C (NO OTHER LANGUAGE) Do NOT use Java library implementations of the data...


Language: Java or C (NO OTHER LANGUAGE)

Do NOT use Java library implementations of the data structures (queues, lists, STs, hashtables etc.)

Have a unit test implemented in main(). And comment every code.

Show examples from the executions.

Question:
First step: write a program based on DFS which can answer questions of the type: "Find the a path from X to Y" Which should result in a list of vertices traversed from X to Y if there is a path.
Second step: Change the program to use BFS.


For the vertex pairs use this as your input:

AL FL
AL GA
AL MS
AL TN
AR LA
AR MO
AR MS
AR OK
AR TN
AR TX
AZ CA
AZ NM
AZ NV
AZ UT
CA NV
CA OR
CO KS
CO NE
CO NM
CO OK
CO UT
CO WY
CT MA
CT NY
CT RI
DC MD
DC VA
DE MD
DE NJ
DE PA
FL GA
GA NC
GA SC
GA TN
IA IL
IA MN
IA MO
IA NE
IA SD
IA WI
ID MT
ID NV
ID OR
ID UT
ID WA
ID WY
IL IN
IL KY
IL MO
IL WI
IN KY
IN MI
IN OH
KS MO
KS NE
KS OK
KY MO
KY OH
KY TN
KY VA
KY WV
LA MS
LA TX
MA NH
MA NY
MA RI
MA VT
MD PA
MD VA
MD WV
ME NH
MI OH
MI WI
MN ND
MN SD
MN WI
MO NE
MO OK
MO TN
MS TN
MT ND
MT SD
MT WY
NC SC
NC TN
NC VA
ND SD
NE SD
NE WY
NH VT
NJ NY
NJ PA
NM OK
NM TX
NV OR
NV UT
NY PA
NY VT
OH PA
OH WV
OK TX
OR WA
PA WV
SD WY
TN VA
UT WY
VA WV

Solutions

Expert Solution

Depth Fisrt Search(DFS)

​
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v) 
{
        int i;
        reach[v]=1;
        for (i=1;i<=n;i++)
          if(a[v][i] && !reach[i]) 
{
                printf("\n %d->%d",v,i);
                dfs(i);
        }
}
void main() 
{
        int i,j,count=0;
        clrscr();
        printf("\n Enter number of vertices:");
        scanf("%d",&n);
        for (i=1;i<=n;i++) 
{
                reach[i]=0;
                for (j=1;j<=n;j++)
                   a[i][j]=0;
        }
        printf("\n Enter the adjacency matrix:\n");
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
           scanf("%d",&a[i][j]);
        dfs(1);
        printf("\n");
        for (i=1;i<=n;i++) 
{
                if(reach[i])
                   count++;
        }
        if(count==n)
          printf("\n Graph is connected"); else
          printf("\n Graph is not connected");
        getch();
}
​

Breadth First Search (BFS)

#include<stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;

void bfs(int v)
 {
        for(i = 1; i <= n; i++)
                if(a[v][i] && !visited[i])
                        q[++r] = i;
        if(f <= r)
 {
                visited[q[f]] = 1;
                bfs(q[f++]);
        }
}

void main()
 {
        int v;
        printf("\n Enter the number of vertices:");
        scanf("%d", &n);
        
        for(i=1; i <= n; i++) 
{
                q[i] = 0;
                visited[i] = 0;
        }
        
        printf("\n Enter graph data in matrix form:\n");
        for(i=1; i<=n; i++) 
{
                for(j=1;j<=n;j++) 
{
                        scanf("%d", &a[i][j]);
                }
        }
        
        printf("\n Enter the starting vertex:");
        scanf("%d", &v);
        bfs(v);
        printf("\n The node which are reachable are:\n");
        
        for(i=1; i <= n; i++) 
{
                if(visited[i])
                        printf("%d\t", i);
                else {
                        printf("\n Bfs is not possible. Not all nodes are reachable");
                        break;
                }
        }
}

Related Solutions

Language: Java or C (NO OTHER LANGUAGE) Do NOT use Java library implementations of the data...
Language: Java or C (NO OTHER LANGUAGE) Do NOT use Java library implementations of the data structures (queues, lists, STs, hashtables etc.) Have a unit test implemented in main(). And comment every code. Show examples from the executions. Assume that the edges defined by the vertex pairs in the data base are one-way. Question: Write a program that can answer if there is a path between any to vertices. For the vertex pairs use this as your input example: AL...
Language: Java or C (NO OTHER LANGUAGE) Do NOT use Java library implementations of the data...
Language: Java or C (NO OTHER LANGUAGE) Do NOT use Java library implementations of the data structures (queues, lists, STs, hashtables etc.) Have a unit test implemented in main(). And comment every code. Show examples from the executions. Assume that the edges defined by the vertex pairs are two-way. Question: First step: write a program based on DFS which can answer questions of the type: "Find the a path from X to Y" Which should result in a list of...
Programming Language Required: C Write a multithreaded program in C (not c++) using the pthread library...
Programming Language Required: C Write a multithreaded program in C (not c++) using the pthread library and dynamic memory(malloc) that multiplies two matrices together. The numbers in the matrices must be read in from a text file. The program should also check if the two matrices are capable of being multiplied together. The amount of threads used has to be dynamic. The user should be able to choose how many threads they wish to use using the command line. Finally,...
JAVA PROGRAMMING LANGUAGE Suppose a library is processing an input file containing the titles of books...
JAVA PROGRAMMING LANGUAGE Suppose a library is processing an input file containing the titles of books in order to identify duplicates. Write a program that reads all of the titles from an input file called bookTitles.inp and writes them to an output file called duplicateTitles.out. When complete, the output file should contain all titles that are duplicated in the input file. Note that the duplicate titles should be written once, even though the input file may contain same titles multiple...
Problem 2 [6pt] In early implementations of Fortran language, a compiler may choose to use static...
Problem 2 [6pt] In early implementations of Fortran language, a compiler may choose to use static allocation (i.e., allocation in the static area) for local variables and parameters, effectively arranging for the variables of different invocations to share the same locations, and thereby avoiding any run-time overhead for creation and destruction of stack frames. However, such implementation changes the meaning of recursive function calls. Write down a simple example and explain how its meaning changes under the “Fortran” semantics as...
Write this program in C++ language. Use the concept of structures. DO NOT use vectors. Q...
Write this program in C++ language. Use the concept of structures. DO NOT use vectors. Q (4) Create a structure called time. Its three members, all type int, should be called hours, minutes, and seconds. Write a program that prompts the user to enter a time value in hours, minutes, and seconds. This should be in 12:59:59 format. This entire input should be assigned first to a string variable. Then the string should be tokenized thereby assigning the 1st token...
this is data structures with C++ language, please do "#1 & a" separately and please send...
this is data structures with C++ language, please do "#1 & a" separately and please send me copyable file 1. Write a program that allows the user to enter the last names of the candidates in a local election and the votes received by each candidate. The program should then output each candidate's name, votes received by that candidate, and the percentage of the total votes received by the candidate. Assume a user enters a candidate's name only once and...
Please use C language and use link list to do this program. This program should ask...
Please use C language and use link list to do this program. This program should ask user to enter two fraction polynomials. Then user chocie if he want add it or multiple it. I need you please to test it to see if it work with these two fraction polynomials 1-  Left Poly Pointer: 1/1x2 + 3/4x + 5/12 2-Right Poly Pointer: 1/1x4 – 3/7x2 + 4/9x + 2/11 AND AFTER ADDING 3- Resulting Poly Pointer: 1/1x4 + 4/7x2 + 43/36x...
In R, Use library(MASS) to access the data sets for this test. Use the Pima.tr data...
In R, Use library(MASS) to access the data sets for this test. Use the Pima.tr data set to answer questions 1-5. What is the average age for women in this data set? What is the maximum number of pregnancies for women in this data set ? What is the median age for women who have diabetes? What is the median age for women who do not have diabetes? What is the third quartile of the skin variable?
Translate the following C code into M4K assembly language. You do not have to use the...
Translate the following C code into M4K assembly language. You do not have to use the frame pointer, just use $sp if you need to use the stack. You do not have to show the stack initialization nor stack cleanup. If you need a specific value for an address, just make an assumption. int A; main() { int B = 5; B = A+B }; // main //Disassembly starts here !main() { //stack and frame pointer init // you do...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT