Znajdowanie mostów

Z RNO-Wiki
(Różnice między wersjami)
m (Algorytm znajdowania mostów w grafie)
(Algorytm znajdowania mostów w grafie)
Linia 16: Linia 16:
 
/**
 
/**
 
   *  Autor: Rafał Nowak (www.rafalnowak.pl)
 
   *  Autor: Rafał Nowak (www.rafalnowak.pl)
   *  Data : 2008.02.27
+
   *  Data : 2008.02.27 , 2008.03.19
 
   *  Adres url: http://www.rafalnowak.pl/wiki/index.php?title=Znajdowanie_most%C3%B3w
 
   *  Adres url: http://www.rafalnowak.pl/wiki/index.php?title=Znajdowanie_most%C3%B3w
 
   *
 
   *
Linia 50: Linia 50:
 
#include<vector>
 
#include<vector>
 
using namespace std;
 
using namespace std;
 
+
 
typedef vector<int >  VI;
 
typedef vector<int >  VI;
typedef pair<int,int> PII;
 
 
const int INF = 1000000000;
 
const int INF = 1000000000;
 
+
 
int n,m, cnt;
 
int n,m, cnt;
 
VI in, pi;
 
VI in, pi;
 
vector<VI> adj;
 
vector<VI> adj;
vector<PII> most;
+
 
+
 
// wczytywanie grafu
 
// wczytywanie grafu
 
// wierzchołki na wejściu numerowane są od 1 do n
 
// wierzchołki na wejściu numerowane są od 1 do n
Linia 76: Linia 74:
 
}
 
}
 
}
 
}
 
+
void insertMost(int a, int b)// kolekcja mostów :-)
+
{
+
if (a==b) return;
+
if (a>b) swap(a,b);
+
most.push_back( PII(a,b) );
+
}
+
 
+
 
void init()
 
void init()
 
{
 
{
 
in.clear (); in.resize (n,INF);
 
in.clear (); in.resize (n,INF);
pi.resize(n); most.clear();
+
pi.resize(n);
 
cnt = 1;
 
cnt = 1;
 
}
 
}
 
+
 
int dfs(int u)
 
int dfs(int u)
 
{
 
{
Linia 103: Linia 95:
 
// że w grafie nie ma krawędzi wielokrotnych
 
// że w grafie nie ma krawędzi wielokrotnych
 
if (v==pi[u]) continue;
 
if (v==pi[u]) continue;
+
 
if (in[v]==INF)
 
if (in[v]==INF)
 
{
 
{
Linia 111: Linia 103:
 
if (in[ans] > in[v]) ans=v;
 
if (in[ans] > in[v]) ans=v;
 
}
 
}
if (ans==u && pi[u]!=u) insertMost(u,pi[u]);
+
if (ans==u && pi[u]!=u) printf("Most : %d -- %d\n", u+1, pi[u]+1);
 
return ans;
 
return ans;
 
}
 
}
 
+
 
int main(void)
 
int main(void)
 
{
 
{
Linia 124: Linia 116:
 
pi[u] = u; dfs(u);
 
pi[u] = u; dfs(u);
 
}
 
}
// przygotowanie listy mostów do odpowiedzi
 
sort(most.begin(), most.end());
 
// wypisanie wszystkich mostów
 
for (int i=0; i<most.size(); i++) printf("%d %d\n", most[i].first+1, most[i].second+1);
 
 
return 0;
 
return 0;
 
}
 
}
Linia 142: Linia 130:
 
</tr>
 
</tr>
 
</table>
 
</table>
 +
 +
Powyższy program dla wejścia
 +
[[Grafika:Graf_prosty.png|right]]
 +
<pre>
 +
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
 +
</pre>
 +
wypisze następujące mosty:
 +
<pre>
 +
Most : 10 -- 9
 +
Most : 9 -- 8
 +
Most : 12 -- 11
 +
Most : 11 -- 8
 +
Most : 8 -- 3
 +
</pre>

Wersja z 11:16, 19 mar 2008


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