图论——例题

Ann ·

更新时间:2024-09-20

· 900 次阅读

在这里插入图片描述

运用java语言编写的程序：

import java.util.ArrayList;
import java.util.List;
public class Main{
	static String str[] = { "English", "Chinese,English", "English,Italy,Russian", "Chinese,Japanese", "German,Italy",
			"Japanese,Russian,French", "French,German" };
	static List list = new ArrayList();
	public static void main(String[] args) {
		String[] s = new String[7];
		s[0] = "English";
		s[1] = "Chinese,English";
		s[2] = "English,Italy,Russian";
		s[3] = "Chinese,Japanese";
		s[4] = "German,Italy";
		s[5] = "Japanese,Russian,French";
		s[6] = "French,German";
		f(s, 0);
		System.out.println(list.get(0));
	}
	public static void f(String[] s, int k) {
		if (k == s.length) {
			if (check(s)) {
				String result = "";
				for (int i = 0; i < s.length; i++) {
					if (s[i].equals(str[0])) {
						// System.out.println(s[i]+"----"+"a");
						result += "a";
					} else if (s[i].equals(str[1])) {
						// System.out.println(s[i]+"----"+"b");
						result += "b";
					} else if (s[i].equals(str[2])) {
						// System.out.println(s[i]+"----"+"c");
						result += "c";
					} else if (s[i].equals(str[3])) {
						// System.out.println(s[i]+"----"+"d");
						result += "d";
					} else if (s[i].equals(str[4])) {
						// System.out.println(s[i]+"----"+"e");
						result += "e";
					} else if (s[i].equals(str[5])) {
						// System.out.println(s[i]+"----"+"f");
						result += "f";
					} else {
						// System.out.println(s[i]+"----"+"g");
						result += "g";
					}
				}
				list.add(result);
				return;
				// System.out.println("=====================================");
			}
		}
		for (int i = k; i < s.length; i++) {
			{
				String ss = s[k];
				s[k] = s[i];
				s[i] = ss;
			}
			f(s, k + 1);
			{
				String ss = s[k];
				s[k] = s[i];
				s[i] = ss;
			}
		}
	}
	// 判断s1和s2是否为反转字符串
	public static boolean isInverseString(String s1, String s2) {
		if (s1.equals(f(s2)))
			return true;
		return false;
	}
	// 返回字符串的倒序输出字符串
	public static String f(String s) {
		if (s.length() == 1)
			return s;
		return f(s.substring(1)) + s.charAt(0);
	}
	// 判断s2中是否包含s1的某个部分
	public static boolean subS(String s1, String s2) {
		String[] ss1 = s1.split(",");
		for (int i = 0; i < ss1.length; i++) {
			if (s2.contains(ss1[i]))
				return true;
		}
		return false;
	}
	// 判断是否符合每个人都可以和旁边人交流
	public static boolean check(String[] s) {
		int sum = 0;
		for (int i = 1; i < s.length; i++) {
			if (subS(s[i], s[i - 1]) && subS(s[0], s[s.length - 1]))
				sum++;
		}
		if (sum == s.length - 1)
			return true;
		return false;
	}
}