Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
Nikolay_it
5 / 5 / 0
Регистрация: 08.05.2012
Сообщений: 15
10.05.2012, 19:13     Теорие графов. Композиция двух неор. графов. #1
Здравствуйте. Прошу помощи уже здесь :| (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;
       }
}
Если же вы не желаете помогать просто так, то возможно сможем договориться за отдельную плату...
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2012, 19:13     Теорие графов. Композиция двух неор. графов.
Посмотрите здесь:

Реализация графов C++
C++ алгоритм Флойда (теория графов).
Реализация алгоритмов теории графов на С/С++ C++
генерирование особых графов C++
Программирование графов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
10.05.2012, 20:28     Теорие графов. Композиция двух неор. графов. #2
с составлением алгоритма "Композиции двух неориентированных графов".
А ты в курсе что должен делать этот алгоритм ?
Nikolay_it
5 / 5 / 0
Регистрация: 08.05.2012
Сообщений: 15
10.05.2012, 20:32  [ТС]     Теорие графов. Композиция двух неор. графов. #3
Графический пример:
Миниатюры
Теорие графов. Композиция двух неор. графов.  
Изображения
  
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
10.05.2012, 20:32     Теорие графов. Композиция двух неор. графов. #4
Файл выглядит следующим образом
А с чего это файл выглядит таким образом ?
Сдается мне что для приведенного графа файл должен быть такой
Код
3
1 2
3 2
Nikolay_it
5 / 5 / 0
Регистрация: 08.05.2012
Сообщений: 15
10.05.2012, 20:43  [ТС]     Теорие графов. Композиция двух неор. графов. #5
Цитата Сообщение от odip Посмотреть сообщение
А с чего это файл выглядит таким образом ?
Сдается мне что для приведенного графа файл должен быть такой
Код
3
1 2
3 2
Возможно я ошибаюсь, но мне объяснили именно таким образом. (Список смежности)
Т.е. входит:
Код
3
1 2
2 1 3
1 2
Выходит:
http://www.cyberforum.ru/attachment....1&d=1336668210
Изображения
 
Nikolay_it
5 / 5 / 0
Регистрация: 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 и
Yandex
Объявления
10.05.2012, 22:03     Теорие графов. Композиция двух неор. графов.
Ответ Создать тему
Опции темы

Текущее время: 23:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru