图C实现 - 深度优先搜索 [英] Graph C implementation - Depth first search

问题描述

我试图用图的邻接表重新presentation实现深度优先搜索算法。这里是我的code：

I am trying to implement depth first search algorithm using adjacency list representation of graphs. Here is my code:

#include<stdio.h>
#include<stdlib.h>
struct edge
{
int vertexIndex;
struct edge *edgePtr;
}edge;

struct vertex
{
int vertexKey;
int visited;
struct edge *edgePtr;
}vertex;


void insertVertex(struct vertex *g, int vertexKey, int *vertexCount)
{
g[*vertexCount].vertexKey=vertexKey;
g[*vertexCount].edgePtr=NULL;
g[*vertexCount].visited=0;
(*vertexCount)++;
}

void insertEdge(struct vertex *g,int vertex1, int vertex2)
{
struct edge *e,*e1,*e2;
e=g[vertex1].edgePtr;
while(e&& e->edgePtr)
{
    e=e->edgePtr;
}
e1=(struct edge *)malloc(sizeof(*e1));
e1->vertexIndex=vertex2;
e1->edgePtr=NULL;
if(e)
e->edgePtr=e1;
else
g[vertex1].edgePtr=e1;

e=g[vertex2].edgePtr;
while(e&& e->edgePtr)
{
    e=e->edgePtr;
}
e2=(struct edge *)malloc(sizeof(*e2));
e2->vertexIndex=vertex1;
e2->edgePtr=NULL;
if(e)
e->edgePtr=e2;
else
g[vertex2].edgePtr=e2;
}

void printGraph(struct vertex *g, int *vertexCount)
{
int i;
struct edge *e;
for(i=0;i<*vertexCount;i++)
{
    printf("%d(%d)",i,g[i].vertexKey);
    e=g[i].edgePtr;
    while(e)
    {
        printf("->%d",e->vertexIndex);
        e=e->edgePtr;
    }
    printf("\n");
}
}

void dfs(struct vertex *g,int vertex1)
{
g[vertex1].visited=1;
printf("%d ",vertex1);
struct edge *e;
e=g[vertex1].edgePtr;

while(e)
{
    if(!(g[e->vertexIndex].visited))
    dfs(g,e->vertexIndex);

    e=e->edgePtr;
}
}
main()
{
struct vertex *g1[10];
int vc1=0;
insertVertex(g1,5,&vc1);
insertVertex(g1,3,&vc1);
insertVertex(g1,4,&vc1);
insertVertex(g1,2,&vc1);
insertVertex(g1,9,&vc1);
insertEdge(g1,0,1);
insertEdge(g1,0,2);
insertEdge(g1,1,3);
insertEdge(g1,1,4);
dfs(g1, 0);
return 0;
}

的事情是，当我运行这个code，在打印DFS输出结束时，程序意外停止，我不明白为什么。你能不能帮我这个好吗？

The thing is that when I run this code, at the end of printing 'dfs' output, the program stops unexpectedly, I don't understand why. Can you help me with this please?

推荐答案

我知道了！
有一个小错误。

I got it! There is a small mistake..

在主函数中，G1的声明应

In the main function, the declaration of g1 should be

struct vertex g1[10];

而不是

struct vertex *g1[10];

这里

更多的解释：HTTP：// iamsoftwareengineer。 blogspot.ie/2012/06/c-graph-implementation-with-adjacency.html

：）

这篇关于图C实现 - 深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！