depth first search graph by using linked list
- by programmerwannabe
im using mac book
and i cannot read the text file using this code.
moreover, can you guys please add function(graph is connected?, and is this graph tree?)
inputA.txt consist
1 2
1 6
1 5
2 3
2 6
3 4
3 6
4 5
4 6
5 6
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#define MAX 10
#define TRUE 1
#define FALSE 0
typedef struct Graph{
int vertex;
struct Graph* link;
} g_node;
typedef struct graphType{
int x;
int visited[MAX];
g_node* adjList_H[MAX];
} graphType;
typedef struct stack{
int data;
struct stack* link;
} s_node;
s_node* top;
void push(int item){
s_node* n=(s_node*)malloc(sizeof(s_node));
n->data = item;
n->link = top;
top = n;
}
int pop(){
int item;
s_node* n=top;
if(top == NULL){
puts("\nstack is empty!\n");
return 0;
}
else {
item = n-> data;
top = n->link;
free(n);
return item;
}
}
void createGraph(graphType* g){
int v;
g->x = 1;
for(v=1 ; v < MAX ; v++){
g -> visited[v] = FALSE;
g -> adjList_H[v] = NULL;
}
}
void insertVertex(graphType* g, int v){
if(((g->x)) > MAX){
puts("\n it has been overed the number of vertex\n");
return ;
}
g -> x++;
}
void insertEdge(graphType* g, int u, int v){
g_node* node;
if(u >= g -> x || v >= g -> x){
puts("\n no vertex in the graph\n");
return ;
}
node = (g_node*)malloc(sizeof(g_node));
node -> vertex = v;
node -> link = g -> adjList_H[u];
g-> adjList_H[u] = node;
}
void print_adjList(graphType* g){
int i;
g_node *p;
for(i=1 ; i<g -> x ; i++){
printf("\n\t\t vertex %d adjacency list ", i);
p = g -> adjList_H[i];
while(p){
printf("-> %d", p-> vertex);
p = p-> link;
}
}
}
void DFS_adjList(graphType* g, int v)
{
g_node* w;
top = NULL;
push(v);
g->visited[v] = TRUE;
printf(" %d", v);
while(top != NULL){
w=g->adjList_H[v];
while(w){
if (!g->visited[w->vertex]){
push(w->vertex);
g->visited[w->vertex] = TRUE;
printf(" %d", w->vertex);
v = w->vertex;
w=g->adjList_H[v];
}
else w= w->link;
}
v = pop();
}
}
int main (int argc, const char * argv[]) {
FILE *fp;
char mychar;
char arr[][2]={0, };
int j, k;
int i;
graphType *G9;
G9 = (graphType*)malloc(sizeof(graphType));
createGraph(G9);
for(i=1; i<7 ; i++)
insertVertex(G9, i);
fp = fopen("inputD.txt", "r");
for(j = 0 ; j< 10 ; j++){
for(k = 0 ; k < 2 ; k++){
mychar = fgetc(fp);
if(mychar = EOF){
j=10;
break;
}
else if(mychar == ' ')
continue;
else if(mychar <= '9' || mychar >= '1'){
arr[j][k] = mychar;
printf("%d%d", arr[i][k]);
}
}
}
insertEdge(G9, 1, 2);
insertEdge(G9, 1, 6);
insertEdge(G9, 1, 5);
insertEdge(G9, 2, 3);
insertEdge(G9, 2, 6);
insertEdge(G9, 3, 4);
insertEdge(G9, 3, 6);
insertEdge(G9, 4, 5);
insertEdge(G9, 4, 6);
insertEdge(G9, 5, 6);
insertEdge(G9, 6, 5);
insertEdge(G9, 6, 4);
insertEdge(G9, 5, 4);
insertEdge(G9, 6, 3);
insertEdge(G9, 4, 3);
insertEdge(G9, 6, 2);
insertEdge(G9, 3, 2);
insertEdge(G9, 5, 1);
insertEdge(G9, 6, 1);
insertEdge(G9, 2, 1);
printf("\n graph adjacency list ");
print_adjList(G9);
printf("\n \n//////////////////////////////////////////////\n\n depth fist search >> ");
DFS_adjList(G9, 1);
return 0;
}
