图的基本常识
图表现的是多对多的关系（链表表现的是一对一的关系，而树表现的是一对多的关系，树是图的特例）。图中储存数据元素的结构体称为顶点（通常用Vi表示）；从一个顶点到另一顶点所经过的所有顶点组成的序列称作一条 路径；将顶点连接起来的线称作 边（有向图中称作弧）；图分为有向图和无向图，有向图中每条路径都是有方向的，且构成路径的序列顺序沿弧的方向排列，不可反向，就像单行路不可逆行一样。无向图中描述两顶点V1 和 V2之间的关系可以用 (V1,V2) 来表示，而有向图中描述从V1到V2的单向关系用 < V1,V2 >表示；权表示某边（弧）在图中的重要程度，就像路线图中有主干通道和小路一样，权通常标在边上；带权的图称作 网。
图的基本操作
首先准备工作： #include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;
const int MAX = 20; // 常量：最多顶点数，用来分配数组长度
const int INF = 99999; // 常量：无限大,带权图中表示不邻接的两顶点的距离
typedef char T; // 元素类型
图的邻接表储存
图是一个多对多的关系，那么如何将图中的各个顶点储存并且可以表现顶点与顶点之间的关系呢？
这里我们介绍邻接表的储存方式：
将图的所有顶点储存在一个结构体数组中，每个顶点结构体包括顶点数据和一个指向顶点邻接顶点的指针域，而邻接顶点结点包括邻接顶点的数据和指向下一个邻接结点的指针，这样一来一个顶点的所有邻接顶点就构成了一个链表。此种储存方式中，通过顶点构成的数组的下标可以不重复地找到所有顶点，而每个顶点的邻接顶点可以通过顶点的指针域指向的链表找到，这样既可以得到所有顶点的数据又可以很清晰地表示顶点与顶点之间的关系。邻接表适合稀疏图。
代码：
//先定义边表的边结点类型ArcNode
struct ArcNode
{
int adjV; // 邻接点的编号
float weight; //边的权,本程序并未使用
ArcNode *nextArc;
};
// 再定义顶点结点 和邻接表类型
typedef
struct VNode
{
T data; // 顶点数据
ArcNode *firstArc; // 链表的头指针,此点的所有邻接边构成的链表
} AdjList[MAX]; // 顶点结点的顺序表(数组)即为邻接表类型：AdjList
// 最后定义邻接表表示图的存储结构ALGraph
typedef
struct
{
AdjList vertices; // 邻接表
int vexnum,arcnum; // 定点数和边数
int kind; // 图的类型:有向、无向、带权.(本程序未使用)
} ALGraph;
/** 从名为fn的文件中读取数据,生成并返回邻接表所表示的图 (为简便，本程序只盘有向图)
数据的格式说明见数据文件*/
ALGraph crateGraph(char* fn)
{
ifstream ifs(fn);
ALGraph alg;
ifs>> alg.vexnum >> alg.arcnum; // 读入顶点数和边数
/* 读入并存储顶点,初始边链表为空*/
for(int i=1; i<=alg.vexnum; i++)
{
ifs >> alg.vertices[i].data;
alg.vertices[i].firstArc = 0; // 空链表
}
/* 存储输入的边*/
int i,j;
for(int k=1; k<=alg.arcnum; k++)
{
/*输入<i,j>边,则在第i个链表头插入一个边结点(adjV为j）*/
ifs >> i >> j ;
ArcNode *p = new ArcNode;
p->adjV = j;
// 链表头部插入结点,更方便. alg.vertices[i].firstArc是第i个链表的头指针
p->nextArc = alg.vertices[i].firstArc;
alg.vertices[i].firstArc = p;
}
return alg;
}
图的遍历
图的遍历分为两种：基于深度优先搜索（DFS）的遍历和基于广度优先搜索的遍历（WFS），下面我们将一一介绍。深搜（DFS）
大概思路：图的深搜类似于树的前序遍历，先访问一个未被访问过的顶点，访问它的一个邻接顶点，访问邻接顶点的一个邻接顶点，将访问过的顶点标记，若遇到访问过的顶点则回到上一个顶点，访问上一个顶点的另一个邻接顶点，直到所有的相邻的顶点均被访问。从上述可以看出，深搜可以将所有连续相邻的顶点访问到，如果是连通图一次深搜就可以将所有顶点访问到，而对于非连通图一次深搜是不能将所有顶点都访问到。
连接表分析：
eg：对于
初始时所有顶点都未被访问过，则访问过程如下：
- 从A开始，在顶点数组中找到A，访问A，标记A，在A的边链表中找到A的邻接顶点B
- 在顶点数组中找到B，访问B，标记B，在B的边链表中找到B的邻接结点C
- 在顶点数组中找到C，访问C，标记C，在C的边链表中找到C的邻接结点A
- 在顶点数组中找到A，A被标记，回到C，在C的边链表中找到C的第二个邻接结点B
- 在顶点数组中找到B，B被标记，回到C，在C的边链表中找到C的第三个邻接结点为空，访问结束。
实现思路：
- 要对所有的顶点进行访问标记，并且由于基于深搜的遍历函数中需要多次调用该函数且保留访问记录，因此可用一个全局的布尔型数组Visited来存放顶点的访问状态，数组容量为所有顶点的个数
- 访问过程中遇到访问过的顶点要回到上一个顶点访问它的另一个相邻顶点，且对每一个顶点的操作相同，这是一个不断回溯的过程，可用递归实现
- 要将所有的连续相邻顶点访问到，则递归的结束条件是最后一个相邻顶点没有与之相邻的顶点了，而相邻顶点存放在边链表ArcNode中，那么递归结束条件是ArcNode链表的结点的nextArt域为空。这个过程可用循环来实现，循环条件是ArcNode链表中结点的nextArt不为空。
bool Visited[MAX];//顶点访问标志 Visited[i]=true 表示第i顶点已访问
/**从第v顶点出发,对邻接表图g进行DeepFirstSearch(DFS)*/
void DFS(ALGraph g, int v)
{
Visited[v] = true;
cout << g.vertices[v].data <<" ";
/*从v各未被访问的邻接点出发DFS*/
for(ArcNode *p=g.vertices[v].firstArc; p; p=p->nextArc )
{
if(Visited[p->adjV]==false)
DFS(g,p->adjV);
}
}
基于DFS的遍历
思路：对每一个顶点进行深搜，每次深搜之前都要将访问标记归零代码：
/**对邻接表图g进行基于DFS的遍历*/
void DFSTraverse(ALGraph g)
{
/* 初始化访问标记*/
for(int i=1; i<=g.vexnum; i++)
Visited[i] =false;
/**从各未访问的顶点DFS. 注:对于连通图,从任一顶点出发DFS,即可遍历所有顶点*/
for(int i=1; i<=g.vexnum; i++)
{
if(!Visited[i])
DFS(g,i);
}
}
广搜（WFS）
大概思路： 广搜类似于树的层次遍历，将一个顶点的所有邻接顶点访问完后，在分别访问每一个临接顶点的所有邻接顶点邻接表分析： 还是上图
- 从A开始，在顶点数组中找到A，访问A，在A的边链表中，依次访问A的所有邻接顶点B，C，D，并作标记
- 分别依次访问B，C，D的所有邻接顶点
- 在顶点数组中找到B，在B的边链表中，依次访问B的邻接结点C，并作标记
- 在顶点数组中找到C，在C的边链表中，A，B，已被访问过，跳过
- 在顶点数组中找到D，在D的边链表中，D的邻接结点为空。
B，C，D所有邻接结点访问完毕，访问结束。
实现思路：
- 由于顶点邻接顶点的邻接顶点的访问顺序是按邻接结点的顺序来的，即先被访问的邻接顶点，它的邻接点先被访问（有点拗口），由此可以队列来存放邻接顶点
- 依次访问每一个邻接顶点的所有邻接顶点，而邻接结点可能也有邻接顶点，故用双层循环实现，外层循环输出起始顶点的邻接顶点，循环条件为起始顶点的邻接结点未被完全访问，即队列不为空；内层循环访问每一个邻接结点的邻接结点，循环条件为边链表结点未被完全访问。
代码：
void BFS(ALGraph g, int v)
{
queue<int> q; // FIFO：先访问的顶点,其邻接点也先访问
if( Visited[v]) // 访问过的顶点,不再盘
return;
cout << g.vertices[v].data << " ";
Visited[v] = true;
q.push(v); //先访问的顶点先放入队列
while(!q.empty()) //当起始顶点的邻接顶点未被全部访问，输出起始顶点邻接顶点的数据
{
int u = q.front();
q.pop(); //访问过的顶点出队列
for(ArcNode* p = g.vertices[u].firstArc; p; p=p->nextArc) //访问邻接顶点的邻接顶点，即顶点的边链表
{
int w = p->adjV; //w是u号顶点各邻接点的编号
if(!Visited[w])
{
Visited[w] = true;
cout << g.vertices[w].data << " ";
q.push(w); //未被访问过的顶点放入队列，之后再访问它的邻接顶点
}
}
}
}
基于WFS的遍历
思路：对每一个顶点进行广搜代码：
/**对邻接表图g进行基于BFS的遍历*/
void BFSTravse(ALGraph g)
{
/* 初始化访问标记*/
for(int i=1; i<=g.vexnum; i++)
Visited[i] =false;
/**从各未访问的顶点BFS.对于连通图,从任一顶点出发BFS,即可遍历*/
for(int v=1; v<=g.vexnum; v++)
{
BFS(g,v);
}
}
输出路径
思路： 类似于树的路径输出，用递归实现。将路径分成第一个顶点和第一个顶点的邻接结点两部分进行路径搜索，而邻接结点同样可以分成上述两部分。 一直进行递归操作直到顶点没有邻接顶点了，也就是说递归结束条件是起始顶点等于终止顶点。代码：
/**基于DFS,输出图g中，从v到d顶点的路径 */
void Search(ALGraph g, int v, int d, vector<int> path )//将顶点的编号放入线性表中
{
Visited[v] = true; //从顶点v开始，访问过就标记
path.push_back(v);
if(v==d) //始终顶点相同，递归结束，回溯，输出路径
{
for(int i=0; i<path.size(); i++)
cout << g.vertices[path[i]].data << ",";
cout << endl<<"----"<<endl;
}
for(ArcNode *p=g.vertices[v].firstArc; p; p=p->nextArc ) //对每一个邻接结点进行递归搜索
{
if( !Visited[p->adjV])
Search(g,p->adjV, d, path);
}
}
构造最小生成树
什么是最小生成树？
用最少的边将图中所有顶点连接起来且要使边权和最小，而将n个顶点全都连起来所需的最少边数为n-1。也就是说找出图中n-1条边使得n个结点都是连通的，但是边权值总和最小而产生的一个子图叫最小生成树。
这里介绍 prim算法构造最小生成树。求两顶点之间的最短路径
这里介绍两种算法：Dijkstra算法和 Floyd算法求两顶点之间的最短路径。求单源点无负边最短路径用Dijkstra，而求所有点最短路径用Floyd。
