An Undirected Graph is a graph where edges have no direction—the connection between vertices is bidirectional. If there's an edge between A and B, you can traverse from A to B and from B to A. This models symmetric relationships like friendships (if A is friends with B, B is friends with A), roads (two-way streets), or physical connections.
Key properties include degree (total edges connected to a vertex), connectivity (whether all vertices are reachable from any vertex), and cycles (paths that start and end at the same vertex). BFS finds the shortest path in unweighted undirected graphs.
Add Vertex: Enter a label and click "Add Vertex".
Connect Vertices: Select two vertices to connect with a bidirectional edge.
Select Vertex: Click on a vertex to select it (yellow highlight).
DFS/BFS: Can traverse in any direction along edges.
Degree: Shows total number of edges connected to each vertex.
BFS Shortest Path: In unweighted graphs, BFS finds the shortest path (minimum edges) between vertices.
Cycle Detection: Track parent vertex during DFS; back edge to non-parent indicates cycle.
Connectivity Check: BFS/DFS from any vertex; if all vertices visited, graph is connected.
Minimum Spanning Tree: Kruskal's or Prim's algorithm finds tree connecting all vertices with minimum total weight.
Bridge Finding: Edges whose removal disconnects the graph (critical connections).
Social Networks: Facebook friendships are bidirectional (if A is B's friend, B is A's friend).
Road Networks: Two-way streets connecting intersections.
Computer Networks: Ethernet connections between devices.
Molecule Structures: Chemical bonds between atoms.
Game Maps: Rooms/areas connected by passages that work both ways.
Wireless Networks: If device A can communicate with B, B can communicate with A.
Add Vertex: Insert a new node into the graph.
Add Edge: Create bidirectional connection between two vertices.
Remove Vertex: Delete vertex and all its incident edges.
Remove Edge: Delete the undirected edge between two vertices.
Get Degree: Count total edges connected to a vertex.
Check Adjacency: Determine if two vertices are directly connected.
Connected Components: Use DFS/BFS from unvisited vertices; each traversal finds one component.
Cycle Detection: DFS with parent tracking; visiting non-parent neighbor indicates cycle.
Bipartite Check: Two-color graph using BFS/DFS; if conflict occurs, graph is not bipartite.
MST (Minimum Spanning Tree): Prim's (grow tree) or Kruskal's (Union-Find) for minimum cost tree.
Bridges and Articulation Points: Tarjan's algorithm with discovery/low times to find critical edges/vertices.
Flood Fill: BFS/DFS to visit all connected cells; used in image processing and games.
Union-Find: Efficient structure for connectivity queries and dynamic edge additions.
/* Undirected Graph implementation in C */
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node* next;
} Node;
typedef struct Graph {
int numVertices;
Node** adjLists;
int* visited;
} Graph;
Node* createNode(int v) {
Node* node = malloc(sizeof(Node));
node->vertex = v;
node->next = NULL;
return node;
}
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(Node*));
graph->visited = malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Undirected: adds edge in BOTH directions
void addEdge(Graph* graph, int src, int dest) {
// Edge from src to dest
Node* node = createNode(dest);
node->next = graph->adjLists[src];
graph->adjLists[src] = node;
// Edge from dest to src (bidirectional)
node = createNode(src);
node->next = graph->adjLists[dest];
graph->adjLists[dest] = node;
}
// Check if graph is connected using DFS
int isConnected(Graph* graph) {
// Reset visited array
for (int i = 0; i < graph->numVertices; i++)
graph->visited[i] = 0;
// DFS from vertex 0
void dfs(int v) {
graph->visited[v] = 1;
Node* adj = graph->adjLists[v];
while (adj) {
if (!graph->visited[adj->vertex])
dfs(adj->vertex);
adj = adj->next;
}
}
dfs(0);
// Check if all vertices were visited
for (int i = 0; i < graph->numVertices; i++)
if (!graph->visited[i]) return 0;
return 1;
}
int main() {
Graph* graph = createGraph(5);
addEdge(graph, 0, 1); addEdge(graph, 0, 2);
addEdge(graph, 1, 2); addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printf("Is Connected: %s\n", isConnected(graph) ? "Yes" : "No");
return 0;
}