Undirected Graphs

Introduction to graphs

• Graph. Set of vertices connected pairwise by edges.
• Graph application

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rK2pJySJ-1586029332520)(…/…/.gitbook/assets/graph-application.png)]

• Some graph-processing problems
  • Path, Shortest path
  • Cycle, Euler tour, Hamilton tour.
  • Connectivity, MST (Minimum Spanning Tree), Biconnectivity.
  • Planarity, Graph isomorphism

Graph API & Graph representation

• Graph drawing, Intuition can be misleading

• Vertex representation: use integers between 0 and V-1, convert between names and integers with symbol table.

• Graph API

  public class Graph
  Graph(int V)
  // create an empty graph with V vertices
  Graph(In in)
  // create a graph from input stream
  void addEdge(int v, int w)
  // add an edge v-w
  Iterable<Integer> adj(int v) // vertices adjacent to v
  int V()
  // number of vertices
  int E()
  // number of edges
  String toString()
  // string representation
  
  

• Set-of-edges graph representation

  • Maintain a list of the edges (linked list or array).

• Adjacency-matrix graph representation

  • Maintain a two-dimensional V-by-V boolean array;
  • for each edge v-w in graph: adj[v][w] = adj[w][v] = true.

• Adjacency-list graph representation

  • Maintain vertex-indexed array of lists.
  • Implementation Graph.java

  public class Graph {
  private final int V;
  private Bag<Integer>[] adj;
  public Graph(int V) {
  // create empty graph with V vertices
  this.V = V;
  // number of vertices
  adj = (Bag<Integer>[]) new Bag[V];
  // array of Bag<Integer>
  for (int v = 0; v < V; v++) {
  adj[v] = new Bag<Integer>();
  }
  }
  public void addEdge(int v, int w) {
  // add edge v-w (parallel edge allowed)
  adj[v].add(w);
  adj[w].add(v);
  }
  public Iterable<Integer> adj(int v) { return adj[v]; }
  }
  

• In practice. Use adjacency-lists representation.

  • Algorithms based on iterating over vertices adjacent to v
  • Real-world graphs tend to be sparse

Depth First Search

• Maze exploration

  • Vertex = intersection.
  • Edge = passage.
  • Goal. Explore every intersection in the maze.

• Depth-first search

  • Gaol. Systematically search through a graph.
  • Idea. Mimic maze exploration.

  DFS(to visit a vertex v)
  Mark v as visited
  Recursively visit all unmarked vertices adjacent to v.
  

  • Typical application
    • Find all vertices connected to a given source vertex.
    • Find a path between two vertices.

• Design pattern for graph processing. Decouple graph type from graph processing.

  • Create a Graph object
  • Pass the Graph to a graph-processing routine
  • Query the graph-processing routine for information

  public class Paths
  Paths(Graph G, int s)
  // find paths in G from source s.
  boolean hasPathTo(int v) // is there a path from s to v?
  Iterable<Integer> pathTo(int v) // path from s to v; null if no such path
  

  Paths paths = new Paths(G, s);
  for (int v = 0; v < G.V(); v++) {
  // print all vertices connected to s.
  if (paths.hasPathTo(v))
  StdOut.println(v)
  }
  

• Implementation of dfs

  • Algorithm
    • Use recursion (ball of string)
    • Mark each visited vertex (and keep track of edge taken to visit it).
    • Return (retrace steps) when no unvisited options.
  • Data Structures
    • boolean[] marked to mark visited vertices.
    • int[] edgeTo to keep tree of paths.
    • (edgeTo(w) == v) means that edge v-w taken to visit w for first time.
  • DepthFirstPaths.java

  public class DepthFirstPaths {
  private boolean[] marked; // marked[v] = true if v connected to s.
  private int[] edgeTo;
  // edgeTo[v] = previous vertex on path from s to v.
  private int s;
  // source vertex.
  public DepthFirstPaths(Graph G, int s) {
  this.s = s;
  edgeTo = new int[G.V()];
  marked = new boolean[G.V()];
  validateVertex(s);
  dfs(G, s);
  }
  // depth first search from v.
  private void dfs(Graph G, int v) {
  marked[v] = true;
  for (int w : G.adj[v]) {
  if (!marked[w]) {
  edgeTo(w) = v;
  dfs(G, w);
  }
  }
  }
  }
  

• DFS proposition. DFS marks all vertices connected to s in time proportional to the sum of their degrees.

• Pf.

  • If w marked, then w connected to s.
  • If w connected to s, then w marked.

public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push[x];
}
path.push[s];
return path;
}

Breadth-First Search

• BFS: Repeat until queue is empty
  • Remove vertex v from queue.
  • Add to queue all unmarked vertices adjacent to v and mark them.
• Shortest Path Find path from s to t that uses fewest number of edges
• Intuition. BFS examines vertices in increasing distance from s.

BFS (from source vertex s)
Put s onto a FIFO queue, and mark s as visited.
Repeat until the queue is empty:
- remove the least recently added vertex v
- add each of v's unvisited neighbors to the queue, and mark them as visited.

• The critical data structures used in depth-first search and breadth-first search are stack and queue, respectively. With depth-first search it is either an explicit stack (with a non-recursive version) or the function-call stack (with a recursive version).
• Proposition. BSF computes shortest path from s to all other vertices in a graph in time proportional to E+V.
• Implementation BreadthFirstPaths.java

public class BreadthFirstPaths{
private static final int INFINITY = Integer.MAX_VALUE;
private boolean[] marked;
// marked[v] = is there an s-v path
private int[] edgeTo;
// edgeTo[v] = previous edge on shortest s-v path 
private int[] distTo;
// disTo[v] = number of edges shortest s-v path
public BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
distTo = new int[G.V()];
edgeTo = new int[G.V()];
validateVertex(s);
bfs(G, s);
}
private void bsf(Graph G, int s) {
Queue<Integer> q = new Queue<Integer>();
for (int v = 0; v < G.V(); v++)
distTo[v] = INFINITY;
distTo[s] = 0;
marked[s] = true;
q.enqueue(s);
while (!q.isEmpty()) {
int v = q.dequeue();
for (w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.enqueue(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
// return the number of edges in a shortest path 
public int distTo(int v) {
return distTo[v];
}
// return a shortest path between source and give vertex v.
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<Integer>();
int x;
for (x = v; distTo[x] != 0; x = edgeTo[x])
path.push[x];
path.push[x];
return path;
}
}

Connected Components

• Connectivity queries

  • Def. Vertices v and w are connected if there is path between them.
  • Goal. Preprocess graph to answer queries of the form is v connected to w? in constant time.

  public class CC
  CC(Graph G) .
  // find connected components in G
  boolean connected(int v, int w) // are v and w connected?
  int count()
  // number of connected components
  int id(int v)
  // component identifier for v
  

  • Union-Find? Not quite.
  • Depth-first search. Yes.

• Def. A connected component is a maximal set of connected vertices.

• Implementation CC.java

  • Goal. Partition vertices into connected components.

  Connected components
  Initialize all vertices as unmarked.
  For each unmarked vertex v, run DFS to identify all
  vertices discovered as part of the same component.
  

  • To visit a vertex v:
    • Mark vertex v as visited.
    • Recursively visit all unmarked vertices adjacent to v.

  public class CC {
  private boolean marked[];
  private int[] id;
  // id[v] = id of component containing v.
  private int count;
  // number of components.
  public CC(Graph G) {
  marked = new boolean[G.V()];
  id = new int[G.V()];
  for (int v = 0; v < G.V(); v++) {
  if (!marked[v]) {
  dfs(G, v);
  count++;
  }
  }
  }
  private void dfs(Graph G, int v) {
  marked[v] = true;
  id[v] = count;
  for (int w : G.adj(v))
  if (!marked(w))
  dfs(G, w);
  }
  public int count() { return count; }
  public int id(int v) { return id[v]; }
  }
  

• Connected components application: particle detection

Graph Challenges

• Graph-processing challenge 1
  • Problem. Is a graph bipartitie? (every edge connect a black vertex and red vertex)
  • How difficult? Typical diligent algorithms student could do it.
• Graph-processing challenge 2
  • Problem. Find a cycle.
  • How difficult? Typical diligent algorithms student could do it
• Graph-processing challenge 3
  • Problem. Find a (general) cycle that uses every edge exactly once. (Eulerian tour)
  • How difficult? Typical diligent algorithms student could do it
• Graph-processing challenge 4
  • Problem. Find a cycle that visits every vertex exactly once. (Halmon… cycle problem)
  • How difficult? Intractable
• Graph-processing challenge 5
  • Problem. Are two graphs identical except for vertex names?
  • How difficult? No one knows
• Graph-processing challenge 6
  • Problem. Lay out a graph in the plane without crossing edges?
  • How difficult? Hire an expert (there is a linear time algorithm based on dfs, quite complex)

WordNet (Exercise)

WordNet specification
WordNet Solution

最后

以上就是传统唇膏为你收集整理的Algs4 - Undirected Graphs, 无向图Undirected Graphs的全部内容，希望文章能够帮你解决Algs4 - Undirected Graphs, 无向图Undirected Graphs所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。