在数学中，图是描述于一组对象的结构，其中某些对象对在某种意义上是“相关的”。这些对象对应于称为顶点的数学抽象（也称为节点或点），并且每个相关的顶点对都称为边（也称为链接或线）。通常，图形以图解形式描绘为顶点的一组点或环，并通过边的线或曲线连接。 图形是离散数学的研究对象之一。

主要有以下两种定义。

图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。其中，顶集的元素被称为顶点(Vertex)，边集的元素被称为边(edge)。

E的元素都是二元组，用(x,y)表示，其中x,y∈V。

图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，I将E中的每一个元素映射到。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

一个图如果任意两顶点之间只有一条边（在有向图中为两顶点之间每个方向只有一条边）；边集中不含环，则称为单图。

阶（Order）：图G中点集V的大小称作图G的阶。

子图（Sub-Graph）：当图G'=(V',E')其中V‘包含于V，E’包含于E，则G'称作图G=(V,E)的子图。每个图都是本身的子图。

生成子图（Spanning Sub-Graph）：指满足条件V(G') = V(G)的G的子图G'。

导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。

度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。

入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。

路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

行迹（Trace）：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。

轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。

闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。

（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）

桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。

数组（邻接矩阵）存储表示（有向或无向）

邻接表存储表示

有向图的十字链表存储表示

无向图的邻接多重表存储表示

一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。

在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。

在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作，它表示从顶点vi到顶点vj有一条边。

若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。

路径长度是指路径上边或弧的数目。

若第一个顶点和最后一个顶点相同，则这条路径是一条回路。

若路径中顶点没有重复出现，则称这条路径为简单路径。

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。

在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。

（1）创建一个图结构 CreateGraph(G)

（2）检索给定顶点 LocateVex(G,elem)

（3）获取图中某个顶点 GetVex(G,v)

（4）为图中顶点赋值 PutVex(G,v,value)

（5）返回第一个邻接点 FirstAdjVex(G,v)

（6）返回下一个邻接点 NextAdjVex(G,v,w)

（7）插入一个顶点 InsertVex(G,v)

（8）删除一个顶点 DeleteVex(G,v)

（9）插入一条边 InsertEdge(G,v,w)

（10）删除一条边 DeleteEdge(G,v,w)

（11）遍历图 Traverse(G,v)

显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。

在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。

图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边

下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。

构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。

下面我们考虑一下如何实现这个操作过程的算法。

分析 ：（1）它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；（2）网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示：

整个算法的执行过程可以描述为：

假设该网以邻接矩阵的形式给出，则完整的算法为：

邻接矩阵:

有向图的邻接矩阵

具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度

无向图的邻接矩阵

在C 语言中，实现邻接矩阵表示法的类型定义如下所示：

边结点的结构为：

adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针

elem是顶点内容，firstedge是指向第一条边或弧结点的指针。

在C语言中，实现邻接表表示法的类型定义如下所示：

创建有向图和无向图邻接表的算法实现：

（1） 创建有向图邻接表

（2）创建无向图的邻接表

常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。

深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。

深度优先遍历算法实现：

int visited[0..n-1]={0,0,...0};

void DFS(AdjList adj,int v)

{//v是遍历起始点的在邻接表中的下标值，其下标从0开始

visited[v]=1; visited(adj[v].elem);

for (w=adj[v].firstedge;w;w=w-＞next)

if (!visited[w-＞adjvex]) DFS(adj,w-＞adjvex);

}

对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测：

其递归算法如下：

对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。

下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题：

（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；

（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。

int visited[0..n-1]={0,0,...0};

void BFS(AdjList adj,int v)

{//v是遍历起始点在邻接表中的下标，邻接表中下标从0开始

InitQueue(Q); //Q是队列

visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);

while (!QueueEmpty(Q)) {

DeQueue(Q,v);

for (w=adj[v].firstedge;w;w=w-＞next)

if (!visited[w-＞adjvex]) {

visited[w-＞adjvex]=1;

visite(adj[w-＞adjvex].elem);

EnQueue(Q,w-＞adjvex); }

}

}

其非递归算法如下：

拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。

举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。

拓扑排序的方法：

（1）从图中选择一个入度为0的顶点且输出之；

（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；

反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。

下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。

下面给出算法实现的基本过程：

{ 将所有入度为0的顶点入栈；

当栈非空时重复执行下列操作：

从栈中退出顶点k；

（1）将k顶点的信息输出；

（2）将与k邻接的所有顶点的入度减1。

}

下面是拓扑排序的完整算法。

树

平面图

完全图：每一对不同顶点间都有边相连的的图，记作Kn。

二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。

完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作Km,n。

正则图：如果图中所有顶点的度皆相等，则此图称为正则图

图是一个有序对，V是结点集，E是边集，当½V½,½E½有限时，称为有限图；否则称无限图.

无向边, 与无序结点(v,u)相关联的边；有向边，与有序结点相关联的边.

无向图，每条边都是无向边的图，记作G=; 每条边都是有向边的图，记作D=.

混合图，既有有向边，也有无向边的图.

平凡图，仅有一个结点的图；零图，边集为空集的图，即仅有结点的图.

自回路(环)，关联于同一个结点的边.

无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边.

简单图，不含平行边和自回路的图.

在无向图G=中，与结点v(ÎV)关联的边数，即为结点度数deg(v)或d(v).；在有向图中，结点v的出度和入度之和为度数.

在有向图D=中，以v(ÎV)为起点的边之条数为出度deg+(v)；以v(ÎV)为终点的边之条数为入度deg－(v)..

最大度数，D(G)=max{d(v)½vÎV}；最小度数，d(G)=min{d(v)½vÎV}

有n个结点的且每对结点都有边相连无向简单图，无向完全图Kn. 此时有 ；有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为有向完全图，.此时有

设G=, V，E的子集V¢,E¢构成的图G¢=是图G的子图；若G¢ÍG且G¢1G，(V¢ÌV或E¢ÌE)，G¢是G的真子图.

生成子图，设图G=, 若E¢ÍE, 则图<.V,E¢>是的生成子图. 即结点与原图G相同的子图，为生成子图.

补图`G=，设G=, 以V为结点集，以使G成为完全图所添加的边为边集E¢的图，就是图G的补图G¢,.，即是完全图, 其中EÇE¢=Æ.

图的同构，设G1=和G2=, 存在双射当且仅当 (f(vi),f(vj))ÎE2，且(vi,vj)与 (f(vi),f(vj))的重数相同. 则G1≌G2.

同构充分条件：建立两个图的对应关系，这个关系是双射函数.

同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同.