(Graph)图，挑着看看

public class DepthFirstSearch { 
	//索引代表顶点，值表示当前顶点是否已经被搜索 
		private boolean[] marked; 
	//记录有多少个顶点与s顶点相通 
		private int count; 
	
	//构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点 
		public DepthFirstSearch(Graph G,int s){ 
	//创建一个和图的顶点数一样大小的布尔数组 
			marked = new boolean[G.V()]; 
	//搜索G图中与顶点s相同的所有顶点 dfs(G,s); 
		}
	
	//使用深度优先搜索找出G图中v顶点的所有相邻顶点 
		private void dfs(Graph G, int v){ 
	//把当前顶点标记为已搜索 
		marked[v]=true; 
	//遍历v顶点的邻接表，得到每一个顶点w 
		for (Integer w : G.adj(v)){ 
	//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 
			if (!marked[w]){ 
				dfs(G,w); 
			} 
		}
	//相通的顶点数量+1 
		count++; 
	}
	
	//判断w顶点与s顶点是否相通 
	public boolean marked(int w){ return marked[w]; }
	
	//获取与顶点s相通的所有顶点的总数 4
	public int count(){ return count; } 
}

public class BreadthFirstSearch { 
//索引代表顶点，值表示当前顶点是否已经被搜索 
	private boolean[] marked; 
//记录有多少个顶点与s顶点相通 
	private int count; 
//用来存储待搜索邻接表的点 
	private Queue<Integer> waitSearch;
	
//构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点 
	public BreadthFirstSearch(Graph G, int s) { 
//创建一个和图的顶点数一样大小的布尔数组 
		marked = new boolean[G.V()]; 
//初始化待搜索顶点的队列 
		waitSearch = new Queue<Integer>(); 
//搜索G图中与顶点s相同的所有顶点 
		dfs(G, s); 
	}

//使用广度优先搜索找出G图中v顶点的所有相邻顶点 
	private void dfs(Graph G, int v) { 
//把当前顶点v标记为已搜索 
		marked[v]=true; 
//把当前顶点v放入到队列中，等待搜索它的邻接表 
		waitSearch.enqueue(v); 
//使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表 
		while(!waitSearch.isEmpty()){ 
			Integer wait = waitSearch.dequeue(); 
//遍历wait顶点的邻接表，得到每一个顶点w 
			for (Integer w : G.adj(wait)) { 
//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 
				if (!marked[w]) {
 					dfs(G, w); 
				} 
			} 
		}
//相通的顶点数量+1 
		count++; 
	}
	
//判断w顶点与s顶点是否相通 
	public boolean marked(int w) { 
		return marked[w]; 
	}
	
//获取与顶点s相通的所有顶点的总数 
	public int count() { 
		return count; 
	} 
}

class Graph { 
    int V;  // 顶点的个数
    list<int> *adj; // 所有顶点的起始指针
};

void topologicalSort(int V, list<int> *adj) { 
    // 计算所有入度
    vector<int> in_degree(V, 0);   
    for (int u=0; u<V; u++) { 
        list<int>::iterator itr; 
        for (itr = adj[u].begin(); itr != adj[u].end(); itr++) {
             in_degree[*itr]++; 
        }
    } 
    // 加入入度为0的点
    queue<int> q; 
    for (int i = 0; i < V; i++) { 
        if (in_degree[i] == 0) q.push(i); 
    }
    int cnt = 0;   
    vector <int> top_order;   
    while (!q.empty()) { 
        int u = q.front(); 
        q.pop(); 
        top_order.push_back(u);   
        // 所有连接点, 入度减去1
        list<int>::iterator itr; 
        for (itr = adj[u].begin(); itr != adj[u].end(); itr++) {
            if (--in_degree[*itr] == 0) q.push(*itr); 
        }
        cnt++; 
    } 
    if (cnt != V) { 
        cout << "There exists a cycle in the graph\n"; 
        return; 
    }   
    for (int i=0; i<top_order.size(); i++) 
        cout << top_order[i] << " "; 
    cout << endl; 
} 

bool isCyclicGraph(vector<int> &start, vector<int> &end) {
    // 找到最大顶点值,构造图,
    int n = 0;
    for (int s : start) {
        n = max(n, s);
    }
    for (int e : end) {
        n = max(n, e);
    }
    // 构造图
    vector<vector<int>> graph(n + 1);
    vector<int> d(n + 1);
    int m = start.size();
    // 计算所有顶点的入度
    for (int i = 0; i < m; i++) {
        graph[start[i]].push_back(end[i]);
        d[end[i]]++;
    }
    queue<int> que;
    // 将所有入度为0的点,加入队列
    for (int i = 1; i <= n; i++) {
        if (graph[i].size() && !d[i]) {
            que.push(i);
        }
    }
    while (!que.empty()) {
        int h = que.front();
        que.pop();
        // 将多有入度为0的点,对应的顶点 入度减去1
        for (int y : graph[h]) {
            d[y]--;
            if (!d[y]) {
                que.push(y);
            }
        }
    }
    // 判断是否所有顶点的入度都是0, 如果是,则没有环,否则就有
    for (int i = 1; i <= n; i++) {
        if (d[i]) {
            return true;
        }
    }
    return false;
}

int minDistance(vector<int> dist, set<int> sptSet) {
    int min_d = INT_MAX, u;
    for(int i = 0, i < dist.size(); i ++) {
        if(sptSet.find(i) == sptSet.end() && dist[v] < min_d) {
            min_d = dist[i], u = i;
        }
    }
    return u;
}
// 使用vector 表示的邻接矩阵, return 起始点到所有点的最小距离
// 没有边的用0填充
vector<int> dijstra(vector<vector<int>> graph, set<int> &sptSet,int src) {
    int V = graph.size();
    vector<int> dist(V, 0);
    for(int i = 0;i < V; i ++) {
        if(i != src) dist[i] = INT_MAX;
    }
    while(sptSet.size() < V-1) {
        // pick mininum distance u
        int u = minDistance(dist, sptSet); 
        sptSet.insert(u);
        // 使用u更新距离
        for(int v = 0; v < V; v ++) {
            if(sptSet.find(v)==sptSet.end() && graph[u][v] 
                        && dist[u] != INT_MAX
                        && dist[u]+graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist;
}