重生之数据结构与算法----图论
简介图结构本质上还有多叉树的变种,图结构在逻辑上，由于若干个节点和边组成。但在实际落地中，一般用邻接表，邻接矩阵来存储图
在标准的树结构中，一般都是单链表表示，即只允许父节点指向子节点，两个子节点之间也不允许互相指向。
而图中，则是双链表放飞自我版，既可以父子之间互相指向，又可以子节点互相链接，形成复杂的网络结构。
图的逻辑视图
可以看到一幅图由节点(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]