Undirected Graph

UndirectedGraph

1. Graphs
	1. Set of vertices connected pairwise by edges
	2. Complex and huge
	3. Terminology
		1. Path: sequence of vertices connected by edges
		2. Cycle: path whose first and last vertices are the same
		3. Euler tour: a cycle that uses each edge exactly once
		4. Hamilton tour: cycle that uses each vertex exactly once
		5. MST: best way to connect all of the vertices
		6. biconnectivity: is there a vertex whose removal disconnects the graph
		7. planarity: draw the graph in the plan with no crossing edges
		8. graph isomorphism: do two adjacency lists represent the same graph
	4. Graph representation
		1. set of edges: inefficient, space E, add edge 1, edge between v and w E, iterate orver vertices adjacent to v E
		2. adjacency-matrix: if sparse, taken too uch space, space V2, add edge 1, edge between v and w 1, iterate over vertices adjacent to v V
		3. adjacency-list representation: Maintain vertex-indexed array of lists (use bag datastructure): space E+V, add edge 1, degree(v), degree(v)
2. DFS
	1. Tremaux maze exploration 米利托的迷宫, Shannon
	2. DFS
		1. Mark v as visited
		2. recursively visit all unmarked vertices w adjacent to v
	3. recursion
	4. After DFS, can find vertices connected to s in constant time, can find a path to s in time proportional to its length
3. BFS
	1. Not recursive, use a queue
	2. BFS
		1. Remove vertex v from queue
		2. add to queue all unmarked vertex adjacent to v and mark them
		3. until queue is empty
	3. DFS put unvisited vertices in a stack
		1. can be implemented either with nonrecursive stack or recusive (hidden stack)
	4. BFS put unvisited vertices in a queue
	5. BFS solve shortest path problem (keep distanceto())
	6. BFS computes shortest path from s to all other vertices in a graph usign time proportional to E+V, each vertex visited once
	7. Kevin Bacon number, six-degress (six-hops)
	8. Erdos number
4. Connected Component
	1. Can be solved in constant time if using adjacency matrix
	2. DFS
		1. Intialize all vertices as unmarked
		2. for each unmarked vertex, run DFS to find all vertices of the same component
5. Graph challenges
	1. Bipartite- DFS
	2. Find cycle- DFS
	3. Euler tour: a connected graph with each vertex even degree (exactly same degree)
	4. Hamilton tour: intractable NP-complete
	5. graph isphmorphism: open question
	6. Planarity: linear time DFS-based planarity