文章目录

图的基本操作

  1. 邻接表
  2. 邻接多重表
  3. 十字链表
  4. 邻接矩阵
  5. prim算法
  6. kruskal算法
  7. 拓扑排序
  8. 关键路径
  9. Dijkstra 算法
    这些课本上都有介绍
    所以我只重点整理了做应用部分的算法：
    <mark>利用Dijkstra 算法求最短路径</mark>

Dijkstra 算法求最短路径思路

需要新建几个全局数组和变量：
bool visited[maxn]; //用于判断顶点是否已经在最短路径树中，或者说是否已找到最短路径
int parent[maxn]; //每个顶点的父亲节点，可以用于还原最短路径树
node d[maxn]; //源点到每个顶点估算距离，最后结果为源点到所有顶点的最
短路。
priority_queue q; //优先队列 stl 实现
vernode Ver[maxn];//结点数组
int n; //顶点个数

在算法实现过程中用到队列，有点类似于邻接表的广度遍历，不过是在遍历的过程中，记录最小权值以及对应边的父结点的下标。
主要代码：


void Dijkstra(int s) //Dijkstra 算法，传入源顶点
{
for (int i = 1; i <= n; i++) //初始化
{
	d[i].id = i;
	d[i].w = INF; //估算距离置 INF
	parent[i] = -1; //每个顶点都无父亲节点
	visited1[i] = false; //都未找到最短路
	}
d[s].w = 0; //源点到源点最短路权值为 0
q.push(d[s]); //压入队列中
while (!q.empty()) //算法的核心，队列空说明完成了操作
{
	node cd = q.top(); //取最小估算距离顶点
	q.pop();
	int u = cd.id;
	if (visited1[u]) //注意这一句的深意，避免很多不必要的操作
	continue;
	visited1[u] = true;
	arcnode * p = Ver[u].firarc;
	//松弛操作
	while (p != NULL) //找所有与他相邻的顶点，进行松弛操作，更新估算距
	离，压入队列。
	{
	int v = p->vertex;
	if (!visited1[v] && d[v].w > d[u].w + p->weight)
	{
	d[v].w = d[u].w + p->weight;
	parent[v] = u;
	q.push(d[v]);
	}
	p = p->next;16
	}
}
}

找最短路径，并输出最短路径过程

此过程就需要用到parent[max]数组，这个数组的含义就是从起点到终点最短路径经过的顶点的父结点
从终点开始，找到它的父结点，也就是上一个结点，依次类推，直到找到起点。但
是整个过程是逆序的，因此我用了一个数组去存储整个最短路径过程的结点下
标，最后输出即可。
主要代码：

int base[maxn], k = 0;
while (parent[ed] != st) {
	base[k] = parent[ed];
	k++;
	ed = parent[ed];
	}
k = k - 1;
cout << "最短路线为：" << endl;
printf("从%s 出发", menu[st].c_str());
while (k >= 0) {
cout << " ==>";
printf("%s", menu[base[k]].c_str()); 
k--;
}
printf(" 最终到达%s\n", menu[temp].c_str());
return OK;

链接：https://pan.baidu.com/s/1Tn1xQSNn0mQonh_ARusxYg
提取码：gka4
图的相关操作以及校园导航系统的代码，课设实验报告均在此盘，有需要可以拿去借鉴。