One thought on “Graph Data Structure”

1. TechTalk Post authorOctober 8, 2021 at 9:34 pm

   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];

   //adjacency matrix
   int adjMatrix[MAX][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() {
   return top == -1;
   }

   //graph functions

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

   //add edge to edge array
   void addEdge(int start,int end) {
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
   }

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

   //get the adjacent unvisited vertex
   int getAdjUnvisitedVertex(int vertexIndex) {
   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
   int unvisitedVertex = getAdjUnvisitedVertex(peek());

   //no adjacent vertex found
   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;

   for(i = 0; i < MAX; i++) // set adjacency { for(j = 0; j < MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex('S'); // 0 addVertex('A'); // 1 addVertex('B'); // 2 addVertex('C'); // 3 addVertex('D'); // 4 addEdge(0, 1); // S - A addEdge(0, 2); // S - B addEdge(0, 3); // S - C addEdge(1, 4); // A - D addEdge(2, 4); // B - D addEdge(3, 4); // C - D printf("Depth First Search: ") depthFirstSearch(); return 0; } Output: Depth First Search: S A D B C

   Log in to Reply ↓