有向图算法
A. 用C语言编写求有向图有多少连通图的算法（数据结构题目）
深度优先搜索。
http://www.cnblogs.com/dzkang2011/p/bfs_dfs.html
#include<iostream>
#include<cstdio>
usingnamespacestd;
#definemaxn100//最大顶点个数
intn,m;//顶点数，边数
structarcnode//边结点
{
intvertex;//与表头结点相邻的顶点编号
intweight=0;//连接两顶点的边的权值
arcnode*next;//指向下一相邻接点
arcnode(){}
arcnode(intv,intw):vertex(v),weight(w),next(NULL){}
arcnode(intv):vertex(v),next(NULL){}
};
structvernode//顶点结点，为每一条邻接表的表头结点
{
intvex;//当前定点编号
arcnode*firarc;//与该顶点相连的第一个顶点组成的边
}Ver[maxn];
voidInit()//建立图的邻接表需要先初始化，建立顶点结点
{
for(inti=1;i<=n;i++)
{
Ver[i].vex=i;
Ver[i].firarc=NULL;
}
}
voidInsert(inta,intb,intw)//尾插法，插入以a为起点，b为终点，权为w的边，效率不如头插，但是可以去重边
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)//如果不要去重边，去掉这一段
{
if(p->weight<w)
p->weight=w;
return;
}
while(p->next!=NULL)
{
if(p->next->vertex==b)//如果不要去重边，去掉这一段
{
if(p->next->weight<w);
p->next->weight=w;
return;
}
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb,intw)//头插法，效率更高，但不能去重边
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidInsert(inta,intb)//尾插法，插入以a为起点，b为终点，无权的边，效率不如头插，但是可以去重边
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)return;//去重边，如果不要去重边，去掉这一句
while(p->next!=NULL)
{
if(p->next->vertex==b)//去重边，如果不要去重边，去掉这一句
return;
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb)//头插法，效率跟高，但不能去重边
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidShow()//打印图的邻接表（有权值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->("<<p->vertex<<","<<p->weight<<")";
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
voidShow2()//打印图的邻接表(无权值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->"<<p->vertex;
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
#defineINF999999
boolvisited[maxn];//标记顶点是否被考察，初始值为false
intparent[maxn];//parent[]记录某结点的父亲结点，生成树，初始化为-1
intd[maxn],time,f[maxn];//时间time初始化为0，d[]记录第一次被发现时，f[]记录结束检查时
voiddfs(ints)//深度优先搜索（邻接表实现），记录时间戳，寻找最短路径
{
cout<<s<<"";
visited[s]=true;
time++;
d[s]=time;
arcnode*p=Ver[s].firarc;
while(p!=NULL)
{
if(!visited[p->vertex])
{
parent[p->vertex]=s;
dfs(p->vertex);
}
p=p->next;
}
time++;
f[s]=time;
}
voiddfs_travel()//遍历所有顶点，找出所有深度优先生成树，组成森林
{
for(inti=1;i<=n;i++)//初始化
{
parent[i]=-1;
visited[i]=false;
}
time=0;
for(inti=1;i<=n;i++)//遍历
if(!visited[i])
dfs(i);
cout<<endl;
}
intmain()
{
inta,b;
cout<<"Enternandm：";
cin>>n>>m;
Init();
while(m--)
{
cin>>a>>b;//输入起点、终点
Insert2(a,b);//插入操作
}
Show2();//邻接表
dfs_travel();//遍历
intcnt=0;//连通图个数
for(inti=1;i<=n;i++)
if(parent[i]==-1)
cnt++;
printf("%d ",cnt);
return0;
}
B. 编写算法，求有向图中各定点的入度
先是根据邻接表的顶点个数n,创建一个int型的数组a[n]（用来存储各顶点的入度）,把a[n]中的每一项置为0。然后再邻接表遍历一下就行了，先是顶点遍历，然后弧遍历。
我大致写一下算法。
#define n 30;
struct diagraph
{
struct vertex * head;
struct Vertex ver;
struct Edge edg;
}
struct Vertex
{
int pos;
Vertex * nextVertex;
Edge * firstEdge;
};
struct Edge
{
int pos;
Edge * nextEdge;
Vertex * endPoint;//弧尾指向结点的指针
}
void main()
{
struct digraph a;
//先是邻接表的建立，我就不写了，建立完之后如下
int a[n];
int i,j;
struct Vertex * current = a.head;
struct Edge * eCurrent;
for(i=0;i<n;i++)
{
eCurrent=current->firstEdge;
while(eCurrent!=0)
{
a[eCurrent->pos]++;
eCurrent=eCurrent->nextEdge;
}
current = current->nextVertex;
}
}
我直接在知道上面写的，只是个大概，能看懂的话就给个分吧
C. 任意给定一个有向图，设计一个算法，对它进行拓扑排序(C++实现)
LS的方法可行，但是比较麻烦，我来说一种特别简单的方法！
我们for每个点，每次碰到一个未处理过的点就 处理（深搜） 这个点，并 处理（深搜） 这个点连向的所有点，处理完每个点连向的所有点后，在堆栈中加入这个点。
差不多就是这样：
dfs(点h)
{
visit[h]=true
for(所有h连向的点)
if(!visit[h连向的点])
dfs(h连向的点)
stack[++top]=h
}
for(所有点)
if(!visit[这个点])
dfs(这个点)
然后按栈输出即可，这个一定是对的，因为我们每次把这个点加入栈之前都已经把这个点连向的点加入栈了，所以满足拓扑序！
D. c++判断有向图是否有环的算法
通常是用邻接矩阵来表示一个有向图。从图中的每一个点出发，用深度优先遍历的算法，如果能够回到出发点，图中就是有环的；如果每一个点都不能回到出发点，那么它就是无环的。
E. 有向图算法问题求助
如果是有向图求度，则度=入度+出度
1、整个循环是for(i=0;i<G.n;i++) Degree[i] = 0;
2、Degree[i]++;
3、Degree[p->adjvex]++;
顺便说一下，可能你的形参名应该是int Degree[]，不然和函数体有矛盾
F. 求有向图两个顶点间的最短路径的方法，用简单语言或举例描述。
在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。
以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。
最短路径问题的提法很多。在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点S∈V到G中其余各顶点的最短路径。
例如：下图(有向图G14)，假定以v1为源点，则其它各顶点的最短路径如下表所示：
图 G14
从有向图可看出，顶点v1到v4的路径有3条：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路径长度分别为：15,20和10。因此v1到v4的最短路径为(v1,v3,v2,v4 )。
为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。
那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法。
迪杰斯特拉算法求最短路径的实现思想是：设有向图G=(V,E)，其中，V={1,2,…,n}，cost是表示G的邻接矩阵，cost[i][j] 表示有向边<i,j>的权。若不存在有向边<i,j>，则cost[i][j]的权为无穷大(这里取值为32767)。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含顶点v1。数组dist记录从源点到其他各顶点当前的最短距离，其初值为dist[i]=cost[v1][i]，i=2,…,n。从S之外的顶点集合V-S 中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S 中的顶点，把w加入集合S中调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v] 和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。
最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到 V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i] 表示从源点到顶点i之间的最短路径的前驱顶点。
G. 用来求解加权有向图的最短路径的算法是什么算法
单元最短路径：
1.如果没有负权环的稀疏图，可以用SPFA，时间复杂度O（KM）
M是边数，K是平均入队列的次数
2.如果没有负权环的稠密图，建议用Dijkstra O（N^2），用二叉堆可优化到
O（NlogN），斐波那契堆编程复杂度太高，不易于实现
3.如果有负权环，可以尝试floyd,O(n^3)
任两点最短路径：floyd较好实现，基于重标号johnson也不错（稀疏图效率高）
具体程序可以上网查