算法概论实验十

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
实验十
实验目的与要求：
（1）	掌握使用图的深度优先搜索算法实现对有向图中是否包含环的判断；
（2）	掌握使用图的深度优先搜索算法实现对有向图的强连通分量的划分。
1．有向图中环的判断问题
【问题描述】
给定一个有向图，要求使用深度优先搜索策略，判断图中是否存在环。

2．有向图的强连通分量问题
【问题描述】
给定一个有向图，设计一个算法，求解并输出该图的各个强连通分量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
import java.util.ArrayList;

public class exam10 {
	//1.有向图判环
	public static String havecycle(int[][] a)
	{	
		if(DFS(a))	//如果没环		
			return "no cycle";
		else
			return "have cycle";
	}
	
	public static boolean DFS(int[][] a)
	//有环返回false
	{
		boolean test = true;
		int length = a.length;
		String[] color = new String[length];
		for(int i=0;i<length;i++)
			color[i] = "white";
		//int clock = 1;
		for(int i=0;i<length;i++)
			if(color[i] == "white")
			{
				test = explore(a,i,color);
				if(test == false)
					return false;
			}
		return true;
	}
	public static boolean explore
	(int[][] a,int u,String[] color)	
	//以u为顶点进行探索
	{
		color[u] = "gray";
		for(int v=0;v<a.length;v++)
		{
			if(a[u][v]!=0 && color[v]=="white")
				explore(a,v,color);
			if(a[u][v]!=0 && color[v]=="gray")	
			//如果有一条回边，表示有一个环
				return false;
		}
		color[u] = "black";
		return true;
	}
	
	//2.找强连通分量
	public static void findSC(int[][] a1)
	{	
		int length = a1.length;
		int[][] a = new int[length][length];
		int[][] b = new int[length][length];
		getGR(a1,b);
		//b是反向图
		getGR(b,a);
		//防止修改原图a=a1
		Set[] set = new Set[length];
		int count = 0;	
		int sum = 0;
		//要在反向图中找一个Post值最大的点,以这个点为起点，在原图上进行DFS，则找到一个强连通部件
		do
		{
			System.out.print("第"+(count+1)+"个连通分量为：");
			getGR(a,b);
			int maxpost = findmaxpost(b);
			set[count]  = DFS2(a,maxpost);		//第一个强连通部件set[0]
			//去掉这个连通部件中的点
			for(int i=0;i<set[count].value.size();i++)
			{
				int p = set[count].value.indexOf(i);
				delete(a,p);	
			}
			sum = sum + set[count].value.size();		//sum计算去掉的点数
			count++;
			System.out.println();
		}while(sum<length);
	}
	
	//在一个图中找出post值最大的节点点
	public static int findmaxpost(int[][] a)
	{
		int max = 0;
		int maxindex = 0;
		int[] post = new int[a.length];
		DFS1(a,post);
		for(int i=0;i<a.length;i++)
		{
			int temp = max;
			max = Math.max(max, post[i]);
			if(max != temp)
				maxindex = i;
		}
		return maxindex; 
	}
	
	public static void DFS1(int[][] a,int[] post)	
	{
		int length = a.length;
		
		String[] color = new String[length];
		for(int i=0;i<length;i++)
			color[i] = "white";
		
		int[] clock = new int[1];
		clock[0] = 1;
		
		for(int i=0;i<length;i++)
			if(color[i] == "white")
			{
				explore1(a,i,color,post,clock);
			}
	}
	
	public static void explore1
	(int[][] a,int u,String[] color,int[] post,int[] clock)//以u为顶点进行探索
	{
		color[u] = "gray";
		clock[0]++;
		for(int v=0;v<a.length;v++)
		{
			if(a[u][v]!=0 && color[v]=="white")
				explore1(a,v,color,post,clock);
		}
		color[u] = "black";
		post[u] = clock[0];
		//System.out.print("post["+u+"]="+post[u]+" ");
		clock[0]++;
	}
	//获得一个图的反向图
	public static void getGR(int[][] a,int[][] b)
	{
		for(int i=0;i<a.length;i++)
			for(int j=0;j<a.length;j++)
				b[i][j] = a[j][i];
	}
	//返回u能访问到的点集
	public static Set DFS2(int[][] a,int u)	
	{
		Set s = new Set();
		int length = a.length;
		String[] color = new String[length];
		for(int i=0;i<length;i++)
			color[i] = "white";
		//初始化完成
		explore2(a,u,color,s);
		return s;
	}
	public static void explore2(int[][] a,int u,String[] color,Set s)//以u为顶点进行探索
	{
		s.value.add(u);
		System.out.print(u+" ");
		color[u] = "gray";
		for(int v=0;v<a.length;v++)
		{
			if(a[u][v]!=0 && color[v]=="white")
				explore2(a,v,color,s);
		}
		color[u] = "black";
	}	
	
	//删除a中所有与p相连的边
	public static void delete(int[][] a,int p)
	{
		for(int i=0;i<a.length;i++)
		{
			a[i][p] = 0;
			a[p][i] = 0;
		}		
	}
	
	
	public static void main(String[] args) {
		//测环
		int[][] a = new int[6][6];
		for(int i=0;i<a.length;i++)
			for(int j=0;j<a.length;j++)
				a[i][j] = 0;	
		a[1][0] = 1;a[1][3] = 1;a[2][1] = 1;a[3][4] = 1;
		a[4][5] = 1;a[5][2] = 1;a[5][3] = 1;
		System.out.println(havecycle(a));
		//强连通分量
		findSC(a);

	}
}