定义
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E) 其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。 图中可以没有边但必须有点。 分为有向图，无向图，还有混合图； 无向图：图的任意两个顶点之间的边都是无向边 有向图：图的任意两个顶点之间的边都是有向边
完全图
无向完全图： 任意两点之间都存在边的图 有向完全图： 任意两点之间都存在方向相反的两条弧
图的基本术语
稀疏图：称边数很少的图为稀疏图 稠密图：称边数很多的图为稠密图 顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数,在有向图中，顶点的度为该点的入度（到顶点的边数）与出度（从顶点向外出的边的数量）之和。 路径长度：不带权的为路径上边的个数，带权图中为路径上边的权值之和， 回路：起点与终点相同的路径，包括环。 简单路径，简单回路：除了第一个顶点和最后一个顶点，剩下的顶点没有重复的。 连通图：任意两个顶点之间都存在互相到达的路径。 连通分量：非连通图中极大连通子图
构造方式
通过邻接表的方式建立图
需要自定义的两个结构体：存储节点信息的结构体
代码语言：javascript复制struct head
{
int data;
child *f; //存储其中一个与其邻接的节点
}第二个是各个邻接节点的信息
代码语言：javascript复制struct child
{
int b;
child *brother; //存储与其节点相连的其他节点
}head p[size];
int p2[size][size]; //存储邻接矩阵
child *d;
for(int i=0;i<size;i )
{
for(int j=0;j<size;j )
{
if(p2[i][j]>0)
{
child *e=new child;
e->b=j;
d=p[i]->f;
if(d==NULL)
{
p[i]->f=e;
}
else{
while(1)
{
if(d->brother==NULL)
{
d->brother=e;
}
d=d->brother;
break;
}
}
}
}遍历方式
深度遍历方式
利用栈可以进行深度遍历。 基本思想就是将一个节点压入栈中，然后在判断与其邻接的节点中有没有未被访问的节点，有的话就将此节点压入栈中，访问之后的节点要对其进行标记防止其二次访问，每次都对栈顶元素进行判定是否还有未访问的邻接节点，若是全部访问，则出栈。
广度遍历方式
利用队列可以进行广度遍历，就是将一个节点入队，然后输出队首元素的值，将与队首元素相连的所有未被访问的邻接节点入队，队首元素出队，不断进行操作，知道队列为空，就完成了广度遍历。
