学步园

图的模型

示例代码

#include <iostream>
using namespace std;

const int topnode = 10;
struct arcnode
{
	int value;
	arcnode* next;
};

struct node
{
	int degree;
	arcnode* first;
};

node  list[topnode+1];
static int nodeNum = 0;
static int graphType;

void setgrapth()
{	
	cout << "please input node number: ";
	cin >> nodeNum;
	for(int  i = 1; i <= nodeNum; i++)
	{
		list[i].degree = 0;
		list[i].first = NULL;
	}	
	
	cout << "please input the graph type: 1 direct grapth 2 no direct grapth \n";
	cin >> graphType;
 
    int begin = 0;
	int end = 0;
	cout << "please input the side: format like these \"beginNum endNum \"\n";	

	while(cin >> begin >> end)
	{
		arcnode* tmp = list[begin].first;
		
		while( tmp != NULL && tmp->value != end )
	    {
		    tmp = tmp->next;
	    }	
		
		if(tmp == NULL)
		{
			tmp = new arcnode;
			tmp->value = end;
			if( NULL == list[begin].first)
			{
				list[begin].first = new arcnode;
				list[begin].first->value = begin;
				list[begin].first->next = tmp;
				tmp->next = NULL;
			}
			else
			{
				tmp->next = list[begin].first->next;
				list[begin].first->next = tmp;
			}
			list[begin].degree++;	

			if(graphType == 2)
			{
				arcnode* tmp2  = new arcnode;
				tmp2->value = begin;
				if( NULL == list[end].first )
				{
					list[end].first = new arcnode;
					list[end].first->value = end;
					list[end].first->next = tmp2;
					tmp2->next = NULL;
				}
				else
				{
					tmp2->next = list[end].first->next;
					list[end].first->next = tmp2;
				}
				list[end].degree++;	
			}
		}

	}

}

void printGraph()
{
	for(int i=1; i <= nodeNum; i++)
	{
		arcnode* printNode = list[i].first;
		while(printNode != NULL)
		{
			cout << printNode->value << "  -> ";
			printNode = printNode->next;
		}
		cout << "NULL" << endl;
	}
}


int main()
{
	setgrapth();
	printGraph();
	cout << "hello world" << endl;
	return 0;
}

代码所做功能

1、构建邻接表

2、打印邻接表

操作示例图：