Follow Me

Graph exercises in C Programming in C

  • Picking up sticks: Pick up sticks is a fascinating game. A collection of colored sticks are dumped in a tangled heap on the table. Players take turns trying to pick up a single stick at a time without moving any of the other sticks. It is very difficult to pick up a st...
  • Beverages: Zahraa has just finished college and decided to go out with friends. Zahraa has some strange habits and thus she decided to celebrate this important moment of her life drinking sugar a lot. She will start drinking beverages with low sugar content, li...
  • Changing strings: Consider the following declaration:typedef struct {    int V;    int E;    int **Adj; } Graph;Given a $$\texttt{start string}$$, $$\texttt{end string}$$ and a $$\texttt{set of strings}$$, find if there exists a path between the $$\texttt{start ...
  • Automata: Consider the following declaration:typedef struct {    int V;    int E;    char **Adj; } automata;An $$\texttt{automata}$$ is a directed weighted graph where weights are characters. Write a function that reads and returns an $$\texttt{automata}...
  • Bellman-Ford Algorithm: If the graph has negative edge costs, then Dijkstra's algorithm does not work. The problem is that once a vertex $$u$$ is declared known, it is possible that from some other, unknown vertex $$v$$ there is a path back to $$u$$ that is very negative. I...
  • Dijkstra Algorithm: A famous solution for the shortest path problem was developed by Dijkstra. Dijkstra's algorithm is a generalization of the BFS algorithm. The regular BFS algorithm cannot solve the shortest path problem as it cannot guarantee that the vertex at the f...
  • Prim Algorithm - Minimal Spanning Tree: A minimum spanning tree of an undirected graph \(G\) is a tree formed from graph edges that connect all the vertices of \(G\) with minimum total cost (weights). A minimum spanning tree exists only if the graph is connected. Prim's algorithm is almos...
  • Kruskal Algorithm - Minimal Spanning Tree: The algorithm starts with V different trees (V is the vertices in the graph). While constructing the minimum spanning tree, every time Kruskal’s algorithm selects an edge that has minimum weight and then adds that edge if it doesn’t create a cycl...
  • Graph Edge Property: Running DFS on a connected graph generates a DFS spanning tree (or spanning forest if the graph is disconnected). With the help of one more vertex state: EXPLORED  (visited but not yet completed) on top of VISITED (visited and completed), we can use...
  • UVA 10009 - All Roads Lead Where: There is an ancient saying that "All Roads Lead to Rome". If this were true, then there is a simple algorithm for nding a path between any two cities. To go from city A to city B, a traveller could take a road from A to Rome, then from Rome to B. Of ...
  • UVA 1112 - Mice and Maze: A set of laboratory mice is being trained to escape a maze. The maze is made up of cells, and each cell is connected to some other cells. However, there are obstacles in the passage between cells and therefore there is a time penalty to overcome the ...
  • Articulation points cut bridges and cut edges: In an undirected graph, a cut vertex (or articulation point) is a vertex, and if we remove it, then the graph splits into two disconnected components. As an example, consider the following figure. Removal of the “D” vertex divides the graph into ...
  • Adjacency matrix representation of a graph: Represent a graph using an adjacency matrix....
  • Adjacency list representation of a graph: Represent a graph using an adjacency list....
  • DFS traversal of a graph using an adjacency matrix: Perform a DFS traversal over a graph represented using an adjacency matrix....
  • Recursive DFS traversal of a graph using an adjacency list: Perform a recursive DFS traversal over a graph represented using an adjacency list....
  • Iterative DFS traversal of a graph using an adjacency list: Perform an iterative DFS traversal over a graph represented using an adjacency list....
  • Iterative BFS traversal of a graph using an adjacency list: Perform an iterative BFS traversal over a graph represented using an adjacency list....
  • Iterative BFS traversal of a graph using an adjacency matrix: Perform an iterative BFS traversal over a graph represented using an adjacency matrix....
  • Path between two vertices: Write a program that checks whether a path exists between two vertices in a graph. Implement the graph using an adjacency list and use DFS....
  • Connected graph: Write a program that checks whether a graph is connected. Implement the graph using an adjacency list and use DFS....
  • Topological sort using BFS traversal of a graph using an adjacency matrix: Perform a topological sort using BFS traversal of a graph using an adjacency matrix....
  • Topological sort using BFS traversal of a graph using an adjacency list: Perform a topological sort using BFS traversal of a graph using an adjacency list....
  • Topological sort using DFS traversal of a graph using an adjacency list: Perform a topological sort using DFS traversal of a graph using an adjacency list...
  • Shortest path from a source in an unweighted graph using an adjacency matrix: Give a ahortest path from a source in an unweighted graph using an adjacency matrix....
  • Shortest path from a source in an unweighted graph using an adjacency list: Give a ahortest path from a source in an unweighted graph using an adjacency list....

Back to the list of exercises

© Copyright 2006-2024    |    All rights reserved