#c #matrix #graph-theory
Вопрос:
У меня есть следующий график, представленный матрицей смежности MyCustomVectorlt;MyCustomVectorlt;intgt;gt; graph :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 1 1 INF INF INF INF INF INF INF INF INF INF INF INF 2 1 0 1 1 1 INF INF INF INF INF INF INF INF INF INF 3 1 1 0 INF INF 1 INF INF INF INF INF INF INF INF INF 4 INF 1 INF 0 1 INF INF INF 1 INF INF INF INF INF INF 5 INF 1 INF 1 0 1 INF INF INF 1 1 INF INF INF INF 6 INF INF 1 INF 1 0 1 INF 1 1 INF 1 INF INF INF 7 INF INF INF INF INF 1 0 1 INF INF INF INF 1 1 1 8 INF INF INF INF INF INF 1 0 INF INF INF INF INF INF 1 9 INF INF INF 1 INF 1 INF INF 0 INF INF INF INF INF INF 10 INF INF INF INF 1 1 INF INF INF 0 INF INF INF INF INF 11 INF INF INF INF 1 INF INF INF INF INF 0 1 INF INF INF 12 INF INF INF INF INF 1 INF INF INF INF 1 0 INF INF INF 13 INF INF INF INF INF INF 1 INF INF INF INF INF 0 1 INF 14 INF INF INF INF INF INF 1 INF INF INF INF INF 1 0 1 15 INF INF INF INF INF INF 1 1 INF INF INF INF INF 1 0 Крайний левый и самый верхний столбец и строка просто представляют # узел. Я думал, что это легче увидеть. Все ребра неориентированы и имеют вес один. INF указывает, что узлы A и B не имеют общего сингулярного ребра.
Я могу вычислить все вершины нечетной степени, которые находятся { 3 4 5 7 14 15 } и содержатся в векторе, который у меня есть MyCustomVectorlt;intgt; oddVertices . Что я хочу сделать, так это построить подграф этого графика только с этими вершинами и их ребрами, так что что-то вроде этого.
0 3 4 5 7 14 15 3 0 INF INF INF INF INF 4 INF 0 1 INF INF INF 5 INF 1 0 INF INF INF 7 INF INF INF 0 1 1 14 INF INF INF 1 0 1 15 INF INF INF 1 1 0 Чтобы я мог запустить алгоритм Флойда Уоршалла на этом графике и получить
0 3 4 5 7 14 15 3 0 2 2 2 3 3 4 2 0 1 3 4 4 5 2 1 0 2 1 1 7 2 3 2 0 1 1 14 3 4 3 1 0 1 15 3 4 3 1 1 0 У меня возникли проблемы с управлением матрицей смежности и захватом столбцов, которые мне нужны. По сути, то, что я хочу сделать, это
- Выполните итерацию по графику
- Обратите внимание, что узел, на котором мы сейчас находимся, содержится в
oddVertices - Добавьте другие узлы, которые содержатся в
oddVertices.
Я не могу использовать какую-либо другую структуру данных , кроме MyCustomVector , и она имеет только базовые функции , такие как [] , size() , pop_back() и push_back() .
Комментарии:
1. каково число узлов и ребер в графике?
2. @arbitrary_A мой график просто имеет дело с узлами, помеченными из {1,…, n}. в этом случае n = 15. «1» в определенном [i][j] указывает на общее ребро между узлами i и j или в противном случае.
Ответ №1:
Просто извлеките строки и столбцы, соответствующие подмножеству индексов:
using std::vector; /* ** input: ** adjacency list adj ** subset of node indices v ** output: ** adj list of induced subgraph subadj */ vectorlt;vectorlt;intgt;gt; get_subgraph(vectorlt;vectorlt;intgt;gt; const amp;adj, vectorlt;intgt; const amp;v) { vectorlt;vectorlt;intgt;gt; subadj(v.length(), vectorlt;intgt;(v.length())); for (unsigned int i = 0; i lt; v.size(); i) for (unsigned int j = 0; j lt; v.size(); j) { subadj[i][j] = adj[v[i]][v[j]]; } return subadj; }