Это пятый день моего участия в августовском испытании обновлений. Узнайте подробности мероприятия: Испытание августовского обновления
Разработка и анализ алгоритмов Тема 1:
Список смежности ориентированного графа G порождает обратный список смежности графа G.
1. Введите количество вершин и ребер ориентированного графа, а также начало и хвост каждого ребра.
2. Функция проектирования использует представление списка смежности для создания и вывода ориентированного графа.
3. Функция проектирования использует список смежности для создания обратного списка смежности ориентированного графа.
4. Вызовите функцию для вывода ориентированного графа, представленного списком обратной смежности.
Алгоритм формирования обратного списка смежности графа G из списка смежности ориентированного графа G выглядит следующим образом: Основной код и комментарии:
//将有向图的出度邻接表改为按入度建立的反向邻接表
void InvertAdjGraph(AdjGraph gout)
{
//反向邻接表表示的有向图gin
AdjGraph gin;
gin.n = gout.n;
gin.e = gout.e;
//设有向图有 n 个顶点，建逆反向邻接表的顶点向量
for (int i = 0; i < gin.n; i++)
{
gin.VexList[i].data = gout.VexList[i].data;
gin.VexList[i].adj = NULL;
}
//邻接表转为反向邻接表
for (int i = 0; i < gin.n; i++)
//取指向邻接点的指针
{
EdgeNode *p = gout.VexList[i].adj;
while (p != NULL)
{
int j = p->dest;
//申请结点空间
EdgeNode *s = (EdgeNode *)malloc(sizeof(EdgeNode));
s->dest = i;
s->link = gin.VexList[j].adj;
gin.VexList[j].adj = s;
//下一个邻接点
p = p->link;
}
}
cout << "使用反向邻接表表示有向图G" << endl;
ShowGraph(gin);
}
Скриншоты и анализ результатов тестирования:
Этот алгоритм в основном использует список смежности для реализации построения графа.Во-первых, нам нужно получить количество вершин и соответствующее количество ребер в графе, а также начало и хвост каждого ребра. После этого ориентированный граф G, представленный списком смежности, устанавливается путем проектирования функции.Самое главное в списке смежности - связать вершины всех ребер, исходящих из одной вершины, а затем голову и хвост каждого край в списке смежности должен быть подключен.Обратно и повторно свяжите в ориентированный граф, представленный новым списком смежности.Это список обратной смежности.Наконец, вам нужно только вызвать функцию, чтобы распечатать ориентированный граф, представленный список обратной смежности.