深度优先搜索
#include <stdio.h>
#include <stdlib.h>
#define N 30
typedef struct node
{
int vno;
struct node *next;
}edgeNode;
typedef edgeNode* Graph[N];
int Create_list(Graph g)
{
int vn,en,k,i,j;
edgeNode *p;
printf("输入顶点数:\n");
scanf("%d",&vn);
printf("输入边数:\n");
scanf("%d",&en);
for(k=0;k<vn;k++)
g[k]=NULL;
for(k=0;k<en;k++)
{
printf("输入边:");
scanf("%d%d",&i,&j);
p=(edgeNode*)malloc(sizeof(edgeNode));
p->vno=j;
p->next=g[i];
g[i]=p;
p=(edgeNode*)malloc(sizeof(edgeNode));
p->vno=i;
p->next=g[j];
g[j]=p;
}
return vn;
}
int visited[N];
void dfs(Graph g,int i)
{
edgeNode *t;
printf("%4d",i);
visited[i]=1;
t=g[i];
while(t!=NULL)
{
if(visited[t->vno]==0)
dfs(g,t->vno);
t=t->next;
}
}
void main()
{
Graph g;
Create_list(g);
dfs(g,0);
}
人家的程序，实现无向图的深度优先搜索，但我看不明白：p->next=g[i];
g[i]=p;
这两句是什么意思？还有它的输入是怎样的，为什么我输入老是O，郁闷死了，都怪水平太低了，见笑了
问题点数：0、回复次数：4Top
1 楼ptxyzgb（小三）回复于 2005-06-04 01:20:36 得分 0
p->next=g[i];
g[i]=p;
这两个语句的目的是为建立图的邻接链表。
输出都是0肯定是你在输入图的顶点不是从0开始。你把顶头从0开始试一下
Top
2 楼nasi00（莫傲·逍遥）回复于 2005-06-04 02:34:08 得分 0
其实用邻接矩阵存的深度优先是很简单的
void dfs(int v)
{
visit[v]=1;
for(int i=0;i<vn;i++)
if(g[v][i] && !visit[i]) {
dfs(i);
}
}
这样就可以dfs一个图了，比如dfs(0)，就是从v0开始dfs整个图
如果该图是不连通的，还可以通过
void solve()
{
int c=0,i;
for(i=0;i<vn;i++)
if(!visit[i]) { dfs(i); c++; }
}
这样算完，c就是连通子集的个数了
其中vn为节点数，g[][]为邻接矩阵，visit[]为标记是否访问过
其实dfs,bfs都是最基础的东东了Top
3 楼WoodJohn（天在下雨,云在哭泣）回复于 2005-06-04 08:38:14 得分 0
这种建立邻接矩阵的方式很巧妙，算是温习了一下^_^。有几个地方你要注意哦：
1.在scanf后加上assert(i<vn&&j<vn)，要不会出现非法访问内存错误
2.visited的元素虽然自动初始化为0，但还是手动初始化为好
3.忘了free?Top
4 楼WoodJohn（天在下雨,云在哭泣）回复于 2005-06-04 09:20:51 得分 0
错了，是邻接链表，不是矩阵
每找到一个邻接的节点，把它加到链表的最前面Top
