图 - 我的个人记载

图结构定义

//定义边结点 
typedef struct ArchNode {
	int adjvex;	 //	该边所指向的顶点的位置 
	struct ArcNode *nextarc; // 指向下一条边的指针 
}ArcNode;

// 定义邻接表的结构 
typedef struct VNode {
	int data; // 顶点信息
	ArcNode *firstarc; // 指向第一条依附该顶点的边的指针 
}VNode, AdjList[MaxValueNum];

typedef struct {
	AdjList vertices;	//邻接表 
	int vexnum, arcnum;	//图的顶点数和边数 
}ALGraph;

建立无向图

//确定顶点vex在G.vertices中的序号 
int LocateVex(ALGraph &G, int vex) {
	for (int i = 0; i < G.vexnum; i ++) {
		if (G.vertices[i].data == vex) {
			return i;
		}
	}
}

//邻接表构造无向图 
void CreateUGD(ALGraph &G) {
	printf("请输入图的总顶点数:"); 
	cin >> G.vexnum;	//顶点数 
	printf("请输入图的总边数:");
	cin >> G.arcnum;	//边数 
	for (int i = 0; i < G.vexnum; i ++) {
		printf("请输入第%d个顶点信息:",(i+1));
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	for (int k = 0; k < G.arcnum; k ++) {
		printf("输入第%d条边的信息:\n", (k+1));
		char u, v;
		printf("输入边依附的第一个顶点:");
		cin >> u;
		printf("输入边依附的第二个顶点:");
		cin >> v;
		//确定u，v在图G中的位置，即在G.vertices中的序号
		int i = LocateVex(G, u);
		int j = LocateVex(G, v);
		struct ArcNode *p1, *p2;
		p1 = new ArcNode;
		p1-> adjvex = j;
        	//头插法
		p1 -> nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		p2= new ArcNode;
		p2 -> adjvex = i;
		p2 -> nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}

void PrintG(ALGraph &G) {
	printf("遍历图的邻接表:\n");
	for (int i = 0; i < G.vexnum; i ++) {
		printf("顶点%c ", G.vertices[i].data);
		ArcNode *p;
		p = G.vertices[i].firstarc;
		while(p) {
			printf("%d--->%c ", p->adjvex, G.vertices[p->adjvex].data);
			p = p -> nextarc; 
		}
	}
}


int main() {
	ALGraph G;
	CreateUGD(G);
	PrintG(G); 
	return 0;
}

图的遍历

DFS深度优先搜索

算法思想
深度优先搜索沿着一条路径一直搜索下去，“一条路走到黑”，直到遇到不能走时再回溯，继续其他分支。
算法步骤

首先访问图中某一起始顶点 $v$
然后从 $v$ 出发，访问与 $v$ 邻接且未被访问过的任意一个顶点 $w_1$ 。
从 $w_1$ 出发进行深度优先遍历，当不能再继续向下访问时，依次退回到最近被访问的结点，若还有邻接结点未访问，回到步骤2继续执行，直到所有结点都访问过。

时间复杂度： $O(V+E)$

bool visited[1005];

//基于邻接表的深度优先遍历
void DFS(ALGraph G, int v) {
	cout << G.vertices[v].data << " ";
	visited[v] = true;
	ArcNode *p = G.vertices[v].firstarc;
	while(p) {//依次检查v 的所有邻接点
		int w = p -> adjvex;//w 为 v 的邻接点
		if (!visited[w]) {//w未被访问
			DFS(G, w);//从w 出发，递归深度优先遍历
		}
		p = p -> nextarc;
	}
}

void DFSTraverse(ALGraph G) {
	for (int v = 0; v < G.vexnum; v ++) {
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; v ++) {
		//v 未被访问，以v 为起点再次深度优先遍历
		if (!visited[v]) {
			DFS(G, v);
		}
	}
}

BFS广度优先搜索

算法思想
类似二叉树的层序遍历，从某个节点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些已访问过的邻接点出发，一层一层地访问。直到所有的结点都访问为止。
算法步骤

初始化所有节点均未被访问，并初始化一个空队列。
从图中的某个节点v 出发，访问v 并标记其已被访问，将v入队。
如果队列非空，则继续执行，否则算法结束。
将队头元素v 出队，依次访问v 的所有未被访问的邻接点，标记已被访问并入队。转向步骤3。

时间复杂度： $O(V+E)$

bool visited[1005];
void BFS(ALGraph G, int v) {
	cout << G.vertices[v].data << " ";
	visited[v] = true;
	SqQueue Q;
	InitQueue(Q);//创建一个普通队列
	EnQueue(Q, v);//将源点v 入队
	while(!QueueEmpty(Q)) {//如果队列不为空
		int u;
		DeQueue(Q, u);//则取出队头元素并赋值给u
		ArcNode *p = G.vertices[u].firstarc;
		while(p) {//依次检查 u 的所有邻接点
			int w = p -> adjvex;//w 为 u 的邻接点
			if (!visited[w]) {//w 未被访问
				cout << G.vertices[w].data << " ";
				visited[w] = true;
				EnQueue(Q, w);
			}
			p = p -> nextarc;
		}
	}
}
void BFSTraverse(ALGraph G) {
	for (int v = 0; v < G.vexnum; v ++) {
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; v ++) {
		//v 未被访问，以v 为起点再次广度优先遍历
		if (!visited[v]) {
			BFS(G, v);
		}
	} 
}

最小生成树算法

普里姆（prim）算法

算法思想

初始时，在图中任取一定加入集合 $T$
之后选择一个与当前 $T$ 中顶点集合距离最近的顶点，并将该顶点和相应的边加入 $T$ ，每次操作后 $T$ 中的顶点数和变数都增1
直到图中所有顶点都并入 $T$ ，就得到了一颗最小生成树

时间复杂度： $O(V^2)$

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, m;
int G[510][510];//存储图
int dist[510];//存储各个节点到生成树的距离
bool vis[510];//节点是否被加入到生成树中
int pre[510];//节点的前驱节点

int prim() {
	
	memset(dist, 0x3f, sizeof(dist));
	int ans = 0;
	dist[1] = 0;//从 1 号节点开始生成
	for (int i = 0; i < n; i ++) {
		//每次循环选出一个点加入到生成树
		int t = -1;
		for (int j = 1; j <= n; j ++) {//每个节点一次判断
			if (!vis[j] && (t == -1 || dist[t] > dist[j]))
			//如果没有在树中，且到树的距离最短，则选择该点
				t = j;
		}
		//如果是孤立点，则不能构造最小生成树 
		if (dist[t] == INF)
			return INF;
		vis[t] = true;// 选择该点
		ans += dist[t];
		for (int j = 1; j <= n; j ++) {
			//更新生成树外的点到生成树的距离
			if (dist[j] > G[t][j] && !vis[j]) {
				dist[j] = G[t][j];
				pre[j] = t;
			}
		}
	}
	return ans;
	
}

void path() {
	for (int i = n; i > 1; i --) {
		cout << i << " " << pre[i] << endl;
	}
}

int main() {
	cin >> n >> m;
	memset(G, 0x3f, sizeof G);
	
	while (m --) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a][b] = G[b][a] = min(G[a][b], c);
	}
	int ans = prim();
	if (ans == INF)	puts("无法构成最小生成树");
	else cout << ans << endl;
	path();
	return 0;
}

克鲁斯卡尔（krusal）算法

算法思想

初始时为只有 $n$ 个顶点而无边的非连通图，每个顶点各自构成一个连通分量
按照边的权值从小到大的顺序，不断选取当前未被选取过且权值最小的边
若该边依附的顶点落在 $T$ 中不同的连通分量上，则将此边加入 $T$
否则舍弃此边而从新选择下一条权值最小的边，直至所有顶点都在一个连通分量上

时间复杂度： $O(Elog_2E)$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
int p[N];//保存并查集

struct Edge{
	int u, v, w;
	bool operator< (const Edge &W)const {//按照边大小降序排列 
		return w < W.w;
	}
}edge[N * 2];


int find(int x) {//并查集找祖宗
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

int kruskal() {
	sort(edge, edge + m);
	for (int i = 1; i <= n; i ++)//初始化并查集
		p[i] = i;
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < m; i ++) {//依次尝试加入每条边
		int pu = find(edge[i].u);// u 点所在的集合
		int pv = find(edge[i].v); // v 点所在的集合
		if (pu != pv) {//如果 u v 不在一个集合中
			p[pu] = pv;// 合并u v
			ans += edge[i].w;
			cnt ++;
		}
	}
	if (cnt < n - 1)//如果边小于点数-1，则不能连通
		return INF;
	return ans;
}

int main() {
	
	scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i ++)
    {
        int a, b, w;
        scanf("%d%d%d",&a, &b, &w);
        edge[i] = {a,b,w};
    }
	int ans = kruskal();
	if (ans == INF)
		puts("无法构成最小生成树");
	else
		cout << ans << endl;
	return 0;
}

最短路算法

迪杰斯特拉算法（dijkstra）算法

算法思想

集合 $S$ 初始化 $\{ 0 \}$ ， $dist[]$ 的初始值 $dist[i]=arcs[0][i],i=1,2...n-1$
从顶点集合 $V-S$ 中选出 $v_j$ ，满足 $dist[j]=Min \{ dist[i] \mid v_i \in V-S \}$ $v_j$ 就是当前求得的一条从 $v_0$ 出发的最短路径的终点，令 $S=S \cup \{j\}$
修改从 $v_0$ 出发到集合 $V-S$ 上任意一个顶点 $v_k$ 可到达的最短路径长度，若 $dist[j]+arcs[j][k]<dist[k]$ ，则更新 $dist[k]=dist[j]+arcs[j][k]$
重复2-3,操作 $n-1$ 次，直到每一个顶点都包含入 $S$

时间复杂度： $O(V^2)$

注：Dijkstra算法不能用来更新带有负权边的图
原因：
每个点被确定后， $dist[j]$ 就是最短距离了，之后就不能再被更新了，而如果有负权边的话，那已经确定的点的 $dist[j]$ 不一定是最短了，可能还可以通过负权边进行更新。

int dijkstra()
{
    memset(dist , 0x3f, sizeof (dist));
    dist[1] = 0;
    for(int i = 0; i < n; i ++)
        {
            int k = -1;
            for(int j = 1; j <= n; j ++)
                if(!st[j] && (k == -1 || dist[k] > dist[j]))
                    k = j;
            st[k] = true;
            for(int j = 1; j <= n; j ++)
                dist[j] = min(dist[j], dist[k] + arcs[k][j]);
        }
    if(dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];
}

佛洛依德（floyd）算法

算法思想
采用动态规划的思想
$F[i][j][k]$ 表示经过若干个编号不超过 $k$ 的结点，从 $i$ 走到 $j$ 的最短路径长度。
可划分两个子问题：
经过编号不超过 $k-1$ 的节点从 $i$ 到 $j$
或者从 $i$ 先到 $k$ 再到 $j$

$F[i][j][k]=min(f[i][j][k-1], f[i][k][k-1]+f[k][j][k-1]$

$k$ 是在动态规划中代表“阶段”，置于外层循环。

时间复杂度： $O(V^3)$

void floyd() {
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

拓扑排序算法

算法思想

选个一个没有前驱的结点开始
从图中删除该顶点和他所有以它为起点的有向边，BFS实现
重复1,2直到当前图中不存在无前驱的的顶点为止，反之图中必然有环存在。

bool TopoSort(ALGraph G){
	int count = 0;
	SqQueue Q;
	InitQueue(Q);//创建一个普通队列
	for (int i = 0; i < G.vexnum; i ++) {
		if (!indegree[i])
			EnQueue(Q, i);
	}
	while(!QueueEmpty(Q)) {
		int u;
		DeQueue(Q, u);
		cout << G.vertices[u].data << " ";//输出顶点 
		cnt ++;
		ArcNode *p = G.vertices[u].firstarc;
		while(p) {//依次检查 v 的所有邻接点
			int v = p -> adjvex;//v 为 u 的邻接点
			if (!(--indegree[v]))
				EnQueue(Q, v); 
			p = p -> nextarc;
		}
	}
	return cnt == G.vertices;
}

Q.E.D.

框框‘s blog

图

图结构定义

建立无向图

图的遍历

DFS深度优先搜索

BFS广度优先搜索

最小生成树算法

普里姆（prim）算法

克鲁斯卡尔（krusal）算法

最短路算法

迪杰斯特拉算法（dijkstra）算法

佛洛依德（floyd）算法

拓扑排序算法

递归和分治

二叉树

框框