图
一.思维导图
（PowerPoint制作画面小，字体较小将就观看）
二.图的知识内容
1.图的基本概念
1.1图的定义
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成。通常表示为:G(V,E),G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
无向图
如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
有向图
如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。
1.2图的基本术语
端点和邻接点：两顶点为一条边的端点时，这两点互称为邻接点。
顶点的度、入度和出度：在无向图中，一个顶点所关联的边的数目称为该顶点的度(degree)。在有向图中,顶点度又分为入度和出度,以顶点j为终点的边数目,称为该顶点的入度(indegree)。以顶点i点的边数目,称为该顶点的出度(outdegree)。一个顶点的入度与出度的和为该顶点的度。（一个图中所有顶点的度之和等于边数的两倍）
完全图：若无向图中的每两个顶点之间都存在着一条边,有向图中的每两个顶点之间都存在着方向相反的西条边称此图为完全图(completed graph)。显然,无向完全图包含有n（n-1）/2条边，有向图包含有你n（n-1）条边。
稠密图和稀疏图：当一个图接近完全图时,称为稠密图(dense graph),相反,当一个图含有较少的边数(如e<nlog2n)时,则称为稀疏图(sparse graph)。
子图：设有两个图G=(V,E)和G'=(V,E'),若V'是V的子集,即V'包含于V,且E是E的子集即E'包含于E,则称G'是G的子图(subgraph)。
路径和路径长短：设图G=(V，{E})中的一个顶点序列{u=Fi0,Fi1,Fi2,….Fim=w}中，(Fi,j-1,Fi,j)∈E 1 ≤j ≤m,则称从顶点u到顶点w之间存在一条路径，路径上边或弧的数目称作路径长度，
若路径中的顶点不重复出现的路径称为简单路径
若路径中第一个顶点到最后一个顶点相同的路径称为回路或环
若路径中第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
回路或环：若一条路径上的开始点与结束点为同一个顶点,则此路径被称为回路或环(cycle)。开始点与结束点相同的简单路径被称为简单回路或简单环(simple cycle)。
联通、连通图和联通分量：
连通图
在无向图G(V,{E})中，如果从顶点V到顶点W有路径，则称V和W是连通的。如果对于图中任意两个顶点Vi、Vj∈V,Vi和Vj都是连通的，则称G是连通图。
连通分量
若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。
强连通图和强联通分量：
强连通图
在有向图G(V,{E})中，如果对于每一对Vi ,Vj∈V,Vi≠Vj,从Vi到Vj和从Vj到Vi都存在有向路径,则称G是强连通图。（n个顶点强联通图至少有n条边）
强连通分量
若有向图不是强连通图，则图中各个极大强连通子图称作此图的强连通分量。
权和网：图中的每一条边都可以附有一个对应的数值,这种与边相关的数值称为权。权可顺示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图(weihgraph),也称作网(net)。
2.图的存储结构和基本运算算法
2.1邻接矩阵存储方法
如下图（老师课件）
/*图的邻接矩阵存储*/
typedef int VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFI 65535
typedef struct
{
VertexType vexs[MAXVEX]; /*顶点表*/
EdgeType matrix[MAXVEX][MAXVEX]; /*邻接矩阵*/
unsigned int numVertexes; /*顶点数*/
unsigned int numEdges; /*边数*/
}Graph;
2.2邻接表存储方式
如下图（老师课件）
2.3图的基本运算算法设计
创建图的运算算法
输出图的运算算法
销毁图的运算算法
代码详见课本260页。
3.图的遍历
3.1图的遍历概念
图建构好后，针对具体的问题，我们常常需要通盘的读取图中的信息，包括顶点（vertex）和边（edge），以及它们之间的关系。这种读取图中所有信息的方法就是图的遍历（traversal），也称为搜索（search），就是从图中某个顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次。遍历是很多图论算法的基础。根据搜索方法的不同，图的遍历分为两种：深度优先遍历（DFS）、广度优先遍历（BFS）。
3.2深度优先遍历和广度优先遍历
遍历需要图形结合来理解，为了更好理解推荐一篇遍历链接给你们
遍历链接
个人理解：深度遍历一个节点接一个节点遍历，不遍历已遍历过的节点。广度遍历先从初始点出发，连接他的节点都要遍历，然后遍历连接初始点的节点的节点，依此类推。
4.生成树和最小生成树
4.1生成树的概念
在一个任意连通图G中，如果取它的全部顶点和一部分边构成一个子图G'，即：V（G'）=V（G）和E（G'）⊆E（G）
若同时满足边集E（G'）中的所有边既能够使全部顶点连通而又不形成任何回路，则称子图G'是原图G的一棵生成树。
4.2无向图的联通分量和生成树
详见课本280页。
4.3普里姆算法、克鲁斯卡尔算法
普里姆算法：适用于稠密
克鲁斯卡尔算法：适用于稀疏
我觉得这篇博客不错，很好理解，复习用的上。
算法链接
5.最短路径
5.1路径的概念
在一个不带权图中,若从一顶点到另一顶点存在着一条路径,则称该路
径长度为该路径上所经过的边的数目,它等于该路径上的顶点数减1。由
于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同,即路径长度不同,把路径长度最短(即经过的边数最少)的那条路径称为最短游(shortest path),其长度称为最短路径长度或最短距离。对于带权图,考虑路径上各边上的权,则把一条路径上所经边的权之和定义为该路制路径长度。从源点到终点可能有不止一条路径,把路径长度最小的那条路径称为最短路径其路径长度(权之和)称为最短路径长度。实际上,只要把不带权图上的每条边看成是权值为1的边,那么不带权图和带权图的最短路径和最短距离的定义就一致了。
5.2从一个顶点到其余各顶点的最短路径
Dijkstra算法介绍
算法特点：
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
算法的思路
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
原文链接，很详细
5.3每对顶点之间的最短路径
6.AOE网与关键路径
6.1相关概念
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称之为AOE网（Activity On edge Network)。由于一个工程，总有一个开始，一个结束，在正常情况下，AOE网只有一个源点一个汇点。入度为零的为开始事件，出度为零的为结束事件，关键活动不存在富余时间，一个AOE网可能存在多个关键路径，但是他们的长度相同。
6.2求AOE网的关键活动
详见课本的306页（讲解困难，能力不足）。
三.疑难问题
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40
include<bits/stdc++.h>
using namespace std;
#define INF 65535
struct Node {
int len, price;
};
int N, M, S, D, Dist[505], Price[505] = {0};
Node G[505][505];
bool visit[505] = {false};
int main() {
cin >> N >> M >> S >> D;
int v, u, l, p;
fill(Dist, Dist + N, INF);
fill(Price, Price + N, INF);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
G[i][j].len = INF;
G[i][j].price = INF;
}
for (int i = 0; i < M; i++) {
cin >> v >> u >> l >> p;
G[v][u].len = G[u][v].len = l;
G[v][u].price = G[u][v].price = p;
}
Dist[S] = 0;
Price[S] = 0;
for (int i = 0; i < N; i++) {
int V = -1, Min = INF;
for (int j = 0; j < N; j++) {
if (Dist[j] < Min && !visit[j]){
V = j;
Min = Dist[j];
}
}
if (V == -1) break;
visit[V] = true;
if (V == D) {
cout << Dist[V] << " " << Price[V];
break;
}
for (int j = 0; j < N; j++) {
if (!visit[j] && Dist[V] + G[V][j].len < Dist[j]) {
Dist[j] = Dist[V] + G[V][j].len;
Price[j] = Price[V] + G[V][j].price;
} else if (!visit[j] && Dist[V] + G[V][j].len == Dist[j]) {
if (Price[j] > Price[V] + G[V][j].price) Price[j] = Price[V] + G[V][j].price;
}
}
}
return 0;
}
总结，要解出一道题，要有身厚的功底，不懂的知识要及时看书，实在不懂csdn辅助理解，同学一起解决。
本题要用到dijstra算法，Dijkstra的本质就是如果收录v使得s到w的距离变短，则s到w的最短路一定经过v。
本题要注意：储存图的时候节点编号从1开始。
邻接矩阵储存的图。
初始化时把每个节点初始化成最远距离。