锐客网

  1. 首页 > it技术 > >

CPSC 319图数结构

算法

【CPSC 319图数结构】Assignment 4
Graphs
You are given an input adjacency matrix representing a directed graph in the following
format:
0 0 0 1 0
0 0 1 0 1
1 0 0 0 0
0 1 0 0 1
0 0 0 0 0
Nodes are to be indexed from 0 to n – 1, where n is the total number of nodes.
You are also given a query file that contains pairs of graph nodes. Your task is to
determine if there is a path between these nodes in the graph and to record this path in the
output file. You must also indicate if the path does not exist.
The format of the query file is start_node, end_node. For example:
0 1
4 2
The format of the output file is start_node, path_node, . . ., path_node, end_node if the
path is found, and start_node, -1, end_node if the path is not found. For the above
example, the output file will be:
0, 3, 1
4, -1, 2
Create a Java program that performs the following steps:

  1. Read the adjacency matrix for a directed graph from the input file and store it in a
    corresponding data structure.
  2. Find the paths between the nodes given in the query file by traversing the graph using
    a depth-first graph traversal. Print the paths to the output1.txt text file.
  3. Find the paths between the nodes given in the query file by traversing the graph using
    a breadth-first graph traversal. Print the paths to the output2.txt text file.
    Be sure to use proper headings and fixed-width columns for both output files. The
    program will be invoked from the command line as follows:
    java Assign4 input query output1 output2
    where Assign4 is the name of the file containing executable bytecode for your program,
    input is the name of the input text file containing the adjacency matrix, query is the name
    of the input text file containing the sequence of nodes for which connecting paths should
    be found, output1 is the name of the text file containing the paths obtained using the
    depth-first graph traversal, and output2 is the name of the text file containing paths
    obtained using the breadth-first graph traversal. If the command line arguments are
    improperly specified, the program should print out a "usage" message and abort. Be sure
    the specified files can be opened or created.
    Create your own input files to test your code. An official input file and query file will be
    made available to the class before the due date; use these files to create your output files.
    You must program all the data structures from scratch; in other words, do not use any
    classes from the Java libraries to implement the graph or queue/stack.
    Bonus (optional)
    Adapt your program so that it also finds the shortest weighted path between the specified
    start node and end node in a weighted directed graph. Use Dijkstra’s Algorithm. Modify
    your program so that an additional output file (specified as output3.txt on the command
    line) is produced. Create your own input files to test your code. Additional official input
    and query files will also be made available; use these to generate your third output file.
    Questions
  4. Describe the algorithm based on the graph traversal to find if there is a loop (a path of
    directed edges of the graph that starts and ends at the same node). Which traversal
    technique (breadth-first or depth-first) is more suitable? What is the worst-case
    complexity of this algorithm?
  5. For a given query file, which traversal technique (breadth-first or depth-first) is more
    efficient in determining if the path exists between the given nodes? Use the provided
    input file and query file to help answer this question.
    Submit electronically using the D2L dropbox:
  6. A readme.txt text file, which indicates how to compile and run your program, and if
    you are doing the bonus part.
  7. Your source code files. Your TA will run your program to verify that it works
    correctly. Make sure your Java program compiles and runs on the Computer Science
    Linux servers.
  8. The output files that your program generates. Name these output1.txt, output2.txt, and
    output3.txt (if doing the bonus part of the assignment).
  9. The answers to the above questions, in Word or PDF format
    Collaboration
    The assignment must be done individually so everything that you hand in must be your
    original work, except for the code copied from the text or course directory, or that
    supplied by your TA. When someone else's code is used like this, you must acknowledge
    the source explicitly. Copying another student's work will be deemed academic
    misconduct. Contact your TA if you have problems getting your code to work.

    推荐阅读


    上一篇：Linux内核添加系统调用

    下一篇：简单易用的APIv3版微信支付SDK