Definição do diagrama
O gráfico é composto por um conjunto de vértices não vazios e um conjunto de arestas entre os vértices. Geralmente é representado como: g (v, e), onde g representa um gráfico, v é o conjunto de vértices no gráfico g e e é o conjunto de arestas no gráfico G.
Gráfico direcionado
Aresta direcionada: se a borda do vértice VI para VJ tiver uma direção, essa borda é chamada de borda direcionada, que também se torna um arco (arco). É representado por um ordenado <vi, vj>. VI é chamado de arco e VJ é chamado de cabeça do arco.
Diagrama desordenado
Borda não direcionada: se a borda entre os vértices VI e VJ não tiver direção, essa borda é chamada de borda não direcionada (borda) e é representada por um par não ordenado (VI, VJ).
Imagem simples
Diagrama simples: na estrutura do gráfico, se não houver vértice em sua própria borda e a mesma borda não aparecer repetidamente, essa imagem é chamada de um diagrama simples.
Classe da imagem
Indica um vértice
A primeira etapa na criação de uma classe gráfica é criar uma classe de vértices para salvar vértices e bordas. Esta classe funciona da mesma forma que a classe de nó de listas vinculadas e árvores de pesquisa binária. A classe Vertex possui dois membros de dados: um para identificar o vértice e o outro para indicar se ele foi acessado. Eles são nomeados Label e foram visitados, respectivamente.
A cópia do código é a seguinte:
Função Vertex (Label) {
this.label = Label;
}
Encontramos todos os vértices em uma matriz e, na aula de gráficos, podemos nos referir a eles por sua posição na matriz
Indica borda
As informações reais do gráfico são armazenadas na "borda" porque elas descrevem a estrutura do gráfico. Um nó pai de uma árvore binária pode ter apenas dois nós filhos, mas a estrutura do gráfico é muito mais flexível. Um vértice pode ter uma borda ou várias bordas conectadas a ele.
Usaremos o método de representar as bordas do gráfico para se tornar uma tabela de adjacência ou uma matriz de tabela de adjacência. Ele armazenará uma matriz composta por uma lista de vértices adjacentes de vértices
Construir um gráfico
Defina a seguinte classe de gráfico:
A cópia do código é a seguinte:
Função Graph (v) {
this.vertices = v; // vértices para o ponto alto
this.edges = 0;
this.adj = [];
for (var i = 0; i <this.vertices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
}
this.Addedge = Adicionado;
this.toString = ToString;
}
Esta classe registra quantas arestas um gráfico representa e usa um comprimento e o número de vértices do gráfico para gravar o número de vértices.
A cópia do código é a seguinte:
function addge () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
}
Aqui, usamos um loop for para adicionar um subarray para cada elemento da matriz para armazenar todos os vértices adjacentes e inicializar todos os elementos em seqüências vazias.
A travessia da imagem
Proversal prioritária de profundidade
DepthfirstSearch, também conhecido como DepthFirstSearch, é referido como DFS para abreviar.
Por exemplo, procurando uma chave em uma sala, independentemente da sala que você inicia, você pode procurar os cantos da sala, mesa de cabeceiras, mesas de cabeceira, debaixo de camas, guarda -roupas, armários de TV, etc. Um a um, para não perder nenhum ponto cego. Depois de pesquisar todas as gavetas e armários de armazenamento, procure a próxima sala.
Pesquisa de prioridade de profundidade:
Pesquisa em profundidade significa acessar um vértice que não foi visitado, marcando-o como acessado e depois acessando recursivamente outros vértices que não foram visitados na tabela de adjacência do vértice inicial.
Adicione uma matriz à classe Graph:
A cópia do código é a seguinte:
this.Marked = []; // Salvar os vértices visitados
for (var i = 0; i <this.vertices; ++ i) {
this.Marked [i] = false; // inicialize para false
}
Função de pesquisa de profundidade:
A cópia do código é a seguinte:
função dfs (v) {
this.Marked [v] = true;
// Se a instrução não for necessária aqui
if (this.adj [v]! = indefinido) {
print ("Vértice visitado:" + V);
para cada (var w neste.adj [v]) {
if (! this.Marked [w]) {
this.dfs (w);
}
}
}
}
Pesquisa pela primeira vez
Pesquisa em amplitude (BFS) é um método de pesquisa cega, com o objetivo de expandir e examinar sistematicamente todos os nós no gráfico para encontrar resultados. Em outras palavras, ele não leva em consideração a localização possível do resultado e pesquisa toda a imagem inteira até que o resultado seja encontrado.
A primeira pesquisa começa com o primeiro vértice e tente acessar o vértice o mais próximo possível dele, conforme mostrado na figura a seguir:
Seu princípio de trabalho é:
1. Primeiro encontre vértices não alcançados adjacentes ao vértice atual e adicione -os à lista e fila dos vértices visitados;
2. Em seguida, retire o próximo vértice v do gráfico e adicione -o à lista de vértices visitados
3. Finalmente, adicione todos os vértices não visitados adjacentes a V à fila
A seguir, é apresentada a definição da função de pesquisa pela primeira vez:
A cópia do código é a seguinte:
função bfs (s) {
var fila = [];
this.Marked = true;
fila.push (s); // adicione ao final da fila
while (fileue.length> 0) {
var v = fileue.shift (); // Retire do líder da equipe
if (v == indefinido) {
print ("Vértice visitado:" + V);
}
para cada (var w neste.adj [v]) {
if (! this.Marked [w]) {
this.edgeto [w] = v;
this.Marked [w] = true;
fila.push (w);
}
}
}
}
Caminho mais curto
Ao realizar uma pesquisa pela primeira vez, o caminho mais curto de um vértice para outro vértice conectado é encontrado automaticamente
Determinar o caminho
Para encontrar o caminho mais curto, precisamos modificar o algoritmo de pesquisa pela primeira vez para gravar o caminho de um vértice para outro. Precisamos de uma matriz para salvar todas as bordas do próximo vértice de um vértice. Nomeamos esta matriz Edgeto
A cópia do código é a seguinte:
this.Edgeto = []; // Adicione esta linha à classe Graph Class
// função bfs
função bfs (s) {
var fila = [];
this.Marked = true;
fila.push (s); // adicione ao final da fila
while (fileue.length> 0) {
var v = fileue.shift (); // Retire do líder da equipe
if (v == indefinido) {
print ("Vértice visitado:" + V);
}
para cada (var w neste.adj [v]) {
if (! this.Marked [w]) {
this.edgeto [w] = v;
this.Marked [w] = true;
fila.push (w);
}
}
}
}
Algoritmo de classificação topológica
A classificação topológica classifica todos os vértices de um gráfico direcionado, de modo que as arestas direcionadas apontam do vértice frontal para o vértice traseiro.
O algoritmo de classificação topológico é semelhante ao BFS. A diferença é que o algoritmo de classificação topológico não produz os vértices acessados imediatamente, mas acessa todos os vértices adjacentes na tabela adjacente atual do vértice. Até que esta lista se esgote, o vértice atual não será empurrado para a pilha.
O algoritmo de classificação topológico é dividido em duas funções. A primeira função é o TOPSORT (), que é usado para definir o processo de classificação e chamar uma função auxiliar TopSortHelper () e, em seguida, exibir a lista de vértices classificados.
O principal trabalho do algoritmo de classificação de topologia é realizado na função recursiva TopSortelper (), que marca o vértice atual conforme acessado e, em seguida, acessa recursivamente cada vértice na tabela de adjacência de vértices atuais, marcando esses vertices conforme acessado. Finalmente, empurre o vértice atual para a pilha.
A cópia do código é a seguinte:
// função topSort ()
função topSort () {
var Stack = [];
var visitado = [];
for (var i = 0; i <this.vertices; i ++) {
visitado [i] = false;
}
for (var i = 0; i <this.vertices; i ++) {
if (visitado [i] == false) {
this.topsOrtHelper (i, visitei, pilha);
}
}
for (var i = 0; i <Stack.length; i ++) {
if (pilha [i]! = indefinido && pilha [i]! = false) {
imprimir (this.vertexlist [pilha [i]]);
}
}
}
// função topSortHelper ()
função topSortHelper (V, visitada, pilha) {
visitado [v] = true;
para cada (var w neste.adj [v]) {
if (! visitado [w]) {
this.topsOrtHelper (visitado [w], visitado, pilha);
}
}
Stack.push (v);
}