无向图

发表于   |   分类于

Introduction

定义： 图是由一组顶点和一组能够将两个顶点相连的边组成

Undirected graphs

Graph. Set of vertices connected pairwise by edges.

Graph applications

图的相关术语

Path. Sequence of vertices connected by edges.
Cycle. Path whose first and last vertices are the same.

Two vertices are connected if there is a path between them.

图相关的一些问题

Path. Is there a path between s and t?
Shortest path. What is the shortest path between s and t?

Cycle. Is there a cycle in the graph?
Euler tour. Is there a cycle that uses each edge exactly once?
Hamilton tour. Is there a cycle that uses each vertex exactly once.

Connectivity. Is there a way to connect all of the vertices?
MST. What is the best way to connect all of the vertices?
Biconnectivity. Is there a vertex whose removal disconnects the graph?

Planarity. Can you draw the graph in the plane with no crossing edges?
Graph isomorphism. Do two adjacency lists represent the same graph?

graph API


Graph API: sample client

Typical graph-processing code

Set-of-edges graph representation

Maintain vertex-indexed array of lists.

Adjacency-list graph representation: Java implementation

深度优先搜索

Design pattern for graph processing

Design pattern. Decouple graph data type from graph processing.

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

Depth-first search demo

To visit a vertex v:

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

Goal. Find all vertices connected to s (and a corresponding path).
Idea. Mimic maze exploration.

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

Depth-first search properties

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

Proposition. After DFS, can find vertices connected to s in constant time and can find a path to s (if one exists) in time proportional to its length.

广度优先搜索

Breadth-first search demo

Repeat until queue is empty:

  • Remove vertex v from queue.
  • Add to queue all unmarked vertices adjacent to v and mark them.

Depth-first search. Put unvisited vertices on a stack.
Breadth-first search. Put unvisited vertices on a queue.

Shortest path. Find path from s to t that uses fewest number of edges.

Breadth-first search properties

Proposition. BFS computes shortest paths (fewest number of edges) from s to all other vertices in a graph in time proportional to E + V.

实现