重生之数据结构与算法----图论
简介图结构本质上还有多叉树的变种,图结构在逻辑上，由于若干个节点和边组成。但在实际落地中，一般用邻接表，邻接矩阵来存储图
在标准的树结构中，一般都是单链表表示，即只允许父节点指向子节点，两个子节点之间也不允许互相指向。
而图中，则是双链表放飞自我版，既可以父子之间互相指向，又可以子节点互相链接，形成复杂的网络结构。
图的逻辑视图
可以看到一幅图由节点(Vertex)与边(Edge)组成，那么从直觉出发，我们可以认为它的数据结构应该是这个样子的
public class Vertex
{
public int Value { get; set; }
Vertex[] Neighbors { get; set; }
}可以看到，与多叉树并无区别，所以图在本质上还是树.因此适用于树的DFS/BFS算法同样适用于图
Degree
图论中有一个独特的概念，叫度(Degree).
在没有方向的图中，Degree就是每个节点相连边的条数。在有方向的图中，Degree被细分为indegree和outdegree
比如在此图中，节点3的indegree为3，outdegree为1。节点4的indegree为3，outdegree为0
图的实际视图
与上面代码相反的是，图的实际存储方式如下
邻接表
0号节点存储着它的indegree，【4，3，1】
2号节点存储着它的indegree，【3，2，4】
......
代码结构如下:
//邻接表
//List存节点，Int[]存储相邻节点
List<int[]> grath = new List<int[]>();邻接矩阵
邻接矩阵则是把所有可能的节点都穷举描绘出来，然后再到上面标点。
代码结构如下：
//邻接矩阵
//二维数组
bool[,] matrix = new bool;为什么会有两种不同存储方式？
因为任何结构都有两个考虑因素，时间与空间。这是一个万能公式。
[*]可以直观的看到，邻接矩阵是空间换时间，通过填充整个矩阵,只需要matrix就能以O(1)的复杂度实现查找。
[*]而邻接表则是时间换空间,只存储必要的信息，节省了空间，但查找复杂度退化为O(N)
加权图
上面介绍的图最基本的结构，是不是很简单？所有的复杂结构都是在简单上一步一步演化的，图也不例外。
那加权图又如何实现呢？回忆我们的套路.算法共一石,空间换时间独占八斗。
邻接表加权
//List<int[]> grath = new List<int[]>();
// 空间换时间，加一个字段存权重不就好了？
List<Edge[]> grath = new List<Edge[]>();
public struct Edge
{
public int Indegree { get; set; }
public int Weight { get; set; }
}
矩阵表加权
//bool[,] matrix = new bool;
//由bool二维数组切换成int二维数组
//=0 代表没有边，!=0 代表有边且与权重
int[,] matrix = new int;
无向图
上面我们介绍的，都是有向无权图与有向加权图。那什么是无向图呢？
很简单，无向图=双向图
所以你无脑数，有几条边就有几个节点，不再区分indegree,outdegree
一个简单的图
public interface IGraphSimple
{
/// <summary>
/// 添加一条边
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
/// <param name="weight"></param>
void AddEdge(int from, int to, int weight);
/// <summary>
/// 删除一条边
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
void RemoveEdge(int from, int to);
/// <summary>
/// 判断两个节点是否相等
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
/// <returns></returns>
bool IsEdge(int from, int to);
/// <summary>
/// 返回一条边的权重
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
/// <returns></returns>
int? Weight(int from, int to);
List<Edge> Neighbors(int v);
}
public struct Edge
{
/// <summary>
/// 相邻的节点
/// </summary>
public int Indegree { get; set; }
/// <summary>
/// 权重
/// </summary>
public int Weight { get; set; }
}
/// <summary>
/// 邻接表实现图
/// </summary>
public class AdjacencySimple : IGraphSimple
{
public static void Run()
{
var s = new AdjacencySimple(10);
s.AddEdge(0, 1, 0);
s.AddEdge(0, 2, 0);
s.AddEdge(2, 5, 0);
s.AddEdge(2, 6, 0);
s.AddEdge(1, 3, 0);
s.AddEdge(1, 4, 0);
s.AddEdge(3, 6, 0);
s.AddEdge(3, 0, 0);
s.AddEdge(6, 0, 0);
s.DFSTraverse(0);
}
private List<List<Edge>> _graph;
private bool[] _visited;
private LinkedList<int> _path=new LinkedList<int>();
public AdjacencySimple(int capacity)
{
//init
_graph = new List<List<Edge>>(capacity);
_visited=new bool;
for (int i = 0; i < capacity; i++)
{
_graph.Add(new List<Edge>());
}
}
public void Add(int from, int to, int weight)
{
//如果是无向加权表，就调用此方法
AddEdge(from, to, weight);
//多维护一遍关系
AddEdge(from,to, weight);
}
public void AddEdge(int from, int to, int weight)
{
var neighbor = new Edge()
{
Indegree = to,
Weight = weight
};
_graph.Add(neighbor);
}
public bool IsEdge(int from, int to)
{
foreach (var edge in _graph)
{
if (edge.Indegree.Equals(to))
{
return true;
}
}
return false;
}
public List<Edge> Neighbors(int from)
{
return _graph;
}
public void Remove(int from, int to)
{
//如果是无向加权表，就调用此方法
RemoveEdge(from, to);
//多维护一遍关系
RemoveEdge(to, from);
}
public void RemoveEdge(int from, int to)
{
var neighbors = _graph;
foreach (var edge in neighbors)
{
if (edge.Indegree.Equals(to))
{
neighbors.Remove(edge);
break;
}
}
}
public int? Weight(int from, int to)
{
var neighbors = _graph;
foreach (var edge in neighbors)
{
if (edge.Indegree.Equals(to))
{
return edge.Weight;
}
}
return null;
}
public void DFSTraverse(int startIndex)
{
if (startIndex < 0 || startIndex >= _graph.Count)
return;
if (_visited)
return;
_visited = true;
//前序遍历
Console.WriteLine($"index={startIndex}");
if (_graph?.Count > 0)
{
foreach (var item in _graph)
{
DFSTraverse(item.Indegree);
}
}
//后序遍历
//Console.WriteLine($"index={index}");
}
}
/// <summary>
/// 邻接矩阵实现图
/// </summary>
public class MatrixSimple : IGraphSimple
{
private int[,] _matrix;
private bool[] _visited;
public static void Run()
{
var s = new MatrixSimple(10);
s.AddEdge(0, 1, 1);
s.AddEdge(0, 2, 2);
s.AddEdge(2, 5, 3);
s.AddEdge(2, 6, 4);
s.AddEdge(1, 3, 5);
s.AddEdge(1, 4, 6);
s.AddEdge(3, 6, 7);
s.AddEdge(3, 0, 8);
s.AddEdge(6, 0, 9);
s.DFSTraverse(0);
}
public MatrixSimple(int capacity)
{
_matrix = new int;
_visited = new bool;
}
public void Add(int from, int to, int weight)
{
//如果是无向加权表，就调用此方法
AddEdge(from, to, weight);
//多维护一遍关系
AddEdge(to, from, weight);
}
public void AddEdge(int from, int to, int weight)
{
_matrix = weight;
}
public bool IsEdge(int from, int to)
{
return _matrix != 0;
}
public List<Edge> Neighbors(int from)
{
var result=new List<Edge>();
var columns = _matrix.GetLength(from);
for (int i = 0; i < columns; i++)
{
if (_matrix > 0)
{
result.Add(new Edge { Indegree = i, Weight = _matrix });
}
}
return result;
}
public void Remove(int from, int to)
{
//如果是无向加权表，就调用此方法
RemoveEdge(from, to);
//多维护一遍关系
RemoveEdge(to, from);
}
public void RemoveEdge(int from, int to)
{
//0代表未使用
_matrix = 0;
}
public int? Weight(int from, int to)
{
return _matrix;
}
public void DFSTraverse(int startIndex)
{
if (_visited)
return;
_visited = true;
//前序遍历
Console.WriteLine($"index={startIndex}");
for (int i = 0; i < _visited.Length; i++)
{
//为0代表未使用
if (_matrix == 0)
continue;
DFSTraverse(i);
}
//后序遍历
//Console.WriteLine($"index={index}");
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]