图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E) 其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。 图中可以没有边但必须有点。 分为有向图,无向图,还有混合图; 无向图:图的任意两个顶点之间的边都是无向边 有向图:图的任意两个顶点之间的边都是有向边
无向完全图: 任意两点之间都存在边的图 有向完全图: 任意两点之间都存在方向相反的两条弧
稀疏图:称边数很少的图为稀疏图 稠密图:称边数很多的图为稠密图 顶点的度:在无向图中,顶点v的度是指依附于该顶点的边数,在有向图中,顶点的度为该点的入度(到顶点的边数)与出度(从顶点向外出的边的数量)之和。 路径长度:不带权的为路径上边的个数,带权图中为路径上边的权值之和, 回路:起点与终点相同的路径,包括环。 简单路径,简单回路:除了第一个顶点和最后一个顶点,剩下的顶点没有重复的。 连通图:任意两个顶点之间都存在互相到达的路径。 连通分量:非连通图中极大连通子图
需要自定义的两个结构体:存储节点信息的结构体
第二个是各个邻接节点的信息
利用栈可以进行深度遍历。 基本思想就是将一个节点压入栈中,然后在判断与其邻接的节点中有没有未被访问的节点,有的话就将此节点压入栈中,访问之后的节点要对其进行标记防止其二次访问,每次都对栈顶元素进行判定是否还有未访问的邻接节点,若是全部访问,则出栈。
利用队列可以进行广度遍历,就是将一个节点入队,然后输出队首元素的值,将与队首元素相连的所有未被访问的邻接节点入队,队首元素出队,不断进行操作,知道队列为空,就完成了广度遍历。