6.1.3 图的基本操作
//Graph node class
public class GraphNode<T>
{
public T Value { get; set; }
public GraphNode(T value)
{
Value = value;
}
}
//Actions of graph
public interface IGraph<T>
{
int NodeNum { get; }
int EdageNum { get; }
int IsNode(GraphNode<T> node);
bool SetNode(GraphNode<T> node);
bool DelNode(GraphNode<T> node);
bool SetEdge(GraphNode<T> node1, GraphNode<T> node2, int value);
bool DelEdge(GraphNode<T> node1, GraphNode<T> node2);
bool IsEdge(GraphNode<T> node1, GraphNode<T> node2);
}
6.2 图的存储结构
6.2.1 邻接矩阵
邻接矩阵用两个数组来表示图，一个数组是一维数组，存储图中顶点的信息，一个数组是二维数组，即矩阵，存储顶点之间的信息。
public class GraphMatrix<T> : IGraph<T>
{
private GraphNode<T>[] nodeArray;
private int[,] edageArray;
public int NodeNum { get; private set; }
public int EdageNum { get; private set; }
public GraphMatrix(int length)
{
nodeArray = new GraphNode<T>[length];
edageArray = new int[length, length];
}
public int IsNode(GraphNode<T> node)
{
for (int i = 0; i < NodeNum; i++)
{
if (node == nodeArray[i])
return i;
}
return -1;
}
public bool SetNode(GraphNode<T> node)
{
if (NodeNum >= nodeArray.Length)
return false;
//If the node is already in the array, return false
if (IsNode(node) != -1)
return false;
nodeArray[NodeNum] = node;
NodeNum++;
return true;
}
public bool DelNode(GraphNode<T> node)
{
int index = IsNode(node);
//If the node was not in node array, return false
if (index == -1)
return false;
//move the last node to the deleted node option
nodeArray[index] = nodeArray[NodeNum - 1];
for (int i = 0; i < NodeNum; i++)
{
if (edageArray[index, i] != 0)
EdageNum -= 1;
if (edageArray[i, index] != 0)
EdageNum -= 1;
edageArray[index, i] = edageArray[NodeNum - 1, i];
edageArray[i, index] = edageArray[i, NodeNum - 1];
}
edageArray[index, index] = 0;
for (int i = 0; i < NodeNum; i++)
{
if (edageArray[NodeNum - 1, i] != 0)
edageArray[NodeNum - 1, i] = 0;
if (edageArray[i, NodeNum - 1] != 0)
edageArray[i, NodeNum - 1] = 0;
}
NodeNum -= 1;
return true;
}
public bool SetEdge(GraphNode<T> node1, GraphNode<T> node2, int value)
{
int index1 = IsNode(node1);
int index2 = IsNode(node2);
//Input node was not exist in node array
if (index1 == -1 || index2 == -1)
return false;
if (edageArray[index1, index2] == 0)
EdageNum += 1;
edageArray[index1, index2] = value;
return true;
}
public bool DelEdge(GraphNode<T> node1, GraphNode<T> node2)
{
int index1 = IsNode(node1);
int index2 = IsNode(node2);
//Input node was not exist in node array
if (index1 == -1 || index2 == -1)
return false;
if (edageArray[index1, index2] != 0)
{
EdageNum -= 1;
edageArray[index1, index2] = 0;
return true;
}
else
//There is no edage between the two input nodes
return false;
}
public bool IsEdge(GraphNode<T> node1, GraphNode<T> node2)
{
int index1 = IsNode(node1);
int index2 = IsNode(node2);
//The input node was not in the node array
if (index1 == -1 || index2 == -1)
return false;
if (edageArray[index1, index2] != 0)
return true;
else
return false;
}
public void PrintMatrix()
{
Console.Write(" ");
for (int i = 0; i < NodeNum; i++)
{
if (i == 0)
Console.Write("| ");
Console.Write(nodeArray[i].Value);
Console.Write(" ");
}
Console.WriteLine();
Console.WriteLine("--+" + string.Empty.PadRight((NodeNum + 1) * 2, '-'));
for (int i = 0; i < NodeNum; i++)
{
Console.Write(nodeArray[i].Value);
Console.Write(" ");
for (int j = 0; j < NodeNum; j++)
{
if (j == 0)
Console.Write("| ");
Console.Write(edageArray[i, j]);
Console.Write(" ");
}
Console.WriteLine();
Console.WriteLine(" |");
}
}
}
邻接矩阵类型的测试：
using GraphObject;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace ConsoleApp
{
class Program
{
static void Main(string[] args)
{
GraphMatrix<int> matrix = new GraphMatrix<int>(100);
//Inial graph object
GraphNode<int> node1 = new GraphNode<int>(1);
GraphNode<int> node2 = new GraphNode<int>(2);
GraphNode<int> node3 = new GraphNode<int>(3);
GraphNode<int> node4 = new GraphNode<int>(4);
GraphNode<int> node5 = new GraphNode<int>(5);
GraphNode<int> node6 = new GraphNode<int>(6);
GraphNode<int> node7 = new GraphNode<int>(7);
GraphNode<int> node8 = new GraphNode<int>(8);
matrix.SetNode(node1);
matrix.SetNode(node2);
matrix.SetNode(node3);
matrix.SetNode(node4);
matrix.SetNode(node5);
matrix.SetNode(node6);
matrix.SetNode(node7);
matrix.SetNode(node8);
matrix.SetEdge(node2, node1, 2);
matrix.SetEdge(node3, node1, 3);
matrix.SetEdge(node2, node3, 4);
matrix.SetEdge(node3, node4, 5);
matrix.SetEdge(node5, node6, 4);
matrix.SetEdge(node8, node6, 1);
Assert.AreEqual<int>(8, matrix.NodeNum);
Assert.AreEqual<int>(6, matrix.EdageNum);
//Scenario 1: Test add new node
GraphNode<int> node9 = new GraphNode<int>(9);
matrix.SetNode(node9);
matrix.SetEdge(node9, node5, 3);
matrix.SetEdge(node9, node8, 1);
matrix.SetEdge(node6, node9, 2);
Assert.AreEqual<int>(9, matrix.NodeNum);
Assert.AreEqual<int>(9, matrix.EdageNum);
//Scenario 2: Test remove node
matrix.DelNode(node8);
Assert.AreEqual<int>(8, matrix.NodeNum);
Assert.AreEqual<int>(7, matrix.EdageNum);
matrix.SetNode(node8);
matrix.SetEdge(node8, node6, 1);
matrix.SetEdge(node9, node8, 1);
Assert.AreEqual<int>(9, matrix.NodeNum);
Assert.AreEqual<int>(9, matrix.EdageNum);
//Scenario 3: Test add/remove new edage
matrix.DelEdge(node3, node4);
Assert.AreEqual<int>(9, matrix.NodeNum);
Assert.AreEqual<int>(8, matrix.EdageNum);
matrix.SetEdge(node3, node4, 5);
Assert.AreEqual<int>(9, matrix.NodeNum);
Assert.AreEqual<int>(9, matrix.EdageNum);
//Scenario 4: Other medthods
Assert.IsTrue(matrix.IsNode(node4) >= 0, "node4 should be exist in matrix");
Assert.IsFalse(matrix.IsNode(new GraphNode<int>(10)) >= 0, "node4 should not be exist in matrix");
Assert.IsTrue(matrix.IsEdge(node3, node1), "edage should be exist in matrix");
Assert.IsFalse(matrix.IsEdge(node3, node2), "edage should not be exist in matrix");
}
}
}
邻接矩阵存储图的类的模型图：
邻接矩阵存储图的类的关系图：
