[TOC]
基本概念
邻接矩阵
邻接表
Depth-First-Search
public void DFS(){
int[] visited = new int[NumVertices];
for(int i = 0; i < NumVertices; i++){
vistied[i] = 0;
DFS(0, visited);
}
}
public void DFS(int v, int[] visited){
System.out.print(Getvalue(v));
visited[v] = 1;
int w = GetFirstNeighbor(v);
while(w != -1){
if(!vistied[w]){
DFS(w, visited);
}
w = GetNextNeighbor(v, w);
}
}
Breadth-First Search(Graph)
遍历每个元素
思想：从图中某顶点V~0~出发，在访问了V~0~之后依次访问v~0~的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先遍历图，直至图中所有顶点都被访问到为止.
import java.util.LinkedList;
import java.util.Queue;
public class Graph<NameType, DistType> {
private int NumVertices; // 图中顶点的数量
// 假设有以下成员函数，需要根据实际情况实现
private int[] neighbors; // 存储每个顶点的邻接顶点
private NameType[] names; // 存储每个顶点的名称
public Graph(int numVertices) {
this.NumVertices = numVertices;
this.neighbors = new int[numVertices];
this.names = (NameType[]) new Object[numVertices]; // 泛型数组初始化
}
public NameType GetValue(int v) {
return names[v];
}
public int GetFirstNeighbor(int v) {
// 返回顶点v的第一个邻接顶点的索引，如果没有则返回-1
// 需要根据实际的图结构实现
return -1;
}
public int GetNextNeighbor(int v, int w) {
// 返回顶点v的下一个邻接顶点的索引，如果没有则返回-1
// 需要根据实际的图结构实现
return -1;
}
public void BFS(int v) {
boolean[] visited = new boolean[NumVertices];
for (int i = 0; i < NumVertices; i++) {
visited[i] = false;
}
System.out.print(GetValue(v) + " ");
visited[v] = true;
Queue<Integer> q = new LinkedList<>();
q.pull(v);
while (!q.isEmpty()) {
v = q.pop();
int w = GetFirstNeighbor(v);
while (w != -1) {
if (!visited[w]) {
System.out.print(GetValue(w) + " ");
visited[w] = true;
q.pull(w);
}
w = GetNextNeighbor(v, w);
}
}
}
// 假设有其他成员函数和构造函数等
}
重要的在于用了一个queue去pull邻接顶点进去
Prim算法
用来求最小生成树的 适用于顶点少边多
我们需要做的是维护一个nearvex数组和lowcost数组
设：原图的顶点集合V(有n 个）
生成树的顶点集合 U(最后也有n个），一开始为空
TE集合为{ }
步骤：
1)U={1}任何起始顶点，TE={ }
2)每次生成（选择）一条边。这条边是所有边(u,v)中代价（权）最小的边，
u属于U,v 属于U
TE=TE+[(u,v)];
U=U+[v]
3)当U!=V
public MST Prim(Graph graph){
MST T = new MST();
int[] nearvex = new int[graph.NumVertices];//记录生成树顶点集合外各顶点，距离集合内哪个顶点最近。
float[] lowcost = new float[graph.NumVertices];//存放生成树顶点集合内顶点到生成树外各顶点的边上的当前最小权值；
for(int i = 1; i < graph.NumVertices; i++){
lowcost[i] = Edge[0][i];
nearvex[i] = 0;
nearvex[0] = -1;
}
for(int i = 1; i < graph.NumVertices; i++){
float min = Integer.MAX_VALUE;
int v = 0;
for(int j = 1; j < graph.NumVertices; j++){
if(nearvex[i] != -1 && lowcost[i] < min ){
min = lowcost[i];
v = j;
}
}
if(v){
MSTEdgeNode e = new MSTEdgeNode();
e.tail = nearvex[v];
e.head = v;
e.cost = lowcost[v];
T,insert(e);//更新生成树
nearvex[v] = -1;//代表这个点已经进入生成树
for(int j = 1; j < graph.NumVertices; j++){
if(nearvex[j] != -1 && lowcost[j] > Edge[v][j]){
nearvex[j] = v;
lowcost[j] = Edge[v][i];
}
}
}
}
return T;
}
O(n^2^)的时间复杂度
Kruskal算法
用来求最小生成树的 适用于顶点多边少
引入一个并查集和一个堆
把边按大小排序，从小到大往生成树里引入边，每次都要保证不和生成树中已有的边构成回路.
MST Kruskal(Graph graph){
MST T = new MST();
MinHeap<MSTnode>H = new MinHeap<MSTnode>(graph.NumEdges);//引入堆来获取每次操作时最小的边
int u, v;
Ufsets F = new Ufsets(graph.NumVertices);//引入并查集实现判断环
for(int u = 0; u < NumVertices; u++){
for(v = u + 1; v < NumVertices; v++){
if(Edge[u][v] != Integer.MAX_VALUE){
MSTnode e = new MSTnode();
e,tail = u;
e.head = v;
e.cost = Edge[u][v];
H.insert(e);//构造小顶堆
}
}
}//建堆O(elog~2~e) e:边的个数
//遍历O(n^2^)
int count = 1;//生成树计数
while(count < NumVertices){
MSTnode e = new MSTnode();
H.Remove(e);
u = F.find(e.tail);
v = F,find(e.head);
if(u != v){//判断是否是环
F.union(u, v);
T.insert(e);
count++;
}
}
}
时间复杂度O(elog~2~e + elog~2~n + n^2^ + n)
Dijkstra算法
用来求非负权值的单源最短路径
贪心思想:当前新产生的一条最短路径能否使已有路径在一步以内变短.
public void Dijkstra(int n, int v){
for(int i = 0; i < n; i++){
dist[i] = Edge[v][i];
s[i] = 0;
if(i!= v && dist[i] < Integer.MAX_VALUE){
path[i] = v;
}
else{
path[i] = -1;
}
}
s[v] = 1;
dist[v] = 0;
for(int i = 0; i < n - 1; i++){
float min = Integer.MAX_VALUE;
int u = v;
for(int j = 0; j < n; j++){
if(!s[j] && dist[j] < min){
u = j;
min = dist[j];
}
s[u] = 1;
for(int w = 0; w < n; w++){
if(!s[w] && Edge[v][w] < Integer.MAX_VALUE && dist[w] > Edge[v][w] + dist[v]){
dist[w] = Edge[v][w] + dist[v];
path[w] = u;
}
}
}
}
}
O(n^2^)时间复杂度
BellmanFord算法
边上权值为任意值的单源最短路径
public void BellmanFord(int n, int v){
for(int i = 0; i < n; i++){
dist[i] = Edge[v][i];
if(i != v && dist[i] < MAXNUM){
path[i] = v;
}
else{
path[i] = -1;
}
}
for(int k = 2; k < n; k++){
for(int u = 0; u < n; u++){
if(u != v){
for(int i = 0; i < n; i++){
if(i != u && Edge[i][u] < MAXNUM && dist[u] > dist[i] + Edge[i][u]){
dist[u] = dist[i] + Edge[i][u];
path[u] = i;
}
}
}
}
}
}
O(n^3^)
Floyd-Warshall算法
用于求所有顶点间的最短路径
前提：各边权值均大于0的带权有向图。
方法：
1)把有向图的每一个顶点作为源点，重复执行Dijkstra算法n次，执行时间为O(n^3^)
2)Floyd方法，算法形式更简单些，但是时间仍然是O(n^3^)
public void Floyd(int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
a[i][j] = Edge[i][j];
if(i == j){
a[i][j] = 0;
}
`if(i != j && a[i][j] < MAXNUM){
path[i][j] = i;
}
else{
path[i][j] = 0;
}
}
}
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(a[i][j] > a[i][k] + a[k][j]){
a[i][j] = a[i][k] + a[k][j];
path[i][j] = k;
}
}
}
}
}
O(n^3^)
AOV网络
用顶点表示活动
拓扑排序
找拓扑序列用的
算法思想：
1）从图中选择一个入度为0的结点输出之.
（如果一个图中，同时存在多个入度为0的结点，则随便输出那一个结点）
2）从图中删掉此结点及其所有的出边.
3）反复执行以上步骤：
a）直到所有结点都输出了，则算法结束
b）如果图中还有结点，但入度不为0，则说明有环路
void topsort( ) throws CycleFound{
Queue q;
int counter = 0;
Vertex v, w;
q = new Queue( );
for each vertex v{
if( v.indegree = = 0 ){
q.enqueue( v );
}
}
while( !q.isEmpty( ) ){
v = q.dequeue( );
v.topNum = ++counter; //Assign next number
for each w adjacent to v{
if( --w.indegree = = 0 ){
q.enqueue(w);
}
}
}
if( counter != NUM_VERTICES ){
throw new CycleFound( );
}
}
O(n + n + e)
AOE网络（事件顶点网络）重点看看概念老忘记
最关键的是从起点到终点的最长路径(因为AOE网络中事件是并行的)
v~e~[i]是v~0~到v~i~的最长路径长度
v~l~[i]是不拖延工期的情况下v~j~发生的最迟时间
e[k] = V~e~[i]
I[k] = VI[j] - dur(<i, j>)
时间余量:l[i] - e[i]最晚-最早
这张图就把递推关系写的很明显了
e[k] == i[k]则说明是关键活动
假设用邻接表实现
public void CriticalPath(){
float[] ve = new float[n + 1];
float[] vl = new float[n + 1];
for(int i = 0; i < n; i++){
ve[i] = 0;
}
for(int i = 0; i < n; i++){
Edge p = NodeTable[i].adj;
while(p != null){
int k = p.dest;
if(ve[i] + p.cost > ve[k]){
ve[k] = ve[i] + p.cost;
}
p = p.link;
}
}//把ve维护好了
for(int i = n - 2; i>= 0; i--){
p = NodeTable[i].adj;
while(p != null){
k = p.dest;
if(vl[k] - p.cost < vl[i]){
vl[i] = vl[k] - p.cost;
}
p = p.link;
}
}//维护vl
for(int i = 0; i < n; i++){
p = NodeTable[i].adj;
while(p != null){
k = p.dest;
float e = ve[i];
float l = vl[k] - p.cost;
if(i == e){
System.out.println("<" + i + k + ">" + "is critical Activity");
}
p = p.link
}
}
}
上面的代码省略了拓扑排序的过程
判断图是否是一个树
import java.util.*;
public class Graph {
private int V; // Number of vertices
private LinkedList<Integer> adj[]; // Adjacency list
// Constructor
@SuppressWarnings("unchecked")
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
// Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v); // Since the graph is undirected
}
// Get the first neighbour of vertex v
Integer getFirstNeighbour(int v) {
return adj[v].isEmpty() ? null : adj[v].get(0);
}
// Get the next neighbour of vertex v after neighbour
Integer getNextNeighbour(int v, int neighbour) {
int index = adj[v].indexOf(neighbour);
return (index == -1 || index == adj[v].size() - 1) ? null : adj[v].get(index + 1);
}
// A recursive function to detect cycle in a subgraph
boolean isCyclicUtil(int v, boolean visited[], int parent) {
visited[v] = true;
Integer neighbour = getFirstNeighbour(v);
while (neighbour != null) {
// If the adjacent node is not visited, then recurse on it
if (!visited[neighbour]) {
if (isCyclicUtil(neighbour, visited, v))
return true;
}
// If an adjacent node is visited and not parent of current vertex, then there is a cycle
else if (neighbour != parent)
return true;
neighbour = getNextNeighbour(v, neighbour);
}
return false;
}
// Function to check if the graph is connected
void DFSUtil(int v, boolean visited[]) {
visited[v] = true;
Integer neighbour = getFirstNeighbour(v);
while (neighbour != null) {
if (!visited[neighbour]) {
DFSUtil(neighbour, visited);
}
neighbour = getNextNeighbour(v, neighbour);
}
}
// Returns true if the graph is a tree, else false.
boolean isTree() {
// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
// Check for cycle using DFS
if (isCyclicUtil(0, visited, -1))
return false;
// Check if the graph is connected
for (int i = 0; i < V; i++) {
if (!visited[i])
return false;
}
return true;
}
public static void main(String args[]) {
// Create a graph given in the above diagram
Graph g1 = new Graph(5);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 3);
g1.addEdge(1, 4);
if (g1.isTree())
System.out.println("Graph is a tree");
else
System.out.println("Graph is not a tree");
Graph g2 = new Graph(5);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(1, 2);
g2.addEdge(1, 3);
g2.addEdge(3, 4);
if (g2.isTree())
System.out.println("Graph is a tree");
else
System.out.println("Graph is not a tree");
}
}