none
поиск мостов в графе RRS feed

Ответы

  • Попробуйте так, незнаю на сколько верно, основывался на примере http://e-maxx.ru/algo/bridge_searching, он как то ближе к вашей задаче, чем то, что вы нашли http://social.msdn.microsoft.com/Forums/ru-RU/fordesktopru/thread/cc0361d5-d5dc-4269-930a-a2f6b8162f6b/ , но посмотрите в учебнике из которого вы брали, что означает d[MAXN], low[x], counter; и как они задаются. (т.е. в 1ом примере тоже не ясно как задается граф g)

     

    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include <iostream>
    #include <cmath>
    #include <complex>
    #include <string.h>
    #include <locale.h>
    using namespace std;
    
    int **a; //Матрица смежности
    int *c; //Массив вершин которые уже были пройденны
    int n; //Количество узлов
    
    //Добавляет вершину к c[]
    void add(int v) 
    {
      int i;
      for (i = 0; c[i] != -1; i++);
      c[i] = v;
    }
    
    //Возвращает true если вершина v содержиться в c[]
    int contain(int v)
    {
      for (int i = 0; i<n; i++)
        if (c[i] == v) return 1;
      return 0;
    }
    
    //Удаляет v из c[]
    void remove(int v) 
    {
      int i;
      for (i = 0; i != v; i++);
      c[i] = -1;
    }
    
    //Очищает c[]
    void clear()
    {
      for (int i = 0; i<n; i++) c[i] = -1;
    }
    
    //Запрашивает ввод элементов
    //По введенным элементам заполняет матрицу смежности
    void createGraph()
    {
      int v1, v2;
      int m;
    
      //Запрашиваем количество вершин
      printf("Vvedite kol-vo vershin: ");
      scanf("%i", &n);
      while (n<=0)
    {
        printf("Zna4enie dolJno Bit' > 0. vvedite pravilnoe zna4enie: ");
        scanf("%i", &n);
      }
      //Создаем массив и запрашиваем ввод дуг
      a = new int*[n];
      for (int i = 0; i<n; i++) a[i] = new int [n];
      for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
          a[i][j] = 0;
      c = new int[n];
    
      //Запрашиваем количество вершин
      printf("vvedite koli4estvo dug: ");
      scanf("%i", &m);
      while (m<=0)
    {
        printf("Zna4enie dolJno Bit' > 0. vvedite pravilnoe zna4enie: ");
        scanf("%i", &m);
      }
    
      for (int i = 0; i<m; i++)
    {
        printf("\nu_%i_1 = ", i + 1);
        scanf("%i", &v1);
        printf("u_%i_2 = ", i + 1);
        scanf("%i", &v2);
        if ((v1<0) || (v1>=n)) v1 = 0;
        if ((v2<0) || (v2>=n)) v2 = 0;
        a[v1][v2] = 1;
        a[v2][v1] = 1;
      }
    }
    
    //Обходит из заданной вершины граф
    //Такой вызов для одной вершины занесет в c[] все
    //вершины из компоненты связности которой принадлежит вызывающая
    //вершина
    void ostav(int i)
    {
      for (int j = 0; j<n; j++)
        if (a[i][j] && (!contain(j)))
    {
          add(j);
          ostav(j);
        }
    }
    
    //Возвращает кол-во компонент связности графа
    //Не содержащего вершины которые были занесены в массив c[]
    //до обращения к функции
    int getComponentCount() 
    {
      int res = 0;
    
      for (int i = 0; i<n; i++)
        if (!contain(i))
    {
          add(i);
          res++;
          ostav(i);
        };
      return res;
    }
    
    #include <vector>
    
    vector<char> used;
    int timer;
    vector<int> tin, fup;
    
    void dfs (int v, int p = -1) 
    {
    	used[v] = true;
    	tin[v] = fup[v] = timer++;
    	for (size_t i=0; i<n; ++i) {
    		int to = a[v][i];
    		if (to == p) continue;
    		if (used[to])
    			fup[v] = min (fup[v], tin[to]);
    		else {
    			dfs (to, v);
    			fup[v] = min (fup[v], fup[to]);
    			if (fup[to] > tin[v])
    			{
    				printf("%d - %d - most", v, to);
    			}
    		}
    	}
    }
    
    void main()
    {
      int d;
      createGraph();
      clear();
    
    	//мосты
    	timer = 0;
    	used.assign (n, false);
    	tin.resize (n);
    	fup.resize (n);
    	dfs (0);
    
      //Вычисляем кол-во комп. связ. графа
      d = getComponentCount();
      printf("Points sochlinenia:");
      for (int i = 0; i<n; i++)
    	{
        //Убираем одну вершину и вычисляем кол-во к.с. для графа без нее
        clear();
        add(i);
        //Если кол-во к.с. увеличилось значит это точка сочленения
        if (getComponentCount() > d) printf("\n%i", i); 
      }
      getch();
    }
    
     
    


    Для связи [mail]
    • Помечено в качестве ответа Gomerchik 26 декабря 2010 г. 20:20
    • Помечено в качестве ответа Gomerchik 26 декабря 2010 г. 20:20
    26 декабря 2010 г. 16:46

Все ответы

  • Тот код, что вы выложили совершенно не читаем, да и не правилен, что за функция внутри main, где она заканчивается, где заканчивается main, есть if в котором совершенно ничего не выполняется и тп... Выложите пожалуйста код или проект в нормально виде, чтобы вам можно было помочь.
    Для связи [mail]
    25 декабря 2010 г. 22:52
  • Да вот изменил код полностью и как прежде необходимо добавить поиск мостов!!!

    в данном коде вводим колич точек и колич ребер, затем координаты u_1_1 и u_1_2 ну тоесть соединяем ребром 1, первую и вторую вершины и так далее

    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include <iostream>
    #include <cmath>
    #include <complex>
    #include <string.h>
    #include <locale.h>
    using namespace std;

    int **a; //Матрица смежности
    int *c; //Массив вершин которые уже были пройденны
    int n; //Количество узлов

    //Добавляет вершину к c[]
    void add(int v)
    {
        int i;
        for (i = 0; c[i] != -1; i++);
        c[i] = v;
    }

    //Возвращает true если вершина v содержиться в c[]
    int contain(int v)
    {
        for (int i = 0; i<n; i++)
            if (c[i] == v) return 1;
        return 0;
    }

    //Удаляет v из c[]
    void remove(int v)
    {
        int i;
        for (i = 0; i != v; i++);
        c[i] = -1;
    }

    //Очищает c[]
    void clear()
    {
        for (int i = 0; i<n; i++) c[i] = -1;
    }

    //Запрашивает ввод элементов
    //По введенным элементам заполняет матрицу смежности
    void createGraph()
    {
        int v1, v2;
        int m;

        //Запрашиваем количество вершин
        printf("Vvedite kol-vo vershin: ");
        scanf("%i", &n);
        while (n<=0)
    {
            printf("Zna4enie dolJno Bit' > 0. vvedite pravilnoe zna4enie: ");
            scanf("%i", &n);
        }
        //Создаем массив и запрашиваем ввод дуг
        a = new int*[n];
        for (int i = 0; i<n; i++) a[i] = new int [n];
        for (int i = 0; i<n; i++)
            for (int j = 0; j<n; j++)
                a[i][j] = 0;
        c = new int[n];

        //Запрашиваем количество вершин
        printf("vvedite koli4estvo dug: ");
        scanf("%i", &m);
        while (m<=0)
    {
            printf("Zna4enie dolJno Bit' > 0. vvedite pravilnoe zna4enie: ");
            scanf("%i", &m);
        }

        for (int i = 0; i<m; i++)
    {
            printf("\nu_%i_1 = ", i + 1);
            scanf("%i", &v1);
            printf("u_%i_2 = ", i + 1);
            scanf("%i", &v2);
            if ((v1<0) || (v1>=n)) v1 = 0;
            if ((v2<0) || (v2>=n)) v2 = 0;
            a[v1][v2] = 1;
            a[v2][v1] = 1;
        }
    }

    //Обходит из заданной вершины граф
    //Такой вызов для одной вершины занесет в c[] все
    //вершины из компоненты связности которой принадлежит вызывающая
    //вершина
    void ostav(int i)
    {
        for (int j = 0; j<n; j++)
            if (a[i][j] && (!contain(j)))
    {
                add(j);
                ostav(j);
            }
    }

    //Возвращает кол-во компонент связности графа
    //Не содержащего вершины которые были занесены в массив c[]
    //до обращения к функции
    int getComponentCount()
    {
        int res = 0;

        for (int i = 0; i<n; i++)
            if (!contain(i))
    {
                add(i);
                res++;
                ostav(i);
            };
        return res;
    }

    void main()
    {
        int d;
        createGraph();
        clear();
        //Вычисляем кол-во комп. связ. графа
        d = getComponentCount();
        printf("Points sochlinenia:");
        for (int i = 0; i<n; i++)
    {
            //Убираем одну вершину и вычисляем кол-во к.с. для графа без нее
            clear();
            add(i);
            //Если кол-во к.с. увеличилось значит это точка сочленения
            if (getComponentCount() > d) printf("\n%i", i);
        }
        getch();
    }

     

     

     

     

    26 декабря 2010 г. 15:04
  • Попробуйте так, незнаю на сколько верно, основывался на примере http://e-maxx.ru/algo/bridge_searching, он как то ближе к вашей задаче, чем то, что вы нашли http://social.msdn.microsoft.com/Forums/ru-RU/fordesktopru/thread/cc0361d5-d5dc-4269-930a-a2f6b8162f6b/ , но посмотрите в учебнике из которого вы брали, что означает d[MAXN], low[x], counter; и как они задаются. (т.е. в 1ом примере тоже не ясно как задается граф g)

     

    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include <iostream>
    #include <cmath>
    #include <complex>
    #include <string.h>
    #include <locale.h>
    using namespace std;
    
    int **a; //Матрица смежности
    int *c; //Массив вершин которые уже были пройденны
    int n; //Количество узлов
    
    //Добавляет вершину к c[]
    void add(int v) 
    {
      int i;
      for (i = 0; c[i] != -1; i++);
      c[i] = v;
    }
    
    //Возвращает true если вершина v содержиться в c[]
    int contain(int v)
    {
      for (int i = 0; i<n; i++)
        if (c[i] == v) return 1;
      return 0;
    }
    
    //Удаляет v из c[]
    void remove(int v) 
    {
      int i;
      for (i = 0; i != v; i++);
      c[i] = -1;
    }
    
    //Очищает c[]
    void clear()
    {
      for (int i = 0; i<n; i++) c[i] = -1;
    }
    
    //Запрашивает ввод элементов
    //По введенным элементам заполняет матрицу смежности
    void createGraph()
    {
      int v1, v2;
      int m;
    
      //Запрашиваем количество вершин
      printf("Vvedite kol-vo vershin: ");
      scanf("%i", &n);
      while (n<=0)
    {
        printf("Zna4enie dolJno Bit' > 0. vvedite pravilnoe zna4enie: ");
        scanf("%i", &n);
      }
      //Создаем массив и запрашиваем ввод дуг
      a = new int*[n];
      for (int i = 0; i<n; i++) a[i] = new int [n];
      for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
          a[i][j] = 0;
      c = new int[n];
    
      //Запрашиваем количество вершин
      printf("vvedite koli4estvo dug: ");
      scanf("%i", &m);
      while (m<=0)
    {
        printf("Zna4enie dolJno Bit' > 0. vvedite pravilnoe zna4enie: ");
        scanf("%i", &m);
      }
    
      for (int i = 0; i<m; i++)
    {
        printf("\nu_%i_1 = ", i + 1);
        scanf("%i", &v1);
        printf("u_%i_2 = ", i + 1);
        scanf("%i", &v2);
        if ((v1<0) || (v1>=n)) v1 = 0;
        if ((v2<0) || (v2>=n)) v2 = 0;
        a[v1][v2] = 1;
        a[v2][v1] = 1;
      }
    }
    
    //Обходит из заданной вершины граф
    //Такой вызов для одной вершины занесет в c[] все
    //вершины из компоненты связности которой принадлежит вызывающая
    //вершина
    void ostav(int i)
    {
      for (int j = 0; j<n; j++)
        if (a[i][j] && (!contain(j)))
    {
          add(j);
          ostav(j);
        }
    }
    
    //Возвращает кол-во компонент связности графа
    //Не содержащего вершины которые были занесены в массив c[]
    //до обращения к функции
    int getComponentCount() 
    {
      int res = 0;
    
      for (int i = 0; i<n; i++)
        if (!contain(i))
    {
          add(i);
          res++;
          ostav(i);
        };
      return res;
    }
    
    #include <vector>
    
    vector<char> used;
    int timer;
    vector<int> tin, fup;
    
    void dfs (int v, int p = -1) 
    {
    	used[v] = true;
    	tin[v] = fup[v] = timer++;
    	for (size_t i=0; i<n; ++i) {
    		int to = a[v][i];
    		if (to == p) continue;
    		if (used[to])
    			fup[v] = min (fup[v], tin[to]);
    		else {
    			dfs (to, v);
    			fup[v] = min (fup[v], fup[to]);
    			if (fup[to] > tin[v])
    			{
    				printf("%d - %d - most", v, to);
    			}
    		}
    	}
    }
    
    void main()
    {
      int d;
      createGraph();
      clear();
    
    	//мосты
    	timer = 0;
    	used.assign (n, false);
    	tin.resize (n);
    	fup.resize (n);
    	dfs (0);
    
      //Вычисляем кол-во комп. связ. графа
      d = getComponentCount();
      printf("Points sochlinenia:");
      for (int i = 0; i<n; i++)
    	{
        //Убираем одну вершину и вычисляем кол-во к.с. для графа без нее
        clear();
        add(i);
        //Если кол-во к.с. увеличилось значит это точка сочленения
        if (getComponentCount() > d) printf("\n%i", i); 
      }
      getch();
    }
    
     
    


    Для связи [mail]
    • Помечено в качестве ответа Gomerchik 26 декабря 2010 г. 20:20
    • Помечено в качестве ответа Gomerchik 26 декабря 2010 г. 20:20
    26 декабря 2010 г. 16:46
  • спосибо прсмотрел задачу с вашими дополнениями!
    26 декабря 2010 г. 17:22
  • Идентификатор min не определен. Помогите, что с этим делать? уже весь инет облазил, ничего более полезного, чем Ваша программа не нашел. 
    Заранее спасибо
    15 декабря 2017 г. 5:02