没有合适的资源？快使用搜索试试~ 我知道了~

首页算法V（C++实现）——图算法

算法V（C++实现）——图算法

源码

1星需积分: 10 113 下载量 199 浏览量更新于2023-07-23 2 收藏 146KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

37页

感谢Robed Sedgewick，研究网络的朋友们可以看看。 Robed Sedgewick拥有斯坦福大学博士学位(导师为Donald E. Knuth)，昔林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是XeroxPARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。除本书外，他还与Philippe Flajolet合著了《算法分析导论》一书

资源详情

资源推荐

This le contains the code from "Algorithms in C++, Third Edition,

Part 5," by Robert Sedgewick, and is covered under the copyright

and warranty notices in that book. Permission is granted for this

code to be used for educational purposes in association with the text,

and for other uses not covered by copyright laws, provided that

the following notice is included with the code:

"This code is from "Algorithms in C++, Third Edition,"

by Robert Sedgewick, Addison-Wesley, 2002."

Commercial uses of this code require the explicit written

permission of the publisher. Send your request for permission,

stating clearly what code you would like to use, and in what

specic way, to: aw.cse@aw.com

----------

CHAPTER 17. Graph Properties and Types

-----

struct Edge

{ int v, w;

Edge(int v = -1, int w = -1) : v(v), w(w) { }

};

class GRAPH

{ private:

// Implementation-dependent code

public:

GRAPH(int, bool);

~GRAPH();

int V() const;

int E() const;

bool directed() const;

int insert(Edge);

int remove(Edge);

bool edge(int, int);

class adjIterator

{

public:

adjIterator(const GRAPH &, int);

int beg();

int nxt();

bool end();

};

-----

template <class Graph>

vector <Edge> edges(Graph &G)

{ int E = 0;

vector <Edge> a(G.E());

for (int v = 0; v < G.V(); v++)

{

typename Graph::adjIterator A(G, v);

for (int w = A.beg(); !A.end(); w = A.nxt())

if (G.directed() || v < w)

a[E++] = Edge(v, w);

}

return a;

}

-----

template <class Graph>

void IO<Graph>::show(const Graph &G)

{

for (int s = 0; s < G.V(); s++)

{

cout.width(2); cout << s << ":";

typename Graph::adjIterator A(G, s);

for (int t = A.beg(); !A.end(); t = A.nxt())

{ cout.width(2); cout << t << " "; }

cout << endl;

}

-----

template <class Graph>

class IO

{

public:

static void show(const Graph &);

static void scanEZ(Graph &);

static void scan(Graph &);

};

-----

template <class Graph>

class CC

{

private:

// implementation-dependent code

public:

CC(const Graph &);

int count();

bool connect(int, int);

};

-----

#include <iostream.h>

#include <stdlib.h>

#include "GRAPH.cc"

#include "IO.cc"

#include "CC.cc"

main(int argc, char *argv[])

{ int V = atoi(argv[1]);

GRAPH G(V);

IO<GRAPH>::scan(G);

if (V < 20) IO<GRAPH>::show(G);

cout << G.E() << " edges ";

CC<GRAPH> Gcc(G);

cout << Gcc.count() << " components" << endl;

}

-----

class DenseGRAPH

{ int Vcnt, Ecnt; bool digraph;

vector <vector <bool> > adj;

public:

DenseGRAPH(int V, bool digraph = false) :

adj(V), Vcnt(V), Ecnt(0), digraph(digraph)

{

for (int i = 0; i < V; i++)

adj[i].assign(V, false);

}

int V() const { return Vcnt; }

int E() const { return Ecnt; }

bool directed() const { return digraph; }

void insert(Edge e)

{ int v = e.v, w = e.w;

if (adj[v][w] == false) Ecnt++;

adj[v][w] = true;

if (!digraph) adj[w][v] = true;

}

void remove(Edge e)

{ int v = e.v, w = e.w;

if (adj[v][w] == true) Ecnt--;

adj[v][w] = false;

if (!digraph) adj[w][v] = false;

}

bool edge(int v, int w) const

{ return adj[v][w]; }

class adjIterator;

friend class adjIterator;

};

-----

class DenseGRAPH::adjIterator

{ const DenseGRAPH &G;

int i, v;

public:

adjIterator(const DenseGRAPH &G, int v) :

G(G), v(v), i(-1) { }

int beg()

{ i = -1; return nxt(); }

int nxt()

{

for (i++; i < G.V(); i++)

if (G.adj[v][i] == true) return i;

return -1;

}

bool end()

{ return i >= G.V(); }

};

-----

class SparseMultiGRAPH

{ int Vcnt, Ecnt; bool digraph;

struct node

{ int v; node* next;

node(int x, node* t) { v = x; next = t; }

};

typedef node* link;

vector <link> adj;

public:

SparseMultiGRAPH(int V, bool digraph = false) :

adj(V), Vcnt(V), Ecnt(0), digraph(digraph)

{ adj.assign(V, 0); }

int V() const { return Vcnt; }

int E() const { return Ecnt; }

bool directed() const { return digraph; }

void insert(Edge e)

{ int v = e.v, w = e.w;

adj[v] = new node(w, adj[v]);

if (!digraph) adj[w] = new node(v, adj[w]);

Ecnt++;

}

void remove(Edge e);

bool edge(int v, int w) const;

class adjIterator;

friend class adjIterator;

};

-----

class SparseMultiGRAPH::adjIterator

{ const SparseMultiGRAPH &G;

int v;

link t;

public:

adjIterator(const SparseMultiGRAPH &G, int v) :

G(G), v(v) { t = 0; }

int beg()

{ t = G.adj[v]; return t ? t->v : -1; }

int nxt()

{ if (t) t = t->next; return t ? t->v : -1; }

bool end()

{ return t == 0; }

};

-----

template <class Graph> class DEGREE

{ const Graph &G;

vector <int> degree;

public:

DEGREE(const Graph &G) : G(G), degree(G.V(), 0)

{

for (int v = 0; v < G.V(); v++)

{ typename Graph::adjIterator A(G, v);

for (int w = A.beg(); !A.end(); w = A.nxt())

degree[v]++;

}

int operator[](int v) const

{ return degree[v]; }

};

-----

static void randE(Graph &G, int E)

{

for (int i = 0; i < E; i++)

{

int v = int(G.V()*rand()/(1.0+RAND_MAX));

剩余36页未读，继续阅读

算法：C++实现 I-IV 基础、数据结构、排序和搜索(第三版) 源码作者：Robert Sedgewick

C++算法：图算法（第3版）.rar

该资源为C++算法——图算法（第三版）PDF版本，包括图搜索、有向图和无环向图、最小生成树、最短路径、网络流

算法I-IV（C++实现）— 基础、数据结构、排序和搜索（第三版）

HASH NWALK：检测超边异常的高效算法——基于Hash和Random Walk的方法

C 语言程序设计（下）——图形界面编程和窗口化应用

# 1. 图形界面编程基础 ## 1.1 GUI（图形用户界面）概述 GUI 是指通过图形方式展示程序界面，用户可以通过鼠标、键盘等操作与程序进行交互。相对于命令行界面，GUI 更加直观友好，用户体验更佳。...

符号转换与优化：sympy2c——用Python实现的符号C/C 代码生成

天文学与计算机42（2023）100666全长产品sympy 2c：从符号表达式到Python中的快速C/C++函数和联合施密特，a，b，b，B。Moserb，C.S. Lorenzb，A. RéfrégierbaScientific IT Services，ETH Zürich，Binzmü...

《数据结构与算法——c++版》

《数据结构与算法——c 版》是一本介绍数据结构和算法的学习教材。这本书以C语言为主要编程语言，全面讲解了数据结构和算法的基本概念及其常见的应用。通过学习本书，读者可以掌握C语言中常用的数据结构和算法，提高...

c++贪心——最大整数

贪心算法是一种问题求解方法，它在每一步总是做出当前情况下的最优选择，以期望获得最优解。而"最大整数"同样可以使用贪心算法来求解。对于"最大整数"的问题，我们可以考虑如下的贪心策略：从高位开始，尽可能选择...

贪心算法之——C++均分纸牌

回答: 这段代码是一个用C++编写的贪心算法，用于均分纸牌。代码中首先读取输入的纸牌数量N和每张纸牌的值，然后计算纸牌的总和sum和平均值average。接下来，通过遍历纸牌数组，将不等于平均值的纸牌进行移动，使得每...

武汉地铁站点最短路径搜索的实现（一）——Dijkstra算法（C++ coding）

好的，以下是基于 Dijkstra 算法实现武汉地铁站点最短路径搜索的 C++ 代码： ```cpp #include #include #include #include using namespace std; const int MAXN = 100; // 最大站点数 const int INF = INT_...

信息学奥赛一本通C++语言——1216：红与黑

红与黑是一道经典的信息学奥赛题目，通常在算法与图论的章节中出现。...另外，可以使用递归或栈来实现DFS算法，使用队列来实现BFS算法。希望以上解答能对你有所帮助！如果还有其他问题，请随时提问。

C++项目——基于QT的电梯仿真系统

这是一个非常有趣的项目！...同时，你也可以使用C++语言编写电梯的逻辑代码，例如状态机、调度算法等等。最后，你可以使用QT提供的调试工具来测试和调试你的程序，确保它能够正常运行并满足用户需求。

零基础学C/C++94——数组中查找数

引用\[1\]是一个C++代码示例，它使用了iostream和stdio.h头文件，并使用了命名空间std。代码中使用了一个while循环来不断读取输入的n值，然后创建一个大小为n的整型数组a，并通过for循环读取数组的元素。接下来，...

关联分析——FP-growth算法 C++带类实现及案例

C++作为一种高效的编程语言，也可以用于实现FP-growth算法。下面是一个基于C++类的FP-growth算法实现及案例示例： ```cpp #include #include #include #include #include using namespace std; class Node ...

关联分析——FP-growth算法 C++带类优化实现及案例

二、FP-growth算法C++实现下面是FP-growth算法的C++实现代码，其中使用了类的封装来优化代码结构： ```cpp #include #include #include #include #include #include using namespace std; //定义FP树节点类 ...

c++实现单纯性算法

2. 然后需要实现单纯性算法的核心部分——找到一个入基变量和出基变量，以及计算新的可行解。 ```c++ int simplex() { while (true) { int p = 0, q = 0; for (int i = 1; i ; i++) { if (c[i] > eps) { p = i...

c++实战之——用哈夫曼算法进行文件压缩解压缩

哈夫曼算法是一种经典的无损数据压缩算法，它通过将频率较高的字符用较短的编码表示，而频率较低的字符用较长的编码表示，从而实现文件的压缩。首先，对于要压缩的文件，我们需要统计各个字符的出现频率。然后，...

sanfracisco

粉丝: 1
资源: 5

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

算法V（C++实现）——图算法

算法：C++实现 I-IV 基础、数据结构、排序和搜索(第三版) 源码 作者：Robert Sedgewick

C++算法：图算法 （第3版）.rar

算法I-IV（C++实现）— 基础、数据结构、排序和搜索（第三版）

算法（c++）——地图着色问题.rar

算法（c++)—— 集合划分问题.rar

Geo-MST：QGIS地理最小生成树插件 v2.0——开源地理信息软件的新功能改进

HASH NWALK：检测超边异常的高效算法——基于Hash和Random Walk的方法

C 语言程序设计（下）——图形界面编程和窗口化应用

符号转换与优化：sympy2c——用Python实现的符号C/C 代码生成

《数据结构与算法——c++版》

c++贪心——最大整数

贪心算法之——C++均分纸牌

武汉地铁站点最短路径搜索的实现（一）——Dijkstra算法（C++ coding）

信息学奥赛一本通C++语言——1216：红与黑

C++项目——基于QT的电梯仿真系统

零基础学C/C++94——数组中查找数

关联分析——FP-growth算法 C++带类实现及案例

关联分析——FP-growth算法 C++带类优化实现及案例

c++实现单纯性算法

c++实战之——用哈夫曼算法进行文件压缩解压缩

会员权益专享

最新资源

算法：C++实现 I-IV 基础、数据结构、排序和搜索(第三版) 源码作者：Robert Sedgewick

C++算法：图算法（第3版）.rar