数据结构（图的存储结构）

亦凉 2022-06-05 04:22 281阅读 0赞

树形结构节点之间是一对多的关系，节点之间有明显的分支关系和层次关系。每一层的结点可以和下一层的多个节点相关，但只能和上一层的一个节点相关。而图中的顶点间的关系是任意的，没有明显的层次关系。  
**图的定义**：图是由非空顶点集合和描述顶点间的关系–边或弧的集合组成。  
**图的基本术语**  
**边，弧，弧头，弧尾**：无向图之间顶点的连线称为边。有向图之间定点的连线称为弧。弧的始点称为弧尾，弧的终点称为弧尾  
**无向完全图**：任意两个顶点之间都有边相连（n(n-1)/2条边）  
**有向完全图**：任意两个顶点之间都有弧相连（n(n-1)条边）  
**顶点的度，入度，出度**：无向图中，顶点v的度是指依附于顶点v的边数；有向图中，顶点v的度是指入度（v为弧头）和出度(v为弧尾)之和  
**权，网**：边上所附带的数据信息称为权，边上带权的图称为网，或者网络  
**简单路径，简单回路**：一条路径上顶点不重复出现称为简单路径。除第一个顶点和最后一个定点重复外，其他定点不重复的回路称为简单回路  
**连通，（强）连通图**：两个顶点之间有路径，称这两个顶点之间是连通的。任意两个丁点都联通的图称为连通图。  
**（强）连通分量，生成树**：图的极大连通图称为连通分量，图的包含全部顶点的极小连通图称为生成树  
（n-1条边）  
**图的存储结构**  
**图的接口定义**：

interface IGraph<T>
        {
            /// <summary>
            /// 获取顶点的数目
            /// </summary>
            /// <returns></returns>
            int GetNumOfVertex();
            /// <summary>
            /// 获取边的数目
            /// </summary>
            /// <returns></returns>
            int GetNumOfEdge();
            /// <summary>
            /// 两个顶点之间设置边
            /// </summary>
            /// <param name="v1"></param>
            /// <param name="v2"></param>
            void SetEdge(Node<T> v1,Node<T> v2);
            /// <summary>
            /// 两个定点之间删除边
            /// </summary>
            /// <param name="v1"></param>
            /// <param name="v2"></param>
            void DelEdge(Node<T> v1,Node<T> v2);
            /// <summary>
            /// 判断两个顶点之间是否有边
            /// </summary>
            /// <param name="v1"></param>
            /// <param name="v2"></param>
            /// <returns></returns>
            bool IsEdge(Node<T> v1,Node<T> v2);
        }

**顶点类**：

class Node<T>
        {
            private T data;
    
            public Node(T val)
            {
                data = val;
            }
            public T Data { get { return data; }set { data = value; } }
        }

**邻接矩阵**  
用一个一维数组用来存储顶点信息。一个二维数组用来存储边（或弧）的信息  
**邻接矩阵类**：

class GraphAdjMatrix<T>:IGraph<T>
        {
            //边稀疏的情况下，邻接矩阵比邻接表更节省空间
            public Node<T> [] nodes;//顶点信息
            private int numEdges;//边（或弧）得数目
            private int[,] matrix;//边（或弧）的信息
    
            public GraphAdjMatrix(int n)
            {
                nodes = new Node<T>[n];
                numEdges = n;
                matrix=new int[n,n];
            }
    
            public Node<T> GetNode(int index)
            {
                return nodes[index];
            }
    
            public void SetNode(int index,Node<T> val)
            {
                nodes[index] = val;
            }
            public int NumEdges { get { return numEdges; } set { numEdges = value; } }
    
            public int GetMatrix(int index1,int index2)
            {
                return matrix[index1, index2];
            }
    
            public void SetMatrix(int index1,int index2)
            {
                matrix[index1, index2] = 1;//无向图
            }
    
            public int GetIndex(Node<T> v )
            {
                for (int i = 0; i < nodes.Length; i++)
                {
                    if (nodes[i].Equals(v))
                    {
                        return i;
                    }
                }
                return -1;
            }
    
            public int GetNumOfVertex()
            {
                return nodes.Length;
            }
    
            public int GetNumOfEdge()
            {
                return numEdges;
            }
    
            public void SetEdge(Node<T> v1, Node<T> v2)
            {
                matrix[GetIndex(v1), GetIndex(v2)] = 1;
                matrix[GetIndex(v2), GetIndex(v1)] = 1;
                numEdges++;
            }
    
            public void DelEdge(Node<T> v1, Node<T> v2)
            {
                matrix[GetIndex(v1), GetIndex(v2)] = 0;
                matrix[GetIndex(v2), GetIndex(v1)] = 0;
                numEdges--;
            }
    
            public bool IsEdge(Node<T> v1, Node<T> v2)
            {
                return matrix[GetIndex(v1), GetIndex(v2)] == 1;
            }
        }

**邻接表**  
是一种顺序存储和链式存储相结合的存储结构，类似于树的孩子链表表示法。顺序存储指的是把顶点信息用一个数组存储起来，而链式存储指的是把与之相连接的顶点用链表连接起来。  
**顶点信息类**：

class VexNode<T>
        {
            private Node<T> data;
            private AdjListNode<T> firstAdj;
            public Node<T> Data { get { return data; } set { data = value; } }
            public AdjListNode<T> FirstAdj { get { return firstAdj; } set { firstAdj = value; } }
    
            public VexNode()
            {
                data = null;
                firstAdj = null;
            }
            public VexNode(Node<T> nd)
            {
                data = nd;
                firstAdj = null;
            }
    
            public VexNode(Node<T> nd, AdjListNode<T> fir)
            {
                data = nd;
                firstAdj = fir;
            }
        }

**与顶点相连的结点类**：

class AdjListNode<T>
        {
            private int adjvex;
            private AdjListNode<T> next;
            public int Adjvex { get { return adjvex; } set { adjvex = value; } }
            public AdjListNode<T> Next { get { return next; } set { next = value; } }
    
            public AdjListNode(int vex)
            {
                adjvex = vex;
                next = null;
            } 
        }

**连接表类**：

class GraphAdjList<T>:IGraph<T>
        {
            private VexNode<T>[] adjList;
            public VexNode<T> this[int index] { get { return adjList[index]; }set { adjList[index] = value; } }
    
            public GraphAdjList(Node<T> []nodes )
            {
                adjList=new VexNode<T>[nodes.Length];
                for (int i = 0; i < adjList.Length; i++)
                {
                    adjList[i].Data = nodes[i];
                    adjList[i].FirstAdj = null;
                }
            }
    
            public int GetIndex(Node<T> v )
            {
                for (int i = 0; i < adjList.Length; i++)
                {
                    if (adjList[i].Equals(v))
                    {
                        return i;
                    }
                }
                return -1;
            }
            public int GetNumOfVertex()
            {
                return adjList.Length;
            }
    
            public int GetNumOfEdge()
            {
                int count = 0;
                foreach (VexNode<T> temp in adjList)
                {
                    AdjListNode<T> p = temp.FirstAdj;
                    while (p != null)
                    {
                        p = p.Next;
                        count++;
                    }
                }
                return count / 2;
            }
    
            public void SetEdge(Node<T> v1, Node<T> v2)
            {
                AdjListNode<T> p = new AdjListNode<T>(GetIndex(v2));
                if (adjList[GetIndex(v1)].FirstAdj == null)
                {
                    adjList[GetIndex(v1)].FirstAdj = p;
                }
                else
                {
                    p.Next = adjList[GetIndex(v1)].FirstAdj;
                    adjList[GetIndex(v1)].FirstAdj = p;
                }
                p=new AdjListNode<T>(GetIndex(v1));
                if (adjList[GetIndex(v2)].FirstAdj == null)
                {
                    adjList[GetIndex(v2)].FirstAdj = p;
                }
                else
                {
                    p.Next = adjList[GetIndex(v2)].FirstAdj;
                    adjList[GetIndex(v2)].FirstAdj = p;
                }
            }
    
            public void DelEdge(Node<T> v1, Node<T> v2)
            {
                AdjListNode<T> p = adjList[GetIndex(v1)].FirstAdj;
                AdjListNode<T> pre = null;
                while (p!=null)
                {
                    if (p.Adjvex==GetIndex(v2))
                    {
                        break;
                    }
                    pre = p;
                    p = p.Next;
                }
                pre.Next = p.Next;
                p = adjList[GetIndex(v2)].FirstAdj;
                pre = null;
                while (p!=null)
                {
                    if (p.Adjvex==GetIndex(v1))
                    {
                        break;
                    }
                    pre = p;
                    p = p.Next;
                }
                pre.Next = p.Next;
            }
    
            public bool IsEdge(Node<T> v1, Node<T> v2)
            {
                AdjListNode<T> p = adjList[GetIndex(v1)].FirstAdj;
                while (p!=null)
                {
                    if (p.Adjvex==GetIndex(v2))
                    {
                        return true;
                    }
                    p = p.Next;
                }
                return false;
            }
        }