图的邻接表表示及其遍历

图的邻接表表示及其遍历

1.图的结构定义

#define MAXVEX 100
#define true 1
typedef char VertexType;		//定义图节点值得类型，可随意更换
typedef int EdgeType;			
typedef struct EdgeNode  		//定义边表节点
{
	int adjvex;              	//存储顶点下标
 	EdgeType weight;            //权重值
	struct EdgeNode* next;      //边指针
}EdgeNode;
typedef struct VertexNode	/*顶点表节点*/
{
	VertexType data;
	EdgeNode* firstedge;
}VertexNode,AdjList[MAXVEX];
typedef struct
{
	AdjList adjList;
	int numVertexes,numEdges;
}GraphAdjList;

2.图的建立

void CreatGraph(GraphAdjList *g)
{
	int i,j,k;
	EdgeNode *e;
	scanf("%d%d",&g->numVertexes,&g->numEdges);//获取顶点数和边数
	char c;
	//gettchar();
	for(i=0;i<g->numVertexes;i++)
	{
		while((c=getchar())=='
'||c==' ');//排除空格和换行符
		g->adjList[i].data = c;            //获取顶点值，
		g->adjList[i].firstedge = NULL;    //将边表置为空
	}
	for(k=0;k<g->numEdges;k++)
	{
		scanf("%d%d",&i,&j);               //输入i,j 在图中有i-->j
		e=(EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = j;
		e->next = g->adjList[i].firstedge;   //头插法建立边表
		g->adjList[i].firstedge= e;
		/*如果为无向图，则加入以下代码
                e=(EdgeNode*)malloc(sizeof(EdgeNode));
                e->adjvex = i;
                e->next = g->adjList[j].firstedge;
                g->adjList[j].firstedge= e;*/
   	}
}

3.图的DFS遍历

void DFS(GraphAdjList *g,int i)
{
        EdgeNode *p;
        visited[i]=true;
        printf("%c ",g->adjList[i].data);
        p = g->adjList[i].firstedge;
        while(p)
        {
                if(visited[p->adjvex]==0)
                        DFS(g,p->adjvex);
                p=p->next;
        }
}

假设有下面这张图，这个图包含两个连通图。

输入如下：

7 6           		 <==输入顶点数和边数
a b c d e f g        <==输入顶点值
0 2 0 3 0 1 4 5 1 6 1 2        <==依次输入边
 

根据输入，可以得到邻接表如下：

根据邻接表可知，该图的深度优先遍历如下:

a->b->c->g->d->e->f

程序运行结果：

证明程序是正确的。
完整程序代码参见：
https://github.com/zkangHUST/DataStructure