图论算法_图论 处理负边权

一、基本概念
（一）、什么是图？
　　很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合。

（二）、图的一些定义和概念
(a)有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。
(b)无向图：图的边没有方向，可以双向。(b)就是一个无向图。

结点的度：无向图中与结点相连的边的数目，称为结点的度。
结点的入度：在有向图中，以这个结点为终点的有向边的数目。
结点的出度：在有向图中，以这个结点为起点的有向边的数目。
权值：边的“费用”，可以形象地理解为边的长度。
连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。
回路：起点和终点相同的路径，称为回路，或“环”。
完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边；

稠密图：一个边数接近完全图的图。
　　　　稀疏图：一个边数远远少于完全图的图。
　　　　
强连通分量：有向图中任意两点都连通的最大子图。右图中，1-2-5构成一个强连通分量。特殊地，单个点也算一个强连通分量，所以右图有三个强连通分量：1-2-5，4，3。

二、图的遍历
（一）、深度优先与广度优先遍历
1、深度优先遍历

void dfs(int i)                                    //图用数组模拟邻接表存储，访问点i
　{
　　 visited[i] = true;                           //标记为已经访问过
　　 for (int j = 1; j <= num[i]; j++)      //遍历与i相关联的所有未访问过的顶点
　　    if (!visited[g[i][j]])
　　       dfs(g[i][j]); 
　}

主程序如下:
　int main()
　{
    ……
    memset(visited,false,sizeof(visited));
    for (int i = 1; i <= n; i++)                  //每一个点都作为起点尝试访问，因为不是从任何
                                                           //一点开始都能遍历整个图的，例如下面的两个图。
        if (!visited[i])
            dfs(i);
    ……
    return 0;
　}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2、广度优先遍历参考广搜
最短路径算法
一、.Floyed-Warshall算法 O(N3)

初始化：点u、v如果有边相连，则dis[u][v]=w[u][v]。
　　如果不相连则dis[u][v]=0x7fffffff
For (k = 1; k <= n; k++)
    For (i = 1; i <= n; i++)
	 For (j = 1; j <= n; j++)
	     If (dis[i][j] >dis[i][k] + dis[k][j])
	         dis[i][j] = dis[i][k] + dis[k][j];
 算法结束：dis[i][j]得出的就是从i到j的最短路径。
　如果是一个没有边权的图，把相连的两点间的距离设为dis[i][j]=true，不相连的两点设为dis[i][j]=false，用Floyed算法的变形：
For (k = 1; k <= n; k++)
  For (i = 1; i <= n; i++)
    For (j = 1; j <= n; j++)
　　  dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
       用这个办法可以判断一张图中的两点是否相连。
　
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、Dijkstra算法O (N2)
用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。
Dijkstra的时间复杂度是O (N2)，它不能处理存在负边权的情况。
算法描述：
设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。
a)初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0;
b)For (i = 1; i <= n ; i++)
1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。
2.u标记为已确定最短路径
3.For 与u相连的每个未确定最短路径的顶点v
if (dis[u]+w[u][v] < dis[v])
{
dis[v] = dis[u] + w[u][v];
pre[v] = u;
}
c)算法结束：dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。
三、Bellman-Ford算法O(NE)
简称Ford（福特）算法，同样是用来计算从一个点到其他所有点的最短路径的算法，也是一种单源最短路径算法。
能够处理存在负边权的情况，但无法处理存在负权回路的情况（下文会有详细说明）。
算法时间复杂度：O(NE)，N是顶点数，E是边数。
算法实现：
设s为起点，dis[v]即为s到v的最短距离，pre[v]为v前驱。w[j]是边j的长度，且j连接u、v。
初始化：dis[s]=0,dis[v]=∞（v≠s），pre[s]=0
For (i = 1; i <= n-1; i++)
For (j = 1; j <= E; j++) //注意要枚举所有边，不能枚举点。
if (dis[u]+w[j]<dis[v]) 　 //u、v分别是这条边连接的两个点。
{
dis[v] =dis[u] + w[j];
pre[v] = u;
}