Разработка и реализация на языке высокого уровня алгоритма выделения сильносвязных компонент ориентированного графа
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
программирования Eclipse универсальна и очень удобна. Простой, понятный интерфейс и хорошее быстродействие помогают разрабатывать программы разной сложности. Универсализм программы дает возможность разрабатывать программные приложения не только на языке С и C++
Список использованной литературы
1.) Семакин И.Г. Основы программирования [Текст] - М.: КомпьютерПресс, 2004. - 170 с.
.) Макарова С.В. Информатика М [Текст] / Под ред. Б.В. Лукашова. - М.:Информатика, 2009. - 176 с.
.) Панасенко, Л.Г. Программирование на Си[Текст] // Под ред. А.В. Иванова.- М.:Информатика, 2008. - 45 с.
.) Партыка, Т.Л. Основы алгоритмирования Учеб.пособие [Текст] / Партыка, Т.Л. - М.: Форум, 2005. - 142 с.
.) Програмирование на СИ ИНФРА-М [Текст] / Под ред. Власенко, П.Г.. - М.:Информатика, 2009. - 109 с..
Приложение
Листинг программы
#include N; // Количество вершин в графе
#define MAX_NODES 100 // Максимальное количество вершин
#define MAX_EDGES 10 // Максимальное количество ребер, выходящих из одной вершиныedges[MAX_NODES][MAX_EDGES]; // Граф, в котором ищем сильно связные компоненты
int edges_c[MAX_NODES];edgesT[MAX_NODES][MAX_EDGES]; // Транспонированый графedgesT_c[MAX_NODES];
int state[MAX_NODES]; // Используется в поиске для того, чтобы отмечать посещенные вершиныf[MAX_NODES],last_f=0; // Список предварительной расстановки вершинc=1; // Номер компоненты (увеличиваем его, когда находим новую)
void dfs(int node){[node]=1;
for(int i=0; i<edges_c[node]; i++) // Самый обыкновенный поиск в глубину.(state[edges[node][i]]==0) // Проходим по всем непосещенным вершинам,(edges[node][i]); // заходя в каждую[last_f++]=node; // Предварительная расстановка вершин в списке.
}dfsT(int node){[node]=1;
for(int i=0; i<edgesT_c[node]; i++) // Самый обыкновенный поиск в глубину в транспонированном графе.(state[edgesT[node][i]]==0) // Проходим по всем непосещенным вершинам,
dfsT(edgesT[node][i]); // заходя в каждую("%d %d\n",node,c);
}scc(){ // Strongly Connected Components - функция выделения сильно связных компонент графаi;(i=0; i<N; i++) state[i]=0;(i=0; i<N; i++) // 1-ый поиск в глубину(state[i]++==0) // ...
dfs(i); // Предварительная расстановка вершин.
for(i=0; i=0; last_f--) // 2-ой поиск в глубину(state[f[last_f]]==0){ // ...
dfsT(f[last_f]); // Окончательное выделение сильно связных компонент++; // увеличиваем номер следующей компоненты
}
}main(){i;("%d",&N);(i=0; i<N; i++) edges_c[i]=edgesT_c[i]=0;(i=0; i<N; i++){j;("%d",&edges_c[i]);(j=0; j<edges_c[i]; j++){to;("%d",&to);
edges[i][j]=to; // Построение исходного графа[to][edgesT_c[to]++]=i; // Построение транспонированного графа
}
}(); // Найти и вывести сильно связные компоненты0;
}
Топологическая сортировка
#include
#include
#include
#define M 15
#define N 1000
#define NE 100
#define P 10007
#define MAX_LINE_LENGTH 100struct
{to;w;
} edge;a[N][NE];ne[N];n = 0;v[N];c;hash_table[P];term[N][M];count;(char *s)
{long i, h1 = 0, h2 = 0;(i = 0; s[i]; i++)
{*= 13;+= s[i] % 13;*= 17;+= s[i] % 17;
}%= P;%= P - 1;++;(hash_table[h1] != -1)
{(strcmp (term[hash_table[h1]], s) == 0) return hash_table[h1];+= h2;%= P;
}_table[h1] = n;(term[n], s);n++;
}(int root)
{i;[root] = c;(i = 0; i < ne[root]; i++)(v[a[root][i].to] == 0)(a[root][i].to);("%s\n", term[root]);
}()
{i, j, id1, id2, m;w;term1[M];term2[M];in[MAX_LINE_LENGTH];(i = 0; i < P; i++) hash_table[i] = -1;(i = 0; i < N; i++) ne[i] = 0;(fgets (in, MAX_LINE_LENGTH, stdin) != NULL)
{(sscanf (in, "%s%s", term1, term2) == 2)
{= getid (term1);= getid (term2);[id2][ne[id2]].to = id1;[id2][ne[id2]].w = w;[id2]++;
}
}= 0;(i = 0; i < n; i++) v[i] = 0;(i = 0; i < n; i++) if (v[i] == 0)
{++;(i);
}0;
}