連通圖演算法
❶ 什麼叫做連通圖
連通圖：是指在圖論中，連通圖基於連通的概念。
在一個無向圖G中，若從頂點到頂點有路徑相連（當然從到也一定有路徑），則稱和是連通的。如果G是有向圖，那麼連接和的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那麼圖被稱作連通圖。圖的連通性是圖的基本性質。
❷ 連通圖的深度優先遍歷演算法
這個第一個點是隨機的。只是看你怎麼儲存的。如果你把v的鄰接頂點用數組保存，那麼它在數組的最前邊。用指針的話，就指向下一個緊接的位置。
❸ 概要描述一個演算法，判斷一個用鄰接矩陣表示的連通圖是否具有歐拉迴路。該演算法效率類型如何
演算法如下：
設鄰接矩陣維度為n*n，將鄰接矩陣進行標准化轉為概率轉移矩陣，方法是每一行元素除以行和保證每行和為1（由於連通，每行和一定大於零，所以除法可實現）
首先判斷矩陣對角線上是否有>0的元素，如有證明有歐拉迴路（自環），否則進行下一步
第二步將矩陣平方，判斷矩陣對角線上是否有>0的元素，如有證明有歐拉迴路（兩個節點的環），否則進行下一步
以此類推，直到計算矩陣的n次方，判斷對角線上是否有>0的元素，如有證明有歐拉迴路，此時仍沒有>0的元素證明該連通圖沒有歐拉迴路
這個方法的依據是，如果將鄰接矩陣標准化為概率轉移矩陣，那麼對矩陣進行k次方，得到的矩陣第(i,j)個元素的意義就是通過k步使得從i走到j的概率，那麼對角線(i,i)代表的就是從i經k步回到i的概率，這個概率大於零就代表有一條迴路。對於一個共有n個節點的有歐拉迴路的連通圖，最短的歐拉迴路結點個數一定小於等於n，所以如果n次方後還沒有出現迴路概率就可以判斷沒有迴路了
演算法效率類型我不太清楚是怎麼算的……不過這個演算法方面，標准化矩陣的部分運算復雜度不超過n，之後至多進行n步，每一步的矩陣冪大概可以到O(n)復雜度，判斷至多也就是O(n)，所以這個復雜度不超過O(n^2)的吧
❹ 一個連通圖的計算
5，最少是n-1，最多是n(n-1)/2。
❺ 如何判斷一個圖是否是連著的圖論，演算法
連通圖的特點是圖中任意兩點都是連通的，也就是說只要從任意一點出發能夠到達所有的點就能夠證明是連通圖，否則就是不連通圖
因為不知道你准備採用什麼，具體演算法我就不寫語言了，只是解釋一下原理：
1 採用數組、鏈表或數組，先將所有頂點定義在數組POINT中。
2 採用二維數組，將所有邊（線段）定義在二維數組LINE中，記錄兩遍，邊的兩個頂點分別作為第一項如（v0,v3）(v3,v0)。
3 取出一個頂點v0加入到新數組CONPOINT中，並在頂點數組POINT中刪除。
4 while循環，停止條件是CONPOINT中都標記著已讀
{
從CONPOINT中取出一個有未讀標記的頂點X，並作已讀標記。
從二維數組LINE中查找第一項中包含X的邊，將選出邊的第二個頂點（1個或多個）取出，並加入到新數組CONPOINT中，並作未讀標記（如果已有該點則不作插入）
將選出的邊從二維數組LINE中刪除。
}
比較CONPOINT和POINT數量，如果少了則不是連通圖
❻ 連通圖用深度優先和廣度優先演算法所得的生成樹是否唯一
理論上遍歷所得的生成樹或序列是不唯一的，演算法本身並沒有對同等條件下哪個點優先訪問做要求。但實際寫代碼的時候肯定要按某種順序遍歷，通常是從小到大，這時首個訪問的點肯定是第一個點，當前點與多個未訪問點相連時也是優先訪問編號小的點，這樣所得的結果就是唯一的了。
❼ 用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;
}
❽ 求無向連通圖中兩點最遠距離演算法，和Dijkstra相反，有想法就行，有代碼更好
如果是無環圖的話，把所有邊取相反數，就變成了求最短路，可以使用floyd
❾ 實現圖的鄰接表表示及連通圖
v v
❿ 怎麼用c語言和數據結構來編寫一個判斷有向圖是否為強連通圖的演算法
強連通圖表明任意兩點之間可以互相到達。
方案1：判斷結點A可以到達的點的方法如下：
首先SA = {A}；
while 1
取SA中任意沒有被去過的點x，根據以x為起點的有向線段，判斷x可以直接到達的點，然後這些點加入SA；
如此循環，直到SA中的點的個數沒有變化了
end
這樣得到的集合SA是所有A可以到達的點的一個集合。
判斷SA 是否等於S，若不等於S，表明不是強連通。
如此循環，求出所有S中的點的能夠到達的點集。如果所有的點集都等於S表明強連通圖。
方案2：可以優化1