天才 發問時間: 電腦與網際網路程式設計 · 1 0 年前

c語言圖形問題

最近在做研究 需要寫一個程式 題目就是要亂數產生100個點 用陣列儲存 並要判斷圖形是否連通(連通的意思是所有點都走過一遍,例如 BFS DFS) 最後列印出連通的所有點 能否用c語言寫出來 希望有人能幫幫忙 一起討論一下 謝謝...........

能否請盡快幫忙 星期四要交差 謝謝.........

已更新項目:

亂數產生100個點 要先去判斷兩點距離是不是小於等於20 表示兩點有邊連結 然後再去判斷此圖形是否有連通(利用BFS DFS)

最後把連通的所有點列出來 請好心人士幫幫 謝謝。。。

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 個已更新項目:

妳能否寄個信給我 我同學有寫出一個程式 它適用C++寫 意思就上程式寫ㄉ那樣 很難用簡短話說的清楚 只是要改成C來寫 他最後沒顯示連通的所有點 能否請把程式寫好 貼上來 希望妳的達匯回是最佳解答 感謝妳的幫忙 謝謝.........

程式太多 貼不上去.......... 我的信箱:s823226@yahoo.com.tw

5 個已更新項目:

我就是看不懂C++的語法 所以才上來請教 我是想請你幫我看看那程式 順便照他程式所表達意思 幫我改成C語言 因為我只熟C 但是又不是很深入 所以才請妳幫忙 拜託妳幫幫忙 謝謝................

可以把妳的程式改成跟他同樣意思 順便註解 讓我看的比較清楚

希望你好心幫幫忙 感激不盡 謝謝.............

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 年前

    到下面的網址看看吧

    ▶▶http://qoozoo09260.pixnet.net/blog

還有問題?馬上發問,尋求解答。