图的概念和表示方法

完全图：任意两个顶点之间都存在边，则称该图为完全图。含有n个顶点的完全图有$\frac{n(n-1)}{2}$条边。含有n个顶点的有向完全图有$n(n-1)$条边稠密图：边数很多的图称为稠密图稀疏图：边数很少的图称为稀疏图

简单路径：除起点和终点外，其余顶点各不相同简单回路：起点和终点相同的最简路径是简单回路

（强）连通图：任何两个顶点之间都由路径为连通图，对于有向图，则为强连通图连同子图：一张图里的子图是连通图极大连通子图：连同子图包含多少个顶点，就包含这些顶点所有的边（强）连通分量：一个图的极大连同子图称为连同分量

极小连通子图：使图保持连通的同时使边数最少生成树：连同图的生成树是包含图全部顶点，使图保持连通的同时使边数最少。生成森林：在非连通图中，连同分量的生成树构成了非连通图的生成森林。

图的遍历

深度优先遍历

过程：

访问定点v；
依次从v的未被访问过的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止

void DFS(ALGraph &G, int v){
    ArcNode *p;
    visited[v] = 1;
    cout << "VNode: " << G.vertices[v].data << endl;
    for(p=(G.vertices[v]).first;p;p=p->next){
        if(!visited[p->adjvex])
            DFS(G, p->adjvex);
    }    
}

void DFSTraverse(ALGraph &G){
    int v;
    for(v=0;v<G.vexnums;++v){
        if(!visited[v]){
            DFS(G, v);
        }
    }
}

问题：DFS一定分两个函数写吗？有没有可能写成一个函数回答：我尝试写到一个函数，但如果将循环的过程写入递归过程，那么每次调用，v都被重置成了0，陷入死循环，我没有好的办法。

广度优先遍历

过程：

访问顶点vi；
访问vi的所有未被访问的邻接点w1, w2, …, wk;
依次从这些邻接点（在步骤2中访问的顶点）出发，访问它们的所有未被访问的邻接点；依次类推，直到图中所有访问过的顶点的邻接点都被访问。

void BFS(ALGraph &G){
    int u,v;
    ArcNode *p;
    queue<int> Q;
    for(v=0;v<G.vexnums;++v){
        if(!visited[v]){
            visited[v] = 1;
            cout << "VNode: " << G.vertices[v].data << endl;
            Q.push(v);
        }
        while(!Q.empty()){
            u = Q.front();
            Q.pop();
            for(p=(G.vertices[u]).first;p;p=p->next){
                if(!visited[p->adjvex]){
                    Q.push(p->adjvex);
                    cout << "VNode: " << G.vertices[p->adjvex].data << endl;
                    visited[p->adjvex] = 1;
                }
            } 
        }
    }
}

最小代价生成树

Prim算法

口语描述：

假设一张连通图有V~1~…V~n~个节点

有两个集合一个用来存节点，叫V；另一个用来存边叫E。

一开始V里有一个节点u~0~，找这个节点最小权重边相连的那个节点v~0~，把v~0~放进集合v，把边放进集合E。
然再在集合V里所有顶点中找它们具有最小权重的边，把这条边连接的顶点放进集合V，把边放进E。
重复2，直到图的所有节点都放进了V。

此时， T=（V，E）就是最小生成树。

正经说法：

假设N（V，E）是连通网，E~T~是N上最小生成树中边的集合。
算法从V~T~={u~0~}(u~0~$\in$V），E~T~={}开始，重复执行下述操作： 1.在所有u$\in$V~T~，v$\in$V-V~T~的边(u, v)$\in$E中找一条代价最小的边（u~0~, v~0~）, 将其并入集合E~T~，同时将v~0~并入集合V~T~。 2.当V~T~=V则结束，此时E~T~必有n-1条边，则T={V~T~， E~T~｝为N的最小生成树。

// 这个算法不对，这样找到的是最短路径
// 最短路径不一定是最小生成树
void Prim(ALGraph &G, int *final, int *D){
	ArcNode *p;
	int v, w, i;
	for(v=0;v<G.vexnums;++v){
		final[v] = 0; D[v] = G.arcs[0][v];
	}
	final[0] = 1;
	// 遍历找最小权重的节点
	for(i=1;i<G.vexnums;++i){
		min = inf;
		for(w=0;w<G.vexnums;++w){
			if(!final[w]&&D[w]<inf){
				v = w; min = D[w];
				// 打印表示这是最小生成树输出的节点
				cout << v;
			}
		}
		final[v]=1;
		for(w=0;w<G.vexnums;++w){
			// 与Dijkstra的差别就在这里，Dijkstra要加上v之前的路径
			// 因为一开始只有v0一个顶点在集合里，所以往集合里添加节点后，只有两种情况
			// 第一种是加进去这个节点，对其他节点没影响
			// 比如说本来是无穷的，加进去还是无穷；
			// 因为第一次加进去的节点，就是找的权重最小的节点，所以不会有其他权重更小的节点的情况
			// 第二种是，本来是无穷的，但是因为加进去这个节点，其他节点到该节点有路径，所以就更新权重
			// 对一个节点更新权重，也表现为到整个集合的权重。
			// 就像前面说的，每次找的都是不在集合中、权重最小的节点
			if(!final[w]&&G.arcs[v][w]<D[w]){
				D[w] = G.arcs[v][w];
			}
		}
	}
	
}

克鲁斯卡尔（Kruskal）算法

口语描述：每次找权重最小的边，要求这条边连接的两个节点不在同一连同分量上，直到所有节点都在同一连通分量上为止。

不要求掌握算法

破圈法

口语描述：和克鲁斯卡尔算法正好相反，每次找到权重最大的边，删去，直到所有形成一个极小连同子图。

破圈法思路简单，但实现对比PRIM算法和克鲁斯卡尔算法复杂

不要求掌握算法

拓扑排序

一些概念：

有向无环图DAG

AOV网：顶点表示活动，边表示活动的顺序关系的有向图

解决问题：工程能否顺序进行，即工程流程是否合理（AOV网）

拓扑序列：由一个有向无环图的顶点组成的序列，满足以下条件：

每个顶点在出现且只出现一次
若顶点A出现在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

拓扑排序方法：

在有向图选一个无前趋的顶点v，输出之；
从有向图中删除v及以v为尾的弧；
重复1, 2, 直到输出全部顶点或有向图中不存在无前趋的结点为止

int TopoSort(ALGraph &G){
    int Indegree[G.vexnums] = {0};
    ArcNode *p;
    int u, v, count;
    stack<int> SS;
    for(v=0;v<G.vexnums;++v){   //统计每个节点的入度数
        for(p=(G.vertices[v]).first;p;p=p->next){
            ++Indegree[p->adjvex];
        }
    }
    for(v=0;v<G.vexnums;++v){
        cout << "Indegree" << v << ": " << Indegree[v] << endl;
        if(Indegree[v]==0) SS.push(v);
    }
    count = 0;
    cout << "The TopoSort Sequence: " ;
    while(!SS.empty()){
        u = SS.top();
        SS.pop();
        ++count;
        cout << u << " ";
        for(p=(G.vertices[u]).first;p;p=p->next){
            Indegree[p->adjvex]--;
            if(Indegree[p->adjvex]==0)
                SS.push(p->adjvex);
        }
    }
    if(count<G.vexnums) return 0;
    return 1;
}

关键路径

概念：

AOE网：顶点表示事件，边表示活动

解决问题：完成整项工程至少需要多少时间，影响工程进度的是哪些关键子工程。

Note：AOE网除了表示活动的先后次序外，还表示了活动的持续时间。

口语描述：

事件的最早发生时间，就是从开始到这个事件最大的权重加到一块。

最迟发生时间，是把所有的最早开始时间算出来之后，倒着算，这个时候用最后一个事件的最晚发生时间减去最大的权重。

某个节点的最迟发生时间等于，这个节点所指向的下一节点min{最晚开始时间-权重}

正式说法：

事件v~k~的最早发生时间v~e~（k）

从开始顶点V到V~k~的最长路径长度 v~e~（源点） = 0 v~e~（k） = Max{v~e~(j) + Weight(v~j~, v~k~)} Note: 在计算v~e~（k）的时候，是按从前往后的顺序来计算的
事件v~k~的最迟发生时间v~l~（k）

保证它所指向的事件v~i~在v~e~（i）时刻能够发生时，该事件最迟必须发生的时间。 v~l~（汇点） = v~e~（汇点） v~l~（j） = Min{v~l~(k) - Weight(v~j~, v~k~)} Note: 在计算v~l~（k）的时候，是按从后往前的顺序来计算的
活动a~i~的最早开始时间e（i）

该活动的起点所表示的时间最早发生的时间。若边<v~k~, v~j~>表示活动a~i~，则e（i） = v~e~（k）
活动a~i~的最迟开始时间l（i）

该时间时该活动的终点所表示事件的最迟发生时间与该活动所需时间之差。若边<v~k~, v~j~>表示活动a~i~，则l（i） = v~l~（j） - Weight(v~k~, v~j~）
一个活动a~i~的最迟开始时间l（i）和其最早开始时间e（i）的差额d（i）=l（i）- e（i）

在不增加完成整个工程所需总时间的情况下，活动a~i~可以拖延的时间。若d（i）= 0，说明该活动必须如期完成，该活动为关键活动。

求关键路径算法步骤：

求AOE网中所有事件的最早发生时间v~e~()
求AOE网中所有事件的最迟发生时间v~l~()
求AOE网中所有活动的最早开始时间e();
求AOE网中所有活动的最迟开始时间l();
求AOE网中所有活动的差额d(), 找出所有d()=0的活动构成关键路径。

最短路径

最短路径算法依赖一种性质：两点之间的最短路径也包含了路径上其他顶点的最短路径

迪杰斯特拉算法

口语描述

一个集合S，初始存放v~0~节点，有一个数组dist[]存放v~0~到其他顶点的最短路径，初始化时若没有直接路径，则路径长度为$\infty$。
在dist中找最小的那条路径，把那条路径连接的顶点放进S集合。
更新dist中的距离，因为增加了v~j~这个跳板，所以v~0~可以通过v~j~ 到达一些没有直接路径的结点。更新它们的dist为v~0~到v~j~的距离加上v~j~到该顶点的距离。
重复2、3，直到所有的顶点都在S中，dist中的距离就是v~0~到各顶点的最短距离。

问题：这样是把最短距离算出来了，可是路径我们不知道啊？

回答：

Dijkstra算法和Prim算法很像，都属于贪心策略，Prim算法是无向图，Dijkstra是有向图。

void Dijkstra(ALGraph &G, int *D, int (*P)[5], int *final){
    int v, w, i, j;
    int min;
    for(v=0;v<G.vexnums;++v){
        final[v] = 0;
        D[v] = G.AdjMatrixs[0][v];
        for(w=0;w<G.vexnums;++w){
            P[v][w] = 0;
        }
        if(D[v]<inf){
            P[v][0] = 1; P[v][v] = 1;
        }
    }
    D[0] = 0;
    final[0] = 1;
    // i仅仅用来计数，循环n-1次，找n-1个到源点的最短路径
    for(i=1;i<G.vexnums;++i){
        min = inf;
        for(w=0;w<G.vexnums;++w){
            if(final[w]==0&&D[w]<min){
                    // v是找到的当前不在集合中，且到源点最近的点
                    v=w; min = D[w]; 
            }
        }
        // 源点归并进集合
        final[v] = 1;
        // 源点归并入集合后，更新其他节点到源点的路径长度
        for(w=0;w<G.vexnums;++w){
            if(final[w]==0&&min+G.AdjMatrixs[v][w]<D[w]){
                D[w] = min + G.AdjMatrixs[v][w];
                for(j=0;j<5;++j)
                    P[w][j] = P[v][j]; 
                P[w][w] = 1;
            }
        }
    }
    cout << "D: ";
    for(i=0;i<G.vexnums;++i){
        cout << D[i] << " ";
    }
    cout << endl;
    cout << "P: " << endl;
    for(i=0;i<G.vexnums;++i){
        for(j=0;j<G.vexnums;++j){
            cout << P[i][j] << " ";
        }
        cout << endl;
    }
}	

问题：这样我们只是把路径上的结点用矩阵表示出来了，可是并不能表示出路径的先后顺序啊？

回答：可以的，通过矩阵可以看出P[i][i]在其他行之后置1的，那么这个节点就在其他节点之后。但是这样似乎对人来说直观，对计算机来说不直观，只通过一行的数据，我们无法知道路径的先后顺序。

Floyd算法

每次加入一个点，更新每个点到彼此的最短路径。

bool Floyd(int n)
{
	for(int k=0;k<n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(path[i][j]<path[i][k]*path[k][j])   //关键点
				path[i][j]=path[i][k]*path[k][j];
				
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(path[i][i]>1)
		return true;
	}
	return false;
}

void Floyd(ALGraph &G, int (*D)[5], int P[][5][5]){
    int v, w, u;
    int i, j, k;
    for(v=0;v<G.vexnums;++v){
        for(w=0;w<G.vexnums;++w){
            D[v][w] = G.AdjMatrixs[v][w];
            for(u=0;u<G.vexnums;u++) P[v][w][u] = 0;
            if(D[v][w]<inf){
                P[v][w][v] = 1; P[v][w][w] = 1;
            }
        }
    }
    for(u=0;u<G.vexnums;++u){
        for(v=0;v<G.vexnums;++v){
            for(w=0;w<G.vexnums;++w){
                if(D[v][u]+D[u][w]<D[v][w]){
                    D[v][w] = D[v][u] + D[u][w];
                    for(int i=0;i<G.vexnums;++i){
                        P[v][w][i] = P[v][u][i] || P[u][w][i];
                    }
                }
                        
            }
        }
    }
    for(i=0;i<G.vexnums;++i){
        for(j=0;j<G.vexnums;++j){
            if(D[i][j]==inf) cout << -1 << " ";
            else cout << D[i][j] << " ";
        }
        cout << endl;
    }
    for(i=0;i<G.vexnums;++i){
        for(j=0;j<G.vexnums;++j){
            for(k=0;k<G.vexnums;++k){
                cout << P[i][j][k];
            }
            cout << " ";
        }
        cout << endl;
    }
}

【算法与数据结构】图