Basic Graph Algorithms - Stanford University
Basic Graph Algorithms
Jaehyun Park CS 97SI
Stanford University
June 29, 2015
Outline
Graphs Adjacency Matrix and Adjacency List Special Graphs Depth-First and Breadth-First Search Topological Sort Eulerian Circuit Minimum Spanning Tree (MST) Strongly Connected Components (SCC)
Graphs
2
Graphs
An abstract way of representing connectivity using nodes (also called vertices) and edges
We will label the nodes from 1 to n m edges connect some pairs of nodes
? Edges can be either one-directional (directed) or bidirectional Nodes and edges can have some auxiliary information
Graphs
3
Why Study Graphs?
Lots of problems formulated and solved in terms of graphs ? Shortest path problems ? Network flow problems ? Matching problems ? 2-SAT problem ? Graph coloring problem ? Traveling Salesman Problem (TSP): still unsolved! ? and many more...
Graphs
4
Outline
Graphs Adjacency Matrix and Adjacency List Special Graphs Depth-First and Breadth-First Search Topological Sort Eulerian Circuit Minimum Spanning Tree (MST) Strongly Connected Components (SCC)
Adjacency Matrix and Adjacency List
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- basic graph algorithms stanford university
- lecture 4 matching algorithms for bipartite graphs
- greedy graph algorithms virginia tech
- graph algorithm 1 topological sort
- parallel graph algorithms chapter 10
- algorithms for graph similarity and subgraph matching
- modularity and graph algorithms graph analysis
- algorithms graph search stanford computer science
- 4 basic graph theory and algorithms
- algorithm and flow chart 1 1 introduction faradars
Related searches
- stanford university philosophy department
- stanford university plato
- stanford university encyclopedia of philosophy
- stanford university philosophy encyclopedia
- stanford university philosophy
- stanford university ein number
- stanford university master computer science
- stanford university graduate programs
- stanford university computer science ms
- stanford university phd programs
- stanford university phd in education
- stanford university online doctoral programs