連通器演算法
A. 已知一個圖的連接矩陣，判斷給定兩個節點是否連通的演算法思想
用深度優先搜索，從給定節點開始，遍歷一遍所有節點，如果另一個節點遍歷到了，就連同，反之不連通
如果要算出所有節點，則每個節點都執行一次DFS，把結果存在一個二維數組里，就能查詢了！
B. 在n個城市之間建設網路,只需保證連通即可，求最經濟的架設方案 多種演算法求解 求完整的程序代碼……
我給出prim和kruscal兩種實現吧，其中prim用到了堆，用於每次選出剩餘邊中的權值最小的邊，而kruscal用到了並查集，用於保存已求得的連通分量。我的題目是hdoj1863，跟上面要求基本相同，這兩種實現都已AC。下面是代碼：
//prim實現
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
struct Node
{
int to;
int cost;
};
int w[102][102];
Node heap[102];
int N,M,res,size;
void down(int p)
{
Node n=heap[p];
for(int q=p<<1;q<=size;q<<=1)
{
if(q<size&&heap[q+1].cost!=-1&&heap[q].cost>heap[q+1].cost)
q++;
if(heap[q].cost==-1||n.cost!=-1&&n.cost<=heap[q].cost)
{
break;
}
heap[p]=heap[q];
p=q;
}
heap[p]=n;
}
void up(int p)
{
if(heap[p].cost==-1)
return;
Node n=heap[p];
for(int q=p>>1;q>=1;q>>=1)
{
if(heap[q].cost!=-1&&heap[q].cost<=n.cost)
break;
heap[p]=heap[q];
p=q;
}
heap[p]=n;
}
void build()
{
for(int i=size>>1;i>0;i--)
down(i);
}
void prim()
{
for(int i=2;i<=M;i++)
{
heap[i-1].cost=w[1][i];
heap[i-1].to=i;
}
size=M-1;
build();
res=0;
for(int i=1;i<M;i++)
{
if(heap[1].cost==-1)
{
res=-1;
return;
}
res+=heap[1].cost;;
int v=heap[1].to;
heap[1]=heap[size--];
down(1);
for(int j=1;j<=size;j++)
{
if(w[v][heap[j].to]!=-1)
{
if(w[v][heap[j].to]<heap[j].cost||heap[j].cost==-1)
{
heap[j].cost=w[v][heap[j].to];
up(j);
}
}
}
}
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF&&N)
{
memset(w,255,sizeof(w));
int a,b,cost;
memset(w,255,sizeof(w));
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&a,&b,&cost);
w[a][b]=w[b][a]=cost;
}
prim();
if(res==-1)
printf("?\n");
else
printf("%d\n",res);
}
}
//kruscal實現
#include<iostream>
#include<algorithm>
usingnamespacestd;
struct Edge
{
intu,v,w;
};
Edge edges[5000];
int parent[102];
intN,M,res;
int find(int v)
{
if(parent[v]>0)
parent[v]=find(parent[v]);
return parent[v]>0?parent[v]:v;
}
voinion_set(inta,int b)
{
if(parent[a]<=parent[b])
{
parent[a]+=parent[b];
parent[b]=a;
}
else
{
parent[b]+=parent[a];
parent[a]=b;
}
}
intcmp(Edge e1,Edge e2)
{
return e1.w<e2.w;
}
Void kruscal()
{
res=0;
memset(parent,255,sizeof(parent));
sort(edges,edges+N,cmp);
intloc=0;
int a,b,p1,p2,count=0;
bool flag=true;
while(loc<N)
{
do
{
loc++;
if(loc>N)
{
flag=false;
break;
}
a=edges[loc].u;
b=edges[loc].v;
p1=find(a);
p2=find(b);
}while(p1==p2);
if(!flag)
break;
res+=edges[loc].w;
union_set(p1,p2);
count++;
}
if(count<M-1)
res=-1;
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF&&N)
{
for(inti=1;i<=N;i++)
scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
kruscal();
if(res==-1)
printf("?\n");
else
printf("%d\n",res);
}
}
C. 強連通分量(Kosaraju演算法)
{ //判斷各個強連通分量是否為出度為0的分量 for(int t = 0; t
D. 連通圖的深度優先遍歷演算法
這個第一個點是隨機的。只是看你怎麼儲存的。如果你把v的鄰接頂點用數組保存，那麼它在數組的最前邊。用指針的話，就指向下一個緊接的位置。
E. connected component是什麼意思
connected component
英[kəˈnektɪd kəmˈpəunənt]
美[kəˈnɛktɪd kəmˈponənt]
連通分支[量];
[例句]The crux of the algorithm comes in determining whether a node is the root of a strongly connected component.
演算法的關鍵是判斷一個結點是否是強連通分量的根。
F. 強連通分量的Gabow演算法思路
這個演算法其實就是Tarjan演算法的變異體，我們觀察一下，只是它用第二個堆棧來輔助求出強連通分量的根，而不是Tarjan演算法裡面的indx[]和mlik[]數組。那麼，我們說一下如何使用第二個堆棧來輔助求出強連通分量的根。
我們使用類比方法，在Tarjan演算法中，每次mlik[i]的修改都是由於環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環裡面只剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環內。那麼Gabow演算法中的第二堆棧變化就是刪除構成環的節點，只剩深度最低的節點，或者全部刪除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那麼只要出棧一直到棧頂那個頂點的訪問時間不大於深度最低的那個頂點。其中每個被彈出的節點屬於同一個強連通分量。那有人會問：為什麼彈出的都是同一個強連通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan演算法有了解的都應該清楚，那麼Tarjan演算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。
現 在，你應該明白其實Tarjan演算法和Gabow演算法其實是同一個思想的不同實現，但是，Gabow演算法更精妙，時間更少(不用頻繁更新mlik[])。 Gabow_Algorithm:
步驟1:
找一個沒有被訪問過的節點v，goto step2(v)。否則，演算法結束。
步驟2(v):
將v壓入堆棧stk1[]和stk2[]
對於v所有的鄰接頂點u：
1) 如果沒有訪問過，則step2(u)
2) 如果訪問過，但沒有刪除，維護stk2[](處理環的過程)
如果stk2[]的頂元素==v，那麼輸出相應的強連通分量 C++：#include<iostream>usingnamespacestd;constintMAXN=110;typedefintAdjTable[MAXN];//鄰接表類型intn;intintm[MAXN];//標記進入頂點時間intbelg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬於第belg[i]個強連通分量intstk1[MAXN];//輔助堆棧intstk2[MAXN];//輔助堆棧AdjTableadj[MAXN];//鄰接表//深搜過程,該演算法的主體都在這里voidVisit(intcur,int&sig,int&scc_num){inti;intm[cur]=++sig;stk1[++stk1[0]]=cur;stk2[++stk2[0]]=cur;for(i=1;i<=adj[cur][0];++i){if(0==intm[adj[cur][i]]){Visit(adj[cur][i],sig,scc_num);}elseif(0==belg[adj[cur][i]]){while(intm[stk2[stk2[0]]]>intm[adj[cur][i]]){--stk2[0];}}}if(stk2[stk2[0]]==cur){--stk2[0];++scc_num;do{belg[stk1[stk1[0]]]=scc_num;}while(stk1[stk1[0]--]!=cur);}}//Gabow演算法,求解belg[1..n],且返回強連通分量個數,intGabow_StronglyConnectedComponent(){inti,sig,scc_num;memset(belg+1,0,sizeof(int)*n);memset(intm+1,0,sizeof(int)*n);sig=0;scc_num=0;stk1[0]=0;stk2[0]=0;for(i=1;i<=n;++i){if(0==intm[i]){Visit(i,sig,scc_num);}}returnscc_num;}Pascalproceretarjan(r:longint);varx,i,j:longint;begininc(timez);time[r]:=timez;low[r]:=timez;inc(top);zh[top]:=r;fori:=p1[r]top2[r]dobeginj:=e[i].y;iftime[j]=0thentarjan(j);iflow[j]<low[r]thenlow[r]:=low[j];end;iftime[r]=low[r]thenrepeatx:=zh[top];num[x]:=r;low[x]:=n+1;//這句話千萬別忘了dec(top);untilx=r;end;
G. 連通器之所以液面相平是因為要保持各高度壓強相等嗎可如果封一段砌築，那一段的壓強都是相等的哦
你把因果顛倒了，靜止狀態下由於靜壓能的作用液面保持相平，封在液體中的氣體往往是被壓縮的p=Pa+pgh
H. 用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;
}