您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
第5课图.doc20页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
文档加载中...广告还剩秒
需要金币：150 &&
你可能关注的文档：
··········
··········
一、选择题
1．图中有关路径的定义是（
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
参考答案：A
2．设无向图的顶点个数为n，则该图最多有（
A．n-1 B．n n-1 /2 C． n n+1 /2 D．0 E．n2
参考答案：B
3．一个n个顶点的连通无向图，其边的个数至少为（
A．n-1 B．n C．n+1 D．nlogn
参考答案：A
4．要连通具有n个顶点的有向图，至少需要（
A．n-l B．n C．n+l D．2n
参考答案：B
5．n个结点的完全有向图含有边的数目（　　）。
A．n*n Ｂ．n（n+1） C．n／2 D．n*（n-1）
参考答案：D
6．一个有n个结点的图，最少有（
）个连通分量。
A．0 B．1 C．n-1 D．n
参考答案：B
7．一个有n个结点的图，最多有（
）个连通分量。
A．0 B．1 C．n-1 D．n
参考答案：D
8．用有向无环图描述表达式 A+B *（（A+B）/A），至少需要顶点的数目为（　　）。
A．5 B．6 C．8 D．9 参考答案：A
9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（　　）。
A．逆拓扑有序 B．拓扑有序 C．无序的 参考答案：A
10．下面结构中最适于表示稀疏无向图的是（
A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表
参考答案：C
11．下列哪一种图的邻接矩阵是对称矩阵？（
A．有向图 B．无向图 C．AOV网 D．AOE网
参考答案：B
12．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。
A． B． C． D．+
参考答案：B
13．下列说法不正确的是（
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度
正在加载中，请稍后...连通图的性质_百度知道
连通图的性质
我有更好的答案
|E|&gt。没有回路的无向图是连通的当且仅当它是树;=|V|,E) 是有向图,E) 是连通的./zhidao/wh%3D450%2C600/sign=fbc3ec65d0eceb7bb8a28/beca80fcfacb0d962397dda0448359://b：|E|=|V|-1.jpg" target="_blank" title="点击查看大图" class="ikqb_img_alink"><img class="ikqb_img" src="http，而反之不成立.jpg" esrc="http.hiphotos：|E|&gt。如果 G=(V.hiphotos，那么边的数目大于等于顶点的数目减一.com/zhidao/wh%3D600%2C800/sign=48cbbbd751b7b03a35e0/beca80fcfacb0d962397dda0448359，即等价于，而反之不成立./zhidao/pic/item/beca80fcfacb0d962397dda0448359，那么它是强连通图的必要条件是边的数目大于等于顶点的数目://b://b;=|V|-1一个无向图 G=(V。<a href="http.baidu
其他类似问题
为您推荐：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁tarjan算法思想：从一个点开始，进行深度优先遍历，同时记录到达该点的时间（dfn记录到达i点的时间），和该点能直接或间接到达的点中的最早的时间（low[i]记录这个值，其中low的初始值等于dfn）。如图：
　　假设我们从1开始DFS，那么到达1的时间为1，到达2的时间为2，到达3的时间为3。同时，点1能直接或间接到达的点中，最小时间为1，点2能通过3间接到达点1，所以点2可到达最早的点时间为1，点3可以直接到达点1，故点3到达的最早的点的时间为1。）。对于每一个没有被遍历到的点A，如果从当前点有一条到未遍历点A的有向边，则遍历到A，同时将点A入栈，时间戳+1并用dfn[a]记录到达点A的时间，枚举从A发出的每一条边，如果该边指向的点没有被访问过，那么继续dfs，回溯后low[a]=min(low[a],low[j])(其中j为A可以到达的点。)如果该点已经访问过并且该点仍在栈里，那么low[a]=min(low[a],dfn[j])。
　　若点j没有被访问过，那么回溯后low[j]就是j能到达最早点，a能到达的最早点当然就是a本身能到达的最早点，或者a通过j间接到达的最早点。若点j已经被访问过，那么low[j]必然没有被回溯所更新。所以low[a]就等于a目前能到达的最小点或a直接到达点j时点j的访问时间。注意：两个句子中的&或&其实指的是两者的最小值。
那么如果我们回溯到一个点K他的low[k]=dfn[k]那么我们将K及其以前在栈中的点依次弹出，这些点即为一个强连通分量。(说明从k出发又回到k)
　　因为该点dfn=low，所以在栈中的该点以上的点都能由该点直接或间接的到达。同时栈中在该点前的任意一点j，其dfn[j] != low[j]（否则点j比点k靠前，又因为dfn[j]=low[j]，j一定先被弹出了。）那么这个点j通过low[j]这个时间的点，一定能到达点k，否则，low[j]能到达点i，又因为dfn&=low所以有2种情况1、dfn&low:那么我们可以找到前面一个更小的点。2、dfn=low：应该在回溯到i的时候就找到了一个强连通分量，从而出栈了。而点k前的点没有出栈，证明其中任意一点都能直接或者间接到达点k，进而证明这些点可以两两互达。
先用刷一道水题入门：
本题的边不带权值，可以用vector表示邻接链表:
#include &cstdio&
#include &memory.h&
#include &vector&
#include &algorithm&
using namespace
//本题的顶点号从1到n，故可直接用作vector的下标，不需要用head数组离散化
const int MAXN = 10001;
int Stack[MAXN];
bool inStack[MAXN];
//DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
int dfn[MAXN], low[MAXN];
int Bcnt, D //记录强连通的个数和当前时间
vector&int& ve[MAXN]; //邻接表保存边
void init() {
Bcnt = Dindex = top = 0;
memset(dfn, -1, sizeof dfn);
memset(inStack, false, sizeof inStack);
for (int i = 1; i & MAXN; ++i) ve[i].clear();
void tarjan(int u) {
int v = 0;
dfn[u] = low[u] = ++D
inStack[u] = true;
Stack[++top] =
int t = ve[u].size();
for (int i = 0; i & ++i) {
v = ve[u][i];
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStack[v])
low[u] = min(low[u], dfn[v]);
if (dfn[u] == low[u]) {
v = Stack[top--];
inStack[v] = false;
} while (u != v);
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
while (scanf("%d%d", &n, &m) != EOF) {
if (m == 0 && n == 0) break;
while (m--) {
scanf("%d%d", &a, &b);
ve[a].push_back(b);
for (int i = 1; i &= ++i)
if (dfn[i] == -1) tarjan(i);
if (Bcnt == 1) puts("Yes");
else puts("No");
只需找出所有的强连通分量，然后遍历所有的边，对于边u-&v，若u、v在不同的连通子图，显然v的子图可以从边u-&v达到，对于这样的两个强连通分量，可以视为一个子图，只需打电话给u所所在的子图中人，然后让这个人再联系u,v所在的两个强连通分量中的所有人。故只需找出所有的子图，打给每个子图中话费最低的那个人即可。
#include &cstdio&
#include &memory.h&
#include &algorithm&
const int MAXN = 1001;
struct N {
int u,//u to v
int//下一个顶点
} edge[MAXN * 2]; //m &= 2000
int head[MAXN],
int DFN[MAXN], Low[MAXN], D//到达某顶点的费用,该子图最小费用 ,当前费用
int Bcnt, Belong[MAXN];
//强连通分量的个数, 当前顶点所属的连通分量
int Stack[MAXN],
bool inStack[MAXN];
void addedge(int u, int v) {
N e = {u, v, head[u]};
edge[edgenum] =
head[u] = edgenum++;
void init() {
edgenum = top = Bcnt = Dindex =
memset(head, -1, sizeof head);
memset(DFN, -1, sizeof DFN);
memset(inStack, false, sizeof inStack);
void tanjar(int u) {
int v = 0;
DFN[u] = Low[u] = ++D
Stack[++top] =
inStack[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) {
v = edge[i].v;
if (DFN[v] == -1) {
tanjar(v);
Low[u] = std::min(Low[u], Low[v]);
} else if (inStack[v])
Low[u] = std::min(Low[u], DFN[v]);
if (DFN[u] == Low[u]) {
v = Stack[top--];
Belong[v] = B //将点加入该强连通图
//printf("bcnt = %d v = %d\n", Bcnt, v);
inStack[v] = false;
} while (u != v);
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int w[MAXN] = {0};
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 1; i &= ++i)
scanf("%d", &w[i]);
while (m--) {
scanf("%d%d", &a, &b);
addedge(a, b);
for (int i = 1; i &= ++i) {
if (DFN[i] == -1) tanjar(i);
//合并强连通图
int mfee[MAXN] = {0};//记录下每个强连图集的最小话费
bool inode[MAXN] = {false}; //不可达的连通图
int pos = 0;
for (int i = 0; i & ++i) {
int u = edge[i].u;
int v = edge[i].v;
if (Belong[u] != Belong[v])
//v所在的连通子图可以由u到达
inode[Belong[v]] = true;
for (int i = 1; i &= B ++i) {
if (!inode[i]) pos++;
mfee[i] = 1e9;
for (int i = 1; i &= ++i) {
int t = Belong[i];
if (!inode[t])
mfee[t] = std::min(mfee[t], w[i]);
int sum = 0;
for (int i = 1; i &= B ++i) {
if (mfee[i] != 1e9) sum += mfee[i];
printf("%d %d\n", pos, sum);
题意：让矿车采到尽可能多的矿。#表示墙，数字表示矿的数目，*表示定点传送，可选择传或者不传，矿车只能向右和向下开，不能倒退。
先来看下，可以求带环最短（最长路径）：
#include &cstdio&
#include &memory.h&
#include &vector&
using namespace
const int MAXN = 100001;
inline int Min(int a, int b) {
return a & b ? a :
inline int Max(int a, int b) {
return a & b ? a :
struct arc {
} edge[150001];
int head[MAXN];
int DFN[MAXN], Low[MAXN], D
int Stack[MAXN],
bool inStack[MAXN];
Belong[MAXN], Bnum[MAXN], B
void addedge(int u, int v) {
arc na = {u, v, head[u]};
edge[edgenum] =
head[u] = edgenum++;
void init() {
Bcnt = top = Dindex = edgenum = 0;
memset(head, -1, sizeof head);
memset(DFN, 0, sizeof DFN);
memset(inStack, false, sizeof inStack);
memset(Bnum, 0, sizeof Bnum);
void tarjan(int u) {
int v = 0;
DFN[u] = Low[u] = ++D
Stack[++top] =
inStack[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) {
v = edge[i].v;
if (DFN[v] == 0) {
tarjan(v);
Low[u] = Min(Low[u], Low[v]);
} else if (inStack[v])
Low[u] = Min(Low[u], DFN[v]);
if (DFN[u] == Low[u]) {
v = Stack[top--];
inStack[v] = false;
Belong[v] = B
Bnum[Bcnt]++;
} while (u != v);
vector&int& G[MAXN];
bool vis[MAXN];
int dfs(int s) {
int maxnum = 0;
vis[s] = true;
int size = G[s].size();
for (int i = 0; i & ++i) {
int v = G[s][i];
if (!vis[v]) {
int tmp = dfs(v);
maxnum = Max(maxnum, tmp);
vis[v] = false;
return Bnum[s] +
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int caseid = 0;
while (scanf("%d%d%d", &n, &m, &s) != EOF) {
while (m--) {
scanf("%d%d", &u, &v);
addedge(u, v);
tarjan(s);
for (int i = 1; i &= B ++i) G[i].clear();
for (int i = 0; i & ++i) {
if (DFN[edge[i].u] == 0) continue;
int u = Belong[edge[i].u];
int v = Belong[edge[i].v];
if (u != v) G[u].push_back(v);
memset(vis, false, sizeof vis);
printf("Case %d:\n%d\n", ++caseid, dfs(Belong[s]));
阅读(...) 评论()数据结构第7章-答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构第7章-答案
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
下载文档到电脑，查找使用更方便
还剩11页未读，继续阅读
你可能喜欢}