#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define maxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
//图的存储方式----邻接矩阵
typedef struct
{
VertexType vex[maxVertexNum]; //存储顶点
EdgeType Edge[maxVertexNum][maxVertexNum]; //存储边的权值
int vexnum, arcnum; //顶点数和边数
}MGraph;
//邻接表
//边表节点
typedef struct ArcNode
{
int adjvex; //节点编号
int weight; //边的权重
struct ArcNode* next; //下一个节点指针
}ArcNode;
//顶点表节点
typedef struct VNode
{
VertexType data;
ArcNode* first;
}VNode, AdjList[maxVertexNum];
//图
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
/*
邻接矩阵:空间复杂度高
邻接表:找某一个顶点的入度必须遍历每个顶点的邻接表,时间复杂度高
*/
//从节点a连向节点b的权值为c的边
void add(ALGraph& G, int a, int b, int c)
{
//初始化边节点p
ArcNode* p = (ArcNode*)malloc(sizeof ArcNode);
p->adjvex = b;
p->weight = c;
//将边节点插入到图中
p->next = G.vertices[a].first;
G.vertices[a].first = p;
}
//遍历某个节点的临接点
void travel(ALGraph& G, int u)
{
for (ArcNode* p = G.vertices[u].first; p != NULL; p = p->next)
{
cout << p->adjvex << endl;
}
}
图的遍历伪代码
BFS:
void BFS_Traverse(ALGraph G)
{
for (int i = 0; i < vexnum; i++) visited[i] = false;
InitQueue(Q);
for (int i = 0; i < vexnum; i++)
if (!visited[i])
BFS(G, i);
}
void BFS(ALGraph G, int u)
{
EnQueue(Q, u);
visit(u);
visited[u] = true;
while (!isEmpty(Q))
{
DeQueue(Q, u);
for (w = firstNeighbor(G, u); w >= 0; w = NextNeighbor)
{
if (!visited[w])
{
visit(w);
EnQueue(Q, w);
visited[w] = true;
}
}
}
}
void DFS_Traverse(ALGraph G)
{
for (int i = 0; i < vexnum; i++) visited[i] = false;
for (int i = 0; i < vexnum; i++)
if (!visited[i])
DFS(G, i);
}
DFS:
void DFS(ALGraph G, int u)
{
visit(u);
visited[u] = true;
for (w = firstNeighbor(G, u); w >= 0; w = NextNeighbor)
{
if (!visited[w])
{
DFS(G, w);
}
}
}
/*最小生成树
1.prim算法:
1.维护一个集合st(已经在连通块(最小生成树)中的点)
2.初始化:将所有点到集合的距离初始化为INF
3.迭代n次
4.每次迭代选择为还没有加入到集合的点 中距离集合的最小值(点到集合的定义)
5.用这个最小值更新其他点到集合的距离
2.kruskal算法
1.将所有边升序排序
2.依次遍历每条边,取出这条边两端的顶点,用并查集判断这两个顶点是否在同一个集合中
若在同一个集合中:继续遍历
若不在同一个集合中:则加入到合并到同一个集合中
*/
/*最短路
dijkstra的最短路算法是贪心的,它贪心的选最小的并且认为这个点不会被更新了
为什么不会被更新了?因为没有负权边.
从而你加入优先队列里的dis只会越来越大,毕竟一个正数 + 一个正数一定变大
不可能以后取出来某一个点更新这个点,故我这个点取出来了,就不会再使用。
Dij的正确性是基于 “放入优先队列的点的dis是单调的” 这一条件。
所以 对于求最短路,我们要求dis单调递增,即不存在负权边,
对于最大乘积,我们要求乘积只允许单调变小,即乘的在0,1之间,
对于最小乘积,我们要求乘积必须单调变大,即所有边权都是>=1的
(似乎也不用严格单调,只要不增不减就行了)
1.dijkstra算法(集合:已经确定最短距离的点)
1.初始化距离:dist[1] = 0, 其他均为INF
2.迭代n - 1次
3.每次迭代找到不在集合中,距离源点距离最近的点。
4.把这个点加入到集合中
5.用这个点更新其他点到源点的距离 更新条件:dist[j] > dist[t] + w;
2.floyd算法
1.建立邻接表
2.更新邻接表:
1.依次以V0, v1, v2, ... 作为中转点更新邻接表的每一项
例如:dist(v0->v2) > distf(v0->v1->v2)
则更新arcs[v0][v2] = arcs[v0][v1] + arcs[v1][v2];
*/
/*拓扑排序(AOV) 边无权值,仅表示顶点之间的前后关系
1.将所有入度为0的点加入到队列中
2.将队列中的点依次出队,并删除以它为起点的有向边
3.重复1, 2 直至队列为空
*/
/*关键路径(AOE) 边有权值:表示完成活动的开销
从源点到汇点的所有路径中,具有最大长度的路径称为关键路径
求关键路径:
1. 计算ve(k): 源点v1 = 0到vk的最长路径长度 ve(k) = max{ve(j) + weight(vj -> vk)},
2. 计算vl(k): vl(汇点) = ve(汇点), vl(k) = min{vl(j) + weight(vk -> vj)},
3. 计算e(i): e(i) = ve(k), 其中vk是边i的起点
4. 计算l(i): l(i) = vl(j) - weight(vk -> vj) ai表示<vk, vj>
5. 计算关键路径:l(i) - e(i) == 0的活动表示关键活动
*/
int main()
{
return 0;
}