图及其相关的定义

图($Graph$Graph)：是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为$G(V,E)$G(V,E)，其中$G$G表示图，$V$V表示顶点的集合，$E$E表示图$G$G中边的集合。
Note：对于$G(V,E)$G(V,E)，强调$V$V有穷非空；$V$V可以为空。

无向边：若顶点$v_i$vi​与$v_j$vj​之间的边没有方向，则称这条边为无向边$(Edge)$(Edge)，用无序偶对$(v_i,v_j)$(vi​,vj​)或$(v_j,v_i)$(vj​,vi​)来表示。
无向图$(Undirected\ graphs)$(Undirected graphs)：若图中任意两个顶点之间的边都是无向边，则称为无向图。在无向图中，如果任意两个顶点之间都存在边，则称为无向完全图。

有向边：若顶点$v_i$vi​与$v_j$vj​之间的边有方向，则称这条边为有向边$(Arc)$(Arc)，用有序偶$&lt;v_i,v_j&gt;$<vi​,vj​>来表示。$v_i$vi​称为弧尾$(Tail)$(Tail)，$v_j$vj​称为弧头$(Head)$(Head)。
有向图$(Directed\ graphs)$(Directed graphs)：若图中任意两个顶点之间的边都是有向边，则称为有向图。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。

稀疏图与稠密图：有很少条边或弧的图称之为稀疏图，反之为稠密图。

权$(Weight)$(Weight)：有些图的边或弧具有与它相关的数字，这些数叫做权。

网$(Network)$(Network)：带权的图通常称作网。

子图$(Subgraph)$(Subgraph)：对于图$G(V,E)$G(V,E)与图$G&#x27;(V&#x27;,E&#x27;)$G′(V′,E′)，如果$V&#x27;\subseteq V$V′⊆V ，$E&#x27;\subseteq E$E′⊆E ，则称G’为G的子图。

邻接点$(Adjacent)$(Adjacent)：对于无向图$G(V,E)$G(V,E)，如果边$(v,v&#x27;)\in E$(v,v′)∈E，则称顶点$v$v和$v&#x27;$v′互为邻接点，边$(v,v&#x27;)$(v,v′)依附于顶点$v$v和$v&#x27;$v′，或者说$(v,v&#x27;)$(v,v′)与顶点$v$v和$v&#x27;$v′相关联。对于有向图$G(V,E)$G(V,E)，如果弧$&lt;v,v&#x27;&gt;\in E$<v,v′>∈E，则称顶点v邻接到顶点$v&#x27;$v′，顶点$v&#x27;$v′邻接自顶点$v$v，弧$&lt;v,v&#x27;&gt;$<v,v′>与顶点$v$v，$v&#x27;$v′相关联。

度$(Degree)$(Degree)，入度$(InDegree)$(InDegree)，出度$(OutDegree)$(OutDegree)：对于无向图，顶点$v$v的度是和$v$v相关联的边的数目，记为$TD(v)$TD(v)。对于有向图，以顶点$v$v为头的弧的数目称为$v$v的入度，记为$ID(v)$ID(v)；以$v$v为尾的弧的数目称为$v$v的出度，记为$OD(v)$OD(v)；$v$v的度$TD(v)=ID(v)+OD(v)$TD(v)=ID(v)+OD(v)。

连通图$(Connected \ Graph )$(Connected Graph)：在无向图$G$G 中，如果从顶点$v$v到顶点$v&#x27;$v′有路径，则称$v$v和$v&#x27;$v′是连通的。如果对于图中任意两个顶点$v_i,v_j \in E$vi​,vj​∈E， $v_i$vi​和$v_j$vj​ 都是连通的，则称$G$G是连通图。

强连通图，强连通分量：在有向图$G$G中，如果对于每一对$v_i,v_j\in V且v_i!=v_j$vi​,vj​∈V且vi​!=vj​，从$v_i$vi​到$v_j$vj​和从$v_j$vj​到$v_i$vi​都存在路径，则称G 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
Note：注意和有向完全图做区分，有向完全图需要任意两个不同的顶点之间存在的是相互反向的弧而不是路径。
Note：一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

连通分量：无向图中的极大连通子图称为连通分量。
Note：1.要是子图；2.子图要是连通的；3.连通子图含有极大顶点数；4.具有极大顶点数的连通子图包含依附于这些顶点的所有边。

生成树：所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的$n$n个顶
点， 但只有足以构成一棵树的$n-1$n−1条边。

有向树：如果一个有向图恰有一个顶点的入度为0 ，其余顶点的入度均为1 ，则是一棵有向树。
有向图的生成森林：一个有向圈的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

图储存结构

邻接矩阵

图或网的邻接矩阵$(Adjacency\ Matrix)$(Adjacency Matrix)存储方式是用一个列表和一个矩阵来表示图。一个列表存储图中顶点信息，一个矩阵(称为邻接矩阵)存储图中的边或弧的信息。
设图$G$G有$n$n个顶点，则邻接矩阵是一个$n\times n$n×n的方阵，定义为：
图：
$arc[i][j]=\begin{cases} 1 &amp; if(v_i,v_j)\in E\ or &lt;v_i,v_j&gt;\in E\\ 0 &amp; else\\ \end{cases}$arc[i][j]={10​if(vi​,vj​)∈E or<vi​,vj​>∈Eelse​
网：
$arc[i][j]=\begin{cases} weight[i][j] &amp; if:(v_i,v_j)\in E\ or &lt;v_i,v_j&gt;\in E\\ 0 &amp; if :i==j\\ inf &amp; else\\ \end{cases}$arc[i][j]=⎩⎪⎨⎪⎧​weight[i][j]0inf​if:(vi​,vj​)∈E or<vi​,vj​>∈Eif:i==jelse​
Note：当图(网)为无向图(网)时，邻接矩阵为对称阵。

有向网的邻接矩阵储存代码

因为无论是无向图(网)还是有向图(网)，作为邻接矩阵储存时代码大致相同，故只列出有向网的邻接矩阵代码。有一点需注意，若为无向图，则其邻接矩阵是对称阵，因此可以只用一个下三角矩阵来储存无向图。因为偷懒，所以只写了通过输入顶点集合$vertices$vertices与边集合$edges\_list$edges_list生成邻接矩阵，用class包装，class方法均略去了。

# -*- coding: utf-8 -*-
"""
Created on Tue Apr  2 16:13:16 2019

@author: Administrator
"""
from numpy import *

class Directed_Graph_Matrix(object):
#Adjacency Matrix
    def __init__(self, vertices=[], edges_list=[]):
        self.edges_dict = {}                                         #{(tail, head):weight}
        self.edges_list=edges_list                                   #(tail, head, weight)
        self.vertices = vertices                                     #顶点
        self.num_edges = len(edges_list)                             #边的数目
        self.num_vertices = len(self.vertices)                       #顶点数目
        self.Mat = zeros((self.num_vertices,self.num_vertices))      #邻接矩阵
        
        if self.num_vertices == 0:
        #图不能为空
            print('图不能为空')
            raise IndexError
            
        for Edge in edges_list:
        #根据edges_list生成self.edges_dict
            self.edges_dict[(Edge[0],Edge[1])]=Edge[2]

        for i in range(self.num_vertices):
            for j in range(self.num_vertices):
                if i==j:
                    self.Mat[i][j]=0
                elif (vertices[i],vertices[j]) in self.edges_dict:
                    self.Mat[i][j]=self.edges_dict[(vertices[i],vertices[j])]
                else:
                    self.Mat[i][j]=inf
                    
vertices=['A','B','C','D','E','F','G','H','I']
edges_list=[['A','B',6],['A','C',4],['A','D',5],['B','E',1],['C','E',1],['D','F',2],['F','H',4],['E','G',9],['E','H',7],['H','I',4],['G','I',2]]
G= Directed_Graph_Matrix(vertices,edges_list)

邻接表

在储存稀疏图时，因为边(弧)的数目较少，虽然依旧可以用邻接矩阵，但是为了避免空间的浪费，故可以考虑邻接表的储存结构。

邻接表的处理办法：

在C语言中的处理办法：
1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2.图中每个顶点$v_i$vi​ 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点$v_i$vi​的边表，有向图则称为顶点$v_i$vi​作为弧尾的出边表。
顶点表节点结构：

$data$data	$firstedge$firstedge

边表节点结构：

$adjvex$adjvex	$next$next

在python中的处理办法：
因为python中具有$list$list这种数据结构，故我们可以直接设一个数据类型为$list$list的变量为$Link$Link来作为邻接表：$Link=[[v_1,[head,weight],[head,weight],...],[v_2,[head,weight],[head,weight],...],...]$Link=[[v1​,[head,weight],[head,weight],...],[v2​,[head,weight],[head,weight],...],...]。
即$Link$Link中成员变量为$[vertex,[head,weight],[head,weight],...]$[vertex,[head,weight],[head,weight],...]：$vertex$vertex储存顶点信息，$[head,weight]$[head,weight]储存弧$&lt;vertex,head&gt;$<vertex,head>的弧头信息以及弧的权重。

下图为无向图的邻接表：

对于有向图，因为每个弧都是由方向的，故我们有两种结构的邻接表，一种叫邻接表，另一种叫逆邻接表。
下图为有向图的两种邻接表：

邻接表的代码

以下是无向图的邻接表代码：

from numpy import *
class Undirected_Grapgh_Link(object):
    def __init__(self,vertices=[],edges_list=[]):
        self.vertices=vertices
        self.edges_list=edges_list          #(tail, head, weight)      
        self.Link=[]                        #邻接表[[vertice,[head,weight],...]]
        self.edges_dict = {}                #{(tail, head):weight}
        self.num_edges = 0
        self.num_vertices = len(self.vertices)
        
        if self.num_vertices==0:
            raise IndexError
        
        else:
            for V in vertices:
                a=[]
                a.append(V)
                for x in self.edges_list:
                    if x[0]==V:
                        a.append([self.vertices.index(x[1]),x[2]])
                    elif x[1]==V:
                        a.append([self.vertices.index(x[0]),x[2]])
                self.Link.append(a)

十字链表

对于有向图来说，邻接装是有缺陆的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。因此考虑将邻接表与逆邻接表结合起来，这就是十字链表。

顶点结构：

data(顶点信息)	firstin(指向该顶点入边表的第一个结点)	firstout(指向该顶点出边表的第一个结点)

边表结构：

tailvex(弧起点)	headvex(弧终点)	headlink(指向终点相同的下一条边)	taillink(指向起点相同的下一条边)

图中的实线箭头是有向图的邻接表的表示，虚线箭头是有向图的逆邻接表的表示。

十字链表的代码以及测试数据

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 15:41:00 2019

@author: Administrator
"""

from numpy import *

class Vertices_Node(object): 				#顶点节点类的创建
    def __init__(self,data,firstin=None,firstout=None):
        self._data=data
        self._firstin=firstin               #指向该顶点入边表的第一个结点
        self._firstout=firstout             #指向该顶点出边表的第一个结点
    
    def get_Data(self):
        return self._data
    
    def set_Data(self,newdata):
        self._Data=newdata
        
    def setFirstin(self,newfirstin):
        self._firstin=newfirstin
        
    def getFirstin(self):
        return self._firstin
        
    def setFirstout(self,newfirstout):
        self._firstout=newfirstout
        
    def getFirstout(self):
        return self._firstout


class Edge_Node(object): 					#边表节点类的创建
    def __init__(self,tailvex,headvex,headlink=None,taillink=None):
        self._tailvex=tailvex               #弧起点在顶点表的下标
        self._headvex=headvex               #弧终点在顶点表的下标
        self._headlink=headlink             #指向终点相同的下一条边
        self._taillink=taillink             #指向起点相同的下一条边
        
    def setTailvex(self,newtailvex):
        self._tailvex=newtailvex
    def getTailvex(self):
        return self._tailvex
    
    def setHeadvex(self,newheadvex):
        self._headvex=newheadvex
    def getHeadvex(self):
        return self._headvex
    
    def setTaillink(self,newtaillink):
        self._taillink=newtaillink
    def getTaillink(self):
        return self._taillink
    
    def setHeadlink(self,newheadlink):
        self._headlink=newheadlink
    def getHeadlink(self):
        return self._headlink
    
    
class Orthogonal_List(object): 				#十字链表类的创建
    def __init__(self,vertices,edge_list=[]):
        self._vertices=[]
        for x in vertices: 					#顶点表
            self._vertices.append(Vertices_Node(x))
            
        self._edge_list=[] 					#边表
        for x in edge_list:
            self._edge_list.append(Edge_Node(vertices.index(x[0]),vertices.index(x[1])))
        
        for VNode in self._vertices:
            current1=None
            current2=None
            for ENode in self._edge_list:          
                if self._vertices.index(VNode)==ENode._tailvex:			#建立十字链表中邻接表部分
                    if VNode._firstout==None:
                        VNode._firstout=ENode
                        current1=VNode._firstout
                    else:
                        current1._taillink=ENode
                        current1=current1._taillink

                if self._vertices.index(VNode)==ENode._headvex:  		#建立十字链表中邻接表部分
                    if VNode._firstin==None:
                        VNode._firstin=ENode
                        current2=VNode._firstin
                    else:
                        current2._headlink=ENode
                        current2=current2._headlink

vertices=['A','B','C','D']
edges_list=[['B','A'],['B','C'],['C','B'],['C','A'],['A','D']]
G=Orthogonal_List(vertices,edges_list)
        

邻接多重表

对于有向图，有优化后的链表结构，即十字链表，那么对于无向图，也有邻接表的优化结构，邻接多重表。
在考虑对无向图的邻接表进行删除操作时，会比较繁琐，例如下图中想要删除边$(v_0,v_2)$(v0​,v2​)，在链表中的操作将会很繁琐。因此仿造十字链表，对无向图的邻接表的边表进行改造。
定义边表节点结构：

$ivex$ivex	$ilink$ilink	$jvex$jvex	$jlink$jlink

其中$ivex$ivex和$jvex$jvex是与某条边依附的两个顶点在顶点表中下标。$ilink$ilink指向依附顶
点$ivex$ivex的下一条边，$jlink$jlink指向依附顶点$jvex$jvex的下一条边。

连线方式：从顶点出发，顶点的$firstedge$firstedge指向某条与该顶点相关联的边，而此边需要指向另一条边，指向的边与该边有存在一个相同的关联点，$ilink$ilink指向的边有关联点$ivex$ivex，$jlink$jlink指向的边有关联点$jvex$jvex。
例如，顶点$v$v的$firstedge$firstedge指向边$(v,w)$(v,w)，边$(v,w)$(v,w)的结构为

$ivex$ivex	$ilink$ilink	$jvex$jvex	$jlink$jlink

则$ilink$ilink需要指向$(v,v&#x27;)$(v,v′)或$(v&#x27;,v)$(v′,v)，$jlink$jlink需要指向$(w,w&#x27;)$(w,w′)或$(w&#x27;,w)$(w′,w)，如此一直下去。

###邻接多重表的代码

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 20:13:07 2019

@author: Administrator
"""



class Vertices_Node(object):
    def __init__(self,data,firstedge=None):
        self._data=data
        self._firstedge=firstedge

class Edge_Node(object):
    def __init__(self,ivex,jvex,ilink=None,jlink=None):
        self._ivex=ivex
        self._jvex=jvex
        self._ilink=ilink
        self._jlink=jlink
    
class Adjacency_Multilist(object):
    def __init__(self,vertices,edge_list=[]):
	
        self._vertices=[]
        for x in vertices:
            self._vertices.append(Vertices_Node(x))
            
        self._edge_list=[]
        for x in edge_list:
            self._edge_list.append(Edge_Node(vertices.index(x[0]),vertices.index(x[1])))
        
        for VNode in self._vertices:
            current=None
            for ENode in self._edge_list:
                if self._vertices.index(VNode)==ENode._ivex or self._vertices.index(VNode)==ENode._jvex:
                    if VNode._firstedge==None:
                        VNode._firstedge=ENode
                        current=ENode
                    elif current._ivex==self._vertices.index(VNode):
                        current._ilink=ENode
                    elif current._jvex==self._vertices.index(VNode):
                        current._jlink=ENode

边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标$(begin)$(begin) ，终点下标$(end)$(end)和权$(weight)$(weight)组成。

边数组结构：

$begin$begin	$end$end	$weight$weight