6 / 6 / 3
Регистрация: 08.05.2012
Сообщений: 15
1

Теорие графов. Композиция двух неор. графов.

10.05.2012, 19:13. Показов 4366. Ответов 5
Метки нет (Все метки)

Здравствуйте. Прошу помощи уже здесь :| (old topic)...
Прошу помочь с составлением алгоритма "Композиции двух неориентированных графов".
Ниже код программы, для работы с графом.
Используется структура данных "список смежности".
Считывание графа происходит из файла.
Файл выглядит следующим образом:
"
3//размер графа
1 2
2 1 3
3 2
"
Графическое изображение графа прикреплено к сообщению.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//---------------------------------------------------------------------------
 
#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#pragma hdrstop
 
//---------------------------------------------------------------------------
 
#pragma argsused
 
using namespace std;
 
struct adj_list {
      int size;
      int *list;
   } ;
 
struct graph {
      int size;
      adj_list *lists;
   } ;
 
void sample(char*, int);                                                        // ?
graph *loadGraph(char*);                                                        // +
void deleteGraph(graph*, int);                                                  // +
void printGraph(graph*, int);                                                   // +
 
int main(int argc, char* argv[])
{
    sample("graph1.txt", 1);
    sample("graph2.txt", 2);
    getch();
    return 0;
}
//---------------------------------------------------------------------------
 
void sample(char f_name[], int f_no)
{
   graph *g = loadGraph(f_name);
   if(g!=NULL)
   {
      cout << "Case " << f_no << ":\nGraph:\n" << endl;
      printGraph(g, g->size);
 
 
 
 
      deleteGraph(g, g->size);
   }
   else cout << "Case " << f_no << " error." << endl;
   return ;
}
 
graph *loadGraph(char f_name[])
{
  FILE *g_file;
  g_file = fopen(f_name, "rt");
     if(g_file == NULL) {
     cout << "Error" << endl;
     return NULL;
     }
     else
     {
        graph *s_graph = new graph;
        fscanf(g_file, "%d", &s_graph->size);
        s_graph->lists = new adj_list[s_graph->size];
        int i = 0, j;
        while(i<s_graph->size)
        {
          fscanf(g_file, "%d", &s_graph->lists[i].size);
          s_graph->lists[i].list = new int[s_graph->lists[i].size];
             for(j=0; j<s_graph->lists[i].size; j++)
                fscanf(g_file, "%d", &s_graph->lists[i].list[j]);
          i++;
        }
       return s_graph;
     }
}
 
void deleteGraph(graph *g, int size)
{
      int i;
      for(i=0; i<size; i++)
      delete []g->lists[i].list;
      delete []g->lists;
      delete g;
      return ;
}
 
void printGraph(graph *g, int co)
{
    if(g!=NULL)
       {
           //cout << "--------------------------------\nGraph:" << endl;
           int i, k;
           for(i=0; i<co; i++)
              {
                  cout << i+1 << ":";
                  for(k=0; k<g->lists[i].size; k++)
                     cout << " " << g->lists[i].list[k];
                  cout << endl;
              }
           cout << "--------------------------------" << endl;
       }
}
Если же вы не желаете помогать просто так, то возможно сможем договориться за отдельную плату...
Изображения
 
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.05.2012, 19:13
Ответы с готовыми решениями:

Для заданных двух графов построить их соединение
добрый день! помогите решить задачу: Соединением графов G1 и G2 называется граф G=(V,E), для...

Реализация графов
Помогите пожалуйста!!!!! как написать программу на Си ++ на эту тему :реализация различных типов...

Теория графов
Есть задание. найти максимальное и среднее расстояние между центральными вершинами...

Представление графов С++
Считывания графу из входного файла. На вход подается текстовый файл следующего вида: n m v1 u1...

5
Эксперт С++
7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
10.05.2012, 20:28 2
с составлением алгоритма "Композиции двух неориентированных графов".
А ты в курсе что должен делать этот алгоритм ?
0
6 / 6 / 3
Регистрация: 08.05.2012
Сообщений: 15
10.05.2012, 20:32  [ТС] 3
Графический пример:
Миниатюры
Теорие графов. Композиция двух неор. графов.  
Изображения
  
0
Эксперт С++
7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
10.05.2012, 20:32 4
Файл выглядит следующим образом
А с чего это файл выглядит таким образом ?
Сдается мне что для приведенного графа файл должен быть такой
Код
3
1 2
3 2
0
6 / 6 / 3
Регистрация: 08.05.2012
Сообщений: 15
10.05.2012, 20:43  [ТС] 5
Цитата Сообщение от odip Посмотреть сообщение
А с чего это файл выглядит таким образом ?
Сдается мне что для приведенного графа файл должен быть такой
Код
3
1 2
3 2
Возможно я ошибаюсь, но мне объяснили именно таким образом. (Список смежности)
Т.е. входит:
Код
3
1 2
2 1 3
1 2
Выходит:
https://www.cyberforum.ru/atta... 1336668210
Изображения
 
0
6 / 6 / 3
Регистрация: 08.05.2012
Сообщений: 15
10.05.2012, 22:03  [ТС] 6
Лексикографическое произведение графов G1=(X1, U1) и G2=(X2, U2) - граф G=G1[G2], состоящий из множества вершин Х=X1хX2, и две вершины s=(x1, x2) и t=(y1, y2) смежны в G тогда и только тогда, когда x1 смежна с y1 или x1=y1 и x2 смежна с y2.

s, t - вершины результирующего графа
x1, y1 - вершины из первого графа
x2, y2 - вершины из второго графа


Если это так, то что будет значить это:
или x1=y1 и
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.05.2012, 22:03
Помогаю со студенческими работами здесь

Представление графов С++
#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int n; int m; vector&lt;int&gt;...

Программирование графов
Неподскажите сайт где очень понятно объясняют графы, как запрограммировать, и т.д. Просто гуглил...

Визуализация графов
В общем есть такой пакет http://ru.wikipedia.org/wiki/Graphviz С помощью него можно вводить граф...

Генерирование особых графов
кто может привести какой-либо тест(пример в текстовом файле) или алгоритм генерирования тестов для ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru