連通圖演算法

① 實現圖的鄰接表表示及連通圖

v v

② 試以鄰接矩陣為存儲結構，寫出連通圖的深度優先搜索演算法。

/* MGraph.cc: 圖的鄰接矩陣存儲表示和實現 */
/* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
/* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */

#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX

#define VType char //頂點值類型
#define EType int //邊權值類型
#define MAXVNUM 50 //最大頂點個數
#define DIGRAPH 0 //有向圖(網)
#define UNDIGRAPH 1 //無向圖(網)
#define INVALID INT_MAX //無效權值(最大整數表示無窮大)
#define EMPTY -1 //"空"頂點序號

//定義鄰接矩陣表示的圖類型Graph:
typedef struct
{
VType v[MAXVNUM]; //頂點序列(頂點編號從0開始)
EType w[MAXVNUM][MAXVNUM]; //鄰接矩陣
int vn, en; //頂點數,邊數
int kind; //圖的種類：=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
}Graph;

int visited[MAXVNUM]; //訪問標志數組(=1已訪問，=0未訪問)。遍歷時用到的全局量。

/* 創建圖G
參數Vex是存放頂點序列的數組
參數VVW是整數數組，以{Vi,Vj,Wij,...,-1}的形式依次存放各邊的起止點序號(Vi,Vj)和權(Wij)，-1是數據結束標志
參數kind=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //頂點數
G.kind = kind; //圖的種類
//置頂點序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化鄰接矩陣:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//構造鄰接矩陣:
p = 0; //VVW數組元素「指針」
n = 0; //邊計數器
while (VVW[p] != -1)
{//只要p未到結束位置便繼續:
i = VVW[p]; //邊的起點序號
j = VVW[p + 1]; //邊的終點序號
w = VVW[p + 2]; //邊的權
G.w[i][j] = w; //置鄰接矩陣的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是無向圖(網),
G.w[j][i] = G.w[i][j]; //則置(i,j)的對稱位置(j,i)
n++; //邊計數器加1
p += 3; //p指向下一組(Vi,Vj,Wij)
}//end while
G.en = n; //邊數
}//CreateGraph

/* 返回G中頂點i的一個未曾訪問過的鄰接點(序號) */
int NextAdjVex(Graph &G, int i)
{
int j, a;

a = EMPTY; //鄰接點序號初始為"空"
//在鄰接矩陣的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若當前元素是無效元素,
continue; //則繼續找。
if (!visited[j])
{//若當前有效元素未曾訪問過,則作為鄰接點a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex

/* 訪問頂點i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit

/* 從第i個頂點出發深度優先遍歷連通圖G */
/* 調用DFS前可能需初始化數組visited[] */
void DFS(Graph &G, int i)
{int a;

visit(G, i); //訪問i頂點
visited[i] = 1; //標注i頂點已訪問
a = NextAdjVex(G, i); //找出一個i的鄰接點a
while (a != EMPTY)
{//只要a存在便繼續:
if (visited[a] == 0) //若a未曾訪問,
DFS(G, a); //則從a出發繼續進行深度優先遍歷。
a = NextAdjVex(G, i); //找出i的下一個鄰接點a
}//end while
}//DFS

/* 從第i個頂點出發深度優先遍歷圖G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各頂點的訪問標志為0(未曾訪問):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //從i出發遍歷
//若G非連通圖，執行一次DFS無法遍歷所有頂點，還需用如下for對尚未訪問的頂點DFS。
//若G是連通圖，執行一次DFS就已遍歷所有頂點，此時如下for什麼也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //對尚未訪問的頂點DFS
}//DFSTrav

//顯示圖的鄰接矩陣
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //頂點數
//以表格形式輸出數組：
//輸出表頭：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//輸出表體(矩陣元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM

③ 概要描述一個演算法，判斷一個用鄰接矩陣表示的連通圖是否具有歐拉迴路。該演算法效率類型如何

演算法如下：
設鄰接矩陣維度為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)的吧

④ 求無向連通圖中兩點最遠距離演算法，和Dijkstra相反，有想法就行，有代碼更好

如果是無環圖的話，把所有邊取相反數，就變成了求最短路，可以使用floyd

⑤ 連通圖的深度優先遍歷演算法

這個第一個點是隨機的。只是看你怎麼儲存的。如果你把v的鄰接頂點用數組保存，那麼它在數組的最前邊。用指針的話，就指向下一個緊接的位置。

⑥ 一個連通圖的計算

5，最少是n-1，最多是n(n-1)/2。

⑦ 用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;
}

⑧ 連通圖用深度優先和廣度優先演算法所得的生成樹是否唯一

理論上遍歷所得的生成樹或序列是不唯一的，演算法本身並沒有對同等條件下哪個點優先訪問做要求。但實際寫代碼的時候肯定要按某種順序遍歷，通常是從小到大，這時首個訪問的點肯定是第一個點，當前點與多個未訪問點相連時也是優先訪問編號小的點，這樣所得的結果就是唯一的了。

⑨ 什麼叫做連通圖

連通圖：是指在圖論中，連通圖基於連通的概念。

在一個無向圖G中，若從頂點到頂點有路徑相連（當然從到也一定有路徑），則稱和是連通的。如果G是有向圖，那麼連接和的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那麼圖被稱作連通圖。圖的連通性是圖的基本性質。

⑩ 怎麼用c語言和數據結構來編寫一個判斷有向圖是否為強連通圖的演算法

強連通圖表明任意兩點之間可以互相到達。
方案1：判斷結點A可以到達的點的方法如下：
首先SA = {A}；
while 1
取SA中任意沒有被去過的點x，根據以x為起點的有向線段，判斷x可以直接到達的點，然後這些點加入SA；
如此循環，直到SA中的點的個數沒有變化了
end
這樣得到的集合SA是所有A可以到達的點的一個集合。
判斷SA 是否等於S，若不等於S，表明不是強連通。

如此循環，求出所有S中的點的能夠到達的點集。如果所有的點集都等於S表明強連通圖。

方案2：可以優化1