有向圖演算法
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也不錯（稀疏圖效率高）
具體程序可以上網查