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

Lista de Adjacências
Em uma lista de adjacências uma aresta com origem em x e destino em y existe se em alguma posição G[x][i], p/ todo i | i < "grau dessa lista" possui o valor y. Caso nenhuma posição tenha y a aresta não existe. Como podemos ver eu estou representando uma lista de adjancências através de uma matriz.

Ela é representada dessa maneira para facilitar a implementação, usando essa forma temos que cada linha da matriz é uma lista de adjacência do vértice da linha atual. Mas como sabemos o fim da lista?

Para isso utilizamos um vetor auxiliar, que chamaremos de grau, onde ele irá representar quantas adjacências esse vértice possui. Então para conferir todas as adjacências de um vértice basta olhar todas as colunas (que forem menor que grau) de sua linha na matriz.

Por exemplo, para verificarmos a aresta de x para y podemos fazer:

for(i=0;i<grau[x];++i){
    if(G[x][i] == y){
        printf("Existe aresta"); 
        break;
    }
}

Vamos ver uma Lista de adjacência para entendermos melhor, começando com um grafo não orientado:

Nessa primeira figura vemos primeiro um grafo não direcionado no item a), no item b) este grafo sendo representado por uma lista de adjacências.
Como seria sua representação através de uma matriz? (observe que estou falando de matriz para representar Listas de Adjacências e não matriz de adjacências)

Na figura acima a parte em cinza são apenas os números de cada vértice e a parte em verde é a lista de adjacências. Podemos ver que na linha 1 estão os elementos que tem arestas ligadas ao vértice 1 e assim sucessivamente.
Agora iremos ver outra lista, mas agora com grafo orientado:

E agora a representação através de matriz desse grafo:

Lendo e montando o grafo em C:

int G[MAXN][MAXN];
int grau[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));
memset(grau,0,sizeof(grau));

//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 (ou não orientado)
G[x][grau[x]++]=y; //já estamos aumentando o grau, ou seja, nova adjacência inserida
G[y][grau[y]++]=x;
}

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