图Graph及相关算法（Dijkstra，Kruskal）-慈云数据

无向图

有向图

邻接矩阵

邻接表

图的bfs，dfs

二部图（二分图）

有向无环图（DAG）

拓扑排序（Topological Sort）

AOV网

迪杰斯特拉Dijkstra

最小生成树

克鲁斯卡尔：Kruskal

普里姆：prim

图是多对多关系，是顶点和边的二元组和。

无向图

1.依附关系：边（v1,v2）依附于顶点v1,v2。

2.完全图：所有可能的边都存在 $C_{n}^{2}$ 。

3.路径：一个点到另一个点的边。

4.简单路径：除起点终点可能相同外，其他点不允许重复出现。

5.连通：有路径可通。（有n个点，可能联通需要n-1条边，一定能联通 $C_{n-1}^{2}+1$ ，拿掉一个点完全联通图+1）

6.连通图：图中所有点之间均有路径可通。

7.子图：子图顶点集合 $\epsilon$ 原顶点集合，边集合 $\epsilon$ 边集合。

8.极大连通子图（连通分量）：画圈的就是。

有向图

1.连通图：相异成对顶点间路径可通。

2.极大连通子图（强连通分量）：成对顶点间均有路径可通。

3.用。

邻接矩阵

边多适用，唯一。

	1	2	3	4	5
1	0	1	1	1	0
2	1	0	1	0	1
3	1	1	0	1	1
4	1	0	1	0	1
5	0	1	1	1	0

邻接表

边少适用，不唯一。

图的bfs，dfs

图的创建：（1）顶点个数（2）申请并初始化（3）放边

DFS:（1）标记数组（2）遍历:1.打印顶点2.标记（3）标记邻接点，找邻接的未处理过的同（2）

BFS：（1）Queue（2）标记初始化（3）起始顶点入队标记（4）处理：弹出，打印，遍历邻接点，未处理邻接点入队，标记，等待处理重复（4）

#include
#include
#include
using namespace std;
typedef struct node
{ 
	int nedge;
	int nV;
	int* pjuzhen;
}Graph;
Graph* Create()
{
	Graph* pGraph = (Graph*)malloc(sizeof(Graph));
	//顶点个数，边的条数
	int nv, ne;
	cin >> nv >> ne;
	pGraph->nedge = ne;
	pGraph->nV = nv;
	pGraph->pjuzhen = (int*)malloc(sizeof(Graph) * nv * nv);
	memset(pGraph->pjuzhen, 0, sizeof(Graph) * nv * nv);
	for (int i = 0; i > v1 >> v2;
		if (v1>=1&& v1=1&&v2pjuzhen[(v1 - 1) * nv + v2 - 1] == 0)
		{
			pGraph->pjuzhen[(v1 - 1) * nv + v2 - 1] = 1;
			pGraph->pjuzhen[(v2 - 1) * nv + v1 - 1] = 1;
		}
		else i--;
	}
	return pGraph;
}
void DFSGraph(Graph* pGraph, int fir, int* pMark)
{
	cout pjuzhen[(fir - 1) * pGraph->nV + i] == 1 && pMark[i] == 0)
		{
			DFSGraph(pGraph, i + 1, pMark);
		}
	}
}
void BFS(Graph* pGraph, int fir)
{
	if (pGraph == NULL || firpGraph->nV)return;
	int* pMark = NULL;
	pMark = (int*)malloc(sizeof(int) * pGraph->nV);
	memset(pMark, 0, sizeof(int) * pGraph->nV);
	queueq;
	q.push(fir);
	pMark[fir - 1] = 1;
	while (!q.empty())
	{
		fir = q.front();
		q.pop();
		cout pjuzhen[(fir - 1) * pGraph->nV + i] == 1 && pMark[i] == 0)
			{
				q.push(i + 1);
				pMark[i] = 1;
			}
		}
	}free(pMark);
	pMark = NULL;
}
void DFS(Graph* pGraph,int fir)
{
	if (pGraph == NULL || fir pGraph->nV)return;
	int* pMark=NULL;
	pMark = (int*)malloc(sizeof(int)*pGraph->nV);
	memset(pMark, 0, sizeof(int) * pGraph->nV);
	DFSGraph(pGraph, fir, pMark);
	free(pMark);
	pMark = NULL;
}
int main()
{
	Graph* p = Create();
	for (int i = 0; i nV * p->nV; i++)
	{
		if (i % p->nV == 0)cout 0,7,6,0}                 (找数最小不为0的点)0,7,6,0}           （v3-v2为5，5+60,7,6,16}    （v2-v4为9，9+7=16）h2 id="%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91" 最小生成树/h2 
h3 id="%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%EF%BC%9AKruskal"克鲁斯卡尔：Kruskal/h3 
p按路径长度从小到大排序，如果两点已经连通就跳过。/p 
p例：/p 
pimg alt="" height="246" src="https://img-blog.csdnimg.cn/direct/ae525244ce3a487e88196c1e1d775559.png" width="425" //p 
p先是3，4，5，6路径连上。/p 
pimg alt="" height="259" src="https://img-blog.csdnimg.cn/direct/5cfe3b0ae25d49c1a33ce0be3d0870b6.png" width="433" //p 
p由于v4,v7已经联通所以跳过11。/p 
p连上15，20，结束。/p 
pimg alt="" height="237" src="https://img-blog.csdnimg.cn/direct/f8706757066a4ff798302a2f8f2617a7.png" width="431" //p 
h3 id="articleContentId"普里姆：prim/h3 
p假设从v1节点寻找。/p 
pv1-v3,v1-v4,v1-v8中v1->v8最小。 
 
v1->v3,v1->v4,v8->v7中v8->v7最小，所以选v8->v7。 
 
v1->v3,v1->v4,v7->v4,v7->v6中，v1->v4最小，选v1->v4。 
 
v1->v3,v4->v3,v4->v5,v4->v6,v7->v6中，v4->v3最小，选v4->v3。 
 
后续同理（由于v4，v7已经连通所以看下一个15）。 
结果：