Graphs

Graphs(图)

• 一组顶点 （有时称为节点）

• 一组边 （有时称为弧），表示两个顶点之间的连接。

Paths(路径)

路径：从顶点 a 到 b 的路径是一系列边，可以从 a 开始沿着 c,d,f 这些边到达。

可以表示为经过的顶点或所经过的边。

• 路径长度:路径中包含的顶点或边的数量。

• 链接或者相邻:两个顶点通过一条边直接连接.

• 可达性:从顶点 a 到顶点 b 是否存在路径。

• 连通性:如果每个顶点都可以从其他每个顶点到达，那么一个图是连通的。

• 完全图:如果每个顶点与其他每个顶点都有一条直接边，则该图是完全的

• 循环:如果路径中包含一个顶点，则该路径是循环的。

• 循环图: 图中至少存在一条回路。

• 环: 回路中除了起点和终点之外的部分。

Weighted graphs(加权图)

这意味着边上附有权重或成本

Directed graphs(有向图)

这意味着边上有方向。

边也就是向量

它具有指向性

Linked Lists, Trees, graphs

其实之前所说的二叉树, 链表, 树都是图的一种特殊形式。

Stanford BasicGraph

Stanford BasicGraph 是一种图数据结构，它提供了一些基本的操作，如创建图、添加顶点、添加边、删除顶点、删除边、查找顶点、查找边、打印图、深度优先搜索、广度优先搜索、最小生成树、最短路径等。

**# include "basicgraph.h"

• g.addEdge(v1, v2); 在两个顶点之间添加一条边
• g.addVertex(name); 向图中添加一个顶点
• g.clear(); 从图中移除所有顶点和边
• g.getEdgeSet(); 返回图中所有边，或者返回从顶点 v 开始的所有边，以指针集合的形式
• g.getNeighbors(v); 返回顶点 v 连接的所有顶点集合
• g.getVertex(name); 返回具有给定名字的顶点的指针
• g.getVertexSet(); 返回图中所有顶点的集合
• g.isNeighbor(v1, v2); 如果从顶点 v1 到 v2 存在一条边，则返回 true
• g.isEmpty(); 如果图中没有顶点和边，则返回 true
• g.removeEdge(v1, v2); 从图中移除一条边
• g.removeVertex(name); 从图中移除一个顶点
• g.size(); 返回图中顶点的数量
• g.toString(); 返回一个字符串，例如 "{a, b, c, a -> b}"，描述图的结构

Depth-first search, Breadth-first search

深度优先搜索 (DFS) 与广度优先搜索 (BFS) 是图的两个最基本的搜索算法。

Depth-first search

你选择一个"邻居"顶点，然后尽可能地跟随他,看看这是否可以将你到达目的地.如果到达那么就停止, 否则你就回去重新尝试另一个

这边有一段伪代码:

dfs from v1 to v2:
    mark v1 as visited, and add to path
    perform a dfs from each of v1's unvisited neighbors n to v2
    if dfs(n,v2)succeeds: a path is found!

Breadth-first search

该算法会从根节点开始，逐层访问节点，即先访问根节点，然后访问根节点的所有邻居节点，接着访问这些邻居节点的未访问过的邻居节点，以此类推，直到所有节点都被访问。

优点: 适用于寻找最短路径

缺点: 相较于 DFS，BFS 算法需要更多的内存，因为它需要维护一个队列来存储未访问的顶点。