2011年5月16日 星期一

[ Data Structures with Java ] Section 26.1 : Representing Graphs

Preface : 
In order to implement a graph, we need some way to represent the set of vertices and their edges. Assume the vertices are v0, v1, v2..., vm-1. An m by m matrix, called an adjacency matrix, identifies the edges. An entry in row i and column j corresponds to the edge e(v, vj). Its value is the weight of the edge, or 0 if the edge does not exist. For instance, below figure shows a non-weighted and a weighted graph, with the corresponding adjacency matrices : 
 

The adjacency matrix representation has the disadvantage that, regardless of the number of edges, it always requites V x V = V^2 entries, where V is the number of vertices. Another representation of a graph associates with each vertex a list of its adjacent vertices (neighbors). This model is often more efficient because it stores information for precisely the edges that actually belong to the graph. For each vertex, an element in the adjacency list is a pair consisting of the destination vertex and the weight of the edge. For the graph from upper figure, we give the adjacency-list representation as below figure : 
 

The DiGraph class uses the adjacency-list representation for a graph. We will discuss more about DiGraph in the follow up sections.

沒有留言:

張貼留言

[JS 文章收集] 用 Node.js 學 JavaScript 語言(1)簡介與安裝

Source From  Here   簡介   Node.js  是 Ryan Dahl 基於 Google 的 V8 引擎於 2009 年釋出的一個 JavaScript 開發平台,主要聚焦於 Web 程式的開發,通常用被來寫網站。但是,要開發網站就勢必要把「 HTML,...