Neste post ensinarei como se usa uma das estruturas para grafos já mostradas aqui.

Matriz de Adjacência:

Na matriz de adjacência uma aresta com origem em x e destino em y existe se G[x][y] é igual a 1, caso seja 0 esta aresta não existe.

Vamos ver uma Matriz de adjacência para entendermos melhor:

Note que o número da linha/coluna representa, na verdade, o vértice.

Como seria o Grafo representado por essa matriz ?
Assim:

Teoria entendida. Agora vamos ver um pouco de programação.

Lendo e montando o grafo em C:

int G[MAXN][MAXN];
int n;

//Lendo o número de vértices (n)
scanf("%d",&n);

//o grafo é zerado, ou seja, não tem nenhuma aresta
memset(G,0,sizeof(G));

//Lendo as n arestas
for(i=1;i<=n;++i){
 scanf("%d %d",&x,&y);
 //está colocando aresta de x para y e de y para x
 //grafo bidirecional
 G[x][y]=1;
 G[y][x]=1;
}

Verificando arestas no grafo em C:

int G[MAXN][MAXN];
int n;

//Lendo as n arestas
for(i=1;i<=n;++i){
 for(j=1;j<=n;++j){
  if(G[i][j] == 1)
   printf("Existe aresta de %d para %d",i,j);
  else
   printf("Nao existe aresta de %d para %d",i,j);
 }
}

Dúvidas/Comentários/Sugestões através de comentários!