package myAlgorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//定义链表的数据结构，用于存储图
class Node {
Vertex vex;// 头结点
Node Next;// 下一个节点
}

//定义节点的数据结构
class Vertex {
String name;// 顶点的名字
Node root;// 以这个节点作为链表的头节点
boolean visited;// 用来识别这个链表是否被访问过
}

//根据自己的理解，重敲一遍DFS和BFS
public class MyDFS {

Vertex[] vts;// 顶点集合
Node[] nodes;// 链表集合
ArrayList<Vertex> path;// 访问路径
int n = 0;
Scanner sc = new Scanner(System.in);

/**
 * 输入顶点数据
 */
public void GetVts() {
    System.out.println("输入你要输入顶点的个数");
    n = sc.nextInt();
    vts = new Vertex[n];
    nodes = new Node[n];
    sc.nextLine();
    for (int i = 0; i < n; i++) {
        System.out.println("请输入第" + (i + 1) + "个顶点");
        vts[i] = new Vertex();
        nodes[i] = new Node();
        vts[i].name = sc.nextLine();
        nodes[i].vex = vts[i];
        vts[i].root = nodes[i];
    }
}

/**
 * 创建图
 */
public void CreateGra() {

    String str = null;
    String[] strarr = null;
    for (int i = 0; i < n; i++) {
        System.out.println("输入" + vts[i].name + "顶点所链接的其他顶点，用空格隔开。（注意第一个顶点下标是0）");
        str = sc.nextLine();
        Node p = nodes[i];
        if (!str.equals("")) {
            strarr = str.split(" ");
            for (int j = 0; j < strarr.length; j++) {
                p.Next = new Node();
                p.Next.vex = vts[Integer.valueOf(strarr[j])];
                p = p.Next;
            }
        }

    }
    sc.close();
}

/**
 * 
 * 第一个for 用于遍历所有的顶点 只有全部节点都被访问过才有可能返回 遍历步骤: 1. 如果该节点未被访问过，则接下来访问它的链表。 2.
 * 将链表中每一个元素当做新的链表头进行递归操作。 3. path 用于记录访问顺序
 * 
 * 总结 ： 第一个for 确保所有节点都被访问过 Dfsvisit 则确保每条链表都被检查过， 但不一定进行操作。
 * 
 */
public void Dfs() {
    path = new ArrayList<Vertex>();
    for (int i = 0; i < n; i++) {
        if (vts[i].visited == false) {
            vts[i].visited = true;
            path.add(vts[i]);
            DFsvisit(vts[i].root);
        }
    }
}

public void DFsvisit(Node node) {
    Node p = node.Next;
    while (p != null) {
        if (p.vex.visited == false) {
            p.vex.visited = true;
            path.add(p.vex);
            DFsvisit(p.vex.root);
        } else {
            p = p.Next;
        }
    }
}

/**
 * 要点： 通过辅助队列， 实现Bfs算法。 1. 先将一个链表的头节点加入队列。 2. 通过while 链表内每一个节点所对应的链表的头结点加入队列中 3.
 * 改变节点的状态， 将节点加入到路径中即可
 * 
 * 
 */
public void Bfs() {
    path = new ArrayList<Vertex>();
    Queue<Node> qu = new LinkedList<Node>();
    qu.add(nodes[0]);
    while (!qu.isEmpty()) {
        Node p = qu.remove();
        while (p != null) {
            if (p.vex.visited == false) {
                p.vex.visited = true;
                path.add(p.vex);
                p = p.Next;
                if (p != null) {
                    qu.add(p.vex.root);
                }
            } else {
                p = p.Next;
            }
        }
    }

}

/**
 * 打印图
 */
public void PrintGraph() {
    for (int i = 0; i < nodes.length; i++) {
        Node p = nodes[i];
        System.out.println("这是顶点" + nodes[i].vex.name + "的链表");
        while (p != null) {
            System.out.print(p.vex.name + "->");
            p = p.Next;
        }
        System.out.println();
    }
}

/**
 * 将访问路径打印出来
 */
public void prinpath() {
    System.out.print("搜索路径：" + path.get(0).name);
    for (int i = 1; i < path.size(); i++) {
        System.out.print("->" + path.get(i).name);
    }
    System.out.println();
}

public static void main(String[] args) {
    MyDFS gp = new MyDFS();
    gp.GetVts();
    gp.CreateGra();
    gp.PrintGraph();

// System.out.println("执行DFS输出");
// gp.Dfs();
// gp.prinpath();
System.out.println("执行BFS输出");
gp.Bfs();
gp.prinpath();
}

}