- トポロジカルソート: DAGの各頂点を辺の向きに沿うように一列に並べる。DAGであることと、トポロジカルソート可能であることは等価
- 強連結成分分解: 強連結成分（SCC, Strongly Connected Component:有向グラフにおいて、互いに行き来が可能な頂点の集合）を求める
- Bellman-Ford法: 始点から他の全ての頂点への最短経路を求める
- Dijkstra法: 負のコストの辺がない。始点から他の全ての頂点への最短経路を求める
- Warshall-Floyd法: すべての2頂点間の最短距離を求める
- SAT（充足可能性問題）: 論理式全体の値を「真」にする真偽値x1,x2...の組み合わせは存在するかを求める
- 頂点被覆問題:
- ハミルトン閉路問題: グラフにおける全ての頂点を一度だけ通る閉路が存在するかを求める
- 巡回セールスマン問題: 都市間移動における総移動コストの最小化問題、問題の大きさは都市数
- ナップザック問題:
- 最小頂点被覆問題: グラフG(V,E)の各枝 e について端点のいずれか少なくとも一方が、V' に含まれるような Vの部分集合 V' のうち、|V'|=k となるものが存在するか、または|V'|の最小値を求める
- 最大独立集合問題: グラフG(V,E)に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの（独立集合）で大きさが最大のものを求める。最小頂点被覆問題と等価。
- 最大クリーク問題: グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。補グラフに対する最大独立集合問題と等価。
最大安定問題は、選ばれた点間で辺がない。最大クリーク問題は、選ばれた点間で辺がある。
- 貪欲法(Greedy Algorithm):
- 局所探索法(Local Search Algorithm):