图： 图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。其中，顶集的元素被称为顶点(Vertex)，边集的元素被称为边(edge)。
有向图： 若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为 < v , w > <v,w> <v,w> ，称为从顶点v到顶点w的弧。如上图中（a）： G 1 = ( V 1 , E 1 ) ∣ ∣ V 1 = { 1 , 2 , 3 } ∣ ∣ E 1 = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > } G_1=(V_1,E_1)||V_1=\{1,2,3\}||E_1=\{<1,2>,<2,1>,<2,3>\} G1=(V1,E1)∣∣V1={1,2,3}∣∣E1={<1,2>,<2,1>,<2,3>}
无向图： 若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为 < v , w > <v,w> <v,w> ，称为从顶点v和顶点w的互为邻接点。如上图中（b）： G 1 = ( V 1 , E 1 ) ∣ ∣ V 1 = { 1 , 2 , 3 , 4 } ∣ ∣ E 1 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) ) } G_1=(V_1,E_1)||V_1=\{1,2,3,4\}||E_1=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4))\} G1=(V1,E1)∣∣V1={1,2,3,4}∣∣E1={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4))}
简单图： 一个图满足：① 不存在重复边；② 不存在顶点到自身的边，则称图G为简单图。数据结构中只讨论简单图，如图a,b,c
多重图： 不满足简单图中两个条件，则称为多重图。
完全图： 在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。拥有n个顶点的无向完全图有 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1) 条边，如图b
子图： 设有两个图 G = ( V , E ) G=(V,E) G=(V,E) 和 G 1 = ( V 1 , E 1 ) G_1=(V_1,E_1) G1=(V1,E1) ，若 V 1 V_1 V1 是 V V V 的子集，且 E 1 E_1 E1 是 E E E 的子集，则称 G 1 G_1 G1 是 G G G 的子图。如图a和c
连通： 若从顶点v到顶点w有路径存在，则称v和w是连通的
连通图： 若图 G G G 中任意两个顶点都是连通的，则称图 G G G 为连通图，否则称为非连通图
连通分量： 无向图中的极大连通子图称为连通分量
极大连通子图：
连通图只有一个极大连通子图，就是它本身。（是唯一的）
非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是一个连通图
称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。
下图为非连通图，图中有两个极大连通子图（连通分量）。
极小连通子图：
一个连通图的生成树是该连通图顶点集确定的极小连通子图。（同一个连通图可以有不同的生成树，所以生成树不是唯一的）
（极小连通子图只存在于连通图中）
用边把极小连通子图中所有节点给连起来，若有n个节点，则有n-1条边。如下图生成树有6个节点，有5条边。
之所以称为极小是因为此时如果删除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。
如果在生成树上添加一条边，一定会构成一个环。
也就是说只要能连通图的所有顶点而又不产生回路的任何子图都是它的生成树。
总结来说：极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的。
强连通图： 有向图 G G G 中， 若对于 V ( G ) V(G) V(G) 中任意两个不同的顶点 v i v_i vi 和 v j v_j vj ，都存在从 v i v_i vi 到 v j v_j vj 以及从 v j v_j vj 到 v i v_i vi 的路径，则称图 G G G 是强连通图。如图c
强连通分量： 有向图的极大强连通子图称为 G G G 的强连通分量，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。
生成树： 连通图的生成树是包含图中所有顶点的一个极小连通子图。若图中有n个点，那么生成树含有n-1条边，无论消去哪条边，整个图就不再连通；而无论在哪两个顶点加上一条边，都会形成回路
生成森林： 在非连通图中，连通分量的生成树构成了非连通图的生成森林。
顶点的度：（无向图）该顶点为一个端点的边的数目，记为 T D ( v ) TD(v) TD(v)。度与边之比为 2 e : e 2e:e 2e:e
顶点的入度：（有向图）以顶点v的为终点的有向边的数目 I D ( v ) ID(v) ID(v)
顶点的出度：（有向图）以顶点v的为起点的有向边的数目 O D ( v ) OD(v) OD(v)
边的权和网： 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值；这种边上带有权值的图称为带权图，也称为网
稠密图： 边数很多的图。一般满足 E ≥ V l o g V E≥VlogV E≥VlogV 的图称为稀疏图
稀疏图： 边数很少的图。一般满足 E < V l o g V E<VlogV E<VlogV 的图称为稀疏图
路径： 顶点 V p V_p Vp 到顶点 V q V_q Vq 之间的一条路径是指顶点序列 V p V_p Vp ， V i 1 V_{i1} Vi1 ， V i 2 V_{i2} Vi2 ，…， V m V_m Vm ， V p V_p Vp
路径长度： 路径上边的数目
回路： 第一个顶点和最后一个顶点相同的路径
简单路径： 顶点不重复出现的路径
简单回路： 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
距离： 从顶点 V 1 V_1 V1 到顶点 V 2 V_2 V2 的最短路径若存在，则此路径的长度称为从顶点 V 1 V_1 V1 到顶点 V 2 V_2 V2 的距离
有向树： 一个顶点的入度为0、其余顶点的入度均为1
不带权图：
A
[
i
]
[
j
]
=
{
1
,
若
(
V
1
,
V
2
)
或
<
V
1
,
V
2
>
是图中的边
0
,
若
(
V
1
,
V
2
)
或
<
V
1
,
V
2
>
不是图中的边
A[i][j]= \begin{cases} 1, & \text {若$(V_1,V_2)$或$ <V_1,V_2> $是图中的边}\\ 0, & \text {若$(V_1,V_2)$或$ <V_1,V_2> $不是图中的边} \end{cases}
A[i][j]={1,0,若(V1,V2)或<V1,V2>是图中的边若(V1,V2)或<V1,V2>不是图中的边
带权图：
A
[
i
]
[
j
]
=
{
W
i
j
,
若
(
V
1
,
V
2
)
或
<
V
1
,
V
2
>
是图中的边
0
或
∞
,
若
(
V
1
,
V
2
)
或
<
V
1
,
V
2
>
不是图中的边
A[i][j]= \begin{cases} W_{ij}, & \text {若$(V_1,V_2)$或$ <V_1,V_2> $是图中的边}\\ 0或∞, & \text {若$(V_1,V_2)$或$ <V_1,V_2> $不是图中的边} \end{cases}
A[i][j]={Wij,0或∞,若(V1,V2)或<V1,V2>是图中的边若(V1,V2)或<V1,V2>不是图中的边
#include <stdio.h>
int main() {
const int MAX_N = 5; // 一共有五个顶点
int G[MAX_N][MAX_N] = {}; // 使用邻接矩阵表示
G[0][2] = 1; // 将图连通且不带权
G[0][4] = 1;
G[1][0] = 1;
G[1][2] = 1;
G[2][3] = 1;
G[3][4] = 1;
G[4][3] = 1;
printf("G:\n");
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
printf("%d",G[i][j]);
}
printf("\n");
}
return 0;
}
注意：
图的邻接矩阵存储表示法具有以下特点∶
我觉得图比问题更容易理解事物本质，所以简单讲一下概念，直接上图。
所谓邻接表，是指对图 G中的每个顶点v建立一个单链表，第 i 个单链表中的结点表示依附于顶点 v 的边（对于有向图则是以顶点v为尾的弧），这个单链表就称为顶点v的边表（对于有向图则称为出边表）。
#include <stdio.h>
#include <vector>
using namespace std;
struct GNode{
int val;
vector<GNode*> neighbors;
GNode(int x):val(x) {
}
};
int main() {
int MAX_N = 5; // 五个节点
GNode *Node[MAX_N];
for(int i = 0; i < MAX_N; i++) {
Node[i] = new GNode(i);
}
Node[0]->neighbors.push_back(Node[2]);
Node[0]->neighbors.push_back(Node[4]);
Node[1]->neighbors.push_back(Node[0]);
Node[1]->neighbors.push_back(Node[2]);
Node[2]->neighbors.push_back(Node[3]);
Node[3]->neighbors.push_back(Node[4]);
Node[4]->neighbors.push_back(Node[3]);
printf("Node:\n");
for(int i = 0; i < MAX_N; i++) {
printf("Node[%d]:",i);
for(int j = 0; j < Node[i]->neighbors.size(); j++) {
printf("%d ",Node[i]->neighbors[j]->val);
}
printf("\n");
}
for (int i = 0; i < MAX_N; i++) {
delete Node[i];
}
return 0;
}
图的邻接表存储方法具有以下特点∶
十字链表是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。
顶点结点：
弧结点：
十字链表存储结构：
typedef struct ArcBox // 弧的结构表示
{
int tailvex, headvex;
InfoType *info;
struct ArcBox *hlink, *tlink;
} VexNode;
typedef struct VexNode // 顶点的结构表示
{
VertexType data;
ArcBox *firstin, *firstout;
} VexNode;
typedef struct
{
VexNode xlist[MAX_VERTEX_NUM];// 顶点结点(表头向量)
int vexnum, arcnum;//有向图的当前顶点数和弧数
} OLGraph;
对于十字链表的一些认识：
表头结点即顶点结点，与邻接表一样是顺序存储。
对于每个顶点结点之后是与之相关联的弧结点（该弧结点中存有弧头、弧尾），而邻接表则是一些与顶点结点相连接的点。
从每个顶点结点开始有两条链表，一条是以该顶点结点为弧头的链表，一条是以该顶点结点为弧尾的链表。
对于其中的每一条链表必然是从顶点结点开始，直到与之相关的弧结点链域headlink和taillink为空是结束，构成一条完整的链表。
邻接多重表存储无向图的方式，可看作是邻接表和十字链表的结合。同邻接表和十字链表存储图的方法相同，都是独自为图中各顶点建立一张链表，存储各顶点的节点作为各链表的首元节点，同时为了便于管理将各个首元节点存储到一个数组中。
邻接多重表各结点的结构示意图，如下图所示：
data：存储此顶点的数据；
firstedge：指针域，用于指向同该顶点有直接关联的存储其他顶点的节点。
各链表中其他节点的结构与十字链表中相同，如下图所示：
mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点；
jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点；
info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；
无向图的邻接多重表表示，如下图所示：
#define MAX_VERTEX_NUM 20 //图中顶点的最大个数
#define InfoType int //边含有的信息域的数据类型
#define VertexType int //图顶点的数据类型
typedef enum {unvisited,visited}VisitIf; //边标志域
typedef struct EBox{
VisitIf mark; //标志域
int ivex,jvex; //边两边顶点在数组中的位置下标
struct EBox * ilink,*jlink; //分别指向与ivex、jvex相关的下一个边
InfoType *info; //边包含的其它的信息域的指针
}EBox;
typedef struct VexBox{
VertexType data; //顶点数据域
EBox * firstedge; //顶点相关的第一条边的指针域
}VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];//存储图中顶点的数组
int vexnum,degenum;//记录途中顶点个数和边个数的变量
}AMLGraph;
#include <stdio.h>
#include <vector>
using namespace std;
struct GNode{
int val;
vector<GNode*> neighbors;
GNode(int x):val(x){
}
};
void DFSGraph(GNode *node, int visit[]) {
visit[node->val] = 1; // 标记已访问的顶点
printf("%d ",node->val);
for(int i = 0; i < node->neighbors.size(); i++) {
if(visit[node->neighbors[i]->val] == 0) {
DFSGraph(node->neighbors[i], visit);
}
}
}
int main() {
int MAX_N = 5;
GNode *Node[MAX_N];
for(int i = 0; i < MAX_N; i++) {
Node[i] = new GNode(i);
}
Node[0]->neighbors.push_back(Node[2]);
Node[0]->neighbors.push_back(Node[4]);
Node[1]->neighbors.push_back(Node[0]);
Node[1]->neighbors.push_back(Node[2]);
Node[2]->neighbors.push_back(Node[3]);
Node[3]->neighbors.push_back(Node[4]);
Node[4]->neighbors.push_back(Node[3]);
int visit[MAX_N] = {0};
for(int i = 0; i < MAX_N; i++) {
if(visit[i] == 0) { // 没有标记的顶点才会被访问
printf("From val(%d): ", Node[i]->val);
DFSGraph(Node[i], visit);
printf("\n");
}
}
for (int i = 0; i < MAX_N; i++) {
delete Node[i];
}
return 0;
}
时间复杂度：以邻接矩阵为例，查找每个顶点的邻接点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)，故总的时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)；以邻接表为例，查找所有顶点的邻接点所需的时间为 O ( ∣ E ∣ ) O(|E|) O(∣E∣) ，访问顶点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)，故总的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)
空间复杂度：需要一个递归栈， O ( ∣ V ∣ ) O(|V|) O(∣V∣)
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
struct GNode{
int val;
vector<GNode*> neighbors;
GNode(int x):val(x){
}
};
void BFSGraph(GNode *node, int visit[]) {
queue<GNode*> q; // 广度优先搜索使用队列
q.push(node);
visit[node->val] = 1; // 标记已访问的顶点
while(!q.empty()){
GNode *temp = q.front();
q.pop();
printf("%d ",temp->val);
for(int i = 0; i < temp->neighbors.size(); i++) {
if(visit[temp->neighbors[i]->val] == 0) {
q.push(temp->neighbors[i]);
visit[temp->neighbors[i]->val] = 1;
}
}
}
}
int main() {
int MAX_N = 5;
GNode *Node[MAX_N];
for(int i = 0; i < MAX_N; i++) {
Node[i] = new GNode(i);
}
Node[0]->neighbors.push_back(Node[2]);
Node[0]->neighbors.push_back(Node[4]);
Node[1]->neighbors.push_back(Node[0]);
Node[1]->neighbors.push_back(Node[2]);
Node[2]->neighbors.push_back(Node[3]);
Node[3]->neighbors.push_back(Node[4]);
Node[4]->neighbors.push_back(Node[3]);
int visit[MAX_N] = {0};
for(int i = 0; i < MAX_N; i++) {
if(visit[i] == 0) { // 没有标记的顶点才会被访问
printf("From val(%d): ", Node[i]->val);
BFSGraph(Node[i], visit);
printf("\n");
}
}
for (int i = 0; i < MAX_N; i++) {
delete Node[i];
}
return 0;
}
时间复杂度：以邻接矩阵为例，查找每个顶点的邻接点所需的时间为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)，故总的时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)；以邻接表为例，在任意顶点的邻接表，每条边至少访问一次，此时时间复杂度为 O ( ∣ E ∣ ) O(|E|) O(∣E∣) ，另外，每个顶点均需搜索一次，此时时间复杂度为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)，故总的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)
空间复杂度：需要一个辅助队列Q，最坏的情况下，空间复杂度为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)