Scribd Logo
Upload

Welcome to Scribd!

  • 97 views

    LAB 5: Graph: 1 Excercises

    Uploaded by

    Duc Cao
    This document provides instructions for a lab exercise on graphs. It includes exercises to read and convert between adjacency matrices and lists, determine graph properties like directed/undirected, degrees, components, and special types of graphs. It also includes exercises to generate related graphs from a given graph, find spanning trees, minimum spanning trees, and shortest paths using various graph algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    LAB 5: Graph: 1 Excercises

    Uploaded by

    Duc Cao
    97 views2 pages
    This document provides instructions for a lab exercise on graphs. It includes exercises to read and convert between adjacency matrices and lists, determine graph properties like directed/undirected, degrees, components, and special types of graphs. It also includes exercises to generate related graphs from a given graph, find spanning trees, minimum spanning trees, and shortest paths using various graph algorithms.

    Original Title

    Lab 5

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides instructions for a lab exercise on graphs. It includes exercises to read and convert between adjacency matrices and lists, determine graph properties like directed/undirected, degrees, components, and special types of graphs. It also includes exercises to generate related graphs from a given graph, find spanning trees, minimum spanning trees, and shortest paths using various graph algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    97 views2 pages

    LAB 5: Graph: 1 Excercises

    Uploaded by

    Duc Cao
    This document provides instructions for a lab exercise on graphs. It includes exercises to read and convert between adjacency matrices and lists, determine graph properties like directed/undirected, degrees, components, and special types of graphs. It also includes exercises to generate related graphs from a given graph, find spanning trees, minimum spanning trees, and shortest paths using various graph algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Data Structures & Algorithms Knowledge Engineering Department

    LAB 5: Graph

    1 Excercises
    1. The ”graph1.txt” file contains information of an Adjacency matrix (Table 1). Read the file and
    output the information of the corresponding Adjacency list.
    2. The ”graph2.txt” file contains information of an Adjacency list (Table 1). Read the file and
    output the information of the corresponding Adjacency matrix.
    Adjacency matrix Adjacency list
    9
    9
    0 0 1 0 0 1 0 0 0
    25
    0 0 0 0 0 0 1 0 0
    6
    0 0 0 0 0 0 1 0 0
    6
    0 0 0 0 1 0 0 0 0
    4
    0 0 0 0 0 1 0 0 0
    5
    0 0 0 1 0 0 0 1 0
    37
    0 0 0 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 1
    28
    0 0 0 0 0 0 0 0 0

    Table 1: Adjacency matrix and corresponding Adjacency list

    3. Implement functions to provide the following information of a given graph:


    • Directed or Undirected Graph.
    • The number of edges and number of vertices.
    • Degree of each vertices for undirected graph. In-degree and Out-degree for directed graph.
    • List of isolated vertices / leaf vertices. .
    • Is the given graph special: Complete graph, Circular graph, Bigraph, Complete bi-
    graph.
    • The number of Connected components. How many of them are trees?
    • The number of Cut vertices and Bridge edges.
    4. Generate a Base undirected graph from a given directed graph.
    5. Generate a Complement graph from a given undirected graph, outputting the corresponding
    adjacency matrix.
    6. Generate a Converse graph from a given directed graph, outputting the corresponding adjacency
    matrix.
    7. Determined Euler cycle from a given graph using Hiehozer’s algorithm.

    Page 1 / 2
    Data Structures & Algorithms Knowledge Engineering Department

    8. Find the spanning tree of a given graph using:

    • DFS traversal • BFS traversal

    9. Find the minimum spanning tree of a given graph using:

    • Prim algorithm. • Kruskal algorithm.

    10. Verify the connection between 2 vertices of a given graph.

    11. Find the shortest path between 2 vertices of a given graph using:

    • Dijkstra algorithm • Floyd-Warshall algorithm


    • Bellman-Ford algorithm

    Page 2 / 2

    You might also like