数据结构--图

1. 术语

1. V(Vertex): 顶点
2. E(Edge): 边
3. (v, w): v顶点与w顶点双向连接
4. <v, w>: v顶点指向w顶点的单项连接

2. 图的表示

2.1 邻接矩阵法

G[i][j] = 1: <v_i, v_j>是G的边

? =0： 无边

1. 无向图用全阵浪费一半空间

   方案：用链表（单行）表示元素下表：(i*(i+1)/2+j)

   ps:整个表看起来：对角线为0，对称

   0
   ...	0
   ...	...	0
   ...	...	...	0
   ...	...	...	...	0

2. 对于网络：值表示权重

   网络：有权重的图

2.2 邻接表法

ps：用这种方法表示的图够稀疏才划算，且：图的表示并非只有这两种，要根据实际情况来设计

G[0]: 指针数组

G[0] --> |下标|指针域| --> |下标|指针域| --> ...

G[1] --> |下标|指针域| --> |下标|指针域| --> ...

...

G[n-1] --> |下标|指针域| --> |下标|指针域| --> ...

ps: 对于带权的网络，还要另加一个域表示权重

特点：

1. 方便找临界点
2. 节约稀疏图的空间（N个头指针+2E个节点）
3. 计算“度”
   • 无向图：方便
   • 有向图：不方便，需构造“你邻接表”来计算“入度”
4. 不方便检查对顶点是否存在边

3. 图的遍历

3.1 DFS

void DFS(Vertex V){
    visited[V] = true;  //点亮第一盏灯
    for(v的每一个邻接点W){  //观察与v相连的灯
        if(!visited[W])  //若未被点
            DFS(W);  //点亮，进入堆栈
    }
}

对于N个顶点，E条边的图，时间复杂度：

1. 邻接表：O(N+E)
2. 邻接矩阵：O(N²)

自然语言描述：往下走，遇到路口挑第一个走，走到不通就往回退，退到起点遍历完成

3.2 BFS

类似树的BFS，树是特殊的图，借助队列来实现

void BFS(Vertex V){
    visited[V] = true;//点灯
    Enqueue(V, Q);//将与V相连的点入队
    while(!IsEmpty(Q)){//队列不空
        V = Dequeue(Q);//出队
        for(V的每个邻接点W){
            visited[w] = true;//电灯
            Enqueue(W,Q);//入队
        }
    }
}

对于N个顶点，E条边的图，时间复杂度：

1. 邻接表：O(N+E)
2. 邻接矩阵：O(N²)

3.3 总结

1. 为何需要两种遍历

   每种遍历适用于不同情况，故两种皆有用

   • BFS：优点是可以得到最优解，缺点是在树的层次较深并且子节点个数较多的情况下，消耗内存现象十分严重。因此，BFS适用于节点的子节点个数不多，并且树的层次不太深的情况。
   • DFS：优点是消耗内存小，缺点是难以寻找最优解，仅仅只能寻找有解。

2. 图不连通怎么办

   //每一个DFS都是在把图的一个连通分量遍历（不连通的部分为一个连通分量）
   void ListComponent(Graph G){
       for(each V in G)//每个连通分量处理一遍
           if(!visited[V])
               DFS(V);
   }
   

4. 最短路径

源点：起点

最短路径

1. 单源最短路径问题（从某点到其他所有点的最短路径）
   • 无权图单源
   • 有权图单源
2. 多源最短路径问题（求任意的顶点的最短路径）

4.1 无权单源

按递增（非递减）的顺序找出到各个顶点的最短路

数据结构--图

原文：https://www.cnblogs.com/blogs-hjq/p/14669160.html