Groph（图）

人生像图，选择不同终点不同。

定义

图是有限结点集合(V)和链接结点的有限边的集合(E)的二元组合G=(V,E)。

无向图

若图中所有的边均满足的两个顶点没有次序关系和方向性，即(v1,v2)和(v2,v1)代表同一条边，则称为无向图。图（b）所示
无向图就是由结点V={1,2,3,4}，和边E={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)},构成的。

无向图的性质

完全图
若图中n个结点间所有可能的边均存在，即有
$ C = n*(n-1)/2 $条边，则称为完全图。
如图（a）（b）都是完全图
依附
边(V1,V2)依附于顶点V1，V2 如图边（1,4）依附于顶点1,4。
子图
若G’ 是图G的子图，则有V（G‘）<=V（G），和E（G’）<=E（G）。如图a是b的子图而c不是b的子图
路径
图中从Vp到Vq的一条路径是指由顶点构成的连续序列Vp，Vi1，Vi2，。。。Vin-1
Vin，Vp，其中(Vp，Vi1),(Vi1，Vi2),….(Vin-1，Vin),(Vin，Vq)均为E（G）的边。
路径长度
路径所含边得数目即为路径的长度
简单路径
指路径上除起点和终点可能相同外，其他顶点都不同。例如b中的{(1,3),(3,2),(2,4)}构成了一条从顶点1,到顶点4的简单路径，且长度为3；而{(1,2),(2,3),(3,4,),(4,2),(2,1)}则不是简单路径。
回路和环
起点和终点为同一顶点的简单路径称为回路或环。例如b中的路径{(1,3),(3,2),(2,1)}构成一个封闭的回路。
连通
若从V1到V2有路径可通，则称顶点V1和顶点V2是连通的。
连通图
图中任意两个结点都有路径相通，称为连通图a，b，c都是连通图
非连通图
只要有两个结点无路径相通，则称为非连通图。图一
连通分量
图中的极大连通子图，即图一中有两个连通分量
度
指无向图中顶点V相关的边得个数

有向图

若图中边得两个顶点存在次序关系和方向性，即和代表两条不同的边则称为有向图。图a所示的有向图就是由结点V={1,2,3}和边E={<2,1>,<2,3>,<3,2>}构成。其中，有序对<2,1>就是由尾部顶点2，指向头部顶点1的有向边，而边<2,3>和<3,2>则是方向不同的两条边.

有向图的性质

完全图
若图中结点间n个有可能的边均存在，即Pn=n*（n-1）条边，称为完全图。如图b
依附
边依附于顶点V1于顶点V2
路径
图中从Vp到Vq的一条路径是指由顶点构成的连续序列Vp，Vi1，Vi2，。。。Vin-1
Vin，Vp，其中,,….,均为E（G）上的有向边。
强连通
如果每个相异成对顶点Vi和Vj都同时有从Vi到Vj和从Vj到Vi的路径，则称该有向图为强连通。
强连通分量
即有向图中的极大强连通子图
入度
顶点V的入度是指以V为终点有向边得个数
(指向该结点的边)
出度
顶点V的出度是指以V为起点有向边的个数。

度=入度+出度

图的存储

邻接链表

邻接矩阵

图的创建

#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#define MAX 10
typedef struct node
{
	int nVertex;
	int nEdge;
	int arr[MAX][MAX];
}MyGraph;
MyGraph *CreateGraph()
{
	int nV;
	int nE;
	int i;
	int a,b;
	MyGraph *pGraph = NULL;
	pGraph = (MyGraph*)malloc(sizeof(MyGraph));
	//邻接矩阵赋值为0
	memset(pGraph,0,sizeof(MyGraph));
	printf("请输入顶点的数量：\n");
	scanf("%d",&nV);
	pGraph->nVertex = nV;
	printf("请输入边的数量:\n");
	scanf("%d",&nE);
	pGraph->nEdge = nE;
	//邻接矩阵赋值
	for(i = 1;i<=nE;i++)
	{
		printf("请输入两个顶点:\n");
		scanf("%d%d",&a,&b);
		//在顶点范围之内 并且为存储边 
		if(a>=1 && a<=nV && b>=1&& b<= nV 
			&& pGraph->arr[a][b] == 0)
		{
			pGraph->arr[a][b] = 1;
			pGraph->arr[b][a] = 1;
		}
		//顶点不对  边已经存在
		else
		{
			i--;
		}
	}
	return pGraph;
}

图的性质总结

无向图邻接矩阵的第i行或第i列非0元素的个数其实就是第i个顶点的度
有向图邻接矩阵的第i行非0元素的个数其实就是第i个顶点的出度，而第i列非0元素的个数是第i个顶点的入度，即第i个顶点的度是第i行和第i列非0元素个数之和
区分无向图和有向图的3个依据是：

图中各边无箭头的是无向图，边有箭头的是有向图
图中各边采用()来描述的是无向图，采用<>来描述的是有向图
图的邻接矩阵若以对角线为对称，若无特别声明就是无向图，不对称的则是有向图。

邻接矩阵和邻接表的区别在于：
- 从空间存储来讲，邻接矩阵适用于边很多的图，邻接表则适用于边不多的图。

从数据结构上讲，邻接矩阵对于图来说是唯一的，而邻接表并不唯一

指针小知识：
函数参数的三种传递方式：1.值传递，2.地址，3.引用。
char str = “Hello”与char str[] = “Hello”的不同？
char str指向的是字符常量区，sizeof()=4字节，可以str = “abc”,可以改变指向的字符常量区，只能读取，不可以str = “h”不可以修改字符常量。
char str[] 把字符常量区的东西拷贝到栈区，str = “h”可以执行，指向栈区，可以任意改变。sizeof() = 6字节，str不可以赋值数组，str是首地址，是常量(无法扩容)。

把一颗普通的树变成二叉树

步骤

把同一个父亲的兄弟连起来。
把同属于一个父亲的孩子(除第一个)其他的都断开。
左面孩子是左孩子，右面兄弟是右孩子，相当于把把当前树拎起来，抖开。
把一片森林变成二叉树

森林：多颗树相互不连接的树。

步骤
首先，把这些树的根都连起来，这样看起来像一颗普通的树。
之后，在根据把一颗普通的树变成二叉树的步骤进行。
图的遍历

DFS 深度优先遍历
给定一个数字作为接口进入，找到当前的第一个非0的关联结点，输出。
然后在查看这个非0结点的第一个结点输出，重复的不输出（用一个辅助数组标记）。

一直找到该结点的当前结点都已经输出过为止，回到上一个相关的结点，依次向右循环遍历。

void mydfs(mygraph *pgraph,int nbegin,int *pmark)
{
	int i;
	//打印
	printf("%d  ",nbegin);
	//标记
	pmark[nbegin] = 1;
	//矩阵遍历
	for(i = 1;i<=pgraph->nvertex;i++)
	{
		//找到当前的第一个非0的关联节点
		if(pgraph->arr[nbegin][i] == 1)
		{
			//检测标记数组
			//未被标记 
			if(pmark[i] == 0)
			{
				mydfs(pgraph,i,pmark);
			}
		}
	}
}
void dfs(mygraph *pgraph,int nbegin)
{
	int *pmark = null;
	if(pgraph == null)return;
	//申请标记数组
	pmark = (int*)malloc(sizeof(int) * (pgraph->nvertex +1));
	memset(pmark,0,sizeof(int) * (pgraph->nvertex +1));
	//遍历矩阵
	mydfs(pgraph,nbegin,pmark);
}

BFS 广度优先遍历

给定一个数字作为接口进入，找到当前的全部非0的关联结点，输出，放入辅助队列并用辅助数组标记。
Pop队列第一个结点，查看其相关联的结点，若没有被标记过，则放入辅助队列并用辅助数组标记。

一直循环此步骤，直到把队列中的结点全部Pop。

void BFS(MyGraph *pGraph,int nBegin)
{
	Queue *pQueue = NULL;
	int *pMark = NULL;
	int i;
	if(pGraph == NULL)return;
	q_Init(&pQueue);
	pMark = (int *)malloc(sizeof(int) * (pGraph->nVertex+1));
	memset(pMark,0,sizeof(int) * (pGraph->nVertex+1));
	q_Push(pQueue,nBegin);
	pMark[nBegin] = 1;
	while( !q_IsEmpty(pQueue))
	{
		nBegin = q_Pop(pQueue);
		printf("%d ",nBegin);
		for(i = 1;i<=pGraph->nVertex;i++)
		{
			if(pGraph->arr[nBegin][i] == 1 && pMark[i] == 0)
			{
				pMark[i] = 1;
				q_Push(pQueue,i);
			}
		}
	}
}

Dijstra迪杰斯特拉算法

求带权图最短路径优化算法

补充：结点2到结点4权值为16。

步骤

贪心算法：选一个最便宜的路。（大概思路）

$ v_1-> ${$ 0,7,0,0,20,32$}$ $我们以结点1作为出发点！
首先先找到一个最便宜的路。$v_1->v_2$的权值为7，0表示此路不通。
然后，假设我们已经从$v_1->v_2$，来计算到其他结点的权值。
$ v_1->v_2-> ${$ 0,7,11,23,20,10$}$ $解释一下11是由于上一个$v_1$不可以直接到3结点，
所以先到2结点花费7，然后再从2到3花费4，所以加起来是11。同理23也是1到2，2到4，
一共花费23。10是因为结点1到6花费32，而结点1到2到6花费10。所以我们每次都要选择花费最少的方案。
之后我们在在1到2中选择下一个目的地（必须是花费最少的权值路径）。所以我们选择6结点。
ps：我们曾经算出来的最少路径不当作下一个目的地进行考虑（如0,7,10）
$ v_1->v_2->v_6 ${$ 0,7,11,23,11,10$ }$ $根据上述理论，第二个11是由1到2到6到5，是1到5最便宜的选择！
选择3结点作为下次的目的地。由于3和5的权值相同，我们就先选3作为下次目的地。
$ v_1->v_2->v_6->v_3 ${$ 0,7,11,17,11,10$ }$ $下次我们将结点5作为目的地。
$ v_1->v_2->v_6->v_3->v_5 ${$ 0,7,11,17,11,10$ }$ $所以就得从结点1出发到各个结点最便宜的路径选择。以及
最少权值。