How to implement a weighted graph?
The graph is set by an adjacency list, read from a file. As a result, the graph = List<Node>
I don't know how to programmatically implement the weight of the edges. Please tell me.
class Node //вершина
{
public string name; //хранит название вершины
//содержит названия вершин, к которым исходят дуги из данной вершины
public List<string> neighbours = new List<string>();
//считывание строки
public Node(string parse)
{
char[] separators =
{
':',
','
};
string[] parseResult = parse.Split(separators);
name = parseResult[0];
for (int i = 1; i < parseResult.Length; i++)
{
neighbours.Add(parseResult[i]);
}
}
// выводит название вершины
public void print()
{
if (neighbours.Count == 0)
{
Console.WriteLine("- Вершина " + name + " не имеет исходящих дуг.");
return;
}
Console.WriteLine("-Вершина " + name + ":");
Console.WriteLine("Исходящие дуги:");
foreach (var i in neighbours)
{
Console.WriteLine("" + name + "-> " + i + "");
}
}
/** добавляет в список вершин-"соседей"
* вершину с заданным именем
*/
public void addEdge(string newEdge)
{
neighbours.Add(newEdge);
}
/** удаляет из списка вершин-"соседей"
* все вхождения deletedEdge
*/
public void deleteEdge(string deletedEdge)
{
while (neighbours.Remove(deletedEdge)) ;
}
public void deleteEdge(int deletedEdge)
{
for (int i = 0; i < neighbours.Count; i++)
{
if (int.Parse(neighbours[i]) == deletedEdge)
{
neighbours.RemoveAt(i);
}
}
}
}
1 answers
Depends on the type of adjacency list, the easiest way is if for N vertices it is represented by a matrix (two-dimensional array) of size NxN, where the weight of the edge is written in the row-column intersection, for example:
_|1|2|3|4|
1|0|7|0|0|
2|7|0|5|0|
3|0|5|0|8|
4|0|0|8|0|
3 edges are described here: (1-2) weighing "7"; (2-3) weighing "5"; (3-4) weighing "8". "0" means that there is no edge between the vertices; the weights can be fractional or negative. This is how a weighted directed graph can be described, except in the case where there can be zero edge weight. -- you will have to invent another flag for the absence of an edge, for example, when writing to text.in the file, put a non-numeric character, and when writing a program (in 2-dimensional.array of numbers) use a constant of type "NaN".
This is not a list of edges/vertices (there is only a table of adjacency) - you do not seem to have any additional tasks =)