第1關:實作圖的橫向優先搜尋
//Graph
///
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Graph.h"
/
Graph* Graph_Create(int n)
{
Graph* g=(Graph*)malloc(sizeof(Graph));
g->n=n;
g->vetex=(char**)malloc(sizeof(char*)*n);
int i;
for (i=0; i<n; i++) g->vetex[i] = NULL;
g->adj=(int*)malloc(sizeof(int)*n*n);
int j;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
g->adj[i*n+j]=0;
}
}
return g;
}
void Graph_Free(Graph* g)
{
free(g->adj);
int i;
for (i=0; i<g->n; i++) free(g->vetex[i]);
free(g->vetex);
free(g);
}
int Graph_WidthFirst(Graph*g, int start, Edge* tree)
//從start号頂點出發橫向優先搜尋,(編号從0開始)
//傳回通路到的頂點數,
//tree[]輸出周遊樹
//傳回的tree[0]是(-1, start),
//真正的周遊樹儲存在tree[1..return-1], return是傳回值
//頂點的通路次序依次為tree[0].to, tree[1].to, ..., tree[return-1].to
//輸入時,tree[]的長度至少為頂點數
//傳回值是從start出發通路到的頂點數
{
const int MAX=1000;
Edge queue[MAX];
int head=0, tail=0;
#define In__(a,b) {queue[tail].from=a; queue[tail].to=b; tail=(tail+1)%MAX;}/
#define Out__(a,b) {a=queue[head].from; b=queue[head].to; head=(head+1)%MAX;}//
#define QueueNotEmpty (head!=tail?1:0)///
#define HasEdge(i,j) (g->adj[(i)*g->n+(j)]==1)
char* visited=(char*)malloc(sizeof(char)*g->n);
memset(visited, 0, sizeof(char)*g->n);
int parent=-1;
int curr=start;
In__(parent, curr);
int k=0; //已經通路的結點數
/*請在BEGIN和END之間實作你的代碼*/
/*****BEGIN*****/
while(QueueNotEmpty)//隊列不為空
{
Out__(parent,curr);//出隊
if(!visited[curr]) //現在結點未被通路
{
visited[curr]=1; //修改visit數組,curr結點現在被通路
tree[k].from=parent;
tree[k].to=curr;
k++;//已被通路結點數增加
for(int j=0;j<g->n;j++)//對未被通路的鄰接結點入隊
{
if(!visited[j]&&HasEdge(curr,j)) //未被通路且與現在的結點之間存在邊
In__(curr,j);
}
}
}
/*****END*******/
return k;
#undef In__//
#undef Out__///
#undef QueueNotEmpty
#undef HasEdge
}
第2關:實作圖的深度優先周遊
//Graph
///
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Graph.h"
Graph* Graph_Create(int n)
{
Graph* g=(Graph*)malloc(sizeof(Graph));
g->n=n;
g->vetex=(char**)malloc(sizeof(char*)*n);
int i;
for (i=0; i<n; i++) g->vetex[i] = NULL;
g->adj=(int*)malloc(sizeof(int)*n*n);
int j;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
g->adj[i*n+j]=0;
}
}
return g;
}
void Graph_Free(Graph* g)
{
free(g->adj);
int i;
for (i=0; i<g->n; i++) free(g->vetex[i]);
free(g->vetex);
free(g);
}
int Graph_DepthFirst(Graph*g, int start, Edge* tree)
//從start号頂點出發深度優先周遊,(編号從開始)
//傳回通路到的頂點數,
//tree[]輸出周遊樹
//傳回的tree[0]是(-1, start),
//真正的周遊樹儲存在tree[1..return-1], return是傳回值
//頂點的通路次序依次為tree[0].to, tree[1].to, ..., tree[return-1].to
//輸入時,tree[]的長度至少為頂點數
//傳回值是從start出發通路到的頂點數
{
/*請在BEGIN和END之間實作你的代碼*/
/*****BEGIN*****/
const int MAX=1000;
Edge stack[MAX];//邊存放在棧中
int top=-1; //棧頂标記為-1
#define Push__(a,b) {top++; stack[top].from=a; stack[top].to=b;}
#define Pop__(a,b) {a=stack[top].from; b=stack[top].to; top--;}///
#define StakNotEmpty (top>=0?1:0)
#define HasEdge(i,j) (g->adj[(i)*g->n+(j)]==1)
char* visited=(char*)malloc(sizeof(char)*g->n);//為visit數組配置設定空間
memset(visited, 0, sizeof(char)*g->n);//初始化一個visit數組
int parent=-1; //parent從棧頂開始
int curr=start;//curr從起始位置出發
Push__(parent, curr);//入棧
int k=0; //用于存儲已經被過通路的結點數
while (StakNotEmpty) {
Pop__(parent, curr); //出棧
if (!visited[curr])//現在的結點若未被通路
{
visited[curr]=1;
//tree中存放的為邊
tree[k].from=parent;
tree[k].to=curr;
k++;
}
for (int j=g->n-1; j>=0; j--)//編号大的開始入棧
{
if (HasEdge(curr,j) && !visited[j]) //已被通路且跟curr之間存在節點
Push__(curr,j);
}
}
free(visited);
return k;
#undef Push__
#undef Pop__///
#undef StakNotEmpty//
#undef HasEdge
/*****END*******/
}