#c #matrix
#c #матрица
Вопрос:
Привет, везде есть объяснение по горячим чертежам, как создать график из adj. matrix. Однако для этого мне нужен простой псевдокод или алгоритм…. Я знаю, как вывести его из adj. matrix и не знаю, почему никто нигде не объясняет, как на самом деле поместить это в код. Я имею в виду не фактический код, а хотя бы алгоритм… Многие говорят .. 1 — это если есть ребро, я знаю, что .. Я создал adj. matrix и не знаю, как перенести его в график. У моих вершин нет имен, они просто индексы матрицы. например, 1-9 — это «имена моей матрицы»
1 2 3 4 5 6 7 8 9
1 0 1 0 0 1 0 0 0 0
2 1 0 1 0 0 0 0 0 0
3 0 1 0 1 0 0 0 0 0
4 0 0 1 0 0 1 0 0 0
5 1 0 0 0 0 0 1 0 0
6 0 0 0 1 0 0 0 0 1
7 0 0 0 0 1 0 0 1 0
8 0 0 0 0 0 0 1 0 0
9 0 0 0 0 0 1 0 0 0
изначально это был лабиринт… нужно пометить строку 1 col4 как начало, а строку 7 col8 как конец…
Никто никогда не говорил мне, как реализовать график из матрицы (без пера): Pp
Спасибо
Комментарии:
1. Матрица смежности — это способ представления графика. Вы имеете в виду, что хотите преобразовать в другое представление? И если да, то как бы вы хотели представить граф?
Ответ №1:
Природа симметрии
Матрица смежности — это представление графика. Для неориентированного графа его матрица симметрична. Например, если есть ребро от vertex i до vertex j , также должно быть ребро от vertex j до vertex i . На самом деле это одно и то же ребро.
*
*
* A'
A *
*
*
Алгоритм
Заметив эту природу, вы можете реализовать свой алгоритм так просто, как:
void drawGraph(vertices[nRows][nCols])
{
for (unsigned int i = 0; i < nRows; i)
{
for (unsigned int j = i; j < nCols; j)
{
drawLine(i, j);
}
}
}
Комментарии:
1. Хм, думаю, я неправильно задал вопрос.. У меня есть эта часть… Этот просто выведет матрицу adj…. Я хочу преобразовать матрицу adj в график… Я установил его, теперь я хочу создать график из матрицы, которую я опубликовал. У меня есть идея, но я не уверен … что-то вроде: node n1 = adjMatrix[0][0]
2. Я хочу знать, как создать вершины из этой матрицы и как перенести ребра из матрицы в них?
3. @user478984: adjMatrix[i][j] — это не сама вершина, она представляет, сколько ребер, соединяющих вершины i и j. i и j являются вершинами. Вы просите ВЫВЕСТИ график из матрицы чего-то другого?
4. я хочу преобразовать матрицу adj в график, а затем продолжить работу с DFS… Для меня все ясно, просто я не знаю, как создать график… из моей adj . матрицы. Это должно работать не только для этой матрицы adj, но и для любой матрицы as input …. хех ..
5. @user478984: Матрица смежности является представлением графика. Вы можете напрямую использовать DFS для этого.
Ответ №2:
Вы можете преобразовать график из представления матрицы смежности в представление на основе узла следующим образом:
#include <iostream>
#include <vector>
using namespace std;
const int adjmatrix[9][9] = {
{0,1,0,0,1,0,0,0,0},
{1,0,1,0,0,0,0,0,0},
{0,1,0,1,0,0,0,0,0},
{0,0,1,0,0,1,0,0,0},
{1,0,0,0,0,0,1,0,0},
{0,0,0,1,0,0,0,0,1},
{0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,1,0,0,0}
};
struct Node {
vector<Node*> neighbours;
/* optional additional node information */
};
int main (int argc, char const *argv[])
{
/* initialize nodes */
vector<Node> nodes(9);
/* add pointers to neighbouring nodes */
int i,j;
for (i=0;i<9; i) {
for (j=0;j<9; j) {
if (adjmatrix[i][j]==0) continue;
nodes[i].neighbours.push_back(amp;nodes[j]);
}
}
/* print number of neighbours */
for (i=0;i<9; i) {
cout << "Node " << i
<< " has " << nodes[i].neighbours.size() <<" outbound edges." << endl;
}
return 0;
}
Здесь граф представлен в виде массива узлов с указателями на достижимые соседние узлы. После настройки узлов и указателей на их соседей вы используете эту структуру данных для выполнения нужных вам алгоритмов построения графиков, в этом (тривиальном) примере выведите количество исходящих направленных ребер, которые имеет каждый узел.