// 强连通分支(邻接表存储).cpp : Defines the entry point for the console application.
//通过二次利用深度优先搜索访问节点,每次的深度优先搜索操作不同
#include "stdafx.h"
#include<iostream>
#define MAX 100
using namespace std;
//深度搜索访问节点层次标志枚举变量
enum Color{white,gray,black};
//边端点结构体
struct edgeNode
{
int no; //边尾端的序号
char info; //边端的名称
struct edgeNode * next; //下一个
};
//节点结构体
struct vexNode
{
char info; //节点名称
struct edgeNode *link; //与之相连的端点
};
//强连通子图的链表头结构体
struct StronConHead
{
int num; // 强连通子图序号
struct StronConNode *link; //此强连通子图的第一个节点
};
//
struct StronConNode
{
int num; //一个强连通子图节点的序号
char info; //一个强连通子图节点的名称
struct StronConNode *next; //下一个
};
//深度搜索访问节点的开始/完成时间结构体
struct Time
{
int num; //节点序号
int time; //时间
};
//存储节点信息,adjlist1存储图,adjlist2存储图的转置
vexNode adjlist1[MAX],adjlist2[MAX];
//访问层次
//还没访问为white,访问了但是还没完成它的所有后裔的搜索为gray
//完成它的所有后裔的搜索为black
Color color[MAX];
//访问的开始时间
Time d[MAX];
//访问的完成时间
Time f[MAX];
//深度搜索时,访问过的节点标志
bool visited[MAX];
//con[j]是序号为j的强连通子图的链表头数组,
StronConHead con[MAX];
//建立邻接表存储与其转置
//adjlist1为节点集,adjlist2为图转置节点集,n为节点个数,e为边数目
void createGraph(vexNode *adjlist1,vexNode *adjlist2,int n,int e)
{
int i;
for(i=1;i<=n;i++)
{
cout<<"请输入节点"<<i<<"的名称:";
cin>>adjlist1[i].info;
adjlist2[i].info = adjlist1[i].info;
adjlist1[i].link = NULL;
adjlist2[i].link = NULL;
}
edgeNode *p1,*p2;
int v1,v2;
for(i=1;i<=e;i++)
{
cout<<"请输入边"<<i<<"的起始节点序号:";
cin>>v1;
cout<<"请输入边"<<i<<"的尾节点序号:";
cin>>v2;
//建立原图邻接表
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v2;
p1->info = adjlist1[v2].info;
p1->next = adjlist1[v1].link;
adjlist1[v1].link = p1;
//建立转置图邻接表
p2 = (edgeNode*)malloc(sizeof(edgeNode));
p2->no = v1;
p2->info = adjlist2[v1].info;
p2->next = adjlist2[v2].link;
adjlist2[v2].link = p2;
}
}
//深度优先搜索有向无权图
//adjlist1为原图的邻接表存储,time为一个全局时间戳,v是第几个节点
void DFS1(vexNode *adjlist1,int &time,int v)
{
color[v] = gray;
time += 1;
d[v].num = v;
d[v].time = time;
edgeNode *p;
p = adjlist1[v].link;
while(p != NULL)
{
if(color[p->no]==white)
{
DFS1(adjlist1,time,p->no);
}
p = p->next;
}
color[v] = black;
time += 1;
f[v].num = v;
f[v].time = time;
}
////降序排列第一次深度搜索各节点的完成时间
void fast_sort_f(Time *f,int begin,int end)
{
if(begin<end)
{
int i = begin-1, j = begin;
f[0] = f[end];
while(j<end)
{
if(f[j].time>f[0].time)
{
i++;
Time temp = f[i];
f[i] = f[j];
f[j] = temp;
}
j++;
}
Time temp1 = f[end];
f[end] = f[i+1];
f[i+1] = temp1;
fast_sort_f(f,begin,i);
fast_sort_f(f,i+2,end);
}
}
//深度优先搜索有向无权图的转置图
//adjlist2为转置图的邻接表存储,con是序号为no的强连通子图的链表头数组,
//time为一个全局时间戳,v是第几个节点
void DFS2(vexNode *adjlist2,StronConHead *con,int &no,int v)
{
visited[v] = true;
StronConNode *p1 = (StronConNode*)malloc(sizeof(StronConHead));
p1->info = adjlist2[v].info;
p1->num = v;
p1->next = con[no].link;
con[no].link = p1;
edgeNode *q1;
q1 = adjlist2[v].link;
while(q1 != NULL)
{
if(!visited[q1->no])
{
DFS2(adjlist2,con,no,q1->no);
}
q1 = q1->next;
}
}
////打印各个强连通分支节点
//con是序号为no的强连通子图的链表头数组,no是强连通全局分支序号
void print_StronConCom(StronConHead *con,int &no)
{
int i;
StronConNode * p;
for(i=1;i<no;i++)
{
cout<<"强连通分支"<<i<<":";
p = con[i].link;
while(p !=NULL)
{
cout<<"("<<p->num<<":"<<p->info<<") ";
p = p->next;
}
cout<<endl;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:";
cin>>cases;
while(cases--)
{
int n,e;
cout<<"请输入节点数:";
cin>>n;
cout<<"请输入边数:";
cin>>e;
//访问节点的时间戳,全局变量
int time = 0;
//no是强连通全局分支序号,全局变量
int no = 1;
//访问标志清空与前驱节点都初始化为0
int i;
for(i=1;i<=n;i++)
{
color[i] = white;
visited[i] = false;
con[i].link = NULL;
}
//创建邻接表
createGraph(adjlist1,adjlist2,n,e);
//第一次深度搜索,搜索原图
for(i=1;i<=n;i++)
{
if(color[i]==white)
DFS1(adjlist1,time,i);
}
//降序排列第一次深度搜索各节点的完成时间
fast_sort_f(f,1,n);
//第二次深度搜索,搜索原图的转置图
for(i=1;i<=n;i++)
{
if(!visited[i])
{
DFS2(adjlist2,con,no,f[i].num);
no += 1;
}
}
//打印各个强连通分支节点
print_StronConCom(con,no);
}
system("pause");
return 0;
}
--------------------------------------------------程序测试-----------------------------------------------------
请输入案例的个数:1
请输入节点数:8
请输入边数:14
请输入节点1的名称:q
请输入节点2的名称:b
请输入节点3的名称:c
请输入节点4的名称:d
请输入节点5的名称:e
请输入节点6的名称:f
请输入节点7的名称:g
请输入节点8的名称:h
请输入边1的起始节点序号:1
请输入边1的尾节点序号:2
请输入边2的起始节点序号:2
请输入边2的尾节点序号:3
请输入边3的起始节点序号:2
请输入边3的尾节点序号:6
请输入边4的起始节点序号:2
请输入边4的尾节点序号:5
请输入边5的起始节点序号:3
请输入边5的尾节点序号:4
请输入边6的起始节点序号:3
请输入边6的尾节点序号:7
请输入边7的起始节点序号:4
请输入边7的尾节点序号:3
请输入边8的起始节点序号:4
请输入边8的尾节点序号:8
请输入边9的起始节点序号:5
请输入边9的尾节点序号:1
请输入边10的起始节点序号:5
请输入边10的尾节点序号:6
请输入边11的起始节点序号:6
请输入边11的尾节点序号:7
请输入边12的起始节点序号:7
请输入边12的尾节点序号:6
请输入边13的起始节点序号:7
请输入边13的尾节点序号:8
请输入边14的起始节点序号:8
请输入边14的尾节点序号:8
强连通分支1:(2:b) (5:e) (1:q)
强连通分支2:(4:d) (3:c)
强连通分支3:(7:g) (6:f)
强连通分支4:(8:h)
请按任意键继续. . .
分享到:
相关推荐
这是一个关于图的建立和遍历的程序,使用c++语言实现的,用的是邻接表储存。
有向图邻接矩阵c++运算操作 基本操作 邻接矩阵 c++实现
通过输入顶点数和边数,自动构造用邻接表表示的图,并显示。
程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
图的邻接矩阵存储和邻接表存储 代码完整 有注释,有需要的可以下载看看,基本是图的邻接矩阵存储和邻接表存储 代码完整
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
本文实例为大家分享了C++有向图的邻接表表示,供大家参考,具体内容如下 一、思路: 有向图的插入有向边、删除边、删除顶点和无向图的有区别。其他的和无向图的类似。 1.插入有向边 只需要插入边就行,不需要插入...
数据结构那本书上的图的邻接表存储 struct node { int vertex; struct node * nextnode; };
里面是有向图的基本操作,这是有邻接表的方式创建的, 大家可以下载看看 如果有错,请见谅
1、 定义邻接表存储的图类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)创建一个邻接表存储的图; 2)返回图中指定边的权值; 3)返回图中某顶点的第一个邻接顶点; 4)返回图中某顶点关于另一个顶点的下...
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
是图的着色问题的基础 用邻接表存储图的结构
无向图的邻接表存储及输出无向图的邻接表存储及输出无向图的邻接表存储及输出
代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图...
一次上机练习——有向图的邻接矩阵转化为邻接表并存储顶点大于50的值 小渣渣写的和大家一起学习进步
十字链表可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,对应于有向图中每一条弧有一个结点,对应于每一个顶点也有一个结点。然后建立有向图,然后利用深度优先遍历求解强连通分量
在键盘上输入有向图,对任意给定的图(顶点数和边数自定),建立它的邻接表并输出。然后判断该图是否强连通。如果是强连通图,求出该图的所有强连通分量并输出字符
c++实现图的邻接表深度优先遍历,广度优先遍历
//以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 int info; //顶点其余的信息 }VertexType; typedef struct { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数,弧数 VertexType vexs[MAXV...