图的基本概念及表示

图的基本概念

逻辑结构二元组B=(K,R),任意一对结点间都允许一个关系存在

  • 分类:无向图、有向图、带权图、稠密图、完全图、连通图等
  • 最一般的数据结构

表示:G=(V, E),有向完全图 $n * (n - 1)$ 条边,无向完全图 $n * (n - 1) / 2$ 条边

带权的连通图称为网络

图G有$n$个顶点,$e$条边,顶点$v_{i}$的度数为$TD(v_{i})$,则有$$e = \frac{1}{2} \sum_{i = 0}^{n - 1}TD(v_{i})$$

环:回路,无向图平行边不构成环,有向图两条边可构成环

连通

连通图:任何两个顶点之间至少存在一条路径

连通分量:不连通的无向图的极大连通子图

强连通:有向图,不同两顶点间存在方向相反的有向路径

强连通分量:非强连通有向图的极大连通子图

生成树:含有全部顶点的一个极小连通子图

若有向图存在顶点有路径到达所有其他顶点,则称有根图

图的储存结构

  • 邻接矩阵
  • 邻接链表
  • 十字链表

邻接矩阵

表达较为稠密的图

$$ A[i, j] = \begin{cases} 1& {(V_{i}, V_{j})\in E \ \lor <V_{i}, V_{j}>\in E } \\ 0& {(V_{i}, V_{j})\notin E \ \lor <V_{i}, V_{j}>\notin E }\end{cases} $$

带权图将其标为每条边的权值

空间代价$O(|V|^{2})$,只与定点数有关

易于确定是否有边

邻接表

顺序存储的顶点表和链接存储的边表

无向图空间代价$O(|V| + 2|E|)$,有向图$O(|V| + |E|)$(入边表、出边表)

带权图直接加一个字段

易于表达稀疏表并增删边

十字链表

  • 顶点表:顺序存储:顶点信息,指向第一条以该点为终点的弧的指针,第一条以其为始的弧的指针
  • 边表:弧头、弧尾、下一条以弧尾为弧尾的弧、下一条以弧头为弧头的弧、弧权值

图的相关算法

ADT

struct Edge
{
    int from, to, weight;
};
struct Graph
{
    int Mark[MAXN];
    int indegree[MAXN];
    int VerticesNum();
    int EdgeNum();
    Edge FirstEdge(int oneVertex);
    Edge NextEdge(Edge preEdge);
    bool setEdge(int fromVertex, int toVertex, int weight);
    bool delEdge(int fromVertex,int toVertex);
    bool IsEdge(Edge oneEdge);
    int FromVertex(Edge oneEdge);
    int ToVertex(Edge oneEdge);
    int Weight(Edge oneEdge);
};

图的周游

每个顶点访问一次

DFS BFS Topological sort

  • 邻接表:时间复杂度有向图$\Theta(n + e)$,无向图$\Theta(n + 2e)$
  • 相邻矩阵:$\Theta(n + n^{2}) = \Theta(n^{2})$

拓扑排序

有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程

无环有向图G中顶点的线性序列称作一个拓扑序列,若有$v \to w$则$v$在$w$前出现

有向图拓扑序列不唯一

对任意有向无环图(DAG),选择入度为0的点删去,再删去其所有出边,并将对应邻接点入度减1

bool TopsortbyQueue(Graph &G)
{
    for (int i = 0; i < G.VerticesNum(); i++)
        G.Mark[i] = UNVISITED;
    std::queue<int>Q;
    for (int i = 0; i < G.VerticesNum(); i++)
        if (G.indegree[i] == 0)
            Q.push(i);
    while (!Q.empty())
    {
        int v = Q.front();
        Q.pop();
        Visit(G, v);
        G.Mark[v] = VISITED;
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e))
        {
            G.indegree[G.ToVertex(e)]--;
            if (G.indegree[G.ToVertex(e)] == 0)
                Q.push(G.ToVertex(e));
        }
    }
    for (int i = 0; i < G.VerticesNum(); i++)
        if (G.Mark[i] == UNVISITED)
            return false;
    return true;
}

时间代价:邻接表:$O(|V| + |E|)$;邻接矩阵$\Theta(|V|^{2})$

最短路径

单源最短路径

Dijkstra
  • 对于能直接到达的点,将距离设为权值,不能直接到达的设为无穷大
  • 如果存在$u$到$v$的边,那$s$到$v$的最短路径即为$min((d[u] + w(u, v), d[v])$
  • 每次松弛后选择最近的顶点重复操作

要求非负权边(贪心),时间代价为最小堆$O((n + e)log \ e)$,直接比较$O(n^{2})$

function Dijkstra(G, w, s)
    for each vertex v in V[G]                        // 初始化
          d[v] := infinity                                 // 將各點的已知最短距離先設成無窮大
          previous[v] := undefined                         // 各点的已知最短路径上的前趋都未知
    d[s] := 0                                              // 因为出发点到出发点间不需移动任何距离,所以可以直接将s到s的最小距离设为0
    S := empty set
    Q := set of all vertices
    while Q is not an empty set                      // Dijkstra演算法主體
          u := Extract_Min(Q)
          S.append(u)
          for each edge outgoing from u as (u,v)
                 if d[v] > d[u] + w(u,v)             // 拓展边(u,v)。w(u,v)为从u到v的路径长度。
                       d[v] := d[u] + w(u,v)               // 更新路径长度到更小的那个和值。
                       previous[v] := u                    // 紀錄前趨頂點
Floyd-Warshall

动态规划

直接对所有边进行松弛,共进行$V - 1$次,如果经过中间节点比不经过要优即更新

通过三重循环检查了所有的可能性,时间代价$O(|V|^{3})$

最小生成树

Prim算法

取最小权边,接着取与已知点相关联的最小权边

最小堆实现

Kruskal算法

每次加入代价最小的边,但是该边关联两个顶点必须属于不同的连通分支(等价类)