Znajdowanie mostów

Z RNO-Wiki


Niech dany będzie graf nieskierowany G = (V,E), gdzie V oznacza zbiór wierzchołków, a E --- zbiór krawędzi.

Mostem nazywamy taką krawędź ze zbioru E, której usunięcie zwiększa liczbę spójnych składowych w grafie G, tzn. jeśli np. krawędź e jest w pewnej składowej oraz jeśli jej usunięcie sprawia, że przestaje być ona spójna, to krawędź e nazywamy mostem.

Na poniższym rysunku przedstawiono przykładowy graf, w którym mosty zaznaczono kolorem czerwonym:
Mosty.png

Algorytm znajdowania mostów w grafie

Aby znaleźć wszystkie mosty w grafie, wystarczy w odpowiedni sposób użyć przeglądania grafu w głąb (DFS). Poniżej znajduje się implementacja algorytmu w jezyku C++. Uwaga: zakładamy, że w grafie nie ma krawędzi wielokrotnych, ale mogą być pętle.

/**
  *   Autor: Rafał Nowak (www.rafalnowak.pl)
  *   Data : 2008.02.27 , 2008.03.19
  *   Adres url: http://www.rafalnowak.pl/wiki/index.php?title=Znajdowanie_most%C3%B3w
  *
  *   W pracy tej zaimplementowano algorytm znajdowania wszystkich mostów
  *   prostym grafie nieskierowanym, tj. bez pętli i krawędzi wielokrotnych.
  *   Tak naprawdę to pętle mogą być :-)
  *   Jeśli chodzi o krawędzie wielokrtotne, to należy lekko zmodyfikować program.
  *
  *   Dany: nieskierowany graf G z wierzchołkami numerowanymi od 1 do n.
  * 
 
Przykładowe wejście:
15 17
1 7
1 2
2 3
3 4
4 5
5 6
6 7
3 6
3 8
8 9
9 10
8 11
11 12
12 15
15 14
14 13
12 13
  **/
#include<algorithm>
#include<vector>
using namespace std;
 
typedef vector<int >   VI;
const int INF = 1000000000;
 
int n,m, cnt;
VI in, pi;
vector<VI> adj;
 
// wczytywanie grafu
// wierzchołki na wejściu numerowane są od 1 do n
void read() 
{
	int i, a,b;
	scanf("%d %d", &n, &m);
	adj.clear(); adj.resize(n);
	for (i=0; i<m; i++)
	{
		scanf("%d %d", &a, &b);
		if (a==b) continue; // pomijaj pętle
		a--; b--; 
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
}
 
 
void init()
{
	in.clear (); in.resize (n,INF);
	pi.resize(n);
	cnt = 1;
}
 
int dfs(int u)
{
	int ans = u;
	in[u] = cnt++;
	for (int i=0; i<adj[u].size(); i++)
	{
		int v = adj[u][i];
		 // pomijaj pętle
		if (v==u) continue;
		 // pomijaj krawędź do poprzednika w drzewie DFS; UWAGA: zakładamy tutaj,
		 // że w grafie nie ma krawędzi wielokrotnych
		if (v==pi[u]) continue;
 
		if (in[v]==INF)
		{
			pi[v] = u;
			v = dfs(v);	
		}
		if (in[ans] > in[v]) ans=v;
	}
	if (ans==u && pi[u]!=u) printf("Most : %d -- %d\n", u+1, pi[u]+1);
	return ans;
}
 
int main(void)
{
	read(); 
	init();
	for (int u=0; u<n; u++)
		if (in[u]==INF)
		{
			pi[u] = u; dfs(u);
		}
	return 0;
}

Powyższy program dla wejścia

Graf prosty.png
15 17
1 7
1 2
2 3
3 4
4 5
5 6
6 7
3 6
3 8
8 9
9 10
8 11
11 12
12 15
15 14
14 13
12 13

wypisze następujące mosty:

Most : 10 -- 9
Most : 9 -- 8
Most : 12 -- 11
Most : 11 -- 8
Most : 8 -- 3
Osobiste