Running graph0_starter4.js

// CPCS 324 Algorithms & Data Structures 2
// Graph data structure starter - Second Traversal
// 2020, Dr. Muhammad Al-Hashimi

// -----------------------------------------------------------------------
// simple graph object with linked-list edge implementation and minimal fields
// extra vertex and edge member fields and methods to be added later as needed


// graph from Figure 3.10 (Levitin, 3rd edition)
// read info to configure *user* property fields of Vertex object,
// note global var naming convention

var _v = [
   {label:"a"},
   {label:"b"},
   {label:"c"},
   {label:"d"},
   {label:"e"},
   {label:"f"},
   {label:"g"},
   {label:"h"},
   {label:"i"},
   {label:"j"}

   ];

var _e = [
   {u:0, v:3},
   {u:0, v:2},
   {u:3, v:2},
   {u:2, v:5},
   {u:5, v:4},
   {u:5, v:1},
   {u:1, v:4},
   {u:0, v:4},
   {u:6, v:7},
   {u:7, v:8},
   {u:8, v:9},
   {u:9, v:6}

   ];


// create a graph (default undirected)
var _g = new Graph();

// if _g is directed (digraph) change property BEFORE input
// _g.digraph = true;

// use global input arrays _v and _e to initialize internal data structures
_g.read_graph(_v,_e);

// perform depth-first search and store result
_g.DFS();

// call BFS similarly



// -----------------------------------------------------------------------
// Vertex object constructor

function Vertex(v)
{
   // user input fields

   this.label = v.label;          // vertex can be labelled

   // more fields to initialize internally

   this.visit = false;            // vertex can be marked visited (useful for traversals)
   this.adjacent = new List();    // init an adjacency list
}

// -----------------------------------------------------------------------
// Graph object constructor

function Graph()
{
   this.verts = [];               // vertex list (an array of Vertex objects)
   this.nv;                       // number of vertices
   this.ne;                       // number of edges
   this.digraph = false;          // true if digraph, false otherwise (default undirected)
   this.dfs_push = [];            // DFS order output array
   this.bfs_out =                 // (fill) BFS order output array

   // --------------------
   // student property fields next


   // --------------------
   // member methods use functions defined below

   this.read_graph = better_input;  // default input reader method
   this.print_graph = list_verts;
   this.add_edge = add_edge;
   this.DFS = DFS;                  // perform a depth-first search
   this.dfs = dfs;                  // DFS a connected component


   // --------------------
   // student methods next; implementing functions in student code section at end

   this.BFS =                       // (fill) perform a breadth-first search
                                    // (fill) BFS a connected component

}


// -------------------------------------------------------
// Functions used by methods of Graph object. Similar to
// normal functions but use object member fields and
// methods, depending on which object is passed by the
// method call through the self variable: this.
//

// --------------------
function list_verts()    // simple vertex lister
{
   for (var i=0; i < this.nv; i++)
   {
      var v = this.verts[i];
      document.write( "VERTEX: ", i,
         " {", v.label, "} - VISIT: ", v.visit,
         " - ADJACENCY: ", v.adjacent.traverse(), "<br>" );
   }
}

// --------------------
function add_edge(u_i,v_i)
{

}

// --------------------
function better_input(v,e)

}

// --------------------
function DFS()
{

}

// --------------------
function dfs(v_i)
{

}


// -----------------------------------------------------------------------
// -----------------------------------------------------------------------
// --- begin student code section ----------------------------------------

function BFS()
{
   // mark all vertices unvisited


   // traverse unvisited connected components

}

// --------------------
function bfs(v_i)
{
   // get vertex v by its id


   // process v


   // initialize queue with v


   // while queue not empty


      // dequeue and process a vertex, u


      // queue all unvisited vertices adjacent to u


}