PROBLEM SOLVING - GRAPH TRICKS

Graph Manipulation Approaches

#	Technique	Use Case	Approach	Complexity	Examples
1	Depth-First Search	Explore all nodes, detect cycles, topological sort	Recursively visit nodes, backtracking when no more unvisited nodes	O(V+E)	Connected components Cycle detection Topological sort Maze solving
2	Breadth-First Search	Shortest path in unweighted graphs, level-order traversal	Use queue to explore nodes level by level	O(V+E)	Shortest path Social network degrees Web crawling
3	Dijkstra's Algorithm	Shortest path in weighted graphs (non-negative weights)	Greedy algorithm using priority queue	O(E log V)	Routing protocols Network routing Pathfinding
4	Kruskal's Algorithm	Minimum spanning tree for weighted graphs	Sort edges, add to MST if no cycle (using Union-Find)	O(E log V)	Network design Cluster analysis Circuit design
5	Topological Sort	Linear ordering of vertices in DAGs	Modified DFS or Kahn's algorithm (in-degree counting)	O(V+E)	Task scheduling Build systems Course prerequisites
6	Floyd-Warshall	All-pairs shortest paths in weighted graphs	Dynamic programming with triple nested loops	O(V³)	Routing tables Distance matrices Traffic management
7	Bellman-Ford	Shortest path with negative weights	Relax all edges V-1 times, detect negative cycles	O(VE)	Currency arbitrage Network routing Negative weight graphs
8	Union-Find	Detect cycles, connected components	Disjoint set with path compression and union by rank	O(α(V))	Kruskal's algorithm Cycle detection Image segmentation

Common Graph Operations

Adjacency List Implementation

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    int V;
    struct Node** adjList;
};

struct Graph* createGraph(int V) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = malloc(V * sizeof(struct Node*));
    for (int i = 0; i < V; i++)
        graph->adjList[i] = NULL;
    return graph;
}

Space Complexity: O(V+E)

BFS Implementation

void BFS(struct Graph* graph, int start) {
    bool *visited = calloc(graph->V, sizeof(bool));
    int queue[graph->V], front = 0, rear = 0;
    
    visited[start] = true;
    queue[rear++] = start;
    
    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);
        
        struct Node* temp = graph->adjList[v];
        while (temp) {
            if (!visited[temp->vertex]) {
                visited[temp->vertex] = true;
                queue[rear++] = temp->vertex;
            }
            temp = temp->next;
        }
    }
    free(visited);
}

Time Complexity: O(V+E)

DFS Implementation

void DFSUtil(struct Graph* graph, int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", v);
    
    struct Node* temp = graph->adjList[v];
    while (temp) {
        if (!visited[temp->vertex])
            DFSUtil(graph, temp->vertex, visited);
        temp = temp->next;
    }
}

void DFS(struct Graph* graph, int start) {
    bool *visited = calloc(graph->V, sizeof(bool));
    DFSUtil(graph, start, visited);
    free(visited);
}

Time Complexity: O(V+E)

Dijkstra's Algorithm

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];
    
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    
    dist[src] = 0;
    
    for (int count = 0; count < V-1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && 
                dist[u] != INT_MAX && 
                dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
    printSolution(dist);
}

Time Complexity: O(V²)

Topological Sort

void topologicalSortUtil(struct Graph* graph, int v, 
                        bool visited[], int stack[], int *top) {
    visited[v] = true;
    
    struct Node* temp = graph->adjList[v];
    while (temp) {
        if (!visited[temp->vertex])
            topologicalSortUtil(graph, temp->vertex, visited, stack, top);
        temp = temp->next;
    }
    stack[++(*top)] = v;
}

void topologicalSort(struct Graph* graph) {
    int stack[graph->V], top = -1;
    bool *visited = calloc(graph->V, sizeof(bool));
    
    for (int i = 0; i < graph->V; i++)
        if (!visited[i])
            topologicalSortUtil(graph, i, visited, stack, &top);
    
    while (top >= 0)
        printf("%d ", stack[top--]);
    free(visited);
}

Time Complexity: O(V+E)

Kruskal's Algorithm

void KruskalMST(struct Graph* graph) {
    struct Edge result[graph->V];
    int e = 0, i = 0;
    
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);
    
    int *parent = (int*)malloc(graph->V * sizeof(int));
    for (int v = 0; v < graph->V; v++) parent[v] = v;
    
    while (e < graph->V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        
        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);
        
        if (x != y) {
            result[e++] = next_edge;
            Union(parent, x, y);
        }
    }
    printMST(result, e);
}

Time Complexity: O(E log V)

Advanced Graph Techniques

#	Technique	Description	Use Case
1	A* Search	Informed search algorithm using heuristics to find shortest path	Pathfinding in games, robotics
2	Tarjan's Algorithm	Finds strongly connected components in directed graphs	Compiler optimization, circuit analysis
3	Ford-Fulkerson	Computes maximum flow in flow networks	Network flow, bipartite matching
4	Hungarian Algorithm	Solves assignment problem in bipartite graphs	Job assignment, resource allocation
5	PageRank	Algorithm to rank web pages by importance	Search engines, recommendation systems
6	Traveling Salesman	Finds shortest possible route visiting all nodes	Logistics, circuit board drilling
7	Articulation Points	Finds critical nodes whose removal increases connected components	Network reliability analysis
8	Bridge Detection	Finds edges whose removal increases connected components	Network design, vulnerability analysis
9	Eulerian Path	Path that visits every edge exactly once	Route optimization, DNA sequencing
10	Hamiltonian Path	Path that visits every vertex exactly once	Route planning, puzzle solving
11	Graph Coloring	Assign colors to vertices so no adjacent vertices share color	Scheduling, register allocation
12	Bipartite Matching	Finds maximum matching in bipartite graphs	Job assignment, dating apps
13	Dominating Set	Subset of vertices where every vertex is adjacent to at least one in set	Network monitoring, facility location
14	Clique Detection	Finds complete subgraphs where every pair is connected	Social network analysis, bioinformatics
15	Community Detection	Identifies groups of densely connected nodes	Social network analysis, recommendation systems

Related Graph Resources

Basic Programs

Interview Questions

MCQs

Graph Tricks