Homework Soursehelp to writ C program There is a help Code below 2 Your tas
help to writ C program (There is a help Code below)
2) Your task is to write a C program for a Depth-First Search algorithm for graphs. The algorithm can be used to calculate reachability of any node in a graph from any other node. If you are not familiar with the Depth-First Search (DFS) algorithm, you can consider the following example. Let us say that we want to explore a graph as shown in the following figure:
A DFS algorithm uses a stack and can be described using the following pseudo-code:
Explanation: The nodes can be represented as integers starting from 0. In order to implement the algorithm, you will need a stack of integers. Since you do not know how many nodes there are until you start reading the input for each test case, you will need to allocate stack as a VLA or using malloc every time you start reading the graph. You can assume that you need a stack of size n if there are n nodes in the graph. You could use an array of integers for keeping the node “marks” as indicated by the algorithm. Namely, all nodes can initially
be marked with “0”, which means that they are not visited. Whenever you push a node on stack, you can mark it with “1”, meaning that it is “on-agenda” to be visited, and when it is poped from the stack, you can finally mark it with “2”, meaning that it was visited.
A way to explain line 5. is that it is a for-loop that iterates through all vertices “b” that are connected to “a” with an edge. Implementation note: You must iterate from the lower number vertices to higher number vertices.
You will assume that 0 is always the source node in this question.
Implementation
Your implementation must consists of the following files:
a7q3.c — the main file containing the main function, which implements reading input, the DFS algorithm, and producing the output;
stack.c — the file with stack functions;
stack.h — the header file for stack functions; and
makefile — the make file for producing the program a7q3. The program should be produced after running make a7q3. Make sure that all these files are added and submitted using SVN.
You should follow guidelines and example discussed in class about writing makefiles and header files.
-----------------------------------------------------------------------------------------------------
Input
The input will consist of a sequence of graph descriptions. Each graph description will start with a number denoting the number of nodes, followed by the list of all edges in the graph. You can assume that graph is an undirected graph. Each edge is represented as two numbers, which are ending nodes of the edge. The list of edges ends with numbers -1 -1. There could be more graphs given in the input, and at the end there will be a number 0 denoting the end of input.
For example, if we have only the graph given in the figure, the input will be as follows:
10 01021213232736456768 787989
-1 -1
0
Implementation hint: An easy approach to storing edges is to use a 2D array adj, called the adjacency matrix, such that adj[i][j] is 1 whenever vertices i and j are connected with an edge, and 0 otherwise.
Output
For each graph, you will print the test case and the number of test case, then the list of visited nodes, and at the end a report about reachable and non-reachable nodes. For example, for the above graph, the output will be:
Test case 1:
0 visited
2 visited
7 visited
?9 visited
8 visited
6 visited
3 visited
1 visited Reachable from 0: 1236789
Not reachable from 0: 45
------------------------------------------------------------------------------------------------
Here is codes that may help you to write yours program
dfs.c
#include <stdio.h>
#include <stdlib.h>
#include \"stack.h\"
typedef struct Graph {
struct NodeGraph* root;
} Graph;
struct NodeGraph initNode(int _h, int _w) {
struct NodeGraph node;
node.pvalue.h = _h;
node.pvalue.w = _w;
node.lft = NULL;
node.rght = NULL;
return node;
}
int main() {
struct Graph g;
struct NodeGraph currentNode;
/* top to bottom graph reading */
g.root = (NodeGraph*)malloc(sizeof(NodeGraph));
*g.root = initNode(0, 3);
g.root->lft = (NodeGraph*)malloc(sizeof(NodeGraph));
*g.root->lft = initNode(1, 2);
g.root->rght = (NodeGraph*)malloc(sizeof(NodeGraph));
*g.root->rght = initNode(1, 4);
(*g.root->lft).lft = (NodeGraph*)malloc(sizeof(NodeGraph));
*(*g.root->lft).lft = initNode(2, 1);
(*g.root->lft).rght = (NodeGraph*)malloc(sizeof(NodeGraph));
*(*g.root->lft).rght = initNode(2, 2);
(*g.root->rght).lft = (NodeGraph*)malloc(sizeof(NodeGraph));
*(*g.root->rght).lft = initNode(2, 3);
(*g.root->rght).rght = (NodeGraph*)malloc(sizeof(NodeGraph));
*(*g.root->rght).rght = initNode(2, 5);
Stack s;
initStack(&s);
push(&s, *g.root);
while (!ifEmpty(&s)) {
currentNode = top(&s);
pop(&s);
printf(\"(%d, %d)\ \", currentNode.pvalue.h, currentNode.pvalue.w);
if (currentNode.lft != NULL) {
push(&s, *currentNode.lft);
}
if (currentNode.rght != NULL) {
push(&s, *currentNode.rght);
}
}
system(\"pause\");
return 0;
}
---------------------------------------------------------------------------------
stack.c
#include \"stack.h\"
void initStack(struct Stack *s) {
s->topP = NULL;
s->bottomP = NULL;
}
void push(struct Stack *s, struct NodeGraph _value) {
ElementStack *newElement;
newElement = (ElementStack*)malloc(sizeof(ElementStack));
newElement->value = _value;
newElement->up = NULL;
newElement->down = NULL;
if (s->topP == NULL) {
s->topP = newElement;
s->bottomP = newElement;
}
else {
newElement->down = s->topP;
s->topP = newElement;
}
}
void pop(struct Stack *s) {
ElementStack *element;
if (s->topP == NULL) {
return;
}
else {
element = s->topP;
s->topP = element->down;
if (s->topP != NULL)
s->topP->up = NULL;
free(element);
}
}
struct NodeGraph top(struct Stack *s) {
return s->topP->value;
}
int ifEmpty(struct Stack *s) {
return (s->topP == NULL ? 1 : 0);
}
---------------------------------------------------------------------------------
stack.h
#include <stdio.h>
#include <stdlib.h>
typedef struct Point {
int h;
int w;
} Point;
typedef struct NodeGraph {
struct Point pvalue;
struct NodeGraph* lft;
struct NodeGraph* rght;
} NodeGraph;
typedef struct ElementStack {
struct NodeGraph value;
struct ElementStack *up;
struct ElementStack *down;
} ElementStack;
typedef struct Stack {
struct ElementStack* topP;
struct ElementStack* bottomP;
} Stack;
void initStack(struct Stack *s);
void push(struct Stack *s, struct NodeGraph _value);
void pop(struct Stack *s);
struct NodeGraph top(struct Stack *s);
int ifEmpty(struct Stack *s);
S 0 3 4 2 6 7 8 9Solution
we will implement depth first search in the following way:
#include<stdio.h>
#include<conio.h>
int array[20][20],reach[20],n;
void depthfirstsearch(int value)
{
int i;
reach[value]=1;
for(i=1;i<=n;i++)
if(array[value][i] && !reach[i])
{
printf(\"\ %d->%d\",value,i);
depthfirstsearch(i);
}
}
void main()
{
int i,j,count=0;
clrscr();
printf(\"\ Firstly please enter number of vertices:\");
scanf(\"%d\",&n);
for(i=1;i<=n;i++)
{
reach[i]=0;
for(j=1;j<=n;j++)
array[i][j]=0;
}
printf(\"\ now weill be entering the adjacency matrix:\ \");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(\"%d\",&array[i][j]);
depthfirstsearch(1);
printf(\"\ \");
for(i=1;i<=n;i++)
{
if(reach[i])
count++;
}
if(count==n)
printf(\"\ The given graph is connected\");
else
printf(\"\ The given graph is not connected\");
getch();
}
