寻找通用汇点

// Graph2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<queue>
using namespace std;
typedef int Vertex;
#define NotAVertex 0
#define INF 65536
//定义链表节点////////////////////////////////////
typedef struct TreeNode *Position;
struct TreeNode {
	int vertex;
	int weight;
	Position Next;
};

//定义邻接表结构/////////////////////////////////////
typedef struct adjaceency_list *adjaceency;
struct adjaceency_list {
	int numVertex;      //大小
	Position* table;   //表地址
};

//邻接表初始化函数////////////////////////////////////
adjaceency initAdjaceency_list(int numVertex)
{
	//申请一个邻接表地址,给邻接表赋初值
	adjaceency adja = (adjaceency)malloc(sizeof(adjaceency_list));
	adja->numVertex = numVertex;
	if (adja == NULL)
		cout << "Error";

	//申请一个table地址
	adja->table = (Position*)malloc(sizeof(Position)*(adja->numVertex + 1));
	if (adja->table == NULL)
		cout << "Error";

	//给邻接表每一个表项添加一个链表表头
	for (int i = 1; i <= adja->numVertex; i++) {
		adja->table[i] = (Position)malloc(sizeof(TreeNode));
		if (adja->table[i] == NULL)
			cout << "Error";
		else {
			adja->table[i]->vertex = i;
			adja->table[i]->weight = 0;       //给每个邻接表项的链表头的权重设为0
			adja->table[i]->Next = NULL;
		}
	}
	return adja;
}

//邻接表的插入函数,制定一个顶点per_ver,把邻接的顶点aft_ver插入其后//////////////////////////////////
void Insert(adjaceency adja, Vertex per_ver, Vertex aft_ver, int weight)
{
	//申请一个链表节点地址
	Position inser = (Position)malloc(sizeof(TreeNode));
	if (inser == NULL)
		cout << "Error";

	//从头插入,修改指针
	inser->vertex = aft_ver;
	inser->weight = weight;                   //从per_ver指向aft_ver的权重
	inser->Next = adja->table[per_ver]->Next;
	adja->table[per_ver]->Next = inser;
}

//打印邻接表//////////////////////////////////////////
void print(adjaceency adja)
{
	cout << "Vertex" << endl;
	for (int i = 1; i <= adja->numVertex; i++)
	{
		Position p = adja->table[i];
		while (p != NULL) {
			cout << p->vertex << ‘\t‘;
			p = p->Next;
		}
		cout << endl;
	}
	cout << endl;
}

//寻找通用汇点,通用汇点是指入度为V-1,出度为0的点
Vertex  findUniversalSink(adjaceency adja)
{
	Vertex UniversalSink;
	Position p;
	bool flag = false;

	//先寻找有没有出度为0的点,若没有直接返回一个空点NotAVertex;
	for (Vertex ver = 1; ver <= adja->numVertex; ver++)
		if (adja->table[ver]->Next == NULL)
		{
			UniversalSink = ver;
			flag = true;
			//这个标志位是为了下面的循环服务的,若下面的循环没有修改这个标志位,说明所有点的邻接点都有UniversalSink;
		}
	if (!flag) return NotAVertex;

	//能运行到这里说明有出度为0的点,有且只有一个,检查是不是所有邻接链表都有它
	for (Vertex ver = 1; ver <= adja->numVertex; ver++)
	{
		if (ver == UniversalSink)  //本身不检查
			continue;
		else
		{
			//每一个链表查找
			p = adja->table[ver]->Next;
			while (p)
			{
				if (p->vertex == UniversalSink)
					break;
				p = p->Next;
			}

			//如果P==NULL说明上面的循环没有提前退出,可见UniversalSink不在该链表里,所以可以直接退出大循环,并设标志位为假
			if (p == NULL)
			{
				break;
				flag = false;
			}
		}
	}
	return flag ? UniversalSink : NotAVertex;
}

int main()
{
	//初始化邻接表////////////////////////////////////////
	adjaceency adja = initAdjaceency_list(7);
	Insert(adja, 1, 3, 4); Insert(adja, 1, 4, 1); Insert(adja, 1, 2, 2);
	Insert(adja, 2, 5, 10); Insert(adja, 2, 4, 3);
	Insert(adja, 3, 6, 5);
	Insert(adja, 4, 3, 2); Insert(adja, 4, 7, 4); Insert(adja, 4, 6, 8);
	Insert(adja, 5, 7, 6); Insert(adja, 5, 4, 2);
	Insert(adja, 6, 4, 1);
	Insert(adja, 7, 6, 1);
	print(adja);

	//寻找通用汇点
	Vertex UniversalSink = findUniversalSink(adja);
	if (findUniversalSink(adja))
		cout << "本图的通用汇点为V" << UniversalSink << endl;
	else
		cout << "本图没有通用汇点" << endl;
	while (1);

    return 0;
}

  

时间: 04-11

寻找通用汇点的相关文章

关于大型网站技术演进的思考(三)--存储的瓶颈(3)(转)

原文:http://www.cnblogs.com/sharpxiajun/p/4251714.html 存储的瓶颈写到现在就要进入到深水区了,如果我们所做的网站已经到了做数据库垂直拆分和水平拆分的阶段,那么此时我们所面临的技术难度的挑战也会大大增强. 这里我们先回顾下数据库的垂直拆分和水平拆分的定义: 垂直拆分:把一个数据库中不同业务单元的数据分到不同的数据库里. 水平拆分:是根据一定的规则把同一业务单元的数据拆分到多个数据库里. 垂直拆分是一个粗粒度的拆分数据,它主要是将原来在一个数据库下的

Commons_logging包 Apache通用日志包

他为Log4JLogger:NoOpLog:LogKitLogger:Jdk14Logger:AvalonLogger提供了一共通用的接口进行调用,使得在使用各种不同的第三方日志包时变得非常简单.SimpleLog:是commons_logging自带的一个控制台输出日志. 可以通过简单的配置使用不同的第三方日志包. 在src根目录下放进commons-logging.properties文件,进行配置使用哪个第三方日志包. #定义了使用的具体第三方的日值包 #org.apache.common

Java反序列化漏洞通用利用分析

2015年11月6日,FoxGlove Security安全团队的@breenmachine 发布的一篇博客[3]中介绍了如何利用Java反序列化漏洞,来攻击最新版的WebLogic.WebSphere.JBoss.Jenkins.OpenNMS这些大名鼎鼎的Java应用,实现远程代码执行. 然而事实上,博客作者并不是漏洞发现者.博客中提到,早在2015年的1月28号,Gabriel Lawrence (@gebl)和Chris Frohoff (@frohoff)在AppSecCali上给出了

C语言的通用链表

在操作系统编程中, 往往是使用C语言, 但C使用起来极为痛苦, 不像C++有方便的STL模板库使用. linux内核中,有一套非常神奇的通用链表结构,能够方便的使用,管理各种类型的数据,我们今天就来研究一下,内核中的C数据结构. 本文参考:[深入分析 Linux 内核链表] 首先,我们的目标是构建一个循环双链表结构,为何是双链表,还要循环,当然是从易用性考虑了,双链表能够方便的得知自己的上一个元素,在内核中管理数据更为方便. 其一般结构大概是这样: 实现机制 首先定义一个list_node结构,

以属性为核心驱动的 全领域通用架构设计原理 (简称:属性架构原理)

以属性为核心驱动的全领域通用架构设计原理 (简称:属性架构原理) 联系方式:13547930387 Email:[email protected] 一.个人声明 我,参加工作也有5年多了,是一名普通的不能在普通的程序员,一直在使用公司自己的产品进行开发,因此技术比较菜,此设计完全是按照自己天真的想法而设计的,如果有不合理或很搞笑的地方,请轻拍,由衷的希望大家能提出宝贵的意见: 根据此设计原理我也做了一个简单的(demo)架构来支撑和验证此理论的可行性,由于技术功底不太好,有不合理之处请大家谅解,

饿了么基于Vue2.0的通用组件开发之路(分享会记录)

Element:一套通用组件库的开发之路 Element 是由饿了么UED设计.饿了么大前端开发的一套基于 Vue 2.0 的桌面端组件库.今天我们要分享的就是开发 Element 的一些心得. 官网:http://element.eleme.io/#/github:https://github.com/ElemeFE/element ## 设计目的 大部分项目起源都是源于业务方的需求,Element 也是一样.随着公司业务发展,内部开始衍生出很多后台系统,UED 部门也接到越来越多的设计需求,

100offer举办的「寻找实干和坚持的技术力量」开源项目投票排名分析程序

由于100offer举办的「寻找实干和坚持的技术力量」开源项目投票活动没有按照票数排序的功能,所以本文写了个小程序来实现这个功能,代码如下: import org.jsoup.Jsoup; import org.jsoup.nodes.Element; import java.net.URL; import java.util.HashMap; import java.util.Map; import java.util.concurrent.atomic.AtomicInteger; /**

Django学习之通用视图(generic views)

Django的通用视图可以减少开发的单调性,它抽象出一些在视图开发中常用的代码和模式,这样就可以在无需编写大量代码的情况下,快速编写出常用的视图函数.下面将使用通用视图重写前面所写的代码.要使用通用视图,我们需要做几件事: 修改URLconf 编写基于通用视图的视图函数 1.修改URLconf from django.conf.urls import patterns,url from blog.views import * urlpatterns = patterns('', url(r'^$

独立思考者模型:寻找潜藏在表象背后的真相 探寻真相的方法

http://www.nowamagic.net/librarys/veda/detail/2370我爱看侦探小说,看侦探小说最大的乐趣不在于知道结局,而在于侦探提出犯罪假设,到现场寻找线索,然后在脑中思考这些线索的关联和矛盾,从而建立犯罪真相的模型,最后将线索填入模型,Bingo!得出结论的思考过程. 这个主题将分享我的5个寻找真相模型,体验成为数据侦探的乐趣. 1.  因果关联模型 我上大学时,我发现一个非常有趣的规律.周围哥们和女朋友分手的概率是和他最近去学校小卖部的概率成正比的,我把这个