圖論演算法c

㈠ 求圖論的生成子圖演算法，要求生成盡可能多的子圖

在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。20世紀80-90年代曾邦哲的綜合系統論（結構論）觀將「四色猜想」命題轉換等價為「互鄰面最大的多面體是四面體」。四色猜想有一段有趣的歷史。每個地圖可以導出一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連接。所以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數拓撲圖論等分支的發展起到推動作用。 （下圖是在上下對折再左右對折以後形成一個輪胎形狀，有7個區域兩兩相連，就是說在一個環面上作圖，需要7種顏色，外國數學家構造林格證明：Np=[(7+√1+48p)/2]，p=1，N1=7。
圖論中最著名的四色猜想解決辦法 韓世君利用三角形性質和數學歸納法解決了四色猜想 摘要：將平面圖的不相連點使其相連（這樣增加著色難度），形成有許多三角形相連的平面圖，根據三角形的穩定性，利用數學歸納法，平面圖進行著色最多需4種顏色。 定理：在平面圖中,對不同頂點進行著色,相鄰頂點著不同顏色,不相鄰頂點著相同顏色,則最多需4種顏色。 證明：在平面圖中，不在同一直線上的三點決定一個平面，那麼三點構成的三角形是平面圖中最基本、最簡單、最穩定、密閉的圖形。 由於在對地圖著色過程中不考慮圖的具體形狀只考慮點是否相鄰，將平面圖的不相連點使其相連（這樣增加著色難度），形成有許多三角形相連的平面圖（三點以下肯定成立）。如圖1：添加輔助線（不相鄰的點使其相鄰，這樣就增加了著色的色數，有利於證明），將圖1分解為4個△ABC。 在平面圖中的無數點中，任取相鄰三點構成各點相鄰的△ABC（見圖2），則需3種顏色A B C,在平面圖中再任取一點 D 與 A B C 三點相鄰,同時D又與A B C三點相連後形成三角形。任取一點E與 A、B、C、D四色相連，E必與四色之一色相同即E點在△ABD中與C色相同、在△ACD中與B色相同、在△BCD中與A色相同、在△ABC外與D色相同，E與另外三色相連形成新的三角形。 在三角形的三點之外任取一點只有在三角形的內部和外部兩種情況且這兩種情況的點不會相鄰，該點最多與三角形的三點相連且又形成新的三角形。 繼續選取一點進行著色，該點同樣最多與三角形的三點相連且又形成新的三角形，該點至少為四色中的一色。逐點（第n點）著色至將所有點（第n+1點）著色只須A、B、C、D四色其中一色。 圖的著色方法：任意一張地圖，將孤立的點用一種顏色著色（A色），不能形成密閉圖形的相連的點用兩種顏色（A、B色）。將剩餘的點不相連的用虛線使其相連形成許多三角形，完全不相連的圖不進行相連。任取相連三點著三種顏色（A、B、C色），再取與其相連的點，如果與A、B、C三色的點都相連著D色，否則著與其不相連的其中一色，用虛線相連的點可以用同一種顏色也可以用兩種顏色，依次取與著色的點相連的點用以上方法進行著色。這樣對所有的點進行著色最多用四色（A、B、C、D色）。 圖論的廣泛應用，促進了它自身的發展。20世紀40-60年代，擬陣理論、超圖理論 、極圖理論，以及代數圖論、拓撲圖論等都有很大的發展 拓撲學在泛函分析、李群論、微分幾何、微分方程和其他許多數學分支中都有廣泛的應用。 （右圖是：下面的三叉安在上面的環面上，就是有3個洞的9個兩兩相連區域，上面的圖上下對折再左右對折就是一個輪胎形狀環面圖2）
左圖是虧格為4時10個兩兩相連區域構造，上圖上下對折，再左右對折，形成一個輪胎形狀，再把下面的四叉按照A,B,C,D編號安上，就是有4個洞的兩兩相連區域圖3（王曉明構造）。

㈡ 圖論演算法的論證

有向無迴路圖又稱為dag。對這種有向無迴路圖的拓撲排序的結果為該圖所有頂點的一個線性序列，滿足如果G包含(u,v)，則在序列中u出現在v之前（如果圖是有迴路的就不可能存在這樣的線性序列）。一個圖的拓撲排序可以看成是圖的所有頂點沿水平線排成的一個序列，使得所有的有向邊均從左指向右。因此，拓撲排序不同於通常意義上對於線性表的排序。
有向無迴路圖經常用於說明事件發生的先後次序，圖1給出一個實例說明早晨穿衣的過程。必須先穿某一衣物才能再穿其他衣物（如先穿襪子後穿鞋），也有一些衣物可以按任意次序穿戴（如襪子和短褲）。
圖中說明經拓撲排序的結點以與其完成時刻相反的順序出現。因為深度優先搜索的運行時間為θ(V+E)，每一個v中結點插入鏈表需佔用的時間為θ(1)，因此進行拓撲排序的運行時間θ(V+E)。
為了證明演算法的正確性，我們運用了下面有關有向無迴路圖的重要引理。 有向圖G無迴路當且僅當對G進行深度優先搜索沒有得到反向邊。
證明：→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。
←：假設G中包含一迴路C，我們證明對G的深度優先搜索將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。（證畢） Topological_Sort(G)演算法可產生有向無迴路圖G的拓撲排序
證明
假設對一已知有問無迴路圖G=(V,E)運行過程DFS以確定其結點的完成時刻。那麼只要證明對任一對不同結點u,v∈V，若G中存在一條從u到v的有向邊，則f[v]<F[U]即可。考慮過程DFS(G)所探尋的任何邊(U,V)，當探尋到該邊時，結點V不可能為灰色，否則V將成為U的祖先，(U,V)將是一條反向邊，和引理1矛盾。
因此，v必定是白色或黑色結點。若v是白色，它就成為u的後裔，因此f[v]<F[U]。若V是黑色，同樣F[V]<F[U]。這樣一來對於圖中任意邊(U,V)，都有F[V]<F[U]，從而定理得證。（證畢）

㈢ c語言演算法求解：對任意給定的網路（頂點數和邊數自定），設計演算法生成它的最小生成樹。

上一個圖和代碼：

圖1為要創建的圖，圖2為對應的最小生成樹

代碼為：

//圖論之最小生成樹：prim演算法實現

#include"stdio.h"

#include"malloc.h"

//聲明

voidoutput(structadjacentlisthead*alh,intmapsize);

structadjacentlistson//鄰接表項結構體

{

intsonelement;

intquanvalue;

structadjacentlistson*next;

};

structadjacentlisthead//鄰接表頭結構體

{

charflag;

intelement;

intcurqvalue;

structadjacentlisthead*previous;

structadjacentlistson*startson;

};

structadjacentlisthead*mapinitialnize(intmapsize)//初始化圖函數

{

structadjacentlisthead*alh=NULL;

structadjacentlistson*newnode=NULL;

inti,x,y,z;

alh=malloc(sizeof(structadjacentlisthead)*mapsize);

if(alh==NULL)

returnNULL;

for(i=0;i<mapsize;i++)

{

alh[i].flag=0;

alh[i].element=i+1;

alh[i].curqvalue=0;

alh[i].previous=NULL;

alh[i].startson=NULL;

}

scanf("%d%d%d",&x,&y,&z);

while(x&&y)//直到輸入的x,y中至少有一個0為止

{

newnode=malloc(sizeof(structadjacentlistson));

newnode->sonelement=y;

newnode->quanvalue=z;

newnode->next=alh[x-1].startson;

alh[x-1].startson=newnode;

scanf("%d%d%d",&x,&y,&z);

}

returnalh;

}

intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小權值對應的結點

{

inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;

for(i=0;i<mapsize;i++)

{

if(alh[i].flag==0&&alh[i].curqvalue!=0)

{

if(alh[i].curqvalue<minvalue)

{

minvalue=alh[i].curqvalue;

minplace=i+1;//

}

}

}

returnminplace;

}

voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成樹

{

structadjacentlistson*alstmp=NULL;

intcurplace=startplace;

while(curplace)

{

alstmp=alh[curplace-1].startson;

alh[curplace-1].flag=1;//正在訪問

while(alstmp)

{

if(alh[alstmp->sonelement-1].flag==0)

{

if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比較方法與有權圖有一點不同

{

alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;

alh[alstmp->sonelement-1].previous=&alh[curplace-1];

}

}

alstmp=alstmp->next;

}

curplace=findminnode(alh,mapsize);//通過函數找到最小的一個結點

}

}

voidoutput(structadjacentlisthead*alh,intmapsize)

{

inti;

for(i=0;i<mapsize;i++)

{

printf("%d點的權值為：%d ",i+1,alh[i].curqvalue);

}

printf("................................................... ");

}

intmain()

{

structadjacentlisthead*alh=NULL;

intmapsize=7,startplace=1;

alh=mapinitialnize(mapsize);

findthemintree(alh,startplace,mapsize);

output(alh,mapsize);

}

輸入數據對應第一圖：

122

134

141

212

243

2510

314

342

365

411

423

432

457

468

474

5210

547

576

635

648

671

744

756

761

000

㈣ 數據結構c語言版圖論題目

給你個模板
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int maxn=10005;
vector<int>g[maxn];
stack<int>s;
int dfs_clk,scc_cnt;
int pre[maxn],lowlink[maxn],scc[maxn];
void dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clk;
s.push(u);
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!scc[v])
{
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if(lowlink[u]==pre[u])
{
scc_cnt++;
for(;;)
{
int x=s.top();s.pop();
scc[x]=scc_cnt;
if(x==u) break;
}
}
}
void find_scc(int n)
{
dfs_clk=scc_cnt=0;
memset(scc,0,sizeof scc);
memset(pre,0,sizeof pre);
for(int i=1;i<=n;i++)
if(!pre[i]) dfs(i);
}
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
for(int i=1;i<=10000;i++)
g[i].clear();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
}
find_scc(n);
cout<<scc_cnt<<endl;
}
}

scc_cnt就是連通子圖的個數

㈤ c語言演算法

離散數學離散數學作為計算機學科的基礎是競賽中涉及最多的數學分支，重中之重又在於圖論和組合數學，尤其是圖論。圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到力不從心，也不必著急，可以慢慢積累。組合數學競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。數論以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。計算幾何計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結合，較常用到的部分包括—線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠不會成為最弱的題。線性代數對線性代數的應用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以藉助於矩陣來找到更好的演算法。 ~

㈥ 這是一個圖論的問題

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等

注意：你的指定點開始的問題，直接從把下面的東西看完後，應用（6）就可以解決，任意開始點的話，就把所有點都指定一下就行了。。。

再補充一個，這個演算法一般圖論書上都有，但是寫的非常之高深莫測，看不懂的。。。建議去看清華大學的數據結構與演算法這本書上的演算法，（藍色封皮的）

設S為最短距離已確定的頂點集（看作紅點集），V-S是最短距離尚未確定的頂點集（看作藍點集）。
①初始化
初始化時，只有源點s的最短距離是已知的(SD(s)=0)，故紅點集S={s}，藍點集為空。
②重復以下工作，按路徑長度遞增次序產生各頂點最短路徑
在當前藍點集中選擇一個最短距離最小的藍點來擴充紅點集，以保證演算法按路徑長度遞增的次序產生各頂點的最短路徑。
當藍點集中僅剩下最短距離為∞的藍點，或者所有藍點已擴充到紅點集時，s到所有頂點的最短路徑就求出來了。
注意：
①若從源點到藍點的路徑不存在，則可假設該藍點的最短路徑是一條長度為無窮大的虛擬路徑。
②從源點s到終點v的最短路徑簡稱為v的最短路徑；s到v的最短路徑長度簡稱為v的最短距離，並記為SD(v)。

（3）在藍點集中選擇一個最短距離最小的藍點k來擴充紅點集
根據按長度遞增序產生最短路徑的思想，當前最短距離最小的藍點k的最短路徑是：
源點，紅點1，紅點2，…，紅點n，藍點k
距離為：源點到紅點n最短距離+<紅點n,藍點k>邊長
為求解方便，設置一個向量D[0．．n-1]，對於每個藍點v∈ V-S，用D[v]記錄從源點s到達v且除v外中間不經過任何藍點(若有中間點，則必為紅點)的"最短"路徑長度（簡稱估計距離）。
若k是藍點集中估計距離最小的頂點，則k的估計距離就是最短距離，即若D[k]=min{D[i] i∈V-S}，則D[k]=SD(k)。
初始時，每個藍點v的D[c]值應為權w<s，v>，且從s到v的路徑上沒有中間點，因為該路徑僅含一條邊<s，v>。
注意：
在藍點集中選擇一個最短距離最小的藍點k來擴充紅點集是Dijkstra演算法的關鍵

（4）k擴充紅點集s後，藍點集估計距離的修改
將k擴充到紅點後，剩餘藍點集的估計距離可能由於增加了新紅點k而減小，此時必須調整相應藍點的估計距離。
對於任意的藍點j，若k由藍變紅後使D[j]變小，則必定是由於存在一條從s到j且包含新紅點k的更短路徑：P=<s，…，k，j>。且D[j]減小的新路徑P只可能是由於路徑<s，…，k>和邊<k，j>組成。
所以，當length(P)=D[k]+w<k，j>小於D[j]時，應該用P的長度來修改D[j]的值。

（5）Dijkstra演算法

Dijkstra(G，D，s){
//用Dijkstra演算法求有向網G的源點s到各頂點的最短路徑長度
//以下是初始化操作
S={s}；D[s]=0； //設置初始的紅點集及最短距離
for( all i∈ V-S )do //對藍點集中每個頂點i
D[i]=G[s][i]； //設置i初始的估計距離為w<s，i>
//以下是擴充紅點集
for(i=0;i<n-1;i++)do{//最多擴充n-1個藍點到紅點集
D[k]=min{D[i]：all i V-S}； //在當前藍點集中選估計距離最小的頂點k
if(D[k]等於∞)
return； //藍點集中所有藍點的估計距離均為∞時，
//表示這些頂點的最短路徑不存在。
S=S∪{k}； //將藍點k塗紅後擴充到紅點集
for( all j∈V-S )do //調整剩餘藍點的估計距離
if(D[j]>D[k]+G[k][j])
//新紅點k使原D[j]值變小時，用新路徑的長度修改D[j]，
//使j離s更近。
D[j]=D[k]+G[k][j]；
}
}

（6）保存最短路徑的Dijkstra演算法
設置記錄頂點雙親的向量P[0．．n-1]保存最短路徑：
當頂點i無雙親時，令P[i]=-1。
當演算法結束時，可從任一P[i]反復上溯至根(源點)求得頂點i的最短路徑，只不過路徑方向正好與從s到i的路徑相反。
。
Dijkstra演算法的時間復雜度為O(n2)
參考資料：http://student.zjzk.cn/course_ware/data_structure/web/tu/tu7.5.2.htm

㈦ c語言在圖論中的應用

我研究的是電力系統的網路拓撲問題，它就是基於圖論的，把電網中的連接方式映射為圖，可以採用c語言編程來實現這個演算法，，

㈧ 用圖論做一個求迷宮最短路徑的演算法

01.#include <stdio.h>
02.#define MAXN 10
03.int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
04.char name[] = {'U', 'D', 'L', 'R'};
05.int q[MAXN * MAXN]; //隊列，保存當前結點編號
06.int vis[MAXN][MAXN], nMap[MAXN][MAXN];
07.int m, n; //行、列數
08.int dir[MAXN * MAXN];
09.int fa[MAXN][MAXN], dis[MAXN][MAXN], last_dir[MAXN][MAXN];
10.void funcInit();
11.void bfs(int x, int y);
12.void funcInput();
13.void print_path(int x, int y);
14.int main()
15.{
16. funcInput();
17. funcInit();
18. bfs(0, 0);
19. print_path(m - 1, n - 1);
20. return 0;
21.}
22.void funcInit()
23.{
24. int i, j;
25. for (i = 0; i != m; ++i)
26. {
27. for (j = 0; j != n; ++j)
28. {
29. vis[i][j] = 0;
30. dis[i][j] = 0;
31. }
32. }
33.}
34.void funcInput()
35.{
36. int i, j;
37. scanf("%d %d", &m, &n);
38. for (i = 0; i != m; ++i)
39. {
40. for (j = 0; j != n; ++j)
41. {
42. scanf("%d", &nMap[i][j]);
43. }
44. }
45.}
46.void bfs(int x, int y)
47.{
48. int front = 0, rear = 0;
49. int d, u; //方向標記、結點編號
50.
51. u = x * m + y;
52. vis[x][y] = 1;
53. fa[x][y] = u;
54. q[rear++] = u; //將當前結點編好放入隊列
55.
56. while (front != rear)
57. {
58. u = q[front++];
59. x = u / m; y = u % m;
60. for (d = 0; d != 4; ++d)
61. {
62. int nx = x + dx[d], ny = y + dy[d];
63. if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && !nMap[nx][ny])
64. {
65. int v = nx * m + ny;
66. q[rear++] = v;
67. vis[nx][ny] = 1;
68. fa[nx][ny] = u;
69. dis[nx][ny] = dis[x][y] + 1; //記錄路徑長度
70. last_dir[nx][ny] = d; //記錄移動方向標記
71. }
72. }
73. }
74.}
75.void print_path(int x, int y)
76.{
77. int c = 0;
78.
79. while (1)
80. {
81. int fx = fa[x][y] / m;
82. int fy = fa[x][y] % m;
83. if (fx == x && fy == y) break;
84. dir[c++] = last_dir[x][y];
85. x = fx; y = fy;
86. }
87. while (c--)
88. {
89. putchar(name[dir[c]]);
90. putchar('/n');
91. }
92. printf("最短路徑長度為:%d/n", dis[m-1][n-1]);
93.}

㈨ 求解：圖論中常見的最短路徑演算法有幾種都是什麼

主要是有三種、、

第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、

第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、

第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、

㈩ 請C語言大神幫個忙

我們學校的競賽題是n*n的，可以參考一下
#include<stdio.h>
#include<string.h>
#define max 100
int mat[max][max],vis[max][max];
void dfs(int x,int y)
{
if(!mat[x][y] || vis[x][y]) return;
vis[x][y]=1;
dfs(x-1,y-1);
dfs(x-1,y+1);
dfs(x-1,y);
dfs(x,y-1);
dfs(x,y+1);
dfs(x+1,y-1);
dfs(x+1,y+1);
dfs(x+1,y);
}
void main()
{ int i,j,n;
char s[100];
memset(mat,0,sizeof(mat));
memset(vis,0,sizeof(vis));
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",s);
for(j=0;j<n;j++)
mat[i+1][j+1]=s[j]-'0';
}
int count=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(!vis[i][j] && mat[i][j]) {count++;dfs(i,j);}
printf("%d\n",count);
}
很久以前的