skip to content

JRSETI Wiki

User Tools

Log In

Site Tools

Recent Changes
Media Manager
Sitemap

Trace: • python

graphs

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

======Graphs======

  * Nodes, Edges
  * No root node like trees
  * Edges can contain data, like strength of conection, etc.
  * Edges can have a direction, "Directed Edge"
  * "Undirected Graph", Edges with no direction
  * Graphs can loop back to the start, unlike Trees
  * "DAG" - Directed Acyclic Graph, - Graph that does not loop
  * 

====Connectivity====

Disconnected graph has one or more nodes not connected to the rest of the graph.

Edge List or 2D or 3D List

====Adjacency====

{{:adjacency_list.png?400|}}{{:adjacency_matrix.png?400|}}

====DFS====

Depth First Search

Use a Stack. 

====BFS====

Breadth First Search

Use a Queue

====Shortest Path Problem====

If the edges are **unweighted**, the shortest past is found via BFS.

====Dijkstra's Algorithm====

graphs.txt · Last modified: 2020/01/13 00:22 by jrseti

Page Tools

Show page
Old revisions
Backlinks
Back to top

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International