特定の学校の友達である学生で構成される無向の友情グラフに取り組んでいます。dfs を使用してクリーク (グラフから接続されているすべてのサブグラフ) を取得したい。しかし、何らかの理由で私のdfsが正しく機能していません..アルゴリズムまたはコードに関する提案は大歓迎です
これは手動で作成されたサンプル グラフです。
import java.util.LinkedHashMap;
public class DFS {
/**
* @param args
*/
class Node {
String personName, schoolName;
Node next;
public Node(String personName, String schoolName, Node next) {
this.personName = personName;
this.schoolName = schoolName;
this.next = next;
}
public String toString() {
return this.personName + " " + this.schoolName;
}
}
public Node[] build() {
Node[] graph = new Node[6];
for (int i = 0; i < graph.length; i++) {
Node temp = new Node(Integer.toString(i + 1), "MIT", null);
graph[i] = temp;
}
graph[0].next = new Node("2", "MIT", null);
graph[1].next = new Node("1", "MIT", null);
graph[1].next.next = new Node("3", "MIT", null);
graph[1].next.next.next = new Node("4", "MIT", null);
graph[2].next = new Node("2", "MIT", null);
graph[2].next.next = new Node("4", "MIT", null);
graph[3].next = new Node("3", "MIT", null);
graph[3].next.next = new Node("2", "MIT", null);
graph[4].next = new Node("6", "MIT", null);
graph[5].next = new Node("5", "MIT", null);
printGraph(graph);
return graph;
}
public void dfsDriver() {
Node[] graph = build();
LinkedHashMap<String, Integer> names = new LinkedHashMap<String, Integer>();
int count = 0;
for (int i = 0; i < graph.length; i++) {
if (graph[i] != null) {
names.put(graph[i].personName, count);
count++;
}
}
boolean[] visited = new boolean[graph.length];
for (int v = 0; v < visited.length; v++) {
visited[v] = false;
}
for (int i = 0; i < graph.length; i++) {
if (graph[i] != null) {
if (!visited[i]) {
System.out.println("Starting at " + graph[i].personName);
dfs(i, visited, names, graph);
}
}
}
}
private void dfs(int i, boolean[] visited, LinkedHashMap<String, Integer> names, Node[] subGraph) {
visited[i] = true;
for (Node e = subGraph[i].next; e != null; e = e.next) {
System.out.println("visiting " + e.personName);
int index = names.get(e.personName);
if (!visited[index]) {
dfs(index, visited, names, subGraph);
}
}
}
public void printGraph(Node[] list) {
System.out.println();
for (int i = 0; i < list.length; i++) {
if (list[i] != null) {
System.out.print(list[i]);
for (Node a = list[i].next; a != null; a = a.next) {
System.out.print(" " + a);
}
System.out.println();
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
DFS a = new DFS();
a.dfsDriver();
}
}