У меня есть матрица смежности орграфа. Как определить связанный или нет?   

1.обходиш граф.
2.смотриш, все ли вершины помеченны.

 Я помню был какой то способ с перемножением матриц смежности. Меня он более всего интересует 

ну тогда можно рассмотреть такую операцию:
берём вектор, в котором будем хранить, до каких вершин уже добрались
под умножением матрицы будем понимать вектор, показывающий до каких вершин можно добраться если иметь возможность делать один шаг по рёбрам (будем считать, что по главной диагонали матрицы стоят 1)
тогда получается, что каждый элемент нового вектора:
Y[n]=OR[i=1..N] ( X[i] and M[n,i] )
эта операция задаёт "умножение" матрицы на вектор - Y=M*X
большинство нужных свойств выводятся из ассоциативности, дистрибутивности и коммутативности операций or/and аналогично операциям +/*

так что берём вектор с одной 1-цей, действуем на него N раз матрицей M и проверяем в нём наличие нулей, если есть - значит, это изолированные вершины (от первой), если нет - весь граф связный

P.S.
подозреваю, можно перевести это всё просто на умножение матриц
потом посмотреть, что это просто возведение в N-ю степень
в том виде, в котором оно представлено выше - количество умножений N
но само по себе возведение в степень можно сделать за log N шагов:
(в качестве иллюстрации)

Ок!  Спасибо!    

Граждане! А вам знакомы такие алгоритмы как обход в ширину и глубину?!! Выкладываю вам текст из Окулова:

3.2.2. Поиск в ширину
Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”. 
 
    Пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа.

    Приведем процедуру реализации данного метода обхода вершин графа.
    Логика просмотра вершин.
    


А вот сам алгоритм, который определяет связан граф или нет обходом в ширину:


Это сообщение отредактировал(а) maxim1000 - 12.12.2006, 01:12

Построение ПВГ для каждой вершины?  Вроде с момощью перемножения проще 

Не проще это точно. dfs легче для понимания имхо. рекурсия в пару строчек выходит. Единственное, может умножением быстрее...

ДФС, не катит в данном случае.


Самый простой алгоритм - это случайное блуждание по графу. Но он работает хорошо только неа не направленных графах

Ну блин, для орграфов, вообще-то, существует совершенной другой алгоритм для определения компонент сильной связности. И вопрос ветки, совершенно этого не касался. Да, и в глубь, намнооого медленнее, в любом случае, надо идти в ширь!!!

Странно, а у меня в ширь сложнее получился чем в глубь 

Хех... не может быть. Если идти в глубь, то теряется много времени при возврате из рекурсии, чего собственно не наблюдается, если идти в ширину.

Ну да? В шируну тоже есть возврат из рекурсии    Но это уже оффтоп  

А можно ещё про перемножение матриц? N раз перемножить раз. А дальше что?

если не ошибаюсь, то вполне достаточно проверить, что в каком-нибудь столбце все элементы- единицы (если граф неориентированный)

И все же самый простой алг, это случайный обход