Summary of Graphical Algorithms
This is an initial listing of the various problems we have done along with a very brief description of the algorithms, enough to point you in the right direction. When you encounter problems, if you can identify them as one of these, then you can look up the specific algorithm that is used to solve the problem. I am trying to keep this brief so refer to your book/ notes for details. There are some items on here that we have not covered yet.
At this point, I have just started to sketch things out. Over the next few weeks I will be adding / changing things as I do some more work on this page (hopefully with some help from you) as I clarify some other the points I have started to list. I there is anything I missed, let me know.
| Problem Name | Description | Algorithm Used | Comments |
| Lexicographical Order | Putting strings in alphabetical order. | Postorder search. | |
| Topological Sorting | Find a total ordering from a partial ordering. | Scan from a minimal of Haase diagram, removing vertices and their edges as you move up the graph. In the event of a tie, you can choose either. | Ordering prereqs. |
| Connectivity | We want to find out if vertices are connected to each other after walks of lengths of n | Prepare an adjacency matrix. If you want to see if paths of length n are connected, then the matrix is An. | Boolean multiplication |
| Euler Circuits in an undirected graph. | Find a circuit so that every edge is traveled and you return to the starting point. | Form the longest cycle.Next, using a point of degree 4 or higher, form another cycle and connect it to the earlier cycle. Repeat until all edges are used | The degree of each vertex must be even. |
| Euler Path in an undirected graph | Find a circuit so that every edge is traveled and you DO NOT return to the starting point. | Start at an odd vertex and take the longest path that you can without returning to the start.. | There are exactly two odd vertices. |
| Hamiltonian Circuit in and undirected graph | Find a circuit that goes through all the vertices and returns to the start. | There are no polynomially bound algorithms. | There are a number of rules to determine if a graph is Hamiltonian circuit. See text and chapter 7 notes. |
| Hamiltoniam Path in and undirected graph | Find a circuit that goes through all the vertices and NOES NOT return to the start. | There are no polynomially bound algorithms. | There are a number of rules to determine if a graph is Hamiltonian path. See text and chapter 7 notes. |
| Shortest Path Problem | Find the shortest path from a starting node to and ending node | Dijkstra's algorithm. Start with the starting node and find the shortest path to adjacent nodes. Label them with the total length of the path to the nodes. Take the node with the smallest number and add it to the set of "looked at" nodes. Next, find the shortest path from these "looked at" nodes to adjacent nodes. Label them and take the shortest. Repeat until you reach the end node. The label on the end node is the minimum distance | See text for detailed example |
| Traveling Salesman Problem | Find a path which goes through all vertices using the minimum amount of units. | .This problem can con be solved in polynomial time as it is essentially finding a Hamiltonian path through a complete graph. There are approximation methods such as the "nearest neighbor that can be used. This method adds the nearest neighbor to nodes on the "looked up" list. It gives a solution which may only be fair. | This is one of the classic examples on NP problems. |
| Minimum Spanning Tree | Find a tree which connects all the points in a graph using the smallest numbers. | Prim's Algorithm.Choose the smallest edge. Add to that edge the vertex that is the closest to the nodes already on the list which do not create a cycle. Add that node and look at nodes that are the closest to the nodes already on the list. | See text for a detailed example. |
| Binary Tree Search | |||
| Preorder Search | Visit the parent, then visit the children from left to right in preorder. | This is a depth-first search. Postfix notation or Reverse Polish notation. No parentheses needed since it in unambiguous. This notation is frequently used in CS, especially in compiler design. | |
| Inorder | Visit the left child in inorder, then the parent, then visit the other children in inorder | This the way we do algebra using infix notation. This may require parentheses. | |
| Preorder | Visit the children from left to right in preorder then visit the parent. | Bottom-up search. Prefix notation or Polish notation. No parentheses needed since it in unambiguous. This notation is frequently used in CS, especially in compiler design. | |
| Bubble Sort | |||
| Merge Sort | |||
You are the visitor to this site.