Graphs

2023-10-08 17:52:22

Presentations

  • Directed Graph
    Graphs
    邻接矩阵&邻接表
  • Undirected Graph
    Graphs
  • Adjacency Matrix
    • Space: Θ ( ∣ V ∣ 2 ) Θ(|V|^2) Θ(∣V∣2)
  • Adjacency List
    • Space: Θ ( ∣ V ∣ + ∣ E ∣ ) Θ(|V| + |E|) Θ(∣V∣+∣E∣)
  • ADT
class Graph { // Graph abstract class
	public:
		virtual int n() =0; // # of vertices
		virtual int e() =0; // # of edges
		// Return index of first, next neighbor 
		virtual int first(int) =0; //
		virtual int next(int, int) =0;
		// Store new edge
		virtual void setEdge(int, int, int) =0;
		// Delete edge defined by two vertices
		virtual void delEdge(int, int) =0;
		// Weight of edge connecting two vertices
		virtual int weight(int, int) =0;
		virtual int getMark(int) =0;
		virtual void setMark(int, int) =0;
};

这里主要注意first和next的使用方法, 下图中
first(0)=1 next(0,1)=4 (0的下一个的下一个)
first(3)=1 next(3,first(3))=2
next(4,next(4,first(4)))=2
Graphs
这个其实是按照数字大小排序的

Graph Traversal

Depth First Search

Graphs

// Depth first search
void DFS(Graph* G, int v) {
	PreVisit(G, v); // Take action
	G->setMark(v, VISITED);
	for (int w = G->first(v); 
			w < G->n(); 
			w = G->next(v,w))
		if (G->getMark(w) == UNVISITED)
			DFS(G, w);
	PostVisit(G, v); // Take action
}

一条路走到底 遇到不能走的再一个一个返回 注意在遍历的时候要顺着一个方向（本遍历是按照字母的顺序）

Breadth First Search

Graphs
这个图画错了 第二层是``b和e 到了每个节点以后访问哪个节点是按照字母大小排序的

void BFS(Graph* G, int start,Queue<int>*Q) {
	int v, w;
	Q->enqueue(start); // Initialize Q
	G->setMark(start, VISITED);
	while (Q->length() != 0) { // Process Q
		Q->dequeue(v);
		PreVisit(G, v); // Take action
		for(w=G->first(v); w<G->n(); w=G->next(v,w))
			if (G->getMark(w) == UNVISITED) {
				G->setMark(w, VISITED);
				Q->enqueue(w);
			}
		PostVisit(G, v); // Take action
	}
}

一层一层向下遍历

Topological Sort (拓扑排序)

  • Algorithm for a directed acyclic（无环） graph ：An ordering of vertices in a directed acyclic graph, such that if there is a path from vi to vj, then vj appears after vi in the ordering.
  • 每个顶点出现且只出现一次。
  • 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
void topsort(Graph* G) { // Topological sort
	int i;
	for (i=0; i<G->n(); i++) // Initialize
		G->setMark(i, UNVISITED);		
	for (i=0; i<G->n(); i++) // Do vertices 
		if (G->getMark(i) == UNVISITED)
			tophelp(G, i); // Call helper
}
void tophelp(Graph* G, int v) { // Process v
	G->setMark(v, VISITED);
	for (int w = G->first(v); w < G->n(); w = G->next(v,w))
		if (G->getMark(w) == UNVISITED)
			tophelp(G, w);
	printout(v); // PostVisit for Vertex v
}
  • 注意这里for (i=0; i<G->n(); i++)保证所有顶点都被访问过，因为有的任可能是没有和别的连接的
  • 是从后向前输出 用的时候要反转
  • 其实就是DFS 只是最后是按照返回的顺序输出的
    Graphs
    Graphs

Shortest Paths Problems

  • d(A, B) is the shortest distance from vertex A to B
  • w(A, B) is the weight of the edge connecting A to B
    • If there is no such edge, then w(A, B) = ∞

Dijkstra’s Algorithm

Linear Approach

// Compute shortest path distances from s,
// return them in D
void Dijkstra(Graph* G, int* D, int s) {
	int i, v, w;
	for (i=0; i < G->n(); i++)  // Initialization
		D[i] = INFINITY;
	D[s] = 0;  //开始点的距离设置为0
	
	for (i=0; i < G->n(); i++) { // 访问所有顶点
		v = minVertex(G, D);  //找到当前的最小值
		if (D[v] == INFINITY) return;  //只有一个节点的情况
		G->setMark(v, VISITED); //标记已访问过
		for (w=G->first(v); w<G->n(); w = G->next(v,w))  //遍历当前节点的相邻节点 更新
			if (D[w] > (D[v] + G->weight(v, w)))
				D[w] = D[v] + G->weight(v, w);
	}
}

// Find min cost vertex
int minVertex(Graph* G, int* D) {
	int i, v;
	
	// Set v to an unvisited vertex
	//从第一个未被访问过的开始
	for (i=0; i<G->n(); i++)
		if (G->getMark(i) == UNVISITED)
			{ v = i; break; }
			
	// Now find smallest D value
	//找到最小的顶点值
	for (i++; i<G->n(); i++)
		if ((G->getMark(i) == UNVISITED) && (D[i] < D[v]))
			v = i;
	return v;
}
  • Total Cost: Θ ( 2 ∣ V ∣ 2 + ∣ E ∣ ) = Θ ( ∣ V ∣ 2 ) Θ(2|V|^2 + |E|) = Θ(|V|^2) Θ(2∣V∣2+∣E∣)=Θ(∣V∣2)
    • Dense graph ( Θ ( ∣ E ∣ ) Θ(|E|) Θ(∣E∣) approaches Θ ( ∣ V ∣ 2 ) ) Θ(|V|^2 )) Θ(∣V∣2)): Θ ( ∣ V ∣ 2 ) Θ( |V|^2) Θ(∣V∣2)
    • Sparse graph Θ ( ∣ E ∣ ) Θ(|E|) Θ(∣E∣) approaches Θ ( ∣ V ∣ ) ) Θ(|V|)) Θ(∣V∣)): Θ ( ∣ V ∣ 2 ) Θ( |V|^2) Θ(∣V∣2)
  • 外层循环是V，找最小值是V，更新最小值相邻节点是E
  • 适合Dence graph

Min Heap Approach

class DijkElem {
	public:
	int vertex, distance;
	DijkElem() { vertex = NULL; distance = NULL; }
	DijkElem(int v, int d) { vertex = v; distance = d; }
};

void Dijkstra(Graph* G, int* D, int s) {
	int i, v, w; // v is current vertex
	DijkElem temp;
	DijkElem E[G->e()]; // Heap array
	temp.distance = 0; temp.vertex = s;
	E[0] = temp; // Initialize heap array
	minheap<DijkElem, DDComp> H(E, 1, G->e()); 
	for (i=0; i<G->n(); i++) { // Get distances
	   //v找到第一个unvisited
		do { 
			if(!H.removemin(temp)) return;
			v = temp.vertex;
		} while (G->getMark(v) == VISITED);
		
		G->setMark(v, VISITED); //标记访问过
		
		if (D[v] == INFINITY) return;  
		
		for(w=G->first(v); w<G->n(); w=G->next(v,w))
			if (D[w] > (D[v] + G->weight(v, w))) {
				D[w] = D[v] + G->weight(v, w);
				temp.distance = D[w]; temp.vertex = w;
				H.insert(temp); // Insert in heap
			}
	}
}
  • Total Cost: Θ ( ( ∣ V ∣ + ∣ E ∣ ) x l o g 2 ∣ E ∣ ) Θ((|V| + |E|) x log_2|E|) Θ((∣V∣+∣E∣)xlog2​∣E∣)
    • Removemin : Θ ( ∣ V ∣ x l o g 2 ∣ E ∣ ) ) Θ(|V| x log_2|E|)) Θ(∣V∣xlog2​∣E∣))
    • Insert : Θ ( ∣ E ∣ x l o g 2 ∣ E ∣ ) ) Θ(|E| x log_2|E|)) Θ(∣E∣xlog2​∣E∣))
    • Dense graph : Θ ( ∣ V ∣ 2 x l o g 2 ∣ V ∣ ) Θ( |V|^2 x log_2|V| ) Θ(∣V∣2xlog2​∣V∣)
    • Sparse graph : Θ ( ∣ V ∣ x l o g 2 ∣ V ∣ ) Θ( |V| x log_2|V| ) Θ(∣V∣xlog2​∣V∣)
  • 适合Sparse graph

All Pairs Shortest Paths Problem

前面是找两个点之间的 这个是找全部的

Floyd’s Algorithm

d(i,k) VS d(i,j)+d(j,k) 找到一个连接两点的中间结点
每次按顺序 选择一个节点作为中间结点

//Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
	int D[G->n()][G->n()]; // Store distances
	
	for (int i=0; i<G->n(); i++) // Initialize
		for (int j=0; j<G->n(); j++)
			D[i][j] = G->weight(i, j);
	
	// Compute all k paths
	for (int k=0; k<G->n(); k++)
		for (int i=0; i<G->n(); i++)
			for (int j=0; j<G->n(); j++)
				if (D[i][j] > (D[i][k] + D[k][j]))
					D[i][j] = D[i][k] + D[k][j];
}
  • Time complexity = Θ ( ∣ V ∣ 3 ) Θ(|V|3) Θ(∣V∣3)
    Graphs
    Graphs

Minimum-Cost Spanning Trees

  • Minimal Cost Spanning Tree (MST) is a subgraph of G
    • has minimum total cost as measured by summing the values of all the edges in the subset
    • keeps the vertices connected
    • 就是可以连接所有点并且权重和最小的几条边

Prim’s Algorithm

  • Similar to Dijkstra’s algorithm for finding the single source shortest paths
    • seek the next closest vertex to any vertex currently in the MST
  • Same result with different starting vertices
void Prim(Graph* G, int* D, int s) {
	int V[G->n()]; // Who's closest
	int i, w;
	for (i=0; i<G->n(); i++) { // Do vertices
		int v = minVertex(G, D); 
		G->setMark(v, VISITED);
		if (D[v] == INFINITY) return;
		if (v != s) AddEdgetoMST(V[v], v);
		for (w=G->first(v); w<G->n();w = G->next(v,w))
			if (D[w] > G->weight(v,w)) {
				D[w] = G->weight(v,w); // Update dist
				V[w] = v; // Update who it came from
			}
	}
}
  • 每次找到与已经访问的节点最近的节点 标记这个节点已访问并且记录这条边

Kruskal’s Algorithm

  • Initially, each vertex is in its own MST
  • Merge two MST’s that have the shortest edge between them
    Graphs 
Class KruskElem {
public:
	int from, to, distance;
	KruskElem( ) { from=-1; to=-1; distance=-1; }
	KruskElem(int f, int t, int d) 
	{ from=f; to=t; distance=d; }
};
Kruskal(Graph& G) { // Kruskal's MST algorithm
	Gentree A[G->n( )]; // Equivalence class array
	KruskElem E[G->e( )]; // Array of edges for min-heap
	int edgecnt = 0;
	for (int i=0; i<G->n( ); i++) // Put edges on array
		for (int w = G->first(i); w<G->n( ); w = G->next(i,w)) {
			E[edgecnt].distance = G->weight(i,w);
			E[edgecnt].from = i;
			E[edgecnt++].to = w;
		}
	Minheap<KruskElem,KKComp> H(E, edgecnt, edgecnt); 
	int numMST = G->n( ); // Init n equiv classes
	for (i=0; numMST>1; i++) { // Combine equiv classes
		KruskElem temp;
		H.removemin(temp); // Get next cheap edge
		int v = temp.from;
		int u = temp.to;
		if (A.differ(v, u)) { // If different equiv classes
			A.UNION(v, u); // Combine equiv classes
			AddEdgetoMST(v,u); // Add to MST
			numMST--; // One less MST
		}
	}
}

  • Steps

    1. Prepare the Krusk Elem Edge Node
    2. Build the MinHeap using Krusk Elem
    3. Remove the minimum value
    4. Add the path if its vertices are not connected
    5. Connect these vertices
      Graphs

  • 按照minheap removemin的方法每次提出一个node 每次检查那条边上的两个顶点是否为一个祖先 如果不是就插入这条边

  • Total cost

    • Worst case: Θ ( ∣ E ∣ l o g ∣ E ∣ ) Θ(|E| log |E|) Θ(∣E∣log∣E∣)
    • Average case: close to Θ ( ∣ V ∣ l o g ∣ E ∣ ) Θ(|V| log |E|) Θ(∣V∣log∣E∣)
上一篇：基于Neo4j的担保社群型态分析挖掘


下一篇：linux下用Apache一个IP多个网站多域名配置方法