# Graph Data Structure

If you want to solve a Rubik’s cube or understand what technology google uses for its maps, this is the place for you.

Many programming problems require you to represent a non-hierarchical relationship between pairs of items. Such problems can be solved by using data structure called graph. I will discuss the concept and implementation of graphs. I will also give various applications of graphs.

We shall see the following :
– Store data in a graph
– Implement a graph
– Apply graphs to solve Programming problems

## One thought on “Graph Data Structure”

1. TechTalk Post author

boarding pass: Src and dest?
you have a stack of unsorted flight boarding passes of a passenger. Only the departure city and destination city are on the boarding pass. how do you find the first departure city and the final destination city

Depth First Search (DFS) algorithm traverses a graph data structure in a depth ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration, It employs the following rules.

Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

The Code in “C” :

#include
#include
#include

#define MAX 5

struct Vertex {
char label;
bool visited;
};

//stack variables

int stack[MAX];
int top = -1;

//graph variables

//array of vertices
struct Vertex* lstVertices[MAX];

//vertex count
int vertexCount = 0;

//stack functions

void push(int item) {
stack[++top] = item;
}

int pop() {
return stack[top–];
}

int peek() {
return stack[top];
}

bool isStackEmpty() {
}

//graph functions

//add vertex to the vertex list
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}

}

//display the vertex
void displayVertex(int vertexIndex) {
printf(“%c “,lstVertices[vertexIndex]->label);
}

int i;

for(i = 0; i < vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
return i;
}
}

return -1;
}

void depthFirstSearch() {
int i;

//mark first node as visited
lstVertices[0]->visited = true;

//display the vertex
displayVertex(0);

//push vertex index in stack
push(0);

while(!isStackEmpty()) {
//get the unvisited vertex of vertex which is at top of the stack

if(unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}

//stack is empty, search is complete, reset the visited flag
for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false;
}
}

int main() {
int i, j;