图

定义

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E) 其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。 图中可以没有边但必须有点。 分为有向图，无向图，还有混合图； 无向图：图的任意两个顶点之间的边都是无向边 有向图：图的任意两个顶点之间的边都是有向边

完全图

无向完全图： 任意两点之间都存在边的图 有向完全图： 任意两点之间都存在方向相反的两条弧

图的基本术语

稀疏图：称边数很少的图为稀疏图 稠密图：称边数很多的图为稠密图 顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数,在有向图中，顶点的度为该点的入度（到顶点的边数）与出度（从顶点向外出的边的数量）之和。 路径长度：不带权的为路径上边的个数，带权图中为路径上边的权值之和， 回路：起点与终点相同的路径，包括环。 简单路径，简单回路：除了第一个顶点和最后一个顶点，剩下的顶点没有重复的。 连通图：任意两个顶点之间都存在互相到达的路径。 连通分量：非连通图中极大连通子图

构造方式

通过邻接表的方式建立图

需要自定义的两个结构体：存储节点信息的结构体

struct head
{
int data;
child *f;   //存储其中一个与其邻接的节点 
}

第二个是各个邻接节点的信息

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;
   }
   }
}
}

遍历方式

深度遍历方式

利用栈可以进行深度遍历。 基本思想就是将一个节点压入栈中，然后在判断与其邻接的节点中有没有未被访问的节点，有的话就将此节点压入栈中，访问之后的节点要对其进行标记防止其二次访问，每次都对栈顶元素进行判定是否还有未访问的邻接节点，若是全部访问，则出栈。

广度遍历方式

利用队列可以进行广度遍历，就是将一个节点入队，然后输出队首元素的值，将与队首元素相连的所有未被访问的邻接节点入队，队首元素出队，不断进行操作，知道队列为空，就完成了广度遍历。