Реализация алгортмов на графах на основе списков
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#define MAXV 10000
#define MAXE 10000000
#define INF 1000000000
using namespace std;
typedef struct
{
int next, prev, to, w;
} node; //структура для ребра графа
typedef struct
{
int next, prev, val;
} bfslist; //структура для обхода в ширину
node graph[MAXV+MAXE*2+1]; // описание ребер
int freenum, bfsfreenum; // свободная ячейка в описаниие графа и в очередях
int length[MAXV+1];
int length2[MAXV+1];
int length3[MAXV+1];
int length4[MAXV+1];
void init(node *graph, int v) // инициализация графа
{
int i;
for (i=0; i<=v; i++) {
graph[i].w = graph[i].to = -1;
graph[i].next = graph[i].prev = i;
} // заполнили первые V "ребер" - начала списков вершин
for (i=v+1; i<=MAXV+MAXE; i++)
graph[i].next = i+1; // все остальное свободно
freenum = v+1;
}
void addedge(node *graph, int a, int b, int w) // добавление ребра
{
int p[2], nfreenum, i;
p[0] = a<b?a:b;
p[1] = a>b?a:b;
for (i=0; i<=1; i++) { // сначала добавляем ребро из меньшего в большее
nfreenum = graph[freenum].next;
graph[freenum].w = w;
graph[freenum].to = p[(i+1)%2];
graph[freenum].next = graph[p[i]].next;
graph[freenum].prev = p[i];
graph[p[i]].next = freenum;
graph[graph[p[i]].next].prev = freenum; // добавление в начало двусвязного списка
freenum = nfreenum;
}
}
void dellistitem(node *graph, int pos) // удаление элемента из двусвязого списка
{
graph[graph[pos].prev].next = graph[pos].next;
graph[graph[pos].next].prev = graph[pos].prev;
graph[pos].next = freenum;
freenum = pos;
}
void deledge(node *graph, int from, int position) // удаление ребра
{
if (from < graph[position].to) { // прямое и обратное
dellistitem(graph, position+1);
dellistitem(graph, position);
} else { //обратное и прямое
dellistitem(graph, position-1);
dellistitem(graph, position);
}
}
void dijkstra(node graph[], int length[], int start, int v) // обычный алгоритм Дейкстры
{
int i, now = start, flag;
bool *used = (bool*)malloc(sizeof(bool)*(v+1)); // посчитано ли полностью
for (i=0; i<=v; i++) { // инициализация. никуда пройти не можем
length[i] = INF;
used[i] = false;
}
length[start] = 0; // начинаем отсюда
do {
flag = false; // было ли обновление
now = 0; // куди идем
for (i=1; i <= v; i++)
if (!used[i] && length[i] < length[now]) { // выбираем ближайшую не использованную
now = i;
flag = true;
}
used[now] = true; // используем
i = graph[now].next; // начинаем бегать по соседям свежедобавленной
while (graph[i].to != -1) { // пока не добежим до начала списка
if (!used[graph[i].to] && length[now] + graph[i].w < length[graph[i].to])
length[graph[i].to] = length[now] + graph[i].w; // пересчитываем
i = graph[i].next; // и к следующей
}
} while (flag && length[now] != INF); // пока что-то добавилось и не обошли всю компоненту связности
}
int minheap(int *heap, int *heapno, int *backindex, int *inheap) // минимум из кучи (возвращает индекс)
{
int minp, pos=0, y, res;
(*inheap)--; // размер кучи уменьшаем
res = heapno[0]; // ответ сохраняем
backindex[res] = -1; // теперь элемента с таким индексом в куче нет
heap[0] = heap[*inheap]; // последний в начало
heapno[0] = heapno[*inheap]; // и тоже самое с его индексом
backindex[heapno[0]] = 0; // пересчитываем позицию в куче для данного индекса
while (pos*2+1 < *inheap) {
y=pos*2+1;
minp=heap[y]<heap[y+1]?y:y+1; // выбираем меньшего сына
if (heap[pos]>heap[minp]) { // и меняем, если надо
backindex[heapno[minp]] = pos;
backindex[heapno[pos]] = minp;
y=heap[pos]; heap[pos]=heap[minp]; heap[minp]=y;
y=heapno[pos]; heapno[pos]=heapno[minp]; heapno[minp]=y;
pos=minp;
} else break;
}
heap[*inheap+1] = INF; // на всякий случай положем за кучей бесконечноть
return res;
}
void addheap(int *heap, int *heapno, int *backindex, int *inheap, int len, int num) // добавление в кучу
{
int minp, y, npos;
int pos=backindex[num];
if (pos == -1) { // такого элемента в куче не было - добавляем
backindex[num] = *inheap; // у него теперь есть индекс
pos = *inheap;
(*inheap)++;
heap[*inheap] = INF; // а за кучей опять положим бесконечность
}
heap[pos] = len; // записываем новые данные
heapno[pos] = num;
while (pos*2+1 < *inheap) { // если элемент стал слишком большой - толкаем вниз
y=pos*2+1;
minp=heap[y]<heap[y+1]?y:y+1;
if (heap[pos]>heap[minp]) {
backindex[heapno[minp]] = pos;
backindex[heapno[pos]] = minp;
y=heap[pos]; heap[pos]=heap[minp]; heap[minp]=y;
y=heapno[pos]; heapno[pos]=heapno[minp]; heapno[minp]=y;
pos=minp;
} else break;
}
npos=(pos-1)/2;
while (pos != 0 && heap[pos] < heap[npos]) { // если стал слишком маленький, то наверх
backindex[heapno[npos]] = pos;
backindex[heapno[pos]] = npos;
y=heap[pos]; heap[pos]=heap[npos]; heap[npos] = y;
y=heapno[pos]; heapno[pos]=heapno[npos]; heapno[npos] = y;
pos=npos;
npos=(pos-1)/2;
}
}
void heap_dijkstra(node graph[], int length[], int start, int v) // Дейкстра с кучей
{
int i, now = start, inheap=0;
bool *used = (bool*)malloc(sizeof(bool)*(v+1));
int *heap = (int*)malloc(sizeof(int)*(v+1));
int *heapno = (int*)malloc(sizeof(int)*(v+1));
int *backindex = (int*)malloc(sizeof(int)*(v+1));
for (i=0; i<=v; i++) {
length[i] = INF;
used[i] = false;
backindex[i] = -1;
}
length[start] = 0;
addheap(heap, heapno, backindex, &inheap, 0, start); // добавляем начальный элемент
do {
if (inheap != 0) { // пока куча не пуста
now = minheap(heap, heapno, backindex, &inheap); // выбираем и удаляем номер минимальной вершины
used[now] = true; // помечаем, как испоьзованный
i = graph[now].next;
while (graph[i].to != -1) { // бегаем по смежным со свежедобавленной
if (!used[graph[i].to] && length[now] + graph[i].w < length[graph[i].to]) {
length[graph[i].to] = length[now] + graph[i].w; // пересчитываем и обновляем кучу
addheap(heap, heapno, backindex, &inheap, length[graph[i].to], graph[i].to);
}
i = graph[i].next;
}
}
} while (inheap != 0);
}
void addto(bfslist *list, int *instep, int *position, int nstep, int start) // добавление в очередь
{
int nbfsfreenum=list[bfsfreenum].next;
list[bfsfreenum].val = start;
list[bfsfreenum].prev = list[nstep].prev;
list[bfsfreenum].next = nstep; // добавляем в конец двусвязного списка с номером nstep
list[list[nstep].prev].next = bfsfreenum;
list[nstep].prev = bfsfreenum;
position[start] = bfsfreenum; // обратный индекс
instep[start] = nstep;
bfsfreenum = nbfsfreenum;
}
void delfrom(bfslist *list, int *instep, int *position, int start) // удаление из очереди
{
if (position[start] != -1) { // если он там вообще есть
int wh = position[start]; // смотрим где конкретно он есть
instep[start] = -1;
position[start] = -1; // теперь его там нет (убрали обратный индекс)
list[list[wh].next].prev = list[wh].prev; // выкидываем из списка
list[list[wh].prev].next = list[wh].next;
list[wh].next = bfsfreenum;
bfsfreenum = wh; // и добавляем новый свободный элемент
}
}
void modbfs(node *graph, int *length, int start, int maxlen) // модифицированный BFS
{
int i, work, edges;
int prev, now;
bfslist *list = (bfslist*)malloc(sizeof(bfslist)*(maxlen+1+MAXV)); // это maxlen очередй
int *instep = (int*)malloc(sizeof(int)*(MAXV+1)); // в какой очереди лежит наша вершина
int *position = (int*)malloc(sizeof(int)*(MAXV+1)); // обратный индекс
for (i=0; i<=maxlen; i++) { // инициализируем пустые очереди
list[i].val = -1;
list[i].next = list[i].prev = i;
}
for (i=0; i<=MAXV; i++) // ни на каком шаге никого нет
instep[i] = -1;
for (i=maxlen+1; i<maxlen+1+MAXV; i++) // свободные ячейк
list[i].next = i+1;
bfsfreenum = maxlen + 1;
for (i=0; i<=MAXV; i++) { // расстояния бесконечные, позиции в очередях неопределенные
length[i] = INF;
position[i] = -1;
}
length[start] = 0; // начальная вершина
addto(list, instep, position, 0, start); // попадает в очередь 0
prev = maxlen; // где у нас последний раз что-то менялось
now = 0; // а это где мы сейчас
while (prev%(maxlen+1) != now%(maxlen+1)) {// пока были изменения за цикл по всем очередям
work = list[now%(maxlen+1)].next; // начало очереди с номером now
while (list[work].val != -1) { // идем по всем вершинам данной очереди
edges = graph[list[work].val].next; // для каждой вершины смотрим список ребер
while (graph[edges].to != -1) { // идем по всем ребрам
if (length[list[work].val] + graph[edges].w < length[graph[edges].to]) { // если надо пересчитать
length[graph[edges].to] = length[list[work].val] + graph[edges].w; // пересчитываем длину
delfrom(list, instep, position, graph[edges].to); // удаляем эту вершину из старой ее позиции
addto(list, instep, position, length[graph[edges].to] % (maxlen+1), graph[edges].to); // и в новую
}
edges = graph[edges].next; // к следующему ребру
}
work = list[work].next; // следующая вершина из очереди
delfrom(list, instep, position, list[list[work].prev].val); // уже обработанную из очереди вынимаем
prev = now; // на этом шаге было обновления
}
now++; // всю очередь посмотрели, идем к следующей
}
}
void simplemodbfs(node *graph, int *length, int start, int maxlen)
{
int i, prev, now, work, edges;
bool *used = (bool*)malloc(sizeof(bool)*(MAXV+1)); // в какой очереди лежит наша вершина
vector <queue <int> > qs(maxlen+1);
for (i=0; i<=MAXV; i++) {
used[i] = false;
length[i] = INF;
}
length[start] = 0; // начальная вершина
qs[0].push(start);
prev = maxlen; // где у нас последний раз что-то менялось
now = 0; // а это где мы сейчас
while (prev%(maxlen+1) != now%(maxlen+1)) {// пока были изменения за цикл по всем очередям
while (qs[now%(maxlen+1)].size() > 0) {
work = qs[now%(maxlen+1)].front();
qs[now%(maxlen+1)].pop();
if (!used[work]) {
edges = graph[work].next; // для каждой вершины смотрим список ребер
while (graph[edges].to != -1) { // идем по всем ребрам
if (length[work] + graph[edges].w < length[graph[edges].to]) { // если надо пересчитать
length[graph[edges].to] = length[work] + graph[edges].w; // пересчитываем длину
qs[length[graph[edges].to] % (maxlen+1)].push(graph[edges].to); // и в новую
}
edges = graph[edges].next; // к следующему ребру
}
prev = now;
}
used[work] = true;
}
now++;
}
}