概念

  • 多对多
  • G = (V,E) 表示，V是定点，E是边
  • 有向边：<$v_i$ , $v_j$>， ==$v_i$ 弧尾 $v_j$弧头== 有向图 <>
    无向边 （） 无向图
  • 邻接关系：若<$v_i$ , $v_j$>，则称$v_i$邻接到$v_j$，或$v_j$和$v_i$邻接
  • 出度：射出的边
    入度：射入的边
    无向图：度
  • 直接前驱，直接后继，无向图两个邻接的点互为直接前驱和直接后继
  • ==不含自连边==
  • 无向完全图：$n*(n-1)/2$
    有向完全图：$n*(n-1)$
  • 加权有向图，加权无向图：统称为网络
  • 路径长度：
    ==若无权重，有向边或无向边的条数==
    ==若有权重：权重之和==
  • 简单路径：除第一个顶点和最后一个顶点可能相同，==其他各顶点不相同==
    简单回路：简单路径上第一个顶点和最后一个相同
  • 子图
  • 连通图：==无向图==中任意两个定点对是连通的
    连通分量：无向图的==极大==连通分量
  • 强连通图：==有向图==中任意两顶点对是连通的
    强连通分量：有向图的==极大==连通分量
  • 连通图的生成树：==极小连通子图==，该连通子图包含连通图的所有n个顶点和它的n-1条边，如果去掉一条边，这个子图将不连通，如果增加一条新的边，加上新加的这条边便形成了回路，有回路就不再是树。连通图的生成树不唯一。

图的存储和操作

邻接矩阵

  • 用一维数组存储顶点，n行n列矩阵（二维数组）存储边
  • 对角线为0：不存在自环
  • 无向图邻接矩阵按对角线对称
  • 有向图中，每一行1的个数为出度，每一列1的个数为入度
    无向图中，每一行或每一列1的个数为度，存储无向图可以只存储上三角或下三角矩阵
  • ==空间消耗大==
  • 带有权值：对应位置数值为权值，==对角线元素数值为0==，若两点间没有边项链，该处值为$\infty$

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 带权值的邻接矩阵 数组实现
// 默认点和权值的数据类型为int

class Graph{
	public:
	int verts,edges;
	int *verlist;
	int **edgematrix;
	int noedge;
	int maxnum;
	bool directed;
	
	public:
	Graph(int e){
		noedge=e;
		verts=0;
		edges=0;
		
		verlist=new int [maxnum];
		edgematrix=new int* [maxnum];
		
		for(int i=0;i<maxnum;i++){
			edgematrix[i]=new int [maxnum];
		}
		for(int i=0;i<maxnum;i++){
			for(int j=0;j<maxnum;j++){
				if(i==j) edgematrix[i][j]=0;
				else edgematrix[i][j]=noedge;
			}
		}
	}
	
	~Graph(){
	delete verlist;
	for(int i=0;i<maxnum;i++){
		delete [] edgematrix[i];
	}
	delete edgematrix;
	}
	
	//判断两个定点之间是否有边
	bool existedge(int vertex1,int vertex2){
		//找到下标
		int i,j;
		for (i=0;i<maxnum;i++){
			if (verlist[i]==vertex1) break;
		}
		for (j=0;j<maxnum;j++){
			if (verlist[j]==vertex1) break;
		}
		if(i==maxnum || j==maxnum || i==j) return false;
		if(edgematrix[i][j]==noedge) return false;
		return true;
	}
	
	void remove (int vertex){
		int i, j, k;
		for (i = 0; i < verts; i++) 
			if (verList[i] == vertex) break; 
		if (i == verts) return; 
		for (j = i; j < verts - 1; j++) 
			verList[j] = verList[j + 1]; 
		for (j = 0; j < verts; j++) 
			if ((j != i) && (edgeMatrix[i][j] != noEdge)) edges--; 
			
		if (directed) {
			for (k = 0; k < verts; k++) {
				if ((k != i) && (edgeMatrix[k][i] != noEdge)) edges--; 
			}
		}
		for (j = i; j < verts - 1; j++) {
			for (k = 0; k < verts; k++) 
				edgeMatrix[j][k] = edgeMatrix[j + 1][k];
		}
		for (j = i; j < verts - 1; j++) {
			for (k = 0; k < verts; k++)
				edgeMatrix[k][j] = edgeMatrix[k][j + 1];
		}
		verts--;
	}

}

2.2 邻接表

  • 对于无向图，邻接于同一个顶点的所有边形成一条单链表
  • 对于有向图，自同一个顶点出发的所有边形成一条单链表
  • 顶点信息可以用一个一维数组来存储，这个数组称为顶点表，保存边信息的单链表称为边表
  • 一个图可以由顶点表和边表共同表示，这种方法称为邻接表表示法

逆邻接表：对于有向图，射向同一个顶点的所有边形成一条单链表

3. 图的遍历

3.1 深度优先遍历 DFS

  1. 选中第一个未被访问过的顶点
  2. 访问、对顶点加已访问标志
  3. 依次从顶点的未被访问过的第一个、第二个、第三个…… 邻接顶点出发，依次进行深度优先搜索。即转向2
  4. 如果还有顶点未被访问过，选中其中一个作为起始顶点，转向2
  5. 如果所有的顶点都被访问到，结束

递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template <class edgeType>
struct edgeNode {
    int dest;                    // 邻接顶点的编号（在verList中的索引）
    edgeType weight;             // 边的权值（如果是带权图）
    edgeNode<edgeType> *link;    // 指向下一条边的指针
    
    edgeNode() : link(NULL) {}
    edgeNode(int d, edgeType w, edgeNode<edgeType> *l = NULL) : dest(d), weight(w), link(l) {}
};

template <class verType, class edgeType>
struct vertexNode {
    verType data;                  // 顶点存储的数据
    edgeNode<edgeType> *adj;       // 指向第一条边的指针
};

template <class verType, class edgeType>
void Graph<verType, edgeType>::DFS(int start, bool visited[]) const
{ 
	edgeNode<edgeType> *p;
  	cout<<verList[start].data<<'\t’; 	
	visited[start] = true; 
	p = verList[start].adj;
	while (p){ 
		if (!visited[p->dest]) 
			DFS(p->dest, visited);
		p = p->link;
	}
} 

template <class verType, class edgeType>
void Graph<verType, edgeType>::DFS() const { 
	bool *visited; int i;
	visited = new bool[verts]; 
	if (!visited) throw illegalSize();
	for (i=0; i<verts; i++) visited[i]=false;
	for (i=0; i<verts; i++){ 
	    if (!visited[i]) DFS(i, visited);
		cout<<endl; 
    } 
}

非递归算法：
选一个顶点进栈，然后反复进行以下操作：
如果栈不空，弹出访问，第一个未被访问的邻接点进栈，第二个未被访问的邻接点进栈，⋯，最后一个未被访问的邻接点进栈。（类似二叉树的前序遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template <class verType, class edgeType>
void Graph<verType, edgeType>::DFS()const { 
	seqStack<int> s;
	edgeNode<edgeType> *p; 
	bool *visited; 
	int i, start;
	
	visited = new bool[verts]; 
	if (!visited) throw illegalSize();
	for (i=0; i<verts; i++) {
		visited[i]=false;
    }

	for (i=0; i<verts; i++){ 
		if (visited[i]) continue;
		s.push(i);
	  	while (!s.isEmpty()) { 
			start = s.top();
			s.pop();
			if (visited[start]) continue;
			cout<<verList[start].data<<'\t’;
			visited[start] = true;
			p = verList[start].adj;
			while (p) { 
				if (!visited[p->dest]) s.push(p->dest);
				p = p->link;
			}
		}
		cout<<'\n’;
	}
}

如果图用邻接表存储，栈可以不保存顶点，而是保存边结点地址

因为每个顶点射出的所有边都在各自用单链表表示的边表中，不需要把访问顶点的所有相邻顶点进栈，只需要将该顶点在边表中的一条其dest顶点未被访问的边结点地址进栈，它出栈时，根据边结点中link字段找下一条其dest顶点未被访问的边，如果有，将它进栈，这样便可保证同一弧尾顶点的所有邻接点可以被一个个挨着查验过去

如果图用邻接矩阵存储，访问完顶点i，可从第0列开始逐列检查；如果遇到第一个有边且顶点j未被访问过，将描述边位置的两元组(i,j)进栈；它出栈时，让第i行第j列后第一个有边且j+m顶点未被访问过的两元组(i,j+m)进栈即可

3.2 广度优先遍历 BFS

  1. 选中第一个未被访问的顶点
  2. 访问、对顶点置已访问过的标志
  3. 依次对顶点的未被访问过的第一个、第二个、第三个……第 m 个邻接顶点 W1 、W2、W3…… Wm 进行访问且进行标记
  4. 依次对顶点 W1 、W2、W3…… Wm 转向操作3
  5. 如果还有顶点未被访问，任选其中一个顶点作为起始顶点，转向2
  6. 如果所有的顶点都被访问到，遍历结束
    （类似二叉树的层次遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template <class verType, class edgeType>
void Graph<verType, edgeType>::BFS()const{ 
	seqQueue<int> q; 
	edgeNode<edgeType> *p;
	bool *visited; 
	int i, start;

	visited = new bool[verts];
	if (!visited) throw illegalSize();
	for (i=0; i<verts; i++) visited[i]=false;

	for (i=0; i<verts; i++){ 
		if (visited[i]) continue;
		q.enQueue(i);
	  	while (!q.isEmpty()) { 
			start = q.front(); 
			q.deQueue();
			if (visited[start]) continue;
			cout<<verList[start].data<<'\t’;
			visited[start] = true;
			p = verList[start].adj;
			while (p) {
				if (!visited[p->dest]) q.enQueue(p->dest);
				p = p->link;
			}
		}
		cout<<'\n’;
	}
}

4. 图的连通性

4.1 无向图的连通性

在深度优先、广度优先遍历算法中增加一个计数器，记录外循环体中，进入内循环的次数，根据次数可以判断出该图是否连通、如果不连通有几个连通分量、每个连通分量包含哪些顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template <class verType, class edgeType>
bool Graph<verType, edgeType>::connected()const { 
	seqQueue<int> q; 
	edgeNode<edgeType> *p;
	bool *visited; 
	int i, start, count=0; //count为计数器
 
	visited = new bool[verts];
	if (!visited) throw illegalSize();
	for (i=0; i<verts; i++) visited[i]=false;

	for (i=0; i<verts; i++) { 
		if (visited[i]) continue;
		q.enQueue(i); 
		count++; 
		while (!q.isEmpty()){ 
			start = q.front(); 
			q.deQueue();
			if (visited[start]) continue;
			cout<<verList[start].data<<'\t’;
			visited[start] = true;
	  		p = verList[start].adj;
			while (p) { 
				if (!visited[p->dest]) q.enQueue(p->dest);
				p = p->link;
			}
		}
		cout<<'\n’;
	}
	if (count==1) return true;
	return false; 
}

4.2 有向图的连通性

当有向图的强连通分量只有一个时，说明它是强连通图；当有向图的强连通分量不止一个时，说明它不是强连通图。对一个强连通分量来说，要求每一对顶点间都有路径可达，比如顶点i和j，不光要从i能到j，还要求从j能到i。

方法：

  1. 对有向图G进行深度优先遍历，按照遍历中回退顶点的次序给每个顶点进行编号。最先回退的顶点的编号为1，其它顶点的编号按回退先后逐次增大1
  2. 将有向图G的所有有向边反向，构造新的有向图Gr
  3. 根据步骤1对顶点进行的编号，选取未访问过的最大编号顶点
  4. 以该顶点为起始点在有向图Gr上进行深度优先遍历
  5. 如果没有访问到所有的顶点，则从剩余的那些未被访问过的顶点中选取编号最大的顶点，以该顶点为起始点再进行深度优先遍历，如此反复，直至所有的顶点都被访问到

4.3 欧拉定理

  • 如果图中一条路径经过了每条边一次且仅一次，这条路径称欧拉路径

  • 如果一条欧拉路径的起点和终点相同，是一个回路，称欧拉回路

  • 具有欧拉回路的图称欧拉图(简称E图)

  • 具有欧拉路径但不具有欧拉回路的图称半欧拉图

  • 一个无向连通图中，如果度为奇数的顶点超过了2个，则欧拉路径是不存在的

  • 一个无向连通图中，如果除了两个顶点的度是奇数而其他顶点的度都是偶数，则从一个度为奇数的顶点出发一定能找到一条经过每条边一次且仅一次的路径回到另外一个度为奇数的顶点

  • 一个无向连通图中，如果顶点的度都是偶数，则从任意一个顶点出发都能经过每条边一次且仅一次并回到原来的顶点

求解欧拉回路：

  1. 任选一个顶点v，从该顶点出发开始深度优先搜索，搜索路径上都是由未访问过的边构成，搜索中访问这些边，最后直到回到顶点v且v没有尚未被访问的边，此时便得到了一个回路，此回路为当前结果回路
  2. 在搜索路径上另外找一个尚有未访问边的顶点，继续如上操作，找到另外一个回路，将该回路拼接在当前结果回路上，形成一个大的、新的结果回路
  3. 如果在新的结果回路中，还有中间某结点有尚未访问的边，回到2；如果没有任何中间顶点尚余未访问的边，访问结束，当前结果回路即欧拉回路

5. 最小代价生成树

6. 最短路径（代码）

6.1 单源最短路径（ Dijkstra 算法）

加权有向图中，每个点权值非负，V中的一个顶点作为源点，要求找出从源点出发到达其它各个顶点的最短路径

每个顶点设置一个距离标签，标识源点到该顶点的最短距离；设置一个顶点集合S，作为已经确定最短路径的顶点集合。
初始时，S置为空且将每个顶点到源点的距离标签置为无穷大。
将源点放入S中，源点的距离标签设置为0，现在以源点作为当前顶点，循环做以下操作：

  1. 沿当前顶点射出的各条边找到其每个邻接点，如有邻接点A，如果当前顶点的距离标签加上其到达顶点A的边的权值小于顶点A上的距离标签，则用当前顶点的距离标签加上边的权值刷新顶点A上的距离标签。
  2. 下一步，在V-S集合中找到距离标签最小的顶点，将该顶点放入S中，并以它为当前顶点，再次进入循环。当所有顶点都进入S时，循环结束。每个顶点上的距离标签即源点到这个顶点的最短距离。

特殊情况：
假如图中边无权值，将每一条边的权值都视作1，用上述的Dijkstra 算法就可以求出。
另外一种方法是从源点出发，使用广度优先遍历的方法遍历顶点，顶点遍历时就是其获得最短距离的机会，其最短距离为遍历时其直接前驱顶点的最短距离加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
template <class edgeType>
struct DijkstraNode{
	int source; //当前最短路径上前一顶点
	int dist; //当前最短路径距离
	bool selected; //顶点是否已经在S中的标志
};

template <class verType, class edgeType>
void Graph<verType, edgeType>::Dijkstra (verType start) const{
	DijkstraNode<edgeType> *DList;
	int i, j, startInt;
	int cnt; //记录集合U中顶点的个数
	int min; //选出的当前离集合最短的顶点
	int dist;

	//查找起始点下标
	for (i=0; i<verts; i++) 
		if (verList[i] == start) break;
		if (i==verts) return;
  
	//创建空间并初始化DList[i]数组
	startInt = i; 
	DList = new DijkstraNode<edgeType> [verts];
	
	for (i = 0; i < verts; i++){
		DList[i].source = -1;
		DList[i].dist = noEdge;
		DList[i].selected = false;
	}
	// 从下标为startInt的点开始
	min = startInt;
	cnt = 1;
	DList[startInt].source = startInt;
	DList[startInt].dist = 0;
	DList[startInt].selected = true;
	
	while (cnt < verts){ 
	// 根据min顶点发出的边，判断是否修正相邻顶点的最短距离
		for (j = 0; j < verts; j++){
			if (edgeMatrix[min][j] == 0) continue; // 对角线元素
			if (DList[j].selected) continue; // 已经加入集合S
			if (edgeMatrix[min][j] == noEdge) continue; // 无边
			if (DList[min].dist + edgeMatrix[min][j] < DList[j].dist){
				DList[j].dist = DList[min].dist + edgeMatrix[min][j];
				DList[j].source = min;
			}
		}
		min = -1;
		dist = noEdge;
		for (i = 0; i < verts; i++){
			if (DList[i].selected) continue;
			if (DList[i].dist < dist){
				min = i;
				dist = DList[i].dist;
			}
		}
	//此时min一定为某个顶点的下标，如果仍然为-1表示该无相图不连通
	//将顶点min加入集合S
		cnt++;
		DList[min].selected = true;
	} 
	// 如果图用邻接矩阵来存储，可以看出时间复杂度为O(n^2)。
}

6.2 顶点对间最短路径（ Floyd 算法）

对任意两个顶点对<i,j>，在顶点对之间增加另外一个顶点k，观察增加后的路径i-k-j距离是否比原本i到j间的距离更小:如果是，就用新的路径、距离替代原本两个顶点间的路径、距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template <class verType, class edgeType>
void Graph<verType, edgeType>::Floyd() const{
	int i, j, k;
	edgeType **A; // 数组A[i][j]记录顶点i到j间的最短距离
	int **pre; // 数组pre[i][j]记录顶点对i到j的最短路径中的中介顶点，
	// 创建动态数组floyd和path
	A = new edgeType *[verts];
	pre = new int *[verts];
	for (i = 0; i < verts; i++){
	A[i] = new edgeType[verts];
	pre[i] = new int[verts];
	}
	//初始化数组floyd和path
	for (i = 0; i < verts; i++) 
		for (j = 0; j < verts; j++){
			A[i][j] = edgeMatrix[i][j];
			pre[i][j] = -1;
		}
	// 迭代计算A数组
	for (k = 0; k < verts; k++){
		for (i = 0; i < verts; i++){
			if (i == k) continue; // 避开加A[i][i]
			for (j = 0; j < verts; j++){
				if ((j == k) || (j == i)) continue; // 避开加A[j][j]和A[i][i]
				if (A[i][j] > (A[i][k] + A[k][j])){
					A[i][j] = A[i][k] + A[k][j];
					pre[i][j] = k;
				}
			}
		}
	}
}

求单源最短路径的Dijkstra算法，是一个贪心算法。一旦一个顶点的距离最短，就将之作为最终源点到该顶点的最短距离，所以Dijkstra算法不支持边上带有负权值的情况。
Floyd算法可以允许带有负权值的边，但==不允许出现带有负权值的边出现在回路且回路中各边的和为负值的情况.==

7. AOV网和AOE网

7.1 AOV网 拓扑排序

AOV网将活动赋予顶点之上，顶点间的有向边表示活动发生的先后顺序，表达了活动之间的前后关系。 AOV网的一个典型应用是课程的先修关系
在一个集合X中，若关系R有如下特点： 关系R是传递的、自反的、反对称的，就称R是集合X上的偏序关系
若集合X上关系R是一个偏序关系，且对于每个a, b∈X，必有aRb或bRa，就称R是集合X上的全序关系
实数轴上的实数集合，以及集合上的≤关系，是实数集合上的全序关系
对集合X上的一个偏序关系R，通过将集合中原本不满足R关系的所有元素对人为地补充设定拥有R关系，从而将R改变为集合X上的一个全序关系，并按照此全序关系将元素排成一个线性序列
在这个线性序列$𝑎_1 、𝑎_2 、…、𝑎_𝑛$中，如果偏序关系中$𝑎_𝑖$ R $𝑎_𝑗$，必有i≤j，这个序列称为拓扑序列，获得拓扑序列的操作称为拓扑排序
一个有向无环图（DAG），反映了课程的先修关系。图中顶点代表了课程，课程之间用有向边相连，是一个偏序关系。现在通过拓扑排序安排一张课程先后次序表，使得所有课程排成一个线性序列。这时的先修关系就是这组课程集合上的一个全序关系，这个线性序列就是原本图中表达的关系的一个拓扑序列。

算法：
首先在图中，找到入度为0的顶点，将这些顶点全部入栈，然后反复循环判断栈是否空，非空则执行以下操作：顶点出栈，如果由该顶点射出了m条有向边，射入的这m个邻接点的入度减一（相当于该顶点对其m个邻接顶点的先修约束已经消失），在各邻接点入度减一的过程中，一旦发现哪个邻接点的入度变为0，将它进栈，然后再次回到循环，直到栈空。

算法的时间代价是$O(n^2)$
如果图用邻接表来存储，时间代价为O(n+e)

7.2 AOE网 关键路径

AOE网将活动赋予边之上，顶点表达了活动发生后到达的某种状态或事件。某个状态或事件既意味着前面所有的活动结束，也意味着后面的活动可以开始。AOE网的一个典型应用是工程问题。

求每个顶点事件的最早发生时间，即从起点到达顶点所需要的最短时间
求每个顶点事件的最迟发生时间，即从起点到达顶点所能容忍的最长时间
当某活动的最早开始时间和最迟开始时间相同时，这些活动便是关键活动

如果一个工程终点的最早时间已知，这个最早时间就是工程需要的总的最短工期，为了达到这个工期目标，可以设定这个时间就是终点事件的最迟发生时间，然后对余下的顶点倒推回去，可以获得其余顶点事件的最迟发生时间

算法的时间代价是$O(n^2)$

http://chenjiayi0505.github.io/2026/07/02/数据结构 第五章 图/
作者
Jiayi Chen
发布于
2026年7月2日
更新于
2026年6月23日
许可协议