算法设计与分析复习题(7)

using namespace std;

int l[M][M]; int c[M][M][M]; int link[M][M]; int main() { int n;

cout<<\输入图的节点数:\ cin>>n; int line;

cout<<\输入有向边的数量:\ cin>>line;

vector graph[20];

memset(l,0,sizeof(l));

for(int i=0;i

int a,b;

cout<<\输入相连的两个节点(a->b):\cin>>a; cin>>b; if (a>=n||b>=n) { }

graph[a].push_back(b); l[a][b]=1;

cout<<\输入节点出错:\return 0;

}

for (int i=0;i

for (int k=1;k

for (int i=0;i

for(int j=0;j

link[i][j]=c[i][j][n-1];

for (int i=0;i

for(int j=0;j

c[i][j][k]=c[i][j][k-1]+c[i][k][k-1]*c[k][j][k-1]; if(c[i][j][k]>=1) c[i][j][k]=1; }

for(int j=0;j

// cout<

if(link[i][j]>=1)

cout<<\节点\到节点\有通路\

memset(visited,0,sizeof(visited)); { } return 0;*/ }

四、算法结果

34、 二叉检索树的主要问题是树高，编写一个控制检索树树高的算法。

void OBST(int n) { int i,j,r,l; double t;

for(i=1;i<=n+1;i++) { }

for( l=1;l<=n;l++) {

for ( i=1;i<=n-l+1;i++) c[i][i-1]=q[i-1]; w[i][i-1]=q[i-1];

cout<<\节点\邻接节点:\

for(vector::iterator it=graph[i].begin();it!=graph[i].end();it++) { }

cout<

cout<<*it;

for(int i=0;i

}

{ }

j=i+l-1; c[i][j]=9999999;

w[i][j]=w[i][j-1]+p[j]+q[j]; for( r=i;r<=j;r++) { }

t=c[i][r-1]+c[r+1][j]+w[i][j]; if(t

c[i][j]=t; root[i][j]=r;

return; }

35、 试写一个在2—3树的插入节点的算法；以及在2—3树的删除节点的算法。 36、 采用深度优先算法找出一个无向图的所有双向连通分支。 37、 编写一个算法，找出一个有向图的所有强连同分支。

38、 为什么查找连通分支的算法总是采用深度优先算法，采用宽度优先算法可以

吗？为什么？ 39、 编写找出一个网络的最大流的算法。

#include #include

using namespace std;

const int maxN=201;

static int edge[maxN][maxN]; bool visited[maxN]; int father[maxN]; int N, M; //边数,顶点数 int ans; //结果 void Ford_Fulkerson( ) {

while(1) {

//一次大循环,找到一条可能的增广路径 queue q;

memset(visited, 0, sizeof(visited)); memset(father, -1, sizeof(father)); int now; visited[0] = true; q.push(0);

while(!q.empty())//广度优先 {

now = q.front(); q.pop();

if(now == M-1) break; for(int i = 0; i < M; i++) {

//每次父亲节点都要更新,权值减为0的边就不算了. if(edge[now][i] && !visited[i]) {

father[i] = now;