浙大数据结构第六讲图（上）

2023-10-08 17:49:16

6.1 什么是图

图表示“多对多”的关系

图包含：

一组顶点：通常用V(Vertex)表示顶点集合
一组边：通常用E(Edge)表示边的集合
边是顶点对：(v,w)∈E，其中v,w ∈ V
有向边<v,w>表示从v指向w的边（单行线）
不考虑重边和自回路

抽象数据类型定义

类型名称：图（Graph）
数据对象集：G（V,E）由一个非空的有限顶点集合V和一个有限边集合E组成。
操作集：对于任意图G ∈ Graph，以及v ∈ V，e ∈ E

Graph Create();//建立并返回空图
Graph InsertVertex(Graph G,Vertex V);//将一个顶点v插入G
Graph InsertEdge(Graph G,Edge e);//将一条边e插入G
void DFS(Graph G,Vertex V);//从顶点V出发优先遍历图G
void BFS(Graph G,Vertex V);//从顶点V出发宽度优先遍历图G
void ShortestPath(Graph G,Vertex V,int Dist[]);//计算图G中顶点v到任意其他顶点的最短距离
void MST(Graph G);//计算图G的最小生成树

怎么在程序中表示一个图

邻接矩阵

邻接矩阵——有什么好处？

直观、简单、好理解
方便检查任意一堆顶点间是否存在边
方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
无向图：对应行（或列）非0元素的个数
有向图：对应行非0元素的个数是“出度”，对应列非0元素的个数是“入度”

邻接矩阵——有什么坏处？

浪费空间——存稀疏图（点很多而边很少），有大量无效元素，但对稠密图（特别是完全图）还是很合算的
浪费时间——统计稀疏图中一共有多少条边

邻接表

邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素

好处：

方便找任一结点的所有“邻接点”
节约稀疏图的空间：需要N个头指针 + 2E个结点（每个结点至少2个域）
方便计算无向图中任一结点的“度”

不足：

对无向图，只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”
不方便检查任意一对顶点间是否存在边

课后练习

6.2 图的遍历

深度优先搜索（Depth First Search，DFS）

例题引入：点亮视线范围内的一盏灯，当视线内的灯全部点亮时原路返回

void DFS(Vertex V)
{
	visited[V] = true;
	for(V的每个邻接点W)
		if(!visited[W]) DFS(W);
}

若有N个顶点、E条边，时间复杂度是
用邻接表存储图，有O（N+E）
用邻接矩阵存储图，有O（N^2）

广度优先搜索（Breadth First Search，BFS）

与树的层序遍历思路类似

void BFS(Vertex V)
{
	visited[V] = true;
	Enqueue(V,Q);
	while(!Isempty(Q))
	{
		V = Dequeue(Q);
		for( V 的每个邻接点 W )
			if(!visited[W])
			{
				visited[W] = true;
				Enqueue(W,Q);
			}
	}
}

若有N个顶点、E条边，时间复杂度是
用邻接表存储图，有O（N+E）
用邻接矩阵存储图，有O（N^2）

两种遍历方法的比较

讨论6.2 把迷宫出口换到哪里就该BFS不爽了？
右下角。BFS需要访问几乎所有节点才可以访问到出口。

总结

BFS是围绕某个点一层一层的进行遍历，借助队列的数据结构实现。
DFS是从一个点出发一直往深处遍历，条件不符就折返，通过栈的数据结构实现。
在正常情况下二者的时间复杂度都是相同的O（v+e），但是在内存的使用上BFS由于要使用队列存储所有的外层节点，所以内存消耗相对较大。

从宏观上来看：
如果你已经知道解离根节点比较近，那么BFS更好
如果整体上每个节点的边很多，那么BFS消耗的内存会很大
如果一棵树很深而解很少，那么DFS可能会很慢（相反如果解很多并且都比较深的话，那么BFS就会很慢）从名字上就很容易得出，
如果一个问题深度无穷而广度有限，那么DFS就没法获得解，但BFS可以，反之也同理。
BFS具有时间优势，因为它不用走回头路，DFS具有空间优势，因为同等情况下，DFS只保存了这一条路线的数据

图连不通怎么办？

连通： 如果从v到w存在一条（无向）路径，则称v和w是连通的。
路径： v到w的路径是一系列顶点{V,v1,v2,...,vn,W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果v到w之间的所有顶点都不同，则称简单路径
回路：起点等于终点的路径
连通图：图中任意两顶点均连通
连通分量：无向图的极大连通子图
极大顶点数：再加1个顶点就不连通了
极大边数：包含子图中所有顶点相连的所有边

对于无向图
强连通： 有向图中顶点V和W之间存在双向路径，则称V和W是强连通的
强连通图：有向图中任意两顶点均强连通
强连通分量：有向图的极大强连通子图

后两个图为G的强连通分量

ListComponents能够遍历不连通的图上所有结点

练习题

小白专场：建立一个图

建立邻接矩阵图

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef struct GNode* PtrToGNode;
typedef struct ENode* PtrToENode;
typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型
typedef PtrToENode Edge;
typedef int WeightType;
typedef int Vertex;
const int MaxVertexNum = 100;
struct GNode
{
	int Nv;//顶点数
	int Ne;//边数
	WeightType G[MaxVertexNum][MaxVertexNum];
};
struct ENode
{
	Vertex V1, V2;//有向边<V1,V2>
	WeightType Weight;//权重
};

MGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for (int V = 0;V < Graph->Nv;V++)
	{
		for (int W = 0;W < Graph->Nv;W++)
		{
			Graph->G[V][W] = 0;
		}
	}
	return Graph;
}
void InsertEdge(MGraph Graph, Edge E)
{
	Graph->G[E->V1][E->V2] = E->Weight;
	Graph->G[E->V2][E->V1] = E->Weight;//若是无向图，还要插入边<V2,V1>
}
MGraph BuildMGraph()
{
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	scanf("%d", &Graph->Ne);
	if (Graph->Ne != 0)
	{
		E = (Edge)malloc(sizeof(struct ENode));
		for (i = 0;i < Graph->Ne;i++)
		{
			scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
			InsertEdge(Graph, E);
		}
	}
	/*如果顶点有数据的话，读入数据
	for (int V = 0;V < Graph->Nv;V++)
		scanf(" %c", &Graph->Data[V]);*/
	return Graph;
}

简化版（考试专用）

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int MAXN = 1000;
int G[MAXN][MAXN], Nv, Ne;
void BulidGraph()
{
	scanf("%d", &Nv);
	for (int i = 0;i < Nv;i++)
		for (int j = 0;j < Nv;j++)
			G[i][j] = 0;
	scanf("%d", &Ne);
	int v1, v2, w;
	for (int i = 0;i < Ne;i++)
	{
		scanf("%d %d %d", &v1, &v2, &w);
		G[v1][v2] = 1;
		G[v2][v1] = 1;
	}
}

码农公寓