Basic terminologies:
Vertices,edges,undirected and directed graph,cyclic & acyclic graph,degree indegree & outdegree and weights. In an undirected graph, the sum of degrees of all vertices is double the vertices (We consider degree=indegree=outdegree in an undirected graph).
Graph representation in C++
Let us say there are n nodes and m edges.
There are two ways to represent a graph
- Adjacency matrix:
adj[i][j] represents there is an edge from node i to j.
int n, m;
cin >> n >> m;
// declare the adjacent matrix
int adj[n+1][n+1];
// take edges as input
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u][v] = 1;
adj[v][u] = 1;
}
2.