Într-un graf neorientat, fiecărei muchii i se poate asocia o pondere (un cost). Putem considera un graf neorientat fără ponderi ca fiind o particularizare a unui graf cu costuri, fiecare muchie având costul 1. Această pondere (sau cost) va exprima intensitatea relaţiei dintre 2 noduri ale grafului.

Reprezentarea unui astfel de graf G=(X,U) se face utilizând o matrice a ponderilor P(n,n) a cărei elemente se definesc astfel:
p(i,j) = 0 dacă i=j
p(i,j) = c(i,j) în cazul în care (i,j) este o muchie din U unde c(i,j) este costul muchiei (i,j)
P(i,j) = $latex \infty$ în restul cazurilor

Utilizarea grafurilor ponderate este des întâlnită în practică. Cel mai sugestiv exemplu este cel al unei reţele de oraşe, nodurile grafului reprezentând oraşele, muchiile reprezentând legăturile (şoselele) dintre oraşe iar costul lor este dat de distanţa dintre oraşe.

Să se scrie un program C care verifică dacă un graf este conex şi să se afişeze toate componentele sale conexe.


#include "stdio.h"
#include "conio.h"
int n,m,a[20][20],viz[20],nrc=0;
void viziteaza(int nod)
{
  int i;
  viz[nod]=nrc;
  for(i=1;i <= n;i++)     if(a[nod][i] == i && viz[i] == 0)       viziteaza(i); } void main() {   int nod,i,j,x,y;   printf("Introdu numărul de noduri:");   scanf("%d",&n);   printf("Introdu numărul de muchii:");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   printf("Introdu muchiile :\n");   for(i=1;i <= m;i++)   {     printf("De la nodul: ");     scanf("%d",&x);     printf("la nodul: ");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   for(nod=1;nod <= n;nod++)     if(viz[nod] == 0)     {       nrc++;       viziteaza(nod);     }   if(nrc == 1)     printf("Graful este conex!\n");   else     printf("Graful nu este conex!\n");   printf("Componentele conexe sunt:\n");   for(i=1;i <= nrc;i++)   {     printf("Componenta %d:",i);       for(j=1;j <= n;j++)         if(viz[j] == i)           printf("%d ",j);     putchar("\n");   }   getch(); }