# c語言圖形問題

2 個已更新項目:

void dfs(int v)

{

int i;

visit[v]=1;

for(i=0;i

3 個已更新項目:

void dfs(int v)

{

int i;

visit[v]=1;

for(i=0;i

4 個已更新項目:

5 個已更新項目:

### 2 個解答

• Inunu
Lv 5
1 0 年前
最佳解答

亂數做 100 vertices, 50 edges, 用 DFS 尋找. 起始點也用亂數決定.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct {

int a;

int b;

} Edge;

int IsConnected(Edge *e, int e_len, int a, int b)

{

while(e_len > 0)

{

if(((e->a == a) && (e->b == b)) ||

((e->a == b) && (e->b == a)))

return 1;

e_len--;

e++;

}

return 0;

}

void main()

{

char *vertices;

int *queue;

int queue_count;

Edge *edges;

int edge_count;

int i, n;

n = 100; // 100 vertices

vertices = (char *)malloc(n);

memset(vertices, 0, n);

queue = (int *)malloc(sizeof(int) * n);

queue_count = 0;

edges = (Edge *)malloc(sizeof(Edge) * n);

edge_count = n / 2;

srand(time(0));

// Choose n random edges

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

{

edges[i].a = (int)(100.0 * (rand() / (RAND_MAX + 1.0)));

edges[i].b = (int)(100.0 * (rand() / (RAND_MAX + 1.0)));

if(edges[i].a == edges[i].b)

i--;

}

// Print all edges

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

printf("%d: (%d, %d)\t", i+1, edges[i].a, edges[i].b);

printf("\n");

// Start from a random vertex

queue[0] = (int)(100.0 * (rand() / (RAND_MAX + 1.0)));

queue_count++;

// mark as part of sub-graph

vertices[queue[0]] = 1;

// DFS search

while(queue_count > 0)

{

int idx = queue[--queue_count];

printf("Node %d\n", idx);

// Check for new vertex to add

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

{

if((vertices[i] == 0) &&

(IsConnected(edges, edge_count, idx, i) ==

1))

{

// mark as part of sub-graph

vertices[i] = 1;

queue[queue_count++] = i;

}

}

}

// Print all vertices in the sub-graph

printf("Subgraph = { ");

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

{

if(vertices[i] != 0)

printf("%d ", i);

}

printf("}\n");

}

2007-11-20 18:23:23 補充：

那就更簡單了.

基本上換湯不換藥:

Vertex 增加 X Y 座標資料.

IsConnect() 的判斷簡化成直接計算距離.

Edge 不用另外記錄, 整個移除.

main() 套入以上變動, 初始改為亂數決定 n 個點的座標位置.

http://www.zycomtech.com/km/subgraph2.c

到目前為止你題目定義也還不夠清楚. 像是 x,y 的範圍我也是用假設的 (MAX_X 和 MAX_Y). 事實上你根本沒交待, 我連是不是用 x,y 這種平面座標去判斷都還不知道, 所以用最廣義的 Edge(a,b) 判斷 a 與 b 是否 "相連".

2007-11-21 07:13:45 補充：

既然有你同學給你的 C++ 和這裡的 C 版本, 等於是一開始就有了答案但不知道怎麼去用. 你比較需要的是找一個同學或助教花時間去研究研究.

就算透過 email 也不及直接找個人面對面教你來得有效率.

• 匿名使用者
6 年前

到下面的網址看看吧