圖

（圖論術語）

鎖定

圖G是指一個三元組(V,E,I)，其中V稱為頂集，E稱為邊集，E與V不相交；I稱為關聯函數，I將E中的每一個元素映射到

。如果e被映射到(u,v)，那麼稱邊e連接頂點u,v，而u,v則稱作e的端點，u,v此時關於e相鄰。同時，若兩條邊i,j有一個公共頂點u，則稱i,j關於u相鄰。

#define MAX_NUM 10
struct
{
	int adjvex;
	float lowcist;
}closedge[MAX_NUM];

{初始化closedge數組的內容；
選擇某個頂點k作為生成樹的
根結點，並將它加入到U集合中；
重複下列操作n-1次：
l選擇一條滿足條件的邊；
l輸出這條邊的兩個端點；
l修改V-U集合中的頂點信息，即與U集合中構成最小
權值的邊。
}

void Mini_SpanTree(GraphG,intk,intn)
{//G是網的鄰接矩陣，k是生成樹根結點的序號，n是網的頂點數目
for(j=0;j<n;j++)
if(j!=k)closedge[j]={k,G[k][j]};
closedge[k].lowcost=0;
for(i=1;i<n;i++)
{
k=minmun(closedge);

printf(k,closedge[k].adjvex);
closedge[k].lowcost=0;//將頂點加入U集合中
for(j=0;j<n;j++)
if(closedge&&G[k][j]<closedge[j].lowcost)
closedge[j]={k,G[k][j]};
}
}

#define MAX_VERTEX_NUM 20
typedef struct graph{
Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
}Graph;

#define MAX_VERTEX_NUM 30//最大頂點個數
typedef struct EdgeLinklist{//邊結點
int adjvex;
struct EdgeLinklist*next;
}EdgeLinklist;
typedef struct VexLinklist{//頂點結點
Elemtype elem;
EdgeLinklist* firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];

void Create_adj(AdjListad j,int n){
for(i=0;i<n;i++){//初始化頂點數組

scanf(&adj.elem);
adj.firstedge=NULL;
}
scanf(&i,&j);//輸入弧

while(i){
s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//創建新的弧結點
s->adgvex=j-1;
s->next=adj[i-1].firstedge;//將新的弧結點插入到相應的位置
adj[i-1].firstegde=s;

scanf(&i,&j);//輸入下一條弧
}
}

void Create_adj(AdjListadj,intn){
for(i=0;i<n;i++){//初始化鄰接表
scanf(&adj.elem);
adj.firstedge=NULL;
}
scanf(&i,&j);//輸入邊

while(i){
s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));
s1->adgvex=j-1;
s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));
s2->adgvex=i-1;
s1->next=adj[i-1].firstedge;
adj[i-1].firstegde=s1;
s2->next=adj[j-1].firstedge;
adj[j-1].firstegde=s2;

scanf(&i,&j);
}
}

int visited[0..n - 1] = { 0,0,...0 };
void DFSTraverse(AdjListadj)
{
	for (v = 0; v < n; v++)if (!visited[v])DFS(adj, v);
}

Boolean visited[MAX_VERTEX_NUM];//訪問標誌數組
Status(*VisitFunc)(intv);//VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse(Graph G, Status(*Visit)(intv)) {
	VisitFunc = Visit;
	for (v = 0; v < G.vexnum; ++v)
		visited[v] = FALSE;//訪問標誌數組初始化
	for (v = 0; v < G.vexnum; ++v)
		if (!visited[v])
			DFS(G, v);//對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v) {//從第v個頂點出發
	遞歸地
		深度優先遍歷圖G
		visited[v] = TRUE; VisitFunc(v);//訪問第v個頂點
	for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空(0)，//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
		//若w是v的最後一個
		鄰接點，則返回空(0)。
		if (!visited[w])
			DFS(G, w);//對v的尚未訪問的鄰接頂點w調用DFS
}

Boolean visited[MAX_VERTEX_NUM];//訪問標誌數組
Status(*VisitFunc)(intv);//VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse(Graph G, Status(*Visit)(intv)) {
	VisitFunc = Visit;
	for (v = 0; v < G.vexnum, ++v)
		visited[v] = FALSE;
	initQueue(Q);//置空輔助隊列Q
	for (v = 0; v < G.vexnum; ++v)
		if (!visited[v]) {
			visited[v] = TRUE; VisitFunc(v);
			EnQueue(Q, v);//v入隊列
			while (!QueueEmpty(Q)) {
				DeQueue(Q, u);//隊頭元素出隊並置為u
				for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
					if (!Visited[w]) {//w為u的尚未訪問的鄰接頂點
						Visited[w] = TRUE; VisitFunc(w);
						EnQueue(Q, w);
					}
			}
		}
}

#define MAX_VERTEX_NUM 30//最大頂點個數
typedef struct EdgeLinklist{//邊結點
int adjvex;
struct EdgeLinklist*next;
}EdgeLinklist;
typedef struct VexLinklist{//頂點結點
Elemtype elem;
int indegree;//記錄頂點的入度
EdgeLinklist* firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];

Status TopologicalSort(AdjListadj)
{
	InitStack(s);
	for (i = 0; i < MAX_VERTEX_NUM - 1; i++)
		if (adj.indegree == 0)Push(s, i);

	while (!StackEmpty(s)) {
		Pop(s, i);
		printf(i);
		for (p = adj.firstedge; p; p = p->next) {
			adj.indegree -= 1;
			if (adj.indegree == 0)Push(s, i);
		}

Boolean visited[MAX_VERTEX_NUM];//訪問標誌數組
Status(*VisitFunc)(intv);//VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse(Graph G,Status(*Visit)(intv)){
VisitFunc=Visit;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE;//訪問標誌數組初始化
for(v=0;v<G.vexnum;++v)
if(!visited[v])
DFS(G,v);//對尚未訪問的頂點調用DFS
}
void DFS(Graph G,int v){//從第v個頂點出發
遞歸地
深度優先遍歷圖G
visited[v]=TRUE;VisitFunc(v);//訪問第v個頂點
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空(0)，//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個
鄰接點，則返回空(0)。
if(!visited[w])
DFS(G,w);//對v的尚未訪問的鄰接頂點w調用DFS
}

Boolean visited[MAX_VERTEX_NUM];//訪問標誌數組
Status(*VisitFunc)(intv);//VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse(Graph G,Status(*Visit)(intv)){
VisitFunc=Visit;
for(v=0;v<G.vexnum,++v)
visited[v]=FALSE;
initQueue(Q);//置空輔助隊列Q
for(v=0;v<G.vexnum;++v)
if(!visited[v]){
visited[v]=TRUE;VisitFunc(v);
EnQueue(Q,v);//v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q,u);//隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!Visited[w]){//w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE;VisitFunc(w);
EnQueue(Q,w);
}
}
}
}

參考資料

• 1.    Graph Theory 4th Electronic Edition 2010, Reinhard Diestel, p.2（英語）  ．Flooved[引用日期2014-02-13]